Parallel maximum flow solver for multi-core machines
Çok çekirdekli mimariler için paralel en büyük akış çözücü
- Tez No: 270501
- Danışmanlar: DOÇ. DR. CAN ÖZTURAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Grafik teorisi, Paralel algoritmalar, Paralel hesaplama, Graph theory, Parallel algorithms, Parallel computing
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Sığalı ağlarda, iki düğüm arasındaki en büyük akışı hesaplayacak, paralel bir algoritma sunuyoruz. Algoritmamız, Goldberg'in itele-tekrar-etiketle (push-relabel) algoritması temel alınarak geliştirilmiştir. Etkin düğüm seçimi için, paralel yürütülmeye uygun, değiştirilmiş bir“ilk giren ilk çıkar”(FIFO) yöntemi kullanılmaktadır. Algoritmamız, pratikte oldukça hız kazandıran global-tekrar-etiketleme (global relabeling) buluşsal (heuristic) yöntemini kullanmaktadır. Çok çekirdekli işlemcileri hedefleyen algoritmamız, görev çalma yöntemi ile, iş yükünü farklı iş parçacıklarına dağıtmaktadır. Çekirdeklerin ortak kullandığı belleğe erişimin senkronizasyonu için, hesaplama açısından pahalı genel amaçlı kilitler yerine, hızlı atomik (atomic) değişkenler kullanılmıştır. Algoritmamızı itele-tekrar-etiketle tabanlı seri algoirtmalar ile karşılaştırdık ve başarımının iyi olduğunu gösterdik.
Özet (Çeviri)
We provide a parallel algorithm for calculating maximum flow between two nodes, in a capacitated network. The algorithm we propose is based on push-relabel algorithm due to Goldberg and uses a modified first in first out selection strategy together with global relabeling heuristic. Our implementation targets multi-core processors, implements task stealing to balance load between multiple threads of execution and uses fast atomic variables for synchronization instead of costly general purpose locks. We compare our algorithm to other push-relabel based algorithms and demonstrate that it performs well in practice.
Benzer Tezler
- Büyük boyutlu şebekelerin diakoptics yöntemi ile kısa devre analizi
Başlık çevirisi yok
ÖMER GÜL
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. ADNAN KAYPMAZ
- İzmir'de Mustafa Kemal Bulvarı'nın peyzaj mimarlığı açısından etüdü ve peyzaj projesi
Başlık çevirisi yok
ENGİN ALPARSLAN
Yüksek Lisans
Türkçe
1985
Peyzaj MimarlığıEge ÜniversitesiPeyzaj Mimarlığı Ana Bilim Dalı
YRD. DOÇ. DR. ÜMİT ERDEM
- Çocuklarda akut stres hiperglisemisinde hormonal değişikliklerin ve kısa süreli prognozun incelenmesi
Başlık çevirisi yok
AYGÜN DİNDAR
Tıpta Uzmanlık
Türkçe
1987
Çocuk Sağlığı ve Hastalıklarıİstanbul ÜniversitesiÇocuk Sağlığı ve Hastalıkları Hemşireliği Ana Bilim Dalı
DOÇ. DR. HÜLYA GÜNÖZ
- Değişik derim zamanı ve önsoğutmanın Bursa siyahı incir çeşidinin meyve kalitesi ve pazarlama süresi üzerine etkileri
Effects of haruest time and precooling on fruit quality and shelf-life of the fig variety“Bursa siyahı”
FÜSUN GÜRSEL ÇELİKEL
- Dislokasyon-dislokasyon etkileşimi
Başlık çevirisi yok
YILDIRIM AYDOĞDU
Yüksek Lisans
Türkçe
1987
Fizik ve Fizik Mühendisliğiİnönü ÜniversitesiFizik Ana Bilim Dalı
Y.DOÇ.DR. MUSTAFA DİKİCİ