Assignment of Job Modules onto Array Processors

This paper deals with the optimum assignment of job modules onto array processors. In array processors it is important to assign job modules onto processors such that the modules that communicate with each other are assigned to adjacent processors, because communication overhead increases as communications occur between processors that are remotely connected. We propose an efficient algorithm to solve this assignment problem for a specific array of processors. The algorithm reduces the quadratic problem to a solvable linear problem that produces a good, but not necessarily optimal solution. This is followed by a phase of iterations in which the solution is improved by small perturbation of the assignment.