TCG-SP: An improved floorplan representation based on an efficient hybrid of Transitive Closure Graph and Sequence Pair

Abstract

This paper presents TCG-SP, a hybrid floorplan representation based on full and cost-effective integration of Transitive Closure Graph (TCG) and Sequence Pair (SP). TCG-SP efficiently reduces the complexity in the operations performed on placement modules, and in the transformation between a representation and its floorplan, compared to other approaches. TCG-SP proposes a fast O(n log n) time complexity scheme to construct SP from placement. In addition, by retaining a full knowledge of SP ordering sequence in TCG-SP representation, an O(n log log n) time complexity packing cost function calculation is attainable. Furthermore, TCG properties allow a dynamic update of geometric dependency among blocks in a floorplan during solution perturbation. Using this property along with SP ordering property, TCG-SP proposes a fast O(n) runtime cost function update to perturb a placement solution. TCG-SP based simulated annealing scheme for floorplan design is developed. Our floorplanner is simulated with real objective functions and proven to be competitive in terms of runtime and solution quality.