Mopping and FPGA global routing using mean field annealing

Abstract

ÖZET ORTA ALAN TAVLAMA METODU KULLANILARAK EŞLEME VE FPGA'LERDEKİ KABA ROTALAMA PROBLEMLERİNİN ÇÖZÜMÜ İsmail Haritaoğlu Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Danışman: Yrd. Doç. Dr. Cevdet Aykanat Eylül, 1994 Birleşimsel eniyileme problemlerini çözmek için önerilen Ortak Alan Tavlama (Mean Field Annealing) algoritması, sinir ağları ve benzetimsel tavlama (Sim ulated Annealing) yöntemlerinin özelliklerini taşır. Bu çalışmada, Ortak Alan Tavlama algoritması Alan Programlamalı Kapı Devrelerinin (Field Pro grammable Gate Arrays) kaba rotalama problemine (Global Routing) ve par alel programlamadaki eşleme (Mapping) problemlerine uyarlanmıştır. Tezin ilk bölümünde Ortak Alan Tavlama algoritması Alan Programlamalı Kapı Devrelerinin (Field Programmable Gate Arrays) kaba rotalama problemi- ninin çözümünde kullanılmıştır. Önerilen algoritmalarının başarımları Locus- Route kaba rotalama algoritması ile kıyaslanarak değerlendirilmiştir. Deneyler algoritmaları karşılaştırmak için kullanılan standart devreler (Benchmarks) üzerinde yapılmıştır. Elde edilen sonuçlar Ortak Alan Tavlama algoritmasının kaba rotalama problemini çözmek için iyi bir alternatif algoritma olarak kul lanılabileceğini göstermektedir. Tezin ikinci bölümünde Mesh ve Hiperküp tipindeki paralel bilgisayarlarındaki eşleme problemi için daha önce önerilen algoritmalardan daha hızlı olan bir algoritma geliştirilmiş ve bu önerilen algorit manın başarımları Kernighan-Lin, Simulated Annealing ve daha önce önerilen ortak alan tavlama metotları ile kıyaslanarak değerlendirilmiştir. Anahtar Sözcükler: Orta Alan tavlama algoritması, Eşleme problemi, Kaba rotalama algoritmaları, Alan programlamh kapı devreleri iv

Mean Field Annealing algorithm which was proposed for solving combinatorial optimization problems combines the properties of neural networks and Simu lated Annealing. In this thesis, MFA is formulated for mapping problem in parallel processing and global routing problem in physical design automation of Field Programmable Gate Array (FPGAs) A new Mean Field Annealing (MFA) formulation is proposed for the mapping problem for mesh-connected and hypercube architectures. The proposed MFA heuristic exploits the conven tional routing scheme used in mesh and hypercube interconnection topologies to introduce an efficient encoding scheme. An efficient implementation scheme which decreases the complexity of the proposed algorithm by asymptotical fac tors is also developed. Experimental results also show that the proposed MFA heuristic approaches the speed performance of the fast Kernighan-Lin heuris tic while approaching the solution quality of the powerful simulated annealing heuristic. Also, we propose an order-independent global routing algorithm for SRAM type FPGAs based on Mean Field Annealing. The performance of the proposed global routing algorithm is evaluated in comparison with LocusRoute global router on ACM/SIGDA Design Automation benchmarks. Experimen tal results indicate that the proposed MFA heuristic performs better than the LocusRoute. iiiKeywords: Mapping, Global Routing, Field Programmable Gate Arrays, Mean Field Annealing