Search

ÖZDOĞRULU STEİNER AĞAÇ PROBLEMİ İÇİNYAKLAŞIK SONUÇ VEREN SERİ VE PARALELALGORİTMALARCİNEL, SertaçYüksek Lisans, Elektrik ve Elektronik Mühendisliği BölümüTez Yöneticisi: Yrd. Doç. Dr. Cüneyt F. BAZLAMAÇCIAralık 2006, 127 SayfaSteiner Ağaç Problemi birçok uygulama alanı bulunan en gözde çizgeproblemlerinden biridir. Bu problemin Hanan tarafından tanımlanan doğrulu biçimi,Çok Büyük Ölçekli Tümleşik (VLSI) Bilgisayar Destekli Tasarım (CAD) işlemininfiziksel tasarım evresinde temel bir soruna çözüm olması nedeniyle özel bir ilgiçekmiştir. Doğrulu Steiner Ağaç Problemi, verilen bir nokta kümesindeki noktaları,fazladan noktalar da kullanabilerek, yalnızca yatay ve dikey doğrularla birleştirenen kısa uzunluktaki ağacı bulmaya çalışır. Problemi kesin sonuç bularak çözençeşitli algoritmalar bulunmaktadır. Ancak problem NP-tamdır ve dolayısıylaözellikle büyük nokta kümeleri için yaklaşık çözüm veren algoritmalarkullanılmalıdır. Bu tez çalışmasında öncelikle yaklaşık çözüm veren algoritmalarüzerinde inceleme yapılmış ve sonrasında yakın zamanda Kahng et. al. tarafındangeliştirilen RST ve Zhou tarafından geliştirilen BGA algoritmaları çalışılmış ve dederinlemesine incelenmiştir. Her iki algoritma da teknik yazında çoğunun kendiarka planları bulunan daha küçük problemlere bölünmüştür. BGA ve RST üzerindeyapılan analiz sonucu tez çalışmasında RST üzerine daha hızlı ve tekrarlamasız birdeğişiklik önerilmiştir. Değiştirilmiş algoritmanın verimliliği hem rasgele hem deVLSI referans örnekleri için test edilmiş ve de gösterilmiştir. Bu algoritmanındağıtık hesaplama ortamı için kısmen paralel biçimi önerilmiştir. Bu algoritma MPI( mesaj gönderim arayüzü ) altyapısı kullanılarak gerçeklenmiş ve de birbirineküme şeklinde bağlı iş istasyonları üzerinde karşılaştırmalı testler yapılmıştır.Önerilen dağıtık algoritmanın özellikle büyük problem örnekleri için umut vericiolduğu gösterilmiştir.Anahtar Kelimeler: Algoritma Analizi, Çizge Algoritmaları, Dağıtık Algoritmalar,Doğrulu Steiner Ağaç Problemi, Yaklaşık Algoritmalar ABSTRACTSEQUENTIAL AND PARALLEL HEURISTICALGORITHMS FOR THE RECTILINEAR STEINERTREE PROBLEMCİNEL, SertaçM.S., Department of Electrical and Electronics EngineeringSupervisor: Asst. Prof. Dr. Cüneyt F. BAZLAMAÇCIDecember 2006, 127 pagesThe Steiner Tree problem is one of the most popular graph problems and has manyapplication areas. The rectilinear version of this problem, introduced by Hanan, hastaken special attention since it addresses a fundamental matter in ?Physical Design?phase of the Very Large Scale Integrated (VLSI) Computer Aided Design (CAD)process. The Rectilinear Steiner Tree Problem asks for a minimum length tree thatinterconnects a given set of points by only horizontal and vertical line segments,enabling the use of extra points. There are various exact algorithms. However theproblem is NP-complete hence approximation algorithms have to be used especiallyfor large instances. In this thesis work, first a survey on heuristics for the RectilinearSteiner Tree Problem is conducted and then two recently developed successfulalgorithms, BGA by Kahng et. al. and RST by Zhou have been studied andinvestigated deeply. Both algorithms have subproblems, most of which haveindividual backgrounds in literature. After an analysis of BGA and RST, the thesisproposes a modification on RST, which leads to a faster and non-recursive version.The efficiency of the modified algorithm has been validated by computational testsusing both random and VLSI benchmark instances. A partially parallelized versionof the modified algorithm is also proposed for distributed computing environments.It is implemented using MPI (message passing interface) middleware and the resultsof comparative tests conducted on a cluster of workstations are presented. Theproposed distributed algorithm has also proved to be promising especially for largeproblem instances.Keywords: Analysis of Algorithms, Approximation Algorithms, DistributedAlgorithms, Graph Theory, Rectilinear Steiner Tree 143