Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules

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. (C) 2017 Elsevier Ltd. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636426
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:22
Dernière modification le : mardi 30 août 2022 - 17:02:43

Identifiants

Collections

Citation

Pengli Ji, Kun He, Yan Jin, Hongsheng Lan, Chumin Li. An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules. Computers and Operations Research, Elsevier, 2017, 86, pp.110-123. ⟨10.1016/j.cor.2017.05.009⟩. ⟨hal-03636426⟩

Partager

Métriques

Consultations de la notice

27