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: Belirtilmemiş.
- 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ı: 71
Ö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
- Akışkan yatak kurutma sisteminde hesaplamalı akış dinamiği analizleri
Computational fluid dynamics analysis for a fluidized bed dryer system
ALPER DOĞAN
Yüksek Lisans
Türkçe
2020
Enerjiİstanbul Teknik ÜniversitesiEnerji Bilim ve Teknoloji Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SENEM ŞENTÜRK LÜLE
- Yüksek gerilim yeraltı kablo sistemlerinde tasarım parametrelerinin elektriksel ve termal performansa etkisinin sonlu elemanlar yöntemi ile incelenmesi
Investigation of the effect of design parameters on electrical and thermal performance in high-voltage underground cable systems with fem
YUNUS BERAT DEMİROL
Yüksek Lisans
Türkçe
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZCAN KALENDERLİ
- Near field investigation of borehole heat exchangers
Başlık çevirisi yok
SELÇUK EROL
Doktora
İngilizce
2016
MimarlıkUniversité libre de Bruxelles (École polytechnique de Bruxelles)Prof. BERTRAND FRANCOIS
- Parallel evolutionary computation for distribution system planning and operation
Dağıtım şebekesi planlama ve işletmesi için paralel evrimsel algoritmalar
SOHEIL YOUNESI
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYDOĞAN ÖZDEMİR
DR. ÖĞR. ÜYESİ OGUZHAN CEYLAN