Generic placeholder image

Recent Advances in Computer Science and Communications

Author(s): Rajendra Bahadur Singh*, Anurag Singh Baghel and Arun Solanki

DOI: 10.2174/2213275911666181030104939

DownloadDownload PDF Flyer Cite As
A Binary Particle Swarm Optimization for IC Floorplanning

Page: [13 - 21] Pages: 9

  • * (Excluding Mailing and Handling)

Explore Articles
About Journal
For Authors
For Editors
For Reviewers

Abstract

Background: In the field of IC physical design, there is a big problem in the IC floorplanning to find the early feedback to estimate the area, wire length, delay, etc. before IC fabrication.

Objective: In this paper, minimization of the area and total wire length on the IC has been done using Binary Particle Swarm Optimization with sequence pair representation.

Methods: Optimization of the IC floorplan works in two phases. In the first phase, the floorplan is constructed by sequence pair representation without any overlapping of the modules on IC floorplan. In the second phase, Binary Particle Swarm Optimization algorithm explores the packing of all modules in floorplan to find better optimal performances i.e. area and wire length.

Results: The results obtained were compared with the solutions derived from other meta-heuristic algorithms, the area is improved maximum up to 10% and the wire length was improved maximum up to 28%.

Conclusion: The Experimental results on Microelectronic Center of North Carolina benchmark circuits show that Binary Particle Swarm Optimization algorithm gives better convergence for the area and wire length optimization than other algorithms.

Keywords: Floorplanning, binary particle swarm optimization, sequence pair, MCNC benchmarks, NP-hard, integrated circuit, horizontal constraint graph, vertical constraint graph.

Graphical Abstract

