An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules |
| |
Affiliation: | 1. School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;2. School of Computer Science and Technology, University of Picardie Jules Verne, Amiens 80039, France;1. LTI-Laboratory, Department of Logistics and Transport Engineering, ENST, Dergana, Algiers, Algeria;2. Centre for Logistics & Heuristic Optimisation, Kent Business School, The University of Kent, Canterbury, Kent CT2 7FS, UK;1. Institute of Hydraulic Engineering and Water Resources Management, RWTH Aachen University, Aachen D 52056, Germany;2. Institute of Particle Science and Engineering, School of Process, Environmental and Materials Engineering, University of Leeds, Leeds LS2 9JT, UK |
| |
Abstract: | We address an important variant of the rectangle packing problem, the soft rectangle packing problem, and explore its problem extension for the fixed-outline floorplanning with soft modules. For the soft rectangle packing problem with zero deadspace, we present an iterative merging packing algorithm that merges all the rectangles into a final composite rectangle in a bottom-up order by iteratively merging two rectangles with the least areas into a composite rectangle, and then shapes and places each pair of sibling rectangles based on the dimensions and position of their composite rectangle in an up-bottom order. We prove that the proposed algorithm can guarantee feasible layout under some conditions, which are weaker as compared with a well-known zero-dead-space packing algorithm. We then provide a deadspace distribution strategy, which can systematically assign deadspace to modules, to extend the iterative merging packing algorithm to deal with soft packing problem with deadspace. For the fixed-outline floorplanning with soft modules problem, we propose an iterative merging packing based hierarchical partitioning algorithm, which adopts a general hierarchical partitioning framework as proposed in the popular PATOMA floorplanner. The framework uses a recursive bipartitioning method to partition the original problem into a set of subproblems, where each subproblem is a soft rectangle packing problem and how to solve the subproblem plays a key role in the final efficiency of the floorplanner. Different from the PATOMA that adopts the zero-dead-space packing algorithm, we adopt our proposed iterative merging packing algorithm for the subproblems. Experiments on the IBM-HB benchmarks show that the proposed packing algorithm is more effective than the zero-dead-space packing algorithm, and experiments on the GSRC benchmarks show that our floorplanning algorithm outperforms three state-of-the-art floorplanners PATOMA, DeFer and UFO, reducing wirelength by 0.2%, 4.0% and 2.3%, respectively. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|