Channel and switchbox routing by simulated annealing
Tavlama benzetimi ile kanal ve anahtar kutusu izgeleme
- Tez No: 23584
- Danışmanlar: PROF. DR. ZAFER ÜNVER
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Kanal îzgeleme, Anahtar Kutusu Izgeleme, Tavfama Benzetimi, Değiştirilmiş Lee Algoritması, öğrenme Algoritmaları, Channel Routing, Switchbox Routing, Simulated Annealing, Modified Lee Algorithm, Learning Algorithms
- Yıl: 1992
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 166
Özet
ÖZ TAVLAMA BENZETİMİ ÎLE KANAL VE ANAHTAR KUTUSU 1ZGELEME AÇAN, Adnan Doktora Tezi, Elektrik ve Elektronik Mühendisliği Anabil im Dalı Tez Yöneticisi: Prof. Dr. Zafer ÜNVER Eylül, 1992, 147 sayfa. Bu çalışmada iki katmanlı kanal ve anahtar kutusu izgeleme problemleri Manhattan modeli kullanılarak incelenmiş ve bu problem¬ lerin çözümüne yönelik başarımı yüksek yeni algoritmalar geliştiril¬ miştir. Algoritmalarda eniyileme için kullanılan temel yöntem rast¬ lantısal tepe tırmanmaya dayalı ve özellikle birleşimsel eniyileme problemleri için başarımı ispatlanmış tavlama benzetimi yöntemidir. Kanal izgeleme problemine yönelik iki yeni algoritma gelişti¬ rilmiştir. Birinci algoritma dikey sınırlama çizgesini kullanarak her su yolunun bir çözüm içinde yer alabileceği yatay kanal hatları küme¬ sinin belirlenmesiyle başlar. Başlangıç biçimlenmesi her su yolunu kendisine karşı düşen yatay kanal kümesinden rastgele seçilen bir hat üzerine yerleştirmeyle belirlenir. Başlangıç biçimlenmesinin genelde içerdiği çakışmalar eniyileme süreci boyunca ortadan kaldırılırlar. Bu algoritmanın önemli özelliklerinden biri, biçimlenme uzayını tamamen izgelenmiş ancak çakışmalar içeren biçimlenmeler üzerinden çakışma içermeyen bir biçimlenme buluncaya kadar araştırmasıdır. Algoritma literatürde kanal izgelemeyle ilgili test problemlerine uygulanmış ve viher problem 1ç1n şimdiye kadar ulaşılabilmiş en küçük kanal geniş¬ liğine sahip bir çözüm makul hesaplama zamanlan içerisinde elde edilmiştir. Hesaplama zamanını düşük tutmak amacıyla sadece yatay su yolu kırılması içermeyen çözümler göz önüne alınmıştır. Kanal izgeleme ile ilgili ikinci algoritma yatay kanal hatla¬ rını teker teker ele alarak işler. Birinci yatay kanal hattından başlayarak işlenmekte olan hat üzerine konulmaya aday su yolları kümesi seçilir. Bu aday su yollarına belli ölçütler gözönüne alınarak puanlar verilir. Aday su yolları arasından aralarında çakışma olmayan ve puanları toplamı mümkün tüm seçenekler arasında en yüksek olan bir alt küme oluşturulur ve bu alt kümedeki su yolları işlenmekte olan yatay hat üzerine yerleştirilirler. Kanal izgelemeyle ilgili test problemleri yatay su yolu parçalarının kırımsız veya kırımlı olmaları dikkate alınarak çözülmüş ve her durumda şimdiye kadar ulaşılabilen en iyi kaliteye sahip çözümler elde edilmiştir. Algoritma tavlama benze¬ timi yöntemine dayalı diğer algoritmalarla karşılaştırıldığında çok daha az hesaplama zamanına ihtiyaç duymaktadır. Anahtar kutusu izgeleme problemi üzerine yönelik de başarımı yüksek iki yeni algoritma geliştirilmiştir. Birinci algoritma uyar¬ lanmış Lee algoritmasını kullanarak su yollarının ratgele izgelenme- siyle elde edilen bir başlangıç biçimlenmesiyle başlar. Başlangıç biçimlenmesinin genelde içerdiği çakışmalar eniyileme süreci boyunca toplam delik içi kaplama sayısı ve toplam su yolu uzunluğu en aza indirilecek şekilde ortadan kaldırılırlar. Algoritma biçimlenme uzayı¬ nı tamamen izgelenmiş ancak çakışmalar içeren biçimlenmeler üzerinden ve çakışma içermeyen en iyi biçimlenme bulununcaya kadar araştırır. viiAlgoritma uçların katmanlara serbest veya önceden belirlenmiş yerle¬ şimleri için kullanılabilir. Test problemleri üzerinde elde edilen çözümlerin kalitesi en az, bazı çok bilinen algoritmalar kullanılarak elde edilen çözümlerin kalitesine eşdeğerdir. Burstein'ın zor problemi gibi bazı tipik test problemleri dikkate alındığında ise, algoritma literatürdeki diğer tüm algoritmalara üstünlük sağlamaktadır. Basit bir öğrenme yöntemine dayanan ikinci algoritmada anahtar kutusu izgeleme problemi için su yollarının en iyi izgeleme sırasının bulunması problemi incelenmiştir. Bu amaçla her su yoluna izgeleme sırasının belli bir konumunda bulunmasının ne kadar iyi olduğunu gösterir bir ağırlık verilir, öğrenme süreci deneme ve kabul¬ lenmeye dayanır; su yolları için bir izgeleme sırası seçilir, uyar¬ lanmış Lee algoritması kullanılarak su yolları bu sırada izgelenir, ve her su yoluna ait ağırlık çakışma sayısının azlığını ödüllendirecek şekilde ayarlanır. Algoritma bazı önemli anahtar kutusu izgeleme problemlerini başarıyla çözerken bazılarında ise az sayıda çakışma içeren sonuçlar vermektedir. Çakışma içeren sonuçların ilk algoritma için başlangıç biçimlenmesi olarak kullanılmasıyla çakışmalar hızlıca kaldırılabilirler. Her iki durumda da ilk algoritmanın doğrudan kulla¬ nılmasına kıyasla hesaplama zamanı önemli miktarlarda düşürülmektedir.
Özet (Çeviri)
ABSTRACT CHANNEL AND SWITCHBOX ROUTING BY SIMULATED ANNEALING AÇAN, Adnan Ph. D. in Electrical & Electronic Engineering Supervisor: Prof. Dr. Zafer ÜNVER September, 1992, 147 pages. In this study, two layer channel and switchbox routing prob lems in the Manhattan model are examined and efficient new algorithms are developed for their solutions. The basic optimization tool used in these algorithms is the simulated annealing method which is based on probabilistic hill climbing and proved to be successful for global optimization, especially for the combinatorial optimization problems. Two algorithms are developed for the channel routing problem. The first algorithm starts with determining the set of tracks, one for each net, to which nets can be assigned in a solution, by using the vertical constraint graph. An initial configuration is obtained by assigning each net to a randomly selected track from the correspond ing track set. This initial configuration contains a number of over laps, in general, which are removed during the optimization process. An important feature of this algorithm is that it searches the con figuration space over completely routed but unfeasible configurations until a feasible configuration, that is a solution, is found. The algorithm is applied for the solution of all the benchmark channel mrouting problems 1n literature and the solutions with the least attainable channel widths are obtained for all problems in reasonable amounts of computation times. Only the solutions with no doglegs are considered because of the computation time requirements. The second algorithm operates in a track by track manner. Starting with the track number one, first the set of all nets that can be assigned to the current track being processed is chosen. These candidate nets are given scores according to several criteria. Secondly, a subset of nonoverlapping candidate nets to be assigned to the current track is formed in such a way that the algebraic sum of net scores in this subset is maximum among all possible selections. The benchmark channel routing problems are handled either with or without doglegs and the solutions with the best attainable qualities are obtained for all cases. The computation times are much shorter when compared to the other algorithms using the SA method. Two efficient algorithms are developed for the solution of switchbox routing problem. The first algorithm starts with an initial configuration obtained by routing the nets in a random order using the modified Lee algorithm. This initial configuration contains, in general, a number of overlaps which are removed while minimizing the number of vias and the total path length during the optimization process. The configuration space is searched over completely routed but unfeasible configurations until an optimal feasible configuration is found. The algorithm can be used with terminal placements in mixed or reserved layer modes. The resulting solutions are at least of the same quality when compared to the ones obtained by the other well- ivknown algorithms. The algorithm outperformes ali the other algorithms 1n literatüre in solvlng some typical sw1tchbox routing problems such as the Bursteln's dlfflcult problem. in the second algorithm wh1ch is based on a simple learning method, the problem of finding an optlmal routing order of nets för a given switchbox routing problem is examined. A net is assigned a weight indicating how good it is to put the net in a particular posltion in the routing order. The process of learning is by trlal and adoption: select an ordering of nets, route the nets in this order using the modified Lee algorithm, and modlfy the weights of nets so as to favor a lower overlap count. The algorithm succesfully routes some important benchmark switchbox problems while the sol ut1ons för some other problems end up with a small number of overlaps. in case of fallure, taking the configuration with overlaps as the initial con- figuration the first algorithm is used which qu1ckly removes the overlaps. in both cases the total computation times decrease in large amounts as compared to the ones required when the first algorithm is used directly.
Benzer Tezler
- Öngerilmeli betonarme köprü kirişinin aktarma süresince deneysel olarak izlenmesi
Başlık çevirisi yok
EKREM BÜLENT KIRCA
Yüksek Lisans
Türkçe
1998
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN BODUROĞLU
- Pilot sembolleri kullanarak kanal kestirimi ve kapasite hesaplaması : Sonlu blok durumu
Channel estimation and capacity calculation using pilot symbols : Finite frame case
UMUT SUPHİ ŞENER
Yüksek Lisans
Türkçe
2007
Elektrik ve Elektronik MühendisliğiHacettepe ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. EMRE AKTAŞ
- Petrol arama çalışmalarında yeraltı telsiz duyarga ağları için kanal modelleme
Channel modelling for wireless underground sensor network used in oil recovery
MUSTAFA ALPER AKKAŞ
Doktora
Türkçe
2014
Elektrik ve Elektronik MühendisliğiEge ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. RADOSVETA SOKULLU
- Taşıtlar arası haberleşme sistemlerinin modellenmesi ve kanal takibi
Modelling and channel tracking on vehicular communication systems
KANİ EREN
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN ALİ ÇIRPAN
- Tekirdağ havzası yüksek çözünürlüklü sismik yansıma verilerinin işlenmesi ve yorumlanması
Processing and interpreting high resolutioned seismic reflection datas of the Tekirdag basin
EMRE PERİNÇEK
Yüksek Lisans
Türkçe
2011
Jeofizik Mühendisliğiİstanbul Teknik ÜniversitesiJeofizik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HÜLYA KURT