An O(n1.5 log n) 1-d compaction algorithm

Key algorithms and properties of 1-d IC layout compaction are presented. In particular, the spacing constraint formulation problem is mapped into the vertical visibility graph construction problem, whose time complexity is O(n log n) if element swappings are not considered. This approach generates enough constraints for the later automatic jogging purposes, while maintaining graph sparsity. The graph solution algorithm is made event-driven to achieve O(n^1.5 log n) expected running time. For hierarchical module assembly. a simple port abstraction method is used with O(n^1.5 log n) worst-case time complexity that allows cells to stretch and pitch match. The speed involvement is due to a transformation to ensure all weights are nonpositive, where the fast Dijkstra´s longest path algorithm call be used. A reverse transformation is required to obtain the solution. An integrated leaf cell compaction and module assembly algorithm was proved to be free from the xy interlock problem. The module assembly problem was established as an integer linear programming problem where there is no known fast algorithm. A heuristic method is used instead to explore layout hierarchy as a practical solution with high speed, low memory and minor area penalties