G.S. Adhar (USA)
Trapezoid Graphs, Parallel Algorithms, Channel Routing.
In two-sided channel routing on a VLSI chip it is often convenient to represent signal nets by trapezoids. In this representation the four corners of the trapezoids are the right most and left-most terminals on the upper side and lower side of the channel respectively. The maximum set of nonintersecting trapezoids is of particular interest since corresponding signal nets can be safely assigned to the same layer in the channel routing. Although a sequential algorithm to compute maximum independent set of trapezoids is known, the sweep line approach employed by the sequential algorithm is incremental in nature and does not yield itself to a parallel solution. In this paper we use three new ideas to find the maximum independent set in parallel. First, for every comparable pair of trapezoids we introduce a new unique ’in-between’ trapezoid. Next, the trapezoids are mapped to their canonical box representation, and finally, a new parallel operation called ’corner stitching’ is applied on boxes to construct chains of boxes which define the independent set. The algorithm presented here is deterministic and is designed to run on a Concurrent Read Concurrent Write parallel random access machine(CRCW-PRAM). The algorithm runs in O(log n) time with O(n2) processors.
Important Links:
Go Back
