A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints

De-xuan ZOU; Gai-ge WANG; Gai PAN; Hong-wei QI

doi:10.1631/FITEE.1500386

Your Location：

Home >

Browse articles >

A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints

Regular Papers | Updated：2022-05-19

- A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints
- 基于修正模拟退火算法及溢出面积模型的固定边界布图规划
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 11, Pages: 1228-1244(2016)
- Affiliations：
  
  1School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China
  2School of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China
- Author bio：
  
  E-mail:zoudexuan@163.com
- Funds：
- DOI：10.1631/FITEE.1500386
  CLC： TN4
- Received：07 November 2015，
  
  Accepted：16 February 2015，
  
  Published：2016-11
- Accepted：
Scan QR Code
De-xuan ZOU, Gai-ge WANG, Gai PAN, et al. A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(11): 1228-1244.
DOI：

De-xuan ZOU, Gai-ge WANG, Gai PAN, et al. A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(11): 1228-1244. DOI： 10.1631/FITEE.1500386.

摘要

无边界布图规划研究面积及线长减少问题很难满足现代设计需求，因此通常被认为是无意义的。我们关注一种难度更大且更有意义的问题--固定边界布图规划。该问题将固定边界约束条件加入无边界布图规划中，使其在实体设计中更有趣、更具挑战性。本文的工作主要分为两部分。第一，提出了一种修正模拟退火算法（Modified simulated annealing algorithm

MSA）。在进化过程初期，用一种新的衰减方程来缓慢减小温度，以增强MSA的全局搜索能力。然后，用传统衰减方程来快速减小温度，以维持MSA的局部搜索能力。第二，设计了一种溢出面积模型来引导MSA寻找可行解，为精炼可行解节省了大量时间。另外，B*-tree是一种有效的布图规划表示法，它被用来执行MSA的扰动操作。最后，以六组带有不同空置率及高宽比的benchmark为例，证实本文所提方法在解决固定边界布图规划问题上的效率，这些问题包括电路n10，n30，n50，n100，n200和n300。与几种现有方法相比，本方法能够更有效地获得令人满意的目标函数值，它们与芯片面积、线长和固定边界约束有关。

Abstract

Outline-free floorplanning focuses on area and wirelength reductions

which are usually meaningless

since they can hardly satisfy modern design requirements. We concentrate on a more difficult and useful issue

fixed-outline floorplanning. This issue imposes fixed-outline constraints on the outline-free floorplanning

making the physical design more interesting and challenging. The contributions of this paper are primarily twofold. First

a modified simulated annealing (MSA) algorithm is proposed. In the beginning of the evolutionary process

a new attenuation formula is used to decrease the temperature slowly

to enhance MSA's global searching capacity. After a period of time

the traditional attenuation formula is employed to decrease the temperature rapidly

to maintain MSA's local searching capacity. Second

an excessive area model is designed to guide MSA to find feasible solutions readily. This can save much time for refining feasible solutions. Additionally

B*-tree representation is known as a very useful method for characterizing floorplanning. Therefore

it is employed to perform a perturbing operation for MSA. Finally

six groups of benchmark instances with different dead spaces and aspect ratios-circuits n10

n30

n50

n100

n200

and n300-are chosen to demonstrate the efficiency of our proposed method on fixed-outline floorplanning. Compared to several existing methods

the proposed method is more efficient in obtaining desirable objective function values associated with the chip area

wirelength

and fixed-outline constraints.

关键词

Keywords

references

SN Adya , , , IL Markov . . Fixed-outline floorplanning: enabling hierarchical design . . IEEE Trans. VLSI Syst. , , 2003 . . 11 ( ( 6 ): ): 1120 - - 1135 . . DOI: 10.1109/TVLSI.2003.817546 http://doi.org/10.1109/TVLSI.2003.817546 . .

A Chambari , , , AA Najafi , , , S.H.A. Rahmati , , , 等 . . An efficient simulated annealing algorithm for the redundancy allocation problem with a choice of redundancy strategies . . Reliab. Eng. Syst. Safety , , 2013 . . 119 158 - - 164 . . DOI: 10.1016/j.ress.2013.05.016 http://doi.org/10.1016/j.ress.2013.05.016 . .

YC Chang , , , YW Chang , , , GM Wu , , , 等 . . B*-trees: a new representation for non-slicing floorplans . . 2000 . . Proc. Design Automation Conf. . . 458 - - 463 . . DOI: 10.1109/DAC.2000.855354 http://doi.org/10.1109/DAC.2000.855354 . .

