Handling soft modules in general nonslicing floorplan using Lagrangian relaxation

Citation
Fy. Young et al., Handling soft modules in general nonslicing floorplan using Lagrangian relaxation, IEEE COMP A, 20(5), 2001, pp. 687-692
Citations number
13
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
ISSN journal
02780070 → ACNP
Volume
20
Issue
5
Year of publication
2001
Pages
687 - 692
Database
ISI
SICI code
0278-0070(200105)20:5<687:HSMIGN>2.0.ZU;2-A
Abstract
In the early stage of floorplan design, many modules have large flexibiliti es in shape (soft modules). Handling soft modules in general nonslicing flo orplan is a complicated problem. Many previous works have attempted to tack le this problem using heuristics or numerical methods, but none of them can solve it optimally and efficiently, In this paper, we show how this proble m can be solved optimally by geometric programming using the Lagrangian rel axation technique. The resulting Lagrangian relaxation subproblem is so sim ple that the optimal size of each module can be computed in linear time. We implemented this method in a simulated annealing framework based on the se quence pair representation, The geometric program is invoked in every itera tion of the annealing process to compute the optimal size of each module to give the best packing. The execution time is much faster (at least 15 time s faster for data sets with more than 50 modules) than that of the most upd ated previous work by Murata and Kuh (1998). For a benchmark data with 49 m odules, we take 3.7 h in total for the whole annealing process using a 600- MHz Pentium m processor while the convex programming approach described by Murata and Koh needs seven days using a 250-MHz DEC Alpha. Our technique wi ll also be applicable to other floorplanning algorithms that use constraint graphs to find module positions in the final packing.