Parallel total weight crossing number algorithm for channel routing on a linear array with a reconfigurable pipelined bus system

Author

Kimm, Haklin

Author_Institution

Dept. of Math. & Comput. Sci, Univ. of Tennessee at Martin, TN, USA

fYear

1997

fDate

9-11 Mar 1997

Firstpage

183

Lastpage

187

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;

fLanguage

English

Publisher

ieee

Conference_Titel

System Theory, 1997., Proceedings of the Twenty-Ninth Southeastern Symposium on

Conference_Location

Cookeville, TN

ISSN

0094-2898

Print_ISBN

0-8186-7873-9

Type

conf

DOI

10.1109/SSST.1997.581604

Filename

581604