Parallel algorithms for shortest path problem on time dependent graphs
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye
Tezin Onay Tarihi: 2015
Tezin Dili: İngilizce
Öğrenci: MEHMET AKİF ERSOY
Danışman: CAN ÖZTURAN
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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.