A Quasi-Newton-based Floorplanner for fixed-outline floorplanning. (May 2021)

• Record Type: Journal Article
• Authors: Ji, Pengli; He, Kun; Wang, Zhengli; Jin, Yan; Wu, Jigang
• Is Part Of: Computers & operations research. Volume 129(2021)
• Publication Date: 2021-05
• Subjects: Packing -- Floorplanning -- Layout optimization -- Physical design -- Quasi-Newton method; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105225
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A Quasi-Newton based Floorplanner (QinFer) for fixed-outline floorplanning problem. Make full use of the capacities of hypergraph partitioning tool and TP technique. A refined distribution algorithm to produce distributed floorplan. Abstract: We address the problem of floorplanning, a crucial step of VLSI design, and propose a novel approach named Quasi-Newton-based FloorplannER (QinFer) for the challenging fixed-outline floorplanning problem. QinFer is an effective two-phase method. The first phase recursively bipartitions the original circuit to a set of subcircuits until each leaf subcircuit contains only one module. By placing each module onto the suboutline of the leaf subcircuit, a distributed floorplan is obtained. The recursive bipartition enables the strongly connected modules to be placed closely so that the obtained floorplan has a good quality of wirelength. By bipartitioning the circuit into leaf subcircuits with only one module and using terminal propagation technology during the whole bipartitioning process, the capabilities of bipartition tool and terminal propagation technology in improving quality of wirelength are fully utilized. The second phase contributes a potential energy function to evaluate the overlap among the modules as well as the protruding portion of modules beyond the outline, and a Quasi-Newton method is employed to reduce the potential energy for the legalization of the distributed floorplan. The Quasi-Newton legalization method is a general method that can be used to calculate a floorplan without constructing any geometric representations for the modules. Moreover, the robustness of QinFer is further improved by incorporating a refined distribution algorithm to establish feasibility for the case of illegal floorplan. Extensive experimental results on public benchmarks show that, in comparison to the well-known approaches DeFer and F-FM, QinFer can generate 7.3 % and 2.1 % better half-perimeter wirelengths, respectively.