A Constructive multi-way circuil partitioning algorithm based on minimum degree ordering

Abstract

Ö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. ivAnahtar Sözcükler: Devre Parçalama, Hiperçizge Parçalama, Karşıt Çizge, Minimum Derece Sıralaması, Kümeleştirilmiş Çizge

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. Keywords: Circuit Partitioning, Hypergraph Partitioning, Dual Graph, Mini mum Degree Ordering, Quotient Graph m