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

Abstract

Yerleşim planlaması, teknolojideki ilerlemelerle birlikte artan devre tasarımı zorluğunu yöneterek, IC ve PCB fiziksel tasarımlarında temel bir tasarım adımını temsil etmektedir. Yerleşim planlaması, devrenin alanını ve modüller arasındaki bağlantıların toplam uzunluğunu azaltmak için modüllerin yerlerini optimize etmektedir. Bu nedenle yerleşim planlaması, devre yerleşimi için bir zemin hazırlamaktadır. Arama uzayının boyutu, modüllerin sayısındaki artış ile birlikte katlanarak büyümektedir. Yerleşim planlaması gösterimi ile bu gösterime karşılık gelen yerleşim planı arasındaki dönüşümün karmaşıklığı gösterim yöntemi ile belirlenmektedir. Araştırmacılar, Polish Notation, Bounded Slicing Grid (BSG), Transitive Closure Graph (TCG), B*Tree ve Sequence Pair (SP) gibi birçok gösterim yöntemini önermişlerdir. Yerleşim planlaması algoritması, yerleşim planı sürecinin hızı ve kalitesi için bir başka önemli faktördür. Simulated Annealing (SA), Genetic Algorithm (GA) ve Relay Race Algorithm (RRA), yerleşim planı problemi için araştırmacılar tarafından kullanılan en popüler stokastik algoritmalar arasında bulunmaktadır. Fakat bu geleneksel algoritmaların da eksiklikleri bulunmaktadır. Bu tezde, bu algoritmaların eksikliklerinin üstesinden gelmek için Modified Relay Race Approach (MRRA) önerilmektedir. RRA tarafından kullanılan kaba arama, detaylı arama ve mutasyon gibi yöntemler, MRRA tarafından da kullanılmaktadır. Öte yandan MRRA, arama yeteneğini ve hesaplama süresini geliştirmek için çift yönlü arama yöntemini ve daha iyi optimize edilmiş parametre değerlerini kullanmaktadır. MRRA, MCNC kriterleri kullanılarak yapılan deneylerin sonuçları göz önünde bulundurulduğunda SA, GA ve RRA yaklaşımlarına göre alan optimizasyonuna ait çözüm kalitesini arttırırken hesaplama süresini de azaltmaktadır.

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 progression 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, floorplanning 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 optimum 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 methods 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 floorplanning process. There are various successful stochastic algorithms for floorplanning including Simulated Annealing (SA), Genetic Algorithm (GA), and Relay Race Algorithm (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 results utilizing MCNC benchmarks, MRRA increased the solution quality and decreased the run time of area optimization, comparing with SA, GA and RRA.