Abstract

Floorplan representation is a fundamental issue in designing a VLSI floorplanning algorithm as the representation has a great impact on the feasibility and complexity of floorplan designs. This survey paper gives an up-to-date account on various non-slicing floorplan representations in VLSI floorplanning.

References

• Jianli Chen, Wenxing Zhu, and M. M. Ali, "A Hybrid Simulated Annealing Algorithm for Nonslicing VLSI Floorplanning", IEEE transactions on systems, man and cybernetics—part c: applications and reviews, VOL. 41, NO. 4, 2011, pp. 544-553.
• Jain L. , Singh G, "A Review: Meta- heuristic Approaches for solving Rectangle Packing Problem", International Journal of Computer Engineering and Technology, Volume 4, Issue 2, 2013, pp. 410- 424.
• Singh K. and Jain L. , "Experimenting Genetic approach to extend rectangular packing heuristic solutions", International Journal of Computer Applications. Special Issue on "Evolutionary Computation for Optimization Techniques", 2010, pp. 1-7.
• Singh L. and Jain L. , "An improved Heuristic for 2D Rectangular packing problem", Proceeding of IEEE International Advance Computing Conference, March-2009, Thaper University, Patiala, IEEE Dehli Section, 2009, pp. 1185-1190.
• Singh L. and Jain L, "Optimal Solution for 2-D Rectangle Packing Problem", International Journal of Applied Engineering Research. VOL. 4, NO. 11, 2009, pp. 2203–2222.
• Guolong Chen, Wenzhong Guo, Yuzhong Chen, "A PSO-based intelligent decision algorithm for VLSI floorplanning", Springer, Soft Computing, 2010, pp. 1329–1337.
• D. F. Wong, C. L. Liu, "A new algorithm for floorplan design. " Proceeding of the ACWIEEE Design AntomationConference, 1986, pp. 101-107.
• S. Nakatake, K. Fujiyoshi, H. Murata and Y. Kajitani, "Module placement on BSG-structure and IC layout applications", Proceedings of 1996 IEEE/ACM, International Conf. on Computer Aided Design, 1996, pp. 484-491.
• Maggie Kang, Wayne W. M. Dai, "General floorplanning with L-shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure" In proceedings of Design Automation Conference 1997 Asia and South Pacific, IEEE, 1997, pp. 265 – 270.
• Yuchun Ma', Sheqin Dong', Xianlong Hong', yici Cai', Chung-Kuan Cheng2, Jun Gu3," VLSI Floorplanning with Boundary Constraints Based on Corner Block List", IEEE, 2001, pp 509-514.
• J. -M. Lin,Y. -W. Chang, S. -P. Lin, "Corner sequence: a P-admissible ?oorplan representation with a worst case linear-time packing scheme", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2003, pp. 679–686.
• H. Murata, K. Fujiyoshi and Y. Kajitani: "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, V01. 15, N0. 12, 1996, pp. 1518-1524.
• Koji kiyota, Kunihiro fuiiyoshi, "Simulated Annealing Search Through General Structure Floorplans Using Sequence-Pair", Symposium On Circuits And Systems, Geneva, Switzerland , IEEE, 2000, pp. 77-80.
• Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, and Shu-Wei Wu, "B*-Trees: A New Representation for Non-Slicing Floorplans" (c)ACM, 2000.
• Tung-Chieh Chen, and Yao-Wen Chang," Modern Floorplanning Based on B*-Tree and Fast Simulated Annealing" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VOL. 25, NO. 4, APRIL 2006, pp. 637-650.
• Jai-Ming Lin and Yao-Wen Chang, " TCG: A Transitive Closure Graph-Based Representation for General Floorplans", IEEE transactions on very large scale integration (vlsi) systems, VOL. 13, NO. 2, 2005, pp. 288-292.
• J. -M. Lin and Y. -W. Chang, "TCG-S: Orthogonal Coupling of P*-admissible Representations for General Floorplans," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, pp. 968 - 980.
• B. H. Gwee, and M. H. Lim, "A GA with heuristic-based decoder for IC Floorplanning", The VLSI journal, 1999, pp. 157-172.
• X. G. Wang, L. S. Yao, and J. R. Gan, "VLSI Floorplanning Method Based on Genetic Algorithms", Chinese Journal of Semiconductors, 2002, pp. 330-335.
• P. -N Guo, C. -K. Cheng, T. , Yoshimura, "An O-tree representation of non-slicing floorplan and its applications", Proc. 36th ACWIEEE Design AutoNation Cont. , 1999, pp. 268-273.
• Liang Huang, Yici Cai, Xianlong Hong, "A Parallel VLSI Floorplanning Algorithm Using Corner Block List Topological Representation", IEEE, 2004, pp. 1208-1212.
• Koichi Haua, Shin'ichi Wakabayashi, Tetsushi Koide, "Solving the Rectangular Packing Problem by an Adaptive GA Based on Sequence-Pair", ASP-DAC, 1999, pp. 181-184.
• Ning Xu', Xian-Long Hong'. She-Qin Dong', he-Bang Yu'," TSCSP: Tabu Search Algorithm for VLSI Module Placement Based on the Clustering Sequence-Pair", IEEE, 2003.
• Chikaaki KODAMA, Kunihiro FUJIYOSHI, and Teppei Koga, "A Novel Encoding Method Into Sequence-Pair ", ISCAS, IEEE, 2004, pp. V329 – V332.
• Pradeep Fernando and Srinivas Katkoori, "An Elitist Non-Dominated Sorting based Genetic Algorithm for Simultaneous Area and Wirelength Minimization in VLSI Floorplanning" In 21st International Conference on VLSI Design, 4-8 January 2008, Hyderabad, India, IEEE Computer Society, 2008, pp. 337-342.
• Dipanjan Sengupta, Andreas Veneris, Steve Wilton, Andre Ivanov, Res Saleh, "Sequence Pair Based Voltage Island Floorplanning", Proceedings of the 2011 International Green Computing Conference and Workshops, IEEE computer society Washington, 2011, pp. 1-6.
• Zhen Chen, Jinzhu Chen, Wenzhong Guo, Guolong Chen, "A Coevolutionary Multi-Objective PSO algorithm for VLSI Floorplanning" 8th International Conference on Natural Computation (ICNC), IEEE, 2012, pp. 712-728.
• Samsuddin, AbAl-Hadi Ab Rahman, Andaljayalakshmi G, "A Genetic Algorithm Approach to VLSI Macro Cell Non-Slicing Floorplans Using Binary Tree", Proceedings of the International Conference on Computer and Communication Engineering, IEEE, 2008.
• Fubing Mao, Ning Xu, Yuchun Ma, "Hybrid Algorithm for Floorplanning Using B*-tree Representation", Third International Symposium on Intelligent Information Technology Application, IEEE, 2009, pp. 228-231.
• Chen, J. , & Chen, J. , "A hybrid evolution algorithm for VLSI ?oorplanning", Int. Conf. Comput. Intell. Software Eng. (CiSE), IEEE, 2010, pp. 1-4.
• Jianli Chen, Wenxing Zhu, "A Hybrid Genetic Algorithm for VLSI Floorplanning", International Conference on Intelligent Computing and Intelligent Systems (ICIS), IEEE, 2010, pp. 128-132.
• S. Anand • S. Saravanasankar • P. Subbaraj, "Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem", Springer , 2011.
• Yiding Han, Koushik Chakraborty, Sanghamitra Roy, Vilasita Kuntamukkala, "A GPU Algorithm for IC Floorplanning: Specification, Analysis and Optimization", 24th Annual Conference on VLSI Design, IEEE, 2011.
• Jai-Ming Lin and Yao-Wen Chang, "TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans", Proc. DAC, IEEE, 2001, pp. 764-769.
• Guolong Chen, Wenzhong Guo, Hongju Cheng, Xiang Fen and Xiaotong Fang, "VLSI Floorplanning Based on Particle Swarm Optimization" Proceedings of 3rd International Conference on Intelligent System and Knowledge Engineering, IEEE ,2008, pp. 1020-1025.
• Guolong Chen, Wenzhong Guo, Yuzhong Chen, "A PSO-based intelligent decision algorithm for VLSI Floorplanning", Soft Computing, VOL. 14, NO. 12, Springer, 2009, pp. 1329-1337.
• Pei-Ning Guo, Toshihiko Takahashi, Chung-Kuan Cheng, "Floorplanning Using a Tree Representation", IEEE transactions on computer-aided design of integrated circuits and systems, VOL. 20, NO. 2, 2001, pp. 281-289.
• Hiroshi Ninomiya, Kimihiko Numayama and Hideki Asai, "Two-staged Tabu Search for Floorplan Problem Using O-Tree Representation", IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, July 16-21, 2006.
• Maolin Tang and Xin Yao, "A Memetic Algorithm for VLSI Floorplanning", IEEE transactions on systems, man, and cybernetics—part b: cybernetics, VOL. 37, NO. 1, 2007, pp. 62-69.
• Maolin Tang, Raymond Y. K. Lau," A Parallel Genetic Algorithm for Floorplan Area Optimization", Seventh International Conference on Intelligent Systems Design and Applications,IEEE, 2007, pp. 801-806
• H. H. Chan, I. L. Markov, "Practical Slicing and Non-slicing Block-Packing without Simulated Annealing", ACM/IEEE Great Lakes Symp. on VLSI, 2004, pp. 282-287.
• Tang, X. , Wong, D. F. , "FAST-SP: a fast algorithm for block placement based on sequence pair", In Proceedings of the ASP-DAC, 2000, pp. 521–526.
• Chang-Tzu Lin, De-Sheng Chen, Yi-Wen Wang. , "GPE: A New Representation for VLSI Floorplan Problem", Proc. ICCD, IEEE, 2002, pp. 531 -533.
• Adya, S. N. , Markov, I. L. , "Fixed-outline floorplanning: enabling hierarchical design", Transactions on Very Large Scale Integration (VLSI) Systems, IEEE Transactions , VOl. 11, Issue: 6 , 2003, pp. 1120-1135.