《三维Mesh多处理机中子网分配策略的研究_英文_》由会员分享，可在线阅读，更多相关《三维Mesh多处理机中子网分配策略的研究_英文_（6页珍藏版）》请在金锄头文库上搜索。
1、An Efficient Processor Allocation Scheme for Three-dimensional*Mesh-connected Multi-computersHong Yue-hua Xu Shuang Wu Hua-jianDepartment of Mathematics and Computer Science, Yulin Normal University, Yulin, 537000, GuangxiAbstract: An efficient processor allocation is crucial for obtaining high perf
2、ormance in multi-computcrs A good processor allocation algorithm should find available processor for incoming jobs, if they exist, with minimum overhead In this paper, we propose such an efficient sub-mesh allocation scheme for three-dimensional mesh-connected multi-computers For allocation, the tim
3、e complexity is lower than the previously proposed schemes. Simulation results show that the algorithm perfonns at least as well as these schemes, yet it has the lowest time complexity.Keywords: allocation scheme; processor allocation; boundary value1 IntroductionMesh interconnection networks have b
4、ecome the most popular networks used in distributed memory parallel computers. This is due to their simplicity, regularity, case of implementation, and scalability. So mesh interconnection is not only the basic model of much academic research, but also is adopted in many parallel multi-computersr， B
5、etween all the topology, three-dimensional mesh is the most important and attraction, such as Tera Computer System and IBM Blue Gene supercomputer both are three-dimensional mesh.A mesh multiprocessor can support a multitasking environment efficiently due to its partitionable structure. In multi-tas
6、king environment, a large number of tasks can be allocated to an independent sub-mesh to implement. Due to the sub-mesh size of the task requires is different, and the system should try to accommodate more tasks, to maximize the utilization of processors, So in order to enhance system performance, e
7、ffective allocation schemes are neededOver the last decade, both at home and abroad the research on the parallel computer processor allocation strategy arc mainly based on twodimensional mesh structure, and all the algorithms used belong to the first fit or best fit.In this paper, a new strategy bas
8、ed on three-dimensional mesh is proposed, and the method can significantly reduce the algorithms time complexity and does not affect system performance2 Basic Concepts and DefinitionsA three-dimensional mesh is denoted by厶,），and W denotes the width and L denotes the length and基金资助：广西自然基金项H(0833286),
9、广西自然青年项H(0832101).作者简介：洪月华(1973-X女,硕士,讲师，广西贵港人,主要研究方向:计算机网络；徐霜(1982-),女，硕士,助教,主要研究 方向：Mesh网络；伍华健(1964)男,教授，硕士生导师,主要研究方向:无线传感器网络、P2P.H denotes the height. Each node is denoted by the address (x.y.z) where 0 x rr,0 y LQ z 5 H Definition 1引 In three-dimensional mesh, a wxlxh submesh S is represented by
10、 (xp ypz,;x2, y2?z2), where(州，),可)is the lower-left corner node at the bottom of S , and (x2,y2.z2) is the upper-right corner at the top ofS (X，x，Z)is called the base node of the sub-mesh, and (x2,y2,z2) is the end node For example, (0,0,0; 5,3,0) represents the mesh M(6,4,5)in Fig. 1. The eight nod
11、es at the lower-left corner can be expressed as (0,0,0; 1,1,1) .The base node of the sub-mesh is (0,0,0), and its end node is (1,1,1).O :1oo.“ 1 JFigi A three-dimensional M(6,4,5) meshDefinition 2 Free sub-mesh refers to the ones that all nodes arc free. Allocation sub-mesh refers to the ones that a
12、ll of the machines in the sub-mesh arc assigned to the same task. A allocation sub-mesh list is a collection of all allocation sub-meshes.Definition 3 The boundary value of a fiee node is the number of allocated neighbors of the node, where a mesh boundary point is considered as having an allocated
13、neighbor beyond that boundary. The boundary value of a free sub-mesh is the sum of the boundary values of its nodes. For example, the boundary value of sub-mesh (0,2,0:1,3,1) in Fig.1 is 12.Definition 4 If the sub-mesh size of a task required is pxqxr then the task is denoted by J(pxqxr). If the sub
14、-meshpxqxr cant find, then consider sub-mesh such as pxrxq qxpxr qxrxp、rxpxq or rxqxp .3 Algorithm DescriptionThe basic idea of the proposed allocation strategy is: First of all, all of free sub-meshes are stored in a free list FL. When a task J(pxxr) comes in, the free list is searched The first se
15、arched sub-mesh that is equal to or greater than the size of pxqxr as the candidateS And then start to compare from the eight vertexes ofS to search for free sub-meshes such as pxrxq、 qx pxr、 qxrxp rxpxq or rxqx p Then the boundary value of the free sub-mesh is calculated, the first subesh ck that h
16、as the largest boundary value is assigned to the task.When ck is assigned to task J , S will be removed from FL, and ck is subtracted firomS This will produce some fragments. If these fragments do not belong to any sub-mesh of FL, it will be added to the head of FL. If a fragment Di is a part of a sub-mesh si in FL, then will be removed from FL. Repeat a
