Geri Dön

Parallel algorithms for shortest path problem on time dependent graphs

Zamana bağımlı çizgelerde en kısa yol problemi için paralel algoritmalar

  1. Tez No: 433931
  2. Yazar: MEHMET AKİF ERSOY
  3. Danışmanlar: PROF. 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: 2015
  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ı: 75

Özet

Zamana bağımlı çizgeler için en kısa yol problemi son yıllarda oldukça popülerleşti. Akıllı telefonlar hayatımızın ayrılamaz bir parçası olduğundan beri, bu telefonlardaki uygulamalar insan hayatını kolaylaştıran birçok olanak sağlıyor. Navigasyon uygulamaları da bunlardan biridir. Son teknoloji ürünü olan yer bulma uygulamaları harita verisinin yanında gerçek zamanlı trafik verilerinden de yararlanmaktadırlar. Dolayısıyla, en kısa yol problemini gerçek zamanlı verilerde, yani zamanla değişen çizgelerde çözmek artık bir gereklilik olmuştur. Zamana bağımlı çizgelerde en kısa yol problemi için literatürde çeşitli ardışıl algoritmalar bulunmaktadır. Ancak, bu algoritmalar genellikle iki problemin sıkıntısını çekmektedirler: yürütüm sürelerinin uzun olması veya çok fazla bellek gereksinimi. Önceden sunulan algoritmalardaki bu problemler, onların, gerçek zamanlı verilerle çalışan ve hızlı yanıt sürelerine ihtiyaç duyan dolaşım uygulamalarında kullanılmasını mümkün kılmamaktadır. Zamana bağımlı akış hızı modeli içeren en kısa yol seri algoritmasının, çok daha fazla bellek gerektirmeden, yürütüm süresinin hızlandırılması için“Değiştirilmiş Dijkstra”algoritmasını temel alarak paralel algoritmalar öneriyoruz. Cuda ve OpenMP kullanarak 3 farklı paralel gerçekleştirme geliştirdik: Bunlar (i) Cuda tabanlı uyarlama, (ii) OpenMP tabanlı uyarlama ve (iii) Cuda ve OpenMP tabanlı karma uyarlama. OpenMP uyarlamasında 10 kat, diğer uyarlamalarda da 17 kat hızlanma elde edilmiştir.

Özet (Çeviri)

Shortest path problem in time dependent graphs has become a popular problem in recent years. Ever since the smart phones became an inseparable part of our lives, the applications on those devices started to provide many functionalities which make human life much easier. Navigation applications are one of them. State of the art navigation applications benefit from real time traffic data besides the map data. Therefore, it becomes a necessity to solve the problem of shortest path with real time data, i.e., on time dependent graphs. Various sequential algorithms for the shortest path problem in time dependent graphs are appearing in the literature. However, these algorithms mostly suffer from the following two problems: long running times or huge memory requirements. These problems of the previously proposed algorithms are making them unsuitable for navigation applications which run on real time data and which need fast response times. In order to speed-up the running time of the sequential algorithm, without requiring much more memory, for shortest path problem with time dependent flow speed model, we propose parallel algorithms based on Modified Dijkstra algorithm. We develop three different parallel implementations by using Cuda and OpenMP: These are (i) a Cuda based version, (ii) an OpenMP based version and (iii) a hybrid Cuda and OpenMP based version. We get up to 10-fold speedup in the OpenMP version, and 17-fold speed up in the other two versions.

Benzer Tezler

  1. Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar

    New methods and algorithms for solving the resource-constrained project scheduling problem

    İHSAN UĞUR

    Doktora

    Türkçe

    Türkçe

    1987

    İşletmeİstanbul Teknik Üniversitesi

    PROF.DR. ATAÇ SOYSAL

  2. Optimal ship navigation and algorithms for stochastic obstacle scenes

    Optimal gemi navigasyonu ve stokastik engelli ortamlar için algoritmalar

    İBRAHİM ARI

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri Mühendisliğiİstanbul Şehir Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. VURAL AKSAKALLI

  3. Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi

    A column generation strategy for large scale airline crew pairing problems

    BAHADIR ZEREN

    Doktora

    Türkçe

    Türkçe

    2017

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    PROF. DR. İBRAHİM OZKOL

  4. Traffic and mobility aware delay modeling for software-defined networks (SDN)

    Yazılım tanımlı ağlar için trafik ve hareket duyarlı gecikme modeli

    MÜGE ÖZÇEVİK

    Doktora

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BERK CANBERK