[1]
S.M. Kang, Y. Leblebici, and C. Kim, CMOS digital integrated circuits: Analysis and design (No. EPFL-BOOK-202021)., McGraw-Hill Higher Education, 2014.
[2]
P. Vasant, Ed., Handbook of research on modern optimization algorithms and applications in engineering and economics., IGI Global, 2016.
[http://dx.doi.org/10.4018/978-1-4666-9644-0]
[3]
P. Sivaranjani, and A. Senthil Kumar, "Hybrid Particle Swarm Optimization-Firefly algorithm (HPSOFF) for combinatorial optimization of non-slicing VLSI floorplanning", J. Intell. Fuzzy Syst., vol. 32, no. 1, pp. 661-669, 2017.
[http://dx.doi.org/10.3233/JIFS-152551]
[4]
J. Chen, and W. Zhu, "A hybrid genetic algorithm for VLSI floorplanning", Intell. Comput. Intell. Syst., vol. 2, pp. 128-132, 2010.
[5]
J. Chen, W. Zhu, and M.M. Ali, "A hybrid simulated annealing algorithm for nonslicing VLSI floorplanning", IEEE Trans. Syst. Man Cybern. C, vol. 41, no. 4, pp. 544-553, 2011.
[http://dx.doi.org/10.1109/TSMCC.2010.2066560]
[6]
A. Kaur, and S.S. Gill, "Hybrid swarm intelligence for VLSI floorplan", In: Proceedings of IEEE International Conference on Computing, Communication and Automation (ICCCA). pp. 224-229,2016.
[http://dx.doi.org/10.1109/CCAA.2016.7813739]
[7]
L.N. Manzoor, R. Sen, P.K. Paul, and K.L. Baishnab, "A survey on VLSI Floorplanning: Its representation and modern approaches of optimization", In Innovations in Information, Embedded and Communication Systems (ICIIECS), 2015 International Conference, pp.1-9, IEEE, 2015.
[8]
C.J. Alpert, D.P. Mehta, and S.S. Sapatnekar, "Handbook of algorithms for physical design automation", 1st Edition, Editor, C.J. Alpert, D.P. Mehta, S.S. Sapatnekar, Auerbach Publications, . 1024, 2008
[http://dx.doi.org/10.1201/9781420013481]
[9]
R.B. Singh, A.S. Baghel, and A. Agarwal, "A review on VLSI floorplanning optimization using metaheuristic algorithms", In: International Conference on Electrical, Electronics, and Optimization Techniques, 2016, pp. 4198-4202.
[http://dx.doi.org/10.1109/ICEEOT.2016.7755508]
[10]
S. Paramasivam, S. Athappan, E.D. Natrajan, and M. Shanmugam, "Optimization of thermal aware VLSI non-slicing floorplanning using hybrid particle swarm optimization algorithm-harmony search algorithm", Circuits Syst., vol. 7, no. 5, p. 562, 2016.
[http://dx.doi.org/10.4236/cs.2016.75048]
[11]
P. Sivaranjani, and A.S. Kumar, "Thermal-aware non-slicing VLSI floorplanning using a smart decision-making psoga based hybrid algorithm", Circuits Syst. Signal Process., vol. 34, no. 11, pp. 3521-3542, 2015.
[http://dx.doi.org/10.1007/s00034-015-0020-x]
[12]
M. Tang, and A. Sebastian, "A genetic algorithm for VLSI floorplanning using O-tree representation", In: Workshops on Applications of Evolutionary Computation., Springer: Berlin, Heidelberg, 2005, pp. 215-224.
[http://dx.doi.org/10.1007/978-3-540-32003-6_22]
[13]
D. Henderson, S.H. Jacobson, and A.W. Johnson, "The theory and practice of simulated annealing", In: Handbook of Metaheuristics., Springer: Boston, MA, 2003, pp. 287-319.
[http://dx.doi.org/10.1007/0-306-48056-5_10]
[14]
R.B. Singh, and A.S. Baghel, Simulated annealing algorithm for VLSI floorplanning for soft blocks Int. J. Comp. Sci. Info. Security,. Vol. 16, No. 4, pp. 117-125.
[15]
G. Chen, W. Guo, H. Cheng, X. Fen, and X. Fang, "VLSI floorplanning based on particle swarm optimization", Intell. Syst. Knowl. Engr., vol. 1, pp. 1020-1025, 2008.
[16]
G. Chen, W. Guo, and Y. Chen, "A PSO-based intelligent decision algorithm for VLSI floorplanning", Soft Comput., vol. 14, no. 12, pp. 1329-1337, 2010.
[http://dx.doi.org/10.1007/s00500-009-0501-6]
[17]
D. Zou, G.G. Wang, A.K. Sangaiah, and X. Kong, "A memory-based simulated annealing algorithm and a new auxiliary function for the fixed-outline floorplanning with soft blocks", J. Ambient Intell. Humaniz. Comput.. 2017, pp. 1-12.
[http://dx.doi.org/10.1007/s12652-017-0661-7]
[18]
C.S. Hoo, J. Kanesan, and H. Ramiah, "Enumeration technique in very large-scale integration fixed-outline floorplanning", IET Circuits Dev. Syst., vol. 8, no. 1, pp. 47-57, 2014.
[http://dx.doi.org/10.1049/iet-cds.2013.0003]
[19]
S. Anand, S. Saravanasankar, and P. Subbaraj, "Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem", Comput. Optim. Appl., vol. 52, no. 3, pp. 667-689, 2012.
[http://dx.doi.org/10.1007/s10589-011-9442-y]
[20]
Lichen Zhu, "Yang Runping, Chen Meixue, Jia Xiaomin, Li Xuanxiang, and Du Shimin, "An efficient simulated annealing based VLSI floorplanning algorithm for slicing structure," In Computer Science & Service System (CSSS),2012 International Conference on, ", pp. 326-330, IEEE, 2012.
[21]
S.T. Hsieh, C.W. Lin, and T.Y. Sun, "Particle swarm optimization for macrocell overlap removal and placement", In Proceedings of IEEE,. 2005, pp. 177-180
[22]
C.L. Valenzuela, and P.Y. Wang, "VLSI placement and area optimization using a genetic algorithm to breed normalized postfix expressions", IEEE Trans. Evol. Comput., vol. 6, no. 4, pp. 390-401, 2002.
[23]
M. Tang, and X. Yao, "A memetic algorithm for VLSI floorplanning", IEEE Trans. Syst. Man Cybern. B Cybern., vol. 37, no. 1, pp. 62-69, 2007.
[http://dx.doi.org/10.1109/TSMCB.2006.883268] [PMID: 17278559]
[24]
J. Lienig, "A parallel genetic algorithm for performance-driven VLSI routing", IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 29-39, 1997.
[http://dx.doi.org/10.1109/4235.585890]
[25]
S. Nakaya, T. Koide, and S. Wakabayashi, An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair..Circuits Syst. Proc., Geneva., , Vol. 3, pp. 65-68, 2000.
[http://dx.doi.org/10.1109/ISCAS.2000.855997]
[26]
"Anand S., S. Saravanasankar, and P. Subbaraj,"A multiobjective optimization tool for Very Large Scale Integrated nonslicing floorplanning", International Journal of Circuit Theory and Applications. 41, no. 9, pp.904-923, 2013.
[27]
C.T. Lin, and D.S. Chen, "Modern floorplanning with boundary and fixed-outline constraints via genetic clustering algorithm", J. Circuits Syst. Comput., vol. 15, no. 1, pp. 107-127, 2006.
[http://dx.doi.org/10.1142/S0218126606002940]
[28]
S. Chen, and T. Yoshimura, "Fixed-outline floorplanning: Block-position enumeration and a new method for calculating area costs", IEEE Trans.on Comput. Aided Des. Integrated Circ.and Syst.. 27(5), 858-871, 2008.
[29]
"V.-T. Lin, D.-S. Chen, and Y.-W. Wang,Modern floorplanning with boundary and fixed-outline constraints via genetic clustering algorithm", Journal of Circuits, Systems, and Computers.. 15, no. 01,pp.107-127, 2006.
[30]
J.M. Lin, and Z.X. Hung, "SKB-tree: A fixed-outline driven representation for modern floorplanning problems", IEEE Trans. Very Large Scale Integr. Syst., vol. 20, no. 3, pp. 473-484, 2012.
[31]
J.M. Lin, and J.H. Wu, "F-FM: Fixed-outline floorplanning methodology for mixed-size modules considering voltage-island constraint", IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 33, no. 11, pp. 1681-1692, 2014.
[http://dx.doi.org/10.1109/TCAD.2014.2351571]
[32]
P.G. Sassone, and S.K. Lim, "Traffic: A novel geometric algorithm for fast wire-optimized floorplanning", IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 25, no. 6, pp. 1075-1086, 2006.
[http://dx.doi.org/10.1109/TCAD.2005.855921]
[33]
E.F. Young, C.C. Chu, and M.L. Ho, "Placement constraints in floorplan design", IEEE Trans. Very Large Scale Integr. Syst., vol. 12, no. 7, pp. 735-745, 2004.
[34]
Y.C. Chen, and Y. Li, "Temperature-aware floorplanning via geometric programming", Math. Comput. Model., vol. 51, no. 7-8, pp. 927-934, 2010.
[http://dx.doi.org/10.1016/j.mcm.2009.08.026]
[35]
C.S. Hoo, K. Jeevan, V. Ganapathy, and H. Ramiah, "Variable-order ant system for VLSI multiobjective floorplanning", Appl. Soft Comput., vol. 13, no. 7, pp. 3285-3297, 2013.
[http://dx.doi.org/10.1016/j.asoc.2013.02.011]
[36]
T.Y. Sun, S.T. Hsieh, H.M. Wang, and C.W. Lin, "Floorplanning based on particle swarm optimization", In: IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures (ISVLSI’06), 2006, p. 5.
[http://dx.doi.org/10.1109/TEVC.2002.802872]
[37]
S.V. Kumar, P.V. Rao, H.A. Sharath, B.M. Sachin, U.S. Ravi, and B.V. Monica, Review on VLSI design using optimization and self-adaptive particle swarm optimization., J. King Saud University-Comp. Info. Sci, 2018.
[http://dx.doi.org/10.1016/j.jksuci.2018.01.001]
[38]
Y.C. Chang, Y.W. Chang, G.M. Wu, and S.W. Wu, "B*-Trees: A new representation for non-slicing floorplans", In: Proceedings of 37th Annual Design Automation Conference, 2000, pp. 458-463.
[39]
Y. Ma, S. Dong, X. Hong, Y. Cai, C.K. Cheng, and J. Gu, "VLSI floorplanning with boundary constraints based on corner block list", In: Proceedings of Asia and South Pacific Design Automation Conference, 2001, pp. 509-514.
[http://dx.doi.org/10.1145/370155.370521]
[40]
"M., & Dai, W. M., “General floorplanning with L-shaped, T-shaped and soft blocks based on bounded slicing grid structure", In: Design Automation Conference, Proceedings of the ASP-DAC’97 Asia and South Pacific. pp. 265-270, IEEE, 1997.
[41]
S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, "Module placement on BSG-structure and IC layout applications", In: Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, 1997, pp. 484-491.
[42]
S.K. Lim, Practical problems in VLSI physical design automation., Springer Science and Business Media, 2008.
[http://dx.doi.org/10.1007/978-1-4020-6627-6]
[43]
J.M. Lin, and Y.W. Chang, "TCG: A transitive closure graph-based representation for general floorplans", IEEE Trans. Very Large Scale Integr. Syst., vol. 13, no. 2, pp. 288-292, .
[44]
J.M. Lin, Y.W. Chang, and S.P. Lin, "Corner sequence-a P-admissible floorplan representation with a worst case linear-time packing scheme", IEEE Trans. Very Large Scale Integr. Syst., vol. 11, no. 4, pp. 679-686, 2003.
[http://dx.doi.org/10.1145/337292.337541]
[45]
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair", IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 15, no. 12, pp. 1518-1524, 1996.
[http://dx.doi.org/10.1109/43.552084]
[46]
Y. Shi, and R.C. Eberhart, "Parameter selection in particle swarm optimization", In: International Conference on Evolutionary Programming. Springer, Berlin: Heidelberg, 1998, pp. 591-600.