Geri Dön

Parallel maximum flow solver for multi-core machines

Çok çekirdekli mimariler için paralel en büyük akış çözücü

  1. Tez No: 270501
  2. Yazar: SELÇUK CİHAN
  3. Danışmanlar: DOÇ. DR. CAN ÖZTURAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    Türkçe

    2020

    Enerjiİstanbul Teknik Üniversitesi

    Enerji Bilim ve Teknoloji Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ SENEM ŞENTÜRK LÜLE

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

    Türkçe

    2024

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖZCAN KALENDERLİ

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

    İngilizce

    2022

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. AYDOĞAN ÖZDEMİR

    DR. ÖĞR. ÜYESİ OGUZHAN CEYLAN