Tech Report CS-88-21

Parallel Constraint Graph Generation

John E. Savage and Markus G. Wloka

December 1988

Abstract:

In this paper we present a parallel algorithm for computing the {\em transitive reduction of an interval DAG}. This is equivalent to a parallel algorithm for computing a minimum-distance constraint DAG from a VLSI layout. An intermediate result developed during the execution of the above algorithm is a parallel algorithm for constructing a {\em tiling} or {\em corner stitching}, a geometrical data structure used in the Magic VLSI layout system. All these computations take time $O(\log ^ 2 n)$ using $O(n / \log n)$ processors on an EREW PRAM, so their processor-time product is optimal. The algorithm can easily be implemented on a practical parallel machine.