Title :
Parallel total weight crossing number algorithm for channel routing on a linear array with a reconfigurable pipelined bus system
Author_Institution :
Dept. of Math. & Comput. Sci, Univ. of Tennessee at Martin, TN, USA
Abstract :
In the channel routing problem, terminals between cells are interconnected completely while reducing channel routing area. The crossing number, the number of crossings between two wires in the channel, is related to the channel routing area. In this paper, we present a parallel algorithm finding a weighted total crossing number in the channel by using LARPBS model (Linear Array with a Reconfigurable Pipelined Bus System), which is based on the advanced fiber optic technology. The parallel total weight crossing number algorithm on the LARPBS model runs in O(n*log(√n)) time using O(n) number of processors, where n is the number of nets in a channel
Keywords :
multiprocessor interconnection networks; parallel algorithms; reconfigurable architectures; LARPBS model; channel routing; channel routing area; fiber optic technology; linear array; parallel algorithm; parallel total weight crossing number algorithm; reconfigurable pipelined bus system; Computer science; Costs; Density measurement; Optical arrays; Parallel algorithms; Propagation delay; Routing; Wires;
Conference_Titel :
System Theory, 1997., Proceedings of the Twenty-Ninth Southeastern Symposium on
Conference_Location :
Cookeville, TN
Print_ISBN :
0-8186-7873-9
DOI :
10.1109/SSST.1997.581604
