Parallel mapping and circut partitioning heuristics based on mean field annealing
Ortak alan tavlamasına dayanan paralel eşleme ve devre parçalama algoritmaları
- Tez No: 23702
- Danışmanlar: 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: Ortak Alan Tavlaması, Sinir 'Ağları, Tavlama Benzetimi, Birleşimsel Eniyileme, Eşleme Problemi, Devre Parçalama Problemi, Paralel İşleme, Çok İşlemcili Bilgisayarlar, Devre parçalama, Hiperküp algoritmalar, Orta alan tavlama yöntemi, Yapay sinir ağları, Mean Field Annealing, Neural Networks, Simulated Annealing, Combinatorial Optimization, Mapping Problem, Circuit Partitioning Problem, Parallel Processing, Multicomputers, Circuit partitioning, Hypercube algorithms, Mean field annealing method, Artificial neural networks, Multiprocessor computers
- Yıl: 1992
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET ORTAK ALAN TAVLAMASINA DAYANAN PARALEL EŞLEME VE DEVRE PARÇALAMA ALGORİTMALARI Tevfik Bultan Bilgisayar Mühendisliği ve Enformatik Bilimleri Bölümü Yüksek Lisans Tez Yöneticisi: Assoc. Prof. Cevdet Aykanat Ocak 1992 Birleşimsel eniyileme problemlerini çözmek için önerilen Ortak Alan Tavlama (OAT) algoritması, sinir ağları ve tavlama benzetimi yöntemlerinin özelliklerini taşır. Bu çalışmada, OAT algoritması eşleme ve devre parçalama problemlerine uyarlanmıştır. Önerilen algoritmaların karmaşıklığını asimtotik olarak azaltan verimli gerçekleme yöntemleri de geliştirilmiştir. Önerilen algoritmaların başaranları tavlama benzetimi ve Kernighan-Lin algoritmaları ile kıyaslıyarak değerlendirilmiştir. Elde edilen sonuçlar OAT'nin eşleme ve devre parçalama problemlerini çözmek için alternatif bir algoritma olarak kullanılabileceğini göstermektedir. Önerilen OAT algoritmaları verimli bir şekilde paralelleştirilmiştir. Devre parçalama problemi için önerilen paralel OAT algo ritmaları iPSC/2 hiperküp çok işlemcili bilgisayarında gerçeklenmiştir. Deney sel sonuçlar önerilen algoritmaların verimli bir şekilde paralelleştirilebildiklerini göstermektedir.VI
Özet (Çeviri)
ABSTRACT PARALLEL MAPPING AND CIRCUIT PARTITIONING HEURISTICS BASED ON MEAN FIELD ANNEALING Tevfik Bultan M. S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Cevdet Aykanat January 1992 Mean Field Annealing (MFA) algorithm, recently proposed for solving com binatorial optimization problems, combines the characteristics of neural net works and simulated annealing. In this thesis, MFA is formulated for the mapping problem and the circuit partitioning problem. Efficient implemen tation schemes, which decrease the complexity of the proposed algorithms by asymptotical factors, are also given. Performances of the proposed MFA algo rithms are evaluated in comparison with two well-known heuristics: simulated annealing and Kernighan-Lin. Results of the experiments indicate that MFA can be used as an alternative heuristic for the mapping problem and the cir cuit partitioning problem. Inherent parallelism of the MFA is exploited by designing efficient parallel algorithms for the proposed MFA heuristics. Paral lel MFA algorithms proposed for solving the circuit partitioning problem are implemented on an iPSC/21 hypercube multicomputer. Experimental results show that the proposed heuristics can be efficiently parallelized, which is crucial for algorithms that solve such computationally hard problems. 'iPSC/2 is a registered trademark of Intel CorporationIV
Benzer Tezler
- Graph and hypergraph partitioning
Çizge ve hiperçizge parçalama
ALİ DAŞDAN
Yüksek Lisans
İngilizce
1993
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEVDET AYKANAT
- Sahada programlanabilir kapı dizileri ile lojik devre tasarımı ve VHDL kullanılarak bazı devrelerin gerçekleştirilmesi
Başlık çevirisi yok
ATEŞ BERNA
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- Paralel işaret işleme sistemi ve bir uygulama
A Parallel signal processing system and an application
FATİH KURUGÖLLÜ
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. A. EMRE HARMANCI
- Değişken rezolüzyonlu görüntü örnekleyici
Multi resolution image sampler
RIZA CAN TARCAN
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiY.DOÇ.DR. M. SAİT TÜRKÖZ
- Bir mikrodalga transistörünün yük empedans düzleminde performans karakterizasyonu
The Performance characterization of a microwave transistor in the load impedance plane
TUNA VURAL
Yüksek Lisans
Türkçe
1999
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. FİLİZ GÜNEŞ