Total views : 172

A Novel High Speed Simulated Annealing Algorithm for Non-Slicing VLSI Floorplanning using B*-Tree Representation

Affiliations

  • Department of Electronics and Communication Engineering, Thapar University, Bhadson Road, Patiala -147004, Punjab, India

Abstract


Objective: To optimise area, interconnecting wirelength and dead space of very large scale integration non-slicing floorplan with high computation speed using evolutionary algorithm intelligently. Methods/Statistical Analysis: Floorplanning is one of the most important steps in physical design automation in very large scale integration (VLSI) and to solve the problem of VLSI floorplanning is an art. Parameters like chip performance, sizing of modules in a chip, yield and reliability of chip are determined using VLSI floorplanning. The Simulated algorithm and B*-tree structure have been implemented in C++ language and compiled in GCC compiler of Ubuntu14.04. Findings: Parameters like chip performance, sizing of modules in a chip, yield and reliability of chip are determined using VLSI floorplanning. Many computer-aided design algorithms are developed for the NP-hard problems like VLSI floorplanning. A simulated annealing (SA) algorithm for the hard module and non-slicing VLSI floorplanning problem is presented. The SA uses a new acquisitive method to construct an initial B*-tree and a new process to explore the search space. Application/Improvements: The SA has been implemented and experimental result with optimisation of area, dead space, wirelength and best timing constraints have been tested on Microelectronic Center of North Carolina (MCNC) benchmarks.

Keywords

B*-Tree, Computer Aided Design, Floorplanning, Simulated Annealing Algorithm, Very Large Scale Integration.

Full Text:

 |  (PDF views: 168)

References


  • Gerez SH. India: Wiley: Algorithms for VLSI Design Automation. 1998; p. 1-6.
  • Chen CH, Tollis IG. Area optimization of spiral floorplans.Journal of Circuits, Systems and Computers. 1993; 3(4):833-57.
  • Adya SN, Markov IL. Fixed-outline floorplanning: enabling hierarchical design. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2003; 11(6):1120-35.
  • Sherwani N. India: Springer: Algorithms for VLSI Physical Design Automation Third Edition. 1998.
  • Chen TC, Chang YW. Modern floorplanning based on B-tree and fast simulated annealing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2006; 25(4):637-50.
  • Anand S, Saravanasankar S, Subbaraj P. Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem.Computational Optimization and Applications. 2012; 52(3):667–89.
  • Hoo CS, Jeevan K, Ganapathy V, Ramiah H. Variable-order ant system for VLSI multiobjective floorplanning. Applied Soft Computing. 2013; 13(7):3285–97.
  • Pang Y, Cheng CK, Yoshimura T. An enhanced perturbing algorithm for floorplan design using the O-tree representation.San Diego, CA, USA: Editors: Proceedings of the International Symposium on Physical Design. 2000; p.168–73.
  • Cohoon J, Hegde S, Martin W, Richards D. Distributed genetic algorithms for the floorplan design problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1991; 10(4):483-92.
  • Chen G, Guo W, Chen Y. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing. 2010; 14(12):1329-37.
  • Ishibuchi H, Yoshida T, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flow shop scheduling.IEEE Transactions on Evolutionary Computation. 2003; 7(2):204–23.
  • Chen J, Zhu W, Ali M. A hybrid simulated annealing algorithm for non-slicing VLSI floorplanning. IEEE Transactions on Systems, Man, and Cybernetics: Systems.2011; 41(4):544–53.
  • Chen YC, Li Y. Temperature-aware floorplanning via geometric programming. Mathematical and Computer Modelling. 2010; 51(7):927-34.
  • Cuesta D, Risco-Martin JL, Ayala JL, Hidalgo JI. 3D thermal-aware floorplanner using a MOEA approximation.Integration, the VLSI Journal. 2013; 46(1):10–21.
  • Gracia N, Rajaram S, Nivethitha N, Sudarsan A. Thermal aware modern VLSI floorplanning. Editor: International Conference on Devices, Circuits and Systems Karunya University Coimbatore, India. 2012; p. 187–90.
  • Hung WL, Xie Y, Vijaykrishnan N, Addo-Quaye C, Theocharides T, Irwin MJ. Thermal-aware floorplanning using genetic algorithms. USA: Silicon Valley Polytechnic Institute: Sixth International Symposium on Quality of Electronic Design. 2005; p. 634–39.
  • Han Y, Koren I. Simulated annealing based temperature aware floorplanning. Journal of Low Power Electronics and Applications. 2007; 3(2):141-55.
  • Huang W, Chen D, Xu R. A new heuristic algorithm for rectangle packing. Computers & Operations Research.2007; 34(11):3270-80.
  • The MCNC Benchmark Problems for VLSI Floorplanning.Date accessed:? Available from: http://www.mcnc.org.
  • Guo PN, Cheng CK, Yoshimura T. An O-tree representation of non-slicing floorplan and its applications. Mary JI, editor: New Orleans, LA, USA: Proceedings of the 36th Annual ACM/IEEE Design Automation Conference. 1999; p. 268-73.
  • Tang M, Sebastian A. Springer: A genetic algorithm for VLSI floorplanning using O-tree representation. In Applications of Evolutionary Computing. 2005; 3449:215-24.
  • Guo PN, Takahashi T, Cheng CK, Yoshimura T.Floorplanning using a tree representation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2001; 20(2):281-89.
  • Lengauer T, Muller R. Robust and accurate hierarchical floorplanning with integrated global wiring. IEEE Transactions on Computer-Aided Design. 1993; 12(6):802-9.
  • Sivaranjani P, Kumar AS. 3D VLSI Non-Slicing Floor Planning using Modified Corner List Representation.Indian Journal of Science and Technology. 2015; 8(35):1-6.
  • Lin JM, Chang YW, Lin SP. Corner sequence-a P-admissible floorplan representation with a worst case linear-time packing scheme. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2003; 11(4):679-86.
  • Dai WM, Kuh ES. Simultaneous floor planning and global routing for hierarchical building block layout.IEEE Transactions on Computer-Aided Design. 1987; 6(5):828-37.
  • Corman T, Leiserson CE, Rivest R. England: McGraw Hill: Introduction to Algorithms. 1990; p. 235.
  • Uma R, Maheswari D, Mala J. Combined Genetic and Simulated Annealing Approach for Test Case Prioritization.Indian Journal of Science and Technology. 2015 Dec; 8(35):1-30.
  • Dalfard VMD. A Simulated Annealing Algorithm for JIT Single Machine Scheduling with Preemption and Machine Idle Time. Indian Journal of Science and Technology; 2011 May; 4(5):1-7.
  • Dalfard VM. Adjustment of the Primitive Parameters of the Simulated Annealing Heuristic. Indian Journal of Science and Technology. 2011 Jun; 4(6):1-5.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.