Article Preview
Top1. Introduction
In parallel computers, interconnection network is used to transfer data between nodes (processors). Interconnection networks can be separated into two types: static and dynamic. In dynamic networks, also called indirect networks, communication links are configured dynamically by switches to form paths between nodes (Grama et al., 2003). In static networks, also called direct networks, there is a direct communication link between nodes. Direct networks have been used in many parallel computers. This is due to their scalability by adding new nodes and channels. Direct networks can also exploit communication locality feature, represented, in this paper, by near neighbor communication, which is exhibited by many real-world applications (Grama et al., 2003). The mesh network is one of the direct networks and it is the most popular network used in multicomputer systems. This is because of many features that mesh network has, such as simplicity, ease of implementation, regularity, and high scalability (Bani-Mohammad, 2008; Reza & Rafie, 2020). Figure 1 shows an example of a 4×3 2D mesh, in which the allocated processors are indicated by black squares and free processors are indicated by white squares.
Figure 1. An example of a 4x3 2D mesh interconnection network
Processor allocation algorithms are responsible for finding sub-meshes for incoming job requests. They are divided into two types, contiguous and noncontiguous. In contiguous allocation, parallel jobs are allocated to distinct contiguous sub-meshes of physically adjacent processors and sub-meshes have the same topology as the underlying interconnection network. These algorithms aim to eliminate contention caused by messages of various jobs in the system and thus reduce inter-processor communication delay (Ababneh et al., 2010; Li, 2019; Zhu, 1992). Contiguous allocation algorithms can lead to high processor fragmentation because of the contiguity condition (Ababneh et al., 2010; Li, 2019; Lo et al., 1997). This fragmentation degrades the system performance in terms of job response time and mean system utilization (ProcSimity V4.3 User’s Manual, 1997).
There are two types of processor fragmentation, internal and external. Internal fragmentation happens when more processors are allocated to a job than it needs. External fragmentation happens when there are available processors to the job request, but they cannot be allocated because they are not contiguous (Chang & Mohapatra, 1998; Lo et al., 1997; Zhu, 1992). Figure 2 shows an example of external and internal fragmentations that results from contiguous allocation. Figure 2 (a) shows an incoming job that requests 3×2 sub-mesh of processors, assuming that the allocation strategy is two dimensional buddy (Li & Cheng, 1991), then 16 processors are allocated to this job resulting in 0.625 (10/16) internal fragmentation. Figure 2 (b) shows an incoming job that requests 2×2 sub-mesh of processors, and the algorithm fails to allocate the requested sub-mesh because the available processors are not contiguous, and this results in an external fragmentation.
Figure 2. An example of external and internal fragmentations