Item Details

Fast Channel Graph Construction

Cohoon, James
Format
Report
Author
Cohoon, James
Abstract
Channel routing is a'va1uable VLSI routing methodology that requires the routing region be divided into rectangular regions or channels, An algorithm is proposed that rapidly constructs the channels and determines the adjacencies between the channels in 0(nlogn +m) time, where n. is the number of segments to represent the circuits modules and m is the number of channels created. The algorithm determines the number of channels through a parameter k. ‘With k set to some value between 0 and 211 the algorithm constructs a channel graph with 001 +krL) channels. No‘ previous algorithm has - allowed users such control over the size of the channelgraph. Traditional algorithms can be considered to have It preset to either 0 or 271. With k set to 0. our algorithm constructs its 0(n) channels as fast asprevious algorithms. And with k set to Zn, our algorithm constructs its 001.2) channels faster than previous algorithms by a factor 001). Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1985
Published Date
1985
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online