A Constructive multi-way circuil partitioning algorithm based on minimum degree ordering
Minimum derece sıralamasına dayalı yapıcı çok kısımlı devre parçalama algoritması
- Tez No: 33484
- Danışmanlar: YRD. DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Devre Parçalama, Hiperçizge Parçalama, Karşıt Çizge, Minimum Derece Sıralaması, Kümeleştirilmiş Çizge, Grafik teorisi, Circuit Partitioning, Hypergraph Partitioning, Dual Graph, Mini mum Degree Ordering, Quotient Graph m, Graph theory
- Yıl: 1994
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET MINIMUM DERECE SIRALAMASINA DAYALI YAPICI ÇOK KISIMLI DEVRE PARÇALAMA ALGORİTMASI Ümit V. Çatalyürek Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Danışman: Yrd, Doç. Dr. Cevdet Aykanat Eylül, 1994 Devre parçalamanın geniş ölçekli tümleşik tasarımlarda bir çok önemli uygulaması vardır. Devre parçalama problemi en uygun şekilde hiperçizge parçalama olarak modellenebilir. Bu çalışmada, yoğunluğu çok seyrek olan simetrik matrislerin faktorizasyonunda yaratılan eleman sayısını azaltmada çokça kullanılan Minimum Derece (MD) sıralama sezgisel metodunu kullanarak yeni bir fc-kısımlı hiperçizge parçalama sezgisel algoritması öneriyoruz. Önerilen algoritma verilen hiperçizgenin karşıt çizgesi üzerinde çalışır. Önerilen algoritma karşıt çizgenin üzerinde çizge düğümlerini biraraya getirerek hiperçizgede yerel olarak minimum ağ-kesme miktarına sahip düğüm demetleri oluşturur. Algoritmanın daha hızlı çalışabilmesi için MD sıralamasında çokça kullanılan kümleştirilmiş çizge kavramı uygulanmıştır. Önerilen algoritma, bir çok standart test devrelerinde, elde edilen çözüm kalitesi açısından, Kernighan-Lin (KL) ve Simulated Annealing gibi çokça kullanılan sezgisel algoritmalardan çok daha iyi sonuçlar vermektedir. Algoritmamızın bir diğer önemli özelliği ise; daha önce önerilmiş metodların tersine, çalışma zamanının artan k değeriyle birlikte azalmasıdır. Hatta, önerilen algoritma hızlı olduğu bilinen KL-tipi algoritmalardan, k > 16 değeri için, standart test devrelerinde daha hızlı çalışmaktadır. iv
Özet (Çeviri)
ABSTRACT A CONSTRUCTIVE MULTI-WAY CIRCUIT PARTITIONING ALGORITHM BASED ON MINIMUM DEGREE ORDERING Ümit V. Çatalyürek M.S. in Computer Engineering and Information Science Advisor: Asst. Prof. Cevdet Aykanat September, 1994 Circuit partitioning has many important applications in VLSI. Circuit parti tioning problem can be most properly modeled as hypergraph partitioning. In this work, we propose a novel &-way hypergraph partitioning heuristic using the Minimum Degree (MD) ordering which is a well-known heuristic for re ducing the amount of fills in the factorization of symmetric sparse matrices. The proposed algorithm operates on the dual graph of the given hypergraph. The algorithm grows node-clusters on the dual graph which induce cell-clusters with locally minimum net-cut sizes. The quotient graph concept, widely used in MD ordering, is exploited for the sake of efficient implementation. The proposed algorithm outperforms well-known heuristics, such as Kernighan-Lin (KL) based algorithms and Simulated Annealing, in terms of solution quality on various VLSI benchmark circuits. A nice property of the proposed algo rithm is that its execution time reduces with increasing k as opposed to the existing iterative heuristics. It is even faster than the fast KL-based algorithms on the partitioning of the benchmark circuits for k > 16.
Benzer Tezler
- Küçük güçlü daimi mıknatıslı doğru akım silecek motoru tasarımı ve gerçekleştirilmesi
Başlık çevirisi yok
SERKAN ODABAŞI
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. NURDAN GÜZELBEYOĞLU
- Design and construction of an electro-rheological valve actuating system
Elektron-rheological valf ile hareketlendirilen bir sistemin dizaynı ve yapımı
EGEMEN RAMAZAN TOPÇU
Yüksek Lisans
İngilizce
1997
Makine MühendisliğiGaziantep ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SADETTİN KAPUCU
- Geniş bandlı empedans uydurucu devre tasarımı için genişletilmiş frekans bandı yaklaşımı ile çözüm
Extended frequency band approach for broad band impedance metching circuit design
ELVAN BANU SALTIK
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. OSMAN PALAMUTÇUOĞULLARI
- Günümüzde ısı değiştirici imalatında kullanılan yöntemler
The Methods that is used at fabrication of the heat exchangers
HÜSEYİN ÇEBİ
- Liderlik etkinliğinin ölçümü için bir model önerisi
Başlık çevirisi yok
ZEYNEP DİDEM DEMİRÖZLÜ
Yüksek Lisans
Türkçe
1998
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TUFAN VEHBİ KOÇ