A modified relay-race algorithm for floorplanning in PCB and IC design

Abstract

Floorplanning is a fundamental design step in the physical design of printed circuit boards (PCBs) andintegrated circuits (ICs), as it handles the complexity of layout design. From a computational point of view, thefloorplanning problem is an NP hard problem, and the size of the search space grows exponentially with increasingnumbers of modules. Thus, the algorithm used is an essential factor for speed and quality of the floorplanningprocess. Although polynomial-time floorplanning algorithms can be implemented when solution space is limited toslicing floorplans, optimal solutions often exist only in the nonslicing floorplan search space. Various stochastic algorithmssuch as simulated annealing (SA), the genetic algorithm (GA), and the relay race algorithm (RRA) can be used withnonslicing floorplans. In this paper, a modified relay race algorithm (MRRA) is proposed. Based on the experimentalresults utilizing MCNC benchmarks, MRRA improved both solution quality and run time for area optimization whencompared with SA, GA, and RRA.