S Chen , , , T Yoshimura . . Fixed-outline floorplanning: block-position enumeration and a new method for calcu-lating area costs . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2008 . . 27 ( ( 5 ): ): 858 - - 871 . . DOI: 10.1109/TCAD.2008.917968 http://doi.org/10.1109/TCAD.2008.917968 . .

TC Chen , , , YW Chang . . Modern floorplanning based on B*-tree and fast simulated annealing . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2006 . . 25 ( ( 4 ): ): 637 - - 650 . . DOI: 10.1109/TCAD.2006.870076 http://doi.org/10.1109/TCAD.2006.870076 . .

TC Chen , , , YW Chang , , , SC Lin . . A new multilevel framework for large-scale interconnect-driven floorplan-ning . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2008 . . 27 ( ( 2 ): ): 286 - - 294 . . DOI: 10.1109/TCAD.2007.907065 http://doi.org/10.1109/TCAD.2007.907065 . .

J Cong , , , J Wei , , , Y Zhang . . A thermal-driven floor-planning algorithm for 3D ICs . . 2004 . . IEEE/ACM Int. Conf. on Computer Aided Design . . 306 - - 313 . . DOI: 10.1109/ICCAD.2004.1382591 http://doi.org/10.1109/ICCAD.2004.1382591 . .

JC Goodson . . A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands . . Eur. J. Oper. Res. , , 2015 . . 241 ( ( 2 ): ): 361 - - 369 . . DOI: 10.1016/j.ejor.2014.09.031 http://doi.org/10.1016/j.ejor.2014.09.031 . .

PN Guo , , , CK Cheng , , , T Yoshimura . . An O-tree representation of non-slicing floorplans and its applications . . 1999 . . Proc. Design Automation Conf. . . 268 - - 273 . . DOI: 10.1109/DAC.1999.781324 http://doi.org/10.1109/DAC.1999.781324 . .

K Haridass , , , J Valenzuela , , , AD Yucekaya , , , 等 . . Scheduling a log transport system using simulated an-nealing . . Inform. Sci. , , 2014 . . 264 302 - - 316 . . DOI: 10.1016/j.ins.2013.12.005 http://doi.org/10.1016/j.ins.2013.12.005 . .

WR Heller , , , K Maling , , , G Sorkin . . The planar package for system designers . . 1982 . . Proc. Design Automation Conf. . . 253 - - 260 . . DOI: 10.1109/DAC.1982.1585509 http://doi.org/10.1109/DAC.1982.1585509 . .

CS Hoo , , , J Kanesan , , , H Ramiah . . Enumeration tech-nique in very large-scale integration fixed-outline floor-planning . . IET Circ. Dev. Syst. , , 2014 . . 8 ( ( 1 ): ): 47 - - 57 . . DOI: 10.1049/iet-cds.2013.0003 http://doi.org/10.1049/iet-cds.2013.0003 . .

AB Kahng . . Classical floorplanning harmful? . . 2000 . . Proc. Int. Symp. on Physical Design . . 207 - - 213 . . DOI: 10.1145/332357.332401 http://doi.org/10.1145/332357.332401 . .

AB Kahng , , , I Markov . . GSRC Floorplan Benchmark , , 2007 . . Available from: http://vlsicad.eecs.umich.edu/BK/GSRCbench/HARD/ http://vlsicad.eecs.umich.edu/BK/GSRCbench/HARD/ . .

J Kennedy , , , RC Eberhart . . Particle swarm optimization . . 1995 . . Proc. IEEE Int. Conf. on Neural Networks . . 1942 - - 1948 . . DOI: 10.1109/ICNN.1995.488968 http://doi.org/10.1109/ICNN.1995.488968 . .

AK Khan , , , R Vatsa , , , S Roy , , , 等 . . A new efficient topological structure for floorplanning in 3D VLSI physical design . . 2014 . . IEEE Int. Advance Computing Conf. . . 696 - - 701 . . DOI: 10.1109/IAdCC.2014.6779409 http://doi.org/10.1109/IAdCC.2014.6779409 . .

S Kirpatrick , , , CD Gelatt , , , MP Vecchi . . Optimization by simulated annealing . . Science , , 1983 . . 220 ( ( 4598 ): ): 671 - - 680 . . DOI: 10.1126/science.220.4598.671 http://doi.org/10.1126/science.220.4598.671 . .

JM Lin , , , YW Chang . . TCG: a transitive closure graph-based representation for non-slicing floorplans . . 2001 . . Proc. Design Automation Conf. . . 764 - - 769 . . DOI: 10.1145/378239.379062 http://doi.org/10.1145/378239.379062 . .

