An efficient processor allocation algorithm using two-dimensional packing

Mesh is one of the most widely used interconnection networks for multiprocessor systems, In this paper, we propose an approach to partition a given mesh into in submeshes which can be allocated to in tasks with grid structures, We adapt two-dimensional packing to solve the submesh allocation problem. Due to the intractability of the two-dimensional packing problem, finding an optimal solution is computationally infeasible. We develop an efficient heuristic packing algorithm called TP-heuristic. Allocating a submesh to each task is achieved using the results of packing, We propose two different methods called uniform scaling and nonuniform scaling, Experiments were carried out to test the accuracy of solutions provided by our allocation algorithm, (C) 1997 Academic Press.