A New Compacting Non-Contiguous Processor Allocation Algorithm for 2D Mesh Multicomputers

A New Compacting Non-Contiguous Processor Allocation Algorithm for 2D Mesh Multicomputers

Saad Bani-Mohammad (Department of Computer Science, Al al-Bayt University, Mafraq, Jordan), Ismail M. Ababneh (Department of Computer Science, Al al-Bayt University, Mafraq, Jordan) and Mohammad Yassen (Department of Computer Science, Al al-Bayt University, Mafraq, Jordan)
Copyright: © 2015 |Pages: 19
DOI: 10.4018/JITR.2015100104
OnDemand PDF Download:
List Price: $37.50


In non-contiguous allocation, a job request can be split into smaller parts that are allocated possibly non-adjacent free sub-meshes rather than always waiting until a single sub-mesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is likely to increase. The extra communication overhead depends on how the allocation request is partitioned and assigned to free sub-meshes. In this paper, a new non-contiguous processor allocation strategy, referred to as Compacting Non-Contiguous Processor Allocation Strategy (CNCPA), is suggested for the 2D mesh multicomputers. In the proposed strategy, a job is compacted into free locations. The selection of the free locations has for goal leaving large free sub-meshes in the system. To evaluate the performance improvement achieved by the proposed strategy and compare it against well-known existing non-contiguous allocation strategies, the authors conducted extensive simulation experiments. The results show that the proposed strategy can improve performance in terms of job turnaround times and system utilization.
Article Preview

1. 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

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing