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, Circuit Partitioning, Hypergraph Partitioning, Dual Graph, Mini mum Degree Ordering, Quotient Graph m
- Yıl: 1994
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar ve Enformatik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 65
Ö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
- Multi-purpose reconfigurable impedance matching network designs and antenna applications
Çok amaçlı ayarlanabilir empedans uyumlama devresi tasarımları ve anten uygulamaları
EVREN UYSAL
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. METİN YAZGI
DOÇ. DR. TAYFUN NESİMOĞLU
- Havlu dokuma makinalarında optimum çözgü gerginliği ve havlu kumaşlar üzerine etkisi
The optimum warp tension on terry loom and its effect on pile fabrics
SEMİH DEMİRAL
Yüksek Lisans
Türkçe
2008
Tekstil ve Tekstil MühendisliğiPamukkale ÜniversitesiMühendislik Bilimleri Bölümü
YRD. DOÇ. DR. GÜNGÖR DURUR
- Dağıtık üretim kaynağı içeren elektrik dağıtım sistemlerinde görünmeyen hataların koruma koordinasyonu üzerindeki etkileri
Impacts of hidden failures on protection coordination in electrical distribution systems with distributed generation
MUSTAFA SELİM SEZGİN
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA BAĞRIYANIK