ISSN:
1572-9125
Keywords:
B.7.1
;
C.1.2
;
F.2.2
;
G.2.2
;
VLSI
;
CAD
;
intervals
;
channel-assignment
;
graph coloring
;
parallel algorithms
;
reconfigurable meshes
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01994843
Permalink