JM Lin , , , ZX Hung . . SKB-tree: a fixed-outline driven representation for modern floorplanning problems . . IEEE Trans. VLSI Syst. , , 2012 . . 20 ( ( 3 ): ): 473 - - 484 . . DOI: 10.1109/TVLSI.2011.2104983 http://doi.org/10.1109/TVLSI.2011.2104983 . .

SW Lin , , , VF Yu . . A simulated annealing heuristic for the multiconstraint team orienteering problem with multiple time windows . . Appl. Soft Comput. , , 2015 . . 37 632 - - 642 . . DOI: 10.1016/j.asoc.2015.08.058 http://doi.org/10.1016/j.asoc.2015.08.058 . .

R Liu , , , S Dong , , , X Hong , , , 等 . . Fixed-outline floor-planning with constraints through instance augmentation . . 2005 . . IEEE Int. Symp. on Circuits and Systems . . 1883 - - 1886 . . DOI: 10.1109/ISCAS.2005.1464979 http://doi.org/10.1109/ISCAS.2005.1464979 . .

TL Ma , , , E.F.Y. Young . . TCG-based multi-bend bus driven floorplanning . . 2008 . . Design Automation Conf. . . 192 - - 197 . . DOI: 10.1109/ASPDAC.2008.4483938 http://doi.org/10.1109/ASPDAC.2008.4483938 . .

K Maling , , , WR Heller , , , SH Mueller . . On finding most optimal rectangular package plans . . 1982 . . Proc. Design Automation Conf. . . 663 - - 670 . . DOI: 10.1109/DAC.1982.1585567 http://doi.org/10.1109/DAC.1982.1585567 . .

H Murata , , , K Fujiyoshi , , , S Nakatake , , , 等 . . VLSI module placement based on rectangle-packing by the sequence pair . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 1996 . . 15 ( ( 12 ): ): 1518 - - 1524 . . DOI: 10.1109/43.552084 http://doi.org/10.1109/43.552084 . .

R.H.J.M. Otten . . Automatic floorplan design . . 1982 . . Proc. Design Automation Conf. . . 261 - - 267 . . DOI: 10.1109/DAC.1982.1585510 http://doi.org/10.1109/DAC.1982.1585510 . .

R Storn , , , K Price . . Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces . . J. Glob. Optim. , , 1997 . . 11 ( ( 4 ): ): 341 - - 359 . . DOI: 10.1023/A:1008202821328 http://doi.org/10.1023/A:1008202821328 . .

SL Wang , , , XQ Zuo , , , XQ Liu , , , 等 . . Solving dynamic double row layout problem via combining simulated annealing and mathematical programming . . Appl. Soft Comput. , , 2015 . . 37 303 - - 310 . . DOI: 10.1016/j.asoc.2015.08.023 http://doi.org/10.1016/j.asoc.2015.08.023 . .

DF Wong , , , CL Liu . . A new algorithm for floorplan design . . 1986 . . Proc. Design Automation Conf. . . 101 - - 107 . . DOI: 10.1109/DAC.1986.1586075 http://doi.org/10.1109/DAC.1986.1586075 . .

K.W.C. Wong , , , E.F.Y. Young . . Fast buffer planning and congestion optimization in interconnect-driven floor-planning . . 2003 . . Proc. Design Automation Conf. . . 411 - - 416 . . DOI: 10.1109/ASPDAC.2003.1195050 http://doi.org/10.1109/ASPDAC.2003.1195050 . .

PH Wu , , , TY Ho . . Thermal-aware bus-driven floor-planning . . 2011 . . Int. Symp. on Low Power Electronics and Design . . 205 - - 210 . . DOI: 10.1109/ISLPED.2011.5993637 http://doi.org/10.1109/ISLPED.2011.5993637 . .

H Xiang , , , XP Tang , , , M.D.F. Wong . . Bus-driven floorplanning . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2004 . . 23 ( ( 11 ): ): 1522 - - 1530 . . DOI: 10.1109/TCAD.2004.836728 http://doi.org/10.1109/TCAD.2004.836728 . .

JT Yan . . Simultaneous wiring and buffer block planning with optimal wire-sizing for interconnect-driven floorplanning . . 2006 . . IEEE Proc. on Computers and Digital Techniques . . 335 - - 347 . . DOI: 10.1049/ip-cdt:20060077 http://doi.org/10.1049/ip-cdt:20060077 . .

JZ Yan , , , C Chu . . DeFer: deferred decision making enabled fixed-outline floorplanning algorithm . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2010 . . 29 ( ( 3 ): ): 367 - - 381 . . DOI: 10.1109/TCAD.2010.2041850 http://doi.org/10.1109/TCAD.2010.2041850 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