Parallel network flow algorithms
Paralel ağ akışı algoritmaları
- Tez No: 731042
- Danışmanlar: PROF. DR. CAN ÖZTURAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- 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ı: 117
Özet
Ağ akışı pek çok sahada uygulaması olan aktif bir araştırma alanıdır. Birçok ağ akışı problemi ya azami akış ya da asgari maliyet akışı problemine indirgenmektedir. Azami akış problemi kenarlarında akış kapasitesi olan bir ağ üzerindeki belirlenmiş iki düğüm arasında olası azami akışı belirlemek üzerinedir. Asgari maliyet problemi arz ve talep düğümleri olan bir ağ üzerinde asgari maliyetli akışı belirlemeye çalışır. Biz bu tezde azami akış ve asgari maliyet akışı problemleri için sırayla iki paralel algoritma sunduk. Birinci olarak azami akış problemi için paylaşımlı hafıza bir paralel itme-etiketleme algoritması sunuyoruz. Eş zamanlı itme ve etiketleme işlemleri için iş parçacıkları arasındaki çarpışmaları önlemek amacıyle çizge renklendirme kullanılmaktadır. Ek olarak hedef düğümlerdeki fazlalık değerleri yarışma durumlarını engellemek için atomik komutlarla güncellenmektedir. Deneyler bizim algoritmamızın geniş ve düşük çaplı ağlarda rekabetçi olduğunu göstermektedir. İkinci olarak asgari maliyet akış probleminin çözümü için ağ simpleks algoritmasının paralel bir uygulamasını sunuyoruz. Genellikle çalışma süresinin çoğunu aldığı için giriş kenarını paralel bir şekilde bulmayı öneriyoruz. Bütün kenarları taramak oldukça vakit alabilir, bu yüzden sadece sabit sayıda kenarı düşünmek yaygındır ki bu da blok arama eksen kuralı olarak adlandırılır. Hesaplamalar birbirinden bağımsız olduğundan kenar taramaları en iyi adayı bulmak için kolaylıkla paralel yapılabilir. Paylaşımlı hafıza paralellik için OpenMP ve bununla beraber vektörleştirme için AVX komutları kullandık. Ayrıca algoritmanın paralel miktarını arttırmak için blok büyüklüklerini ayarlamayı denedik. Deneyler hızlanmanın 4 kata kadar mümkün olduğunu fakat genellikle daha düşük olduğunu göstermektedir.
Özet (Çeviri)
Network flows is an active area of research that has applications in a wide variety of fields. Several network flow problems are reduced to either the maximum flow problem or the minimum cost flow problem. Maximum flow problem involves finding the maximum possible amount of flow between two designated nodes on a network with arcs having flow capacities. Minimum cost flow problem tries to determine a flow with the minimum cost on a network with supply and demand nodes. In this thesis, we propose two parallel algorithms for the maximum flow and the minimum cost flow problems respectively. First, we present a shared memory parallel push-relabel algorithm for the maximum flow problem. Graph coloring is used to avoid collisions between threads for concurrent push and relabel operations. In addition, excess values of target nodes are updated using atomic instructions to prevent race conditions. The experiments show that our algorithm is competitive for wide graphs with low diameters. Second, we contribute a parallel implementation of the network simplex algorithm that is used for the solution of minimum cost flow problem. We propose finding the entering arc in parallel as it often takes the majority of the execution time. Scanning all arcs can take quite some time, so it is common to consider only a fixed number of arcs which is referred as the block search pivoting rule. Arc scans can easily be done in parallel to find the best candidate as the calculations are independent of each other. We used shared memory parallelism using OpenMP along with vectorization using AVX instructions. We also tried adjusting block sizes to increase the parallel portion of the algorithm. Our experiments show speedups up to 4 are possible, though they are typically lower.
Benzer Tezler
- Elektrikli araçların dağıtım şebekesine etkisinin maliyet analizi ve genetik algoritma ile en iyileştirilmesi
Effects of electric vehicles on distribution network, cost analysis and optimization with genetic algorithm
HAZAL ÇİFTÇİ
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. BELGİN EMRE TÜRKAY
- Parallel maximum flow solver for multi-core machines
Çok çekirdekli mimariler için paralel en büyük akış çözücü
SELÇUK CİHAN
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CAN ÖZTURAN
- A Parallel computer hardware and software architecture for digital signal processing
Başlık çevirisi yok
HALUK GÜMÜŞKAYA
Doktora
İngilizce
1995
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT ÖRENCİK
- Parallel solution of unsteady, incompressible three-dimensional Navier-Stokes equations with a new implicit method
Zamana bağlı, sıkıştırılamaz, üç boyutlu Navier-Stokes denklemlerinin yeni bir kapalı metodlar paralel çözümü
VİLDAN ÜSTOĞLU ÜNAL
Doktora
İngilizce
2003
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiAstronomi ve Uzay Bilimleri Ana Bilim Dalı
PROF. DR. ÜLGEN GÜLÇAT
- 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