Fast constraint graph generation algorithms for VLSI layout compaction

Three new fast constraint graph generation algorithms, PPSS-1D, PPSS-1Dk and PPSS-2D, are presented for VLSI layout compaction. The algorithms are based on parallel plane sweep shadowing (PPSS). The PPSS-1D algorithm improves the time spent on searching processes from O(Nˆ1.5) to O(G*N) with extra O(G) memory where G is independent of N. PPSS-1Dk, the successor to PPSS-1D, eliminates the possibility of generation of unnecessary constraints using extra O(k*G) memory. PPSS-2D improves the O(NlogN) sorting time required by PPSS to O(NlogN/logG). The experimental results show the superiority of each algorithm to the PPSS algorithm on time complexity bases