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

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 chal-lenging. 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 temper-ature 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 veryuseful 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

Fixed-outline floorplanning / Modified simulated annealing algorithm / Global search / Excessive area model / B*-tree representation

References

[1] Adya, S.N., Markov, I.L., 2003. Fixed-outline floorplanning: enabling hierarchical design.IEEE Trans. VLSI Syst., 11(6):1120–1135.http://dx.doi.org/10.1109/TVLSI.2003.817546

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

[3] Chang, Y.C., Chang, Y.W., Wu, G.M., , 2000. B*-trees: a new representation for non-slicing floorplans. Proc. De-sign Automation Conf., p.458–463. http://dx.doi.org/10.1109/DAC.2000.855354

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

[5] Chen, T.C., Chang, Y.W., 2006. Modern floorplanning based on B*-tree and fast simulated annealing.IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 25(4):637–650. http://dx.doi.org/10.1109/TCAD.2006.870076

[6] Chen, T.C., Chang, Y.W., Lin, S.C., 2008. A new multilevel framework for large-scale interconnect-driven floorplan-ning.IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 27(2):286–294. http://dx.doi.org/10.1109/TCAD.2007.907065

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

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

[9] Guo, P.N., Cheng, C.K., Yoshimura, T., 1999. An O-tree representation of non-slicing floorplans and its applica-tions. Proc. Design Automation Conf., p.268–273. http://dx.doi.org/10.1109/DAC.1999.781324

[10] Haridass, K., Valenzuela, J., Yucekaya, A.D., , 2014. Scheduling a log transport system using simulated an-nealing.Inform. Sci., 264:302–316. http://dx.doi.org/10.1016/j.ins.2013.12.005

[11] Heller, W.R., Maling, K., Sorkin, G., 1982. The planar pack-age for system designers. Proc. Design Automation Conf., p.253–260. http://dx.doi.org/10.1109/DAC.1982.1585509

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

[13] Kahng, A.B., 2000. Classical floorplanning harmful? Proc. Int. Symp. on Physical Design, p.207–213. http://dx.doi.org/10.1145/332357.332401

[14] Kahng, A.B., Markov, I., 2007. GSRC Floorplan Benchmark. Available from http://vlsicad.eecs.umich.edu/BK/ GSRCbench/HARD/.

[15] Kennedy, J., Eberhart, R.C., 1995. Particle swarm optimiza-tion. Proc. IEEE Int. Conf. on Neural Networks, p.1942–1948. http://dx.doi.org/10.1109/ICNN.1995.488968

[16] Khan, A.K., Vatsa, R., Roy, S., , 2014. A new efficient topological structure for floorplanning in 3D VLSI physical design. IEEE Int. Advance Computing Conf., p.696–701. http://dx.doi.org/10.1109/IAdCC.2014.6779409

[17] Kirpatrick, S., Gelatt, C.D., Vecchi, M.P., 1983. Optimization by simulated annealing.Science, 220(4598):671–680. http://dx.doi.org/10.1126/science.220.4598.671

[18] Lin, J.M., Chang, Y.W., 2001. TCG: a transitive closure graph-based representation for non-slicing floorplans. Proc. Design Automation Conf., p.764–769. http://dx.doi.org/10.1145/378239.379062

[19] Lin, J.M., Hung, Z.X., 2012. SKB-tree: a fixed-outline driven representation for modern floorplanning problems.IEEE Trans. VLSI Syst., 20(3):473–484. http://dx.doi.org/10.1109/TVLSI.2011.2104983

[20] Lin, S.W., Yu, V.F., 2015. A simulated annealing heuristic for the multiconstraint team orienteering problem with mul-tiple time windows. Appl. Soft Comput., 37:632–642. http://dx.doi.org/10.1016/j.asoc.2015.08.058

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

[22] Ma, T.L., Young, E.F.Y., 2008. TCG-based multi-bend bus driven floorplanning. Design Automation Conf., p.192–197. http://dx.doi.org/10.1109/ASPDAC.2008.4483938

[23] Maling, K., Heller, W.R., Mueller, S.H., 1982. On finding most optimal rectangular package plans. Proc. Design Automation Conf., p.663–670. http://dx.doi.org/10.1109/DAC.1982.1585567

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

[25] Otten, R.H.J.M., 1982. Automatic floorplan design. Proc. Design Automation Conf., p.261–267. http://dx.doi.org/10.1109/DAC.1982.1585510

[26] Storn, R., Price, K., 1997. Differential evolution—a simple and efficient heuristic for global optimization over con-tinuous spaces.J. Glob. Optim., 11(4):341–359. http://dx.doi.org/10.1023/A:1008202821328

[27] Wang, S.L., Zuo, X.Q., Liu, X.Q., , 2015. Solving dy-namic double row layout problem via combining simu-lated annealing and mathematical programming.Appl. Soft Comput., 37:303–310. http://dx.doi.org/10.1016/j.asoc.2015.08.023

[28] Wong, D.F., Liu, C.L., 1986. A new algorithm for floorplan design. Proc. Design Automation Conf., p.101–107. http://dx.doi.org/10.1109/DAC.1986.1586075

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

[30] Wu, P.H., Ho, T.Y., 2011. Thermal-aware bus-driven floor-planning. Int. Symp. on Low Power Electronics and De-sign, p.205–210. http://dx.doi.org/ 10.1109/ISLPED.2011.5993637

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

[32] Yan, J.T., 2006. Simultaneous wiring and buffer block plan-ning with optimal wire-sizing for interconnect-driven floorplanning. IEEE Proc. on Computers and Digital Techniques, p.335–347. http://dx.doi.org/10.1049/ip-cdt:20060077

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

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg