A constant-time channel-assignment algorithm on reconfigurable meshes

The channel-assignment problem is central to the integrated circuit fabrication process. Given a two-sided printed circuit board, we wish to maken pairs of components electrically equivalent. The connections are made using two vertical runs along with a horizontal one. Each horizontal run lies in a channel. The channel-assignment problem involves minimizing the total number of channels used.Recent advances in VLSI have made it possible to build massively parallel machines. To overcome the inefficiency of long distance communications among processors, some parallel architectures have been augmented by bus systems. If such a bus system can be dynamically changed to suit communication needs among processors, it is referred to asreconfigurable. The reconfigurable mesh is one of the practical models featuring a reconfigurable bus system. In this paper, we propose a constant-time algorithm to solve the channel-assignment problem of sizen on a reconfigurable mesh of sizen×n.This work was supported by NASA under grant NCC1-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.