A fast constraint graph based compactor for VLSI circuit layouts

The compactor consists of three parts: event sorting, graph building and graph solving. The event sorting portion is a pre-processor to prepare the data from the layout for constraint graph generation. The authors adopt the quicksort algorithm. The graph building part is the core of the compactor. Since the constraint graph building is the most time consuming step in constraint graph based compactions, it is strategic to develop an efficient constraint graph generation algorithm. Among various constraint graph generation techniques the perpendicular plane sweep approach of Burns and Newton results in run times approaching O(NlogN), where N is the number of elements in the layout, but in the worst case it is still O(N²). The authors have improved the perpendicular plane sweep method with space complexity of O(N) and time complexity reduced to O(NlogN) in the worst case. The last part of the compactor is graph solving in which the fast event-driven algorithm is used. The compactor is developed in C on microVAX 3600. The results show that the improvement is significant