Parallel mapping and circut partitioning heuristics based on mean field annealing

Abstract

Ö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 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.

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 Keywords: Mean Field Annealing, Neural Networks, Simulated Annealing, Combinatorial Optimization, Mapping Problem, Circuit Partitioning Problem, Parallel Processing, Multicomputers.