A modified relay-race algorithm for floorplanning in PCB and IC design
Floorplanning is a fundamental design step in the physical design of printed circuit boards PCBs and integrated circuits ICs , as it handles the complexity of layout design. From a computational point of view, the floorplanning problem is an NP hard problem, and the size of the search space grows exponentially with increasing numbers of modules. Thus, the algorithm used is an essential factor for speed and quality of the floorplanning process. Although polynomial-time floorplanning algorithms can be implemented when solution space is limited to slicing floorplans, optimal solutions often exist only in the nonslicing floorplan search space. Various stochastic algorithms such as simulated annealing SA , the genetic algorithm GA , and the relay race algorithm RRA can be used with nonslicing floorplans. In this paper, a modified relay race algorithm MRRA is proposed. Based on the experimental results utilizing MCNC benchmarks, MRRA improved both solution quality and run time for area optimization when compared with SA, GA, and RRA.
Keywords:
Placement, floorplanning, CAD VLSI, printed circuit board,
___
- [1] Singh RB, Baghel AS, Agarwal A. A review on VLSI floorplanning optimization using metaheuristic algorithms. In: 2016 International Conference on Electrical, Electronics, and Optimization Techniques; Tamil Nadu, India; 2016. pp. 4198-4202.
- [2] Banerjee S, Ratna A, Roy S. Satisfiability modulo theory based methodology for floorplanning in VLSI circuits. In: 2016 Sixth International Symposium on Embedded Computing and System Design; Patna, India; 2016. p. 91-95.
- [3] Laskar NM, Sen R, Paul PK, Baishnab KL. A survey on VLSI floorplanning: its representation and modern approaches of optimization. In: 2015 International Conference on Innovations in Information, Embedded and Communication Systems; Coimbatore, India; 2015. p. 1-9.
- [4] Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science 1983; 220 (4598): 671–680.
- [5] Wong DF, Liu CL. A new algorithm for floorplan design. In: 23rd ACM/IEEE Design Automation Conference; Las Vegas, NV, USA; 1986. pp. 101–107.
- [6] Rebaudengo M, Reorda MS. GALLO: A genetic algorithm for floorplan area optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 1996; 15 (8): 943–951.
- [7] Sheng Y, Takahashi A, Ueno S. Relay-race algorithm: a novel heuristic approach to VLSI/PCB placement. In: 2011 IEEE Computer Society Annual Symposium on VLSI; Chennai, India; 2011. pp. 96-101.
- [8] Moni DJ. Certain optimization techniques for floorplanning in VLSI physical design. PhD, Anna University, Guindy, India, 2009.
- [9] Murata H, Fujiyoshi K, Nakatake S, Kajitani Y. VLSI module placement based on rectangle-packing by the sequencepair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 1996; 15 (12): 1518–1524.
- [10] Ray BNB, Tripathy AR, Samal P, Das M, Mallik P. Half-perimeter wirelength model for VLSI analytical placement. In: 2014 International Conference on Information Technology; Bhubaneswar, India; 2014. pp. 287–292.
- [11] Otten R. Efficient floorplan optimization. In: International Conference on Computer Design; Port Chester, NY, USA; 1983. pp. 499-502.
- [12] Nakaya S, Koide T, Wakabayashi S. An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair. In: 2000 IEEE International Symposium on Circuits and Systems, Emerging Technologies for the 21st Century; Geneva, Switzerland; 2000. pp. 65–68.
- [13] Lin CT, Chen DS, Wang YW. An efficient genetic algorithm for slicing floorplan area optimization. In: 2002 IEEE International Symposium on Circuits and Systems; Phoenix-Scottsdale, AZ, USA; 2002. pp. I-II.
- [14] Gwee BH, Lim MH. A GA with heuristic-based decoder for IC floorplanning. Integration 1999; 28 (2): 157-172.
- [15] Drakidis A, Mack RJ, Massara RE. Packing-based VLSI module placement using genetic algorithm with sequencepair representation. IEE Proceedings - Circuits, Devices and Systems 2006; 153 (6): 545–551.
- ISSN: 1300-0632
- Yayın Aralığı: Yılda 6 Sayı
- Yayıncı: TÜBİTAK