AN EFFICIENT PROCESSOR ALLOCATION ALGORITHM USING 2-DIMENSIONAL PACKING

Mesh is one of the most widely used interconnection networks for multi processor 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 submes h allocation problem. Due to the intractability of the two-dimensional packing problem, finding an optimal solution is computationally infea sible. We develop an efficient heuristic packing algorithm called TP-h euristic. Allocating a submesh to each task is achieved using the resu lts of packing, We propose two different methods called uniform scalin g and nonuniform scaling, Experiments were carried out to test the acc uracy of solutions provided by our allocation algorithm, (C) 1997 Acad emic Press.