Article Preview
TopIntroduction
Multicomputers, comprising of many processing elements that are associated through an interconnection network. Among the different multicomputer designs, those based on the mesh network have gotten much consideration because of its simplicity, scalability, structural regularity, partition-ability, and ease of implementation of this network (Yoo & Das, 2002; Chang & Mohapatra, 1998; Sharma & Pradhan, 1996; Kim & Yoon, 1998; Chiu & Chen, 1999; Ababneh & Bani-Mohammad, 2011; Ababneh, 2006; Ababneh, 2008; Ababneh, 2001; Ababneh, 2009; Ababneh et al., 2015; Ababneh et al., 2010; Bani-Mohammad & Ababneh, 2013; Bani-Mohammad et al., 2010; Bani-Mohammad et al., 2011; Bani-Mohammad et al., 2015; Bani-Mohammad et al., 2007a; Bani-Mohammad et al., 2008; Bani-Mohammad et al., 2006; Bani-Mohammad et al., 2007b; Bani-Mohammad et al., 2009). Meshes are reasonable to a variety of applications, including matrix computations, image processing and problems with task graphs that can be embedded naturally into the mesh.
Efficient processor allocation and job scheduling are critical to accomplish and harness the full computational power of vast scale multicomputers (Yoo & Das, 2002; Chiu & Chen, 1999; Ababneh, 2006; Bani-Mohammad et al., 2007a; Bani-Mohammad et al., 2006; Yoo et al., 1997). The aim of processor allocation is to choose the arrangement of processors on which parallel jobs are executed, while the aim of job scheduling is to choose the following job to be executed (Yoo & Das, 2002).
In distributed memory multicomputers, separate contiguous processor sub-meshes are assigned to jobs for the duration of their execution (Yoo & Das, 2002; Ababneh, 2006; Ababneh, 2001; Ababneh, 2009; Ababneh et al., 2015; Ababneh et al., 2010; Bani-Mohammad et al., 2006; Bani-Mohammad et al., 2007b; Bani-Mohammad et al., 2009; Zhu, 1992). Both two-dimensional (2D) and three-dimensional (3D) meshes and tori have been utilized in recent experimental and commercial multicomputers. Most contiguous processor allocation strategies that are proposed in the previous studies are for 2D meshes (Chiu & Chen, 1999; Ababneh, 2006; Ababneh, 2009; Ababneh et al., 2010; Chuang & Tzeng, 1994; Zhu, 1992). In spite of the fact that the 2D mesh has been used in a various of parallel machines, such as the Cray XE6m (Cray, 2014b), the iWARP (Peterson et al., 1991) and the Touchstone Delta system (Intel, 1991), current multicomputers, such as the K-computer (Riken & Fujitsu, 2014), the Cray XE6 (Cray, 2014a) and the IBM BlueGene/L (Horn et al., 2014) use the 3D mesh or the 3D tori (Cray, 2014a; Horn et al., 2014; Riken & Fujitsu, 2014) as an interconnection network due to their characteristics such as lower diameter and lower average communication distance (Athas & Seitz, 1988).