Parallel maze routing algorithms on a hypercube multicomputer

Abstract

ÖZET HİPERKÜP ÇOK İŞLEMCİLİ BİLGİSAYARINDA PARALEL LABİRENT YOL BELİRLEME ALGORİTMALARI Tahsin Mertefe Kurç Bilgisayar Mühendisliği ve Enformatik Bilimleri Bölümü Yüksek Lisans Tez Yöneticisi: Doçent Dr. Cevdet Aykanat Kasım, 1991 Tümdevre tasarımında, devre bağlantılarının yapılması zaman alan bir iştir. Burada amaç bütün devre bağlantılarını en kısa yolları kullanarak yapmaktır. Eğer, her seferinde bir devre grubunun bağlantısı yapılırsa bunun adına labirent yol belirleme yöntemi denir. Bu yöntem için, hüristik algoritmalar vardır. Ancak, bu tip algoritmalar devre bağlantılarına getirdikleri kısıtlamalardan dolayı, bazen var olan bağlantıları bulamazlar. Bu yüzden, devrelerin bulunduğu alanın, tümden taranması gereke bilir. Lee'nin algoritması ve Lee benzeri algoritmalar bu tip algoritmalardır. Lee'nin algoritması ve Lee benzeri algoritmalar hesaplama bakımından pahalı ve devre yüzeyi için çok bilgisayar hafızası gerektiren algoritmalardır. Bu nedenle bu tip algoritmalar çok işlemcili bilgisayarlarda, paralel olarak çözmek için uygundur. Bu çalışmada, Lee benzeri labirent yol bulma algoritmalarının, hiperküp çok işlemcili bilgisayarında paralelleştirilmesi anlatılmaktadır.VI Anahtar kelimeler : Tümdevre tasarımı, labirent yol bulma yöntemi, Lee'nin labirent 3'ol bulma algoritması, Lee benzeri labirent algoritmaları, çok işlemcili bilgisayar, hiperküp topolojisi.

ABSTRACT PARALLEL MAZE ROUTING ALGORITHMS ON A HYPERCUBE MULTICOMPUTER Tahsin Mertefe Kurç M. S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Dr. Cevdet Aykanat November, 1991 Global routing phase is a time consuming task in VLSI layout. In global routing phase of the layout problem, the overall objective is to realize all the net interconnections using shortest paths. Efficient heuristics are used, for the global routing phase. However, due to the assumptions and constraints they impose, heuristics may fail to find a path for a net even if one exists. Re-routing is required for such nets. This re-routing phase requires the exhaustive search of the wiring area. Lee's maze routing algorithm and Lee type maze routing algorithms are exhaustive search algorithms used in re-routing phase. These algorithms are computationally expensive algorithms and consume large amounts of computer time for large grid sizes. Hence, these algorithms are good candidates for parallelization. Also, these algorithms require large memory space to hold the wiring grid. Therefore, the effective paralleliza tion of these algorithms require the partitioning of the computations and the grid among the processors. Hence, these algorithms can be parallelized on distributees-memory message passing multiprocessors (multicomputers).IV In this work, efficient parallel Lee type maze routing algorithms are devel oped for hypercube-connected multicomputers. These algorithms are imple mented on an Intel's iPSC/2 hypercube multicomputer. Keywords: VLSI layout, maze routing, Lee's maze routing algorithm, Lee type maze routing algorithms, multicomputer, hypercube topology.