Paralel ağ akışı algoritmaları

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.