A modified relay - race approach to automated floorplanning in PCB and in design

Abstract

Floorplanning is a fundamental design step in the physical design of IC and PCB, as it manages the complexity of circuit design, which is increasing with the pro gression in technology. Floorplanning optimizes the locations of the modules to reduce the circuit area and wirelength of interconnections. Therefore, floorplanning provides a base assignment for circuit layout. From the computational point of view, floorplan ning problem is an NP hard problem. The size of the search space grows exponentially with increasing number of modules. Thus, it is a very challenging task to find an op timum solution. The scope of the search space and the complexity of transformation between floorplanning representation and its corresponding floorplan are determined by the representation method. Researchers have proposed many representation meth ods such as Polish Notation, Bounded Sliced Grid (BSG), Transitive Closure Graph (TCG), B*Tree, and Sequence Pair (SP). In addition to the representation method, floorplanning algorithm is another essential factor for speed and quality of the floor planning process. There are various successful stochastic algorithms for floorplanning including Simulated Annealing (SA), Genetic Algorithm (GA), and Relay Race Algo rithm (RRA). However, there are also shortcomings of these traditional algorithms. In this thesis, a Modified Relay Race Approach (MRRA) is proposed to overcome these shortcomings. It utilizes basic methods of RRA such as rough search, focusing search, and relay. On the other hand, it uses dual path search method and better optimized parameters to improve the search ability and run time. Based on the experimental re sults utilizing MCNC benchmarks, MRRA increased the solution quality and decreased the run time of area optimization, comparing with SA, GA and RRA.