Fast Channel Graph Construction

Author:Cohoon, James, Department of Computer ScienceUniversity of Virginia

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

All rights reserved (no additional license for public reuse)
Source Citation:

Cohoon, James. "Fast Channel Graph Construction." University of Virginia Dept. of Computer Science Tech Report (1985).

University of Virginia, Department of Computer Science
Published Date: