Article Preview
Top1. Introduction
Highly parallel computers are very popular for many applications nowadays. They reduce cost by using multiple cheap computing resources instead of building large expensive supercomputers (Foster, 1995).
Highly parallel computers typically have distributed memory and processors communicate with each other using an interconnection network. Commonly used interconnection networks nowadays are the 3D meshes and tori. Moreover, multi-core processors use different classes of interconnection networks, including the 2D mesh. Examples of multi-core systems that use the 2D mesh are the Heracle (Kinsy et al., 2011), and the tile processor (Wentzlaff et al., 2007).
A mesh interconnection network is a direct interconnection network, with the processors arranged as the nodes of a grid, and point-to-point links that connect each node to its neighbors. Mesh multicomputers are suitable for different applications such as matrix computations, image processing and problems having task graphs that can be embedded naturally into the mesh. Examples of mesh multicomputers are the Tera Computer, Cray T3D, MIT J-Machine and the IBM BlueGene/L (Bani-Mohammad, 2008).
The performance of a multicomputer depends on how processors are allocated to parallel jobs. Processor allocation strategies are divided into two categories: contiguous and non-contiguous. In contiguous allocation, jobs are allocated distinct contiguous processor sub-meshes for the duration of their execution. Contiguous allocation suffers from processor fragmentation (Bani-Mohammad, 2008; Bani-Mohammad et al., 2007a; Bani-Mohammad et al., 2009; ProcSimity, 1997; Windisch et al., 1995).
Processor fragmentation can be classified into internal and external fragmentation. Internal fragmentation occurs when more processors are allocated to a job than it requires (Bani-Mohammad et al., 2009; Bani-Mohammad et al., 2006; Chang & Mohaptra, 1998; Lo et al., 1997; Windisch et al., 1995). External fragmentation occurs when a sufficient number of processors are available to satisfy a request, but they cannot be allocated because they are not contiguous or they do not have a suitable shape (Lo et al., 1997). For example, Figure 1 shows an internal fragmentation of 2 processors, and Figure 2 shows an external fragmentation of 4 processors, assuming that contiguous allocation is applied.
Figure 1. An internal fragmentation of 2 processors
Figure 2. An external fragmentation of 4 processors assuming that the contiguous allocation algorithm is applied