Analysis of parallel iterative graph applications on shared memory systems
Ortak bellekli sistemler üzerinde çalışan paralel tekrarlayan çizge uygulamalarının analizi
- Tez No: 486730
- Danışmanlar: DOÇ. ÖZCAN ÖZTÜRK
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 85
Özet
Çizge analiz uygulamaları; sosyal ağlar, proteinler arası etkileşimler, güç nakli şebekeleri, taşıma ağlar gibi birçok alana uygulanabilirlikleri sayesinde gittikçe önem kazanmıştır. Çizge veri setlerinin karmaşık ve çok çeşitli yapıda olması nedeniyle, günümüz sistemlerinin sayısal işlem yapabilme kapasitesi artsa da etkili bir çizge algoritması geliştirmek son derece zordur. Büyük çizge veri setlerini işlemek amacıyla önceden hazırlanmış yapıların ve fonksiyonların bulunduğu farklı dizayn kararları alan birçok çerçeve geliştirilmiştir. Fakat bu çerçeveler arasında en iyi tasarım seçimlerinin nasıl olacağı hakkında ortak bir karar yoktur. Bu tezde; işlemlerim uygulanma sırası, veri erişim biçimleri ve iş aktivasyonu gibi farklı tasarım kararlar göz önüne alınarak, tekrarlayan çizge uygulamalarına örnek teşkil eden üç algoritmanın çeşitli paralel geliştirmeleri sunulmuştur. Bu üç algoritma şunlardır:“PageRank”,“Tek Kaynaklı En Kısa Yollar”ve“Sığ-Öncelikli Arama”. Her bir uygulamanın, hem gerçek hem de sentetik çizge veri setleri üzerinde performans, ölçeklenebilirlik ve iş verimi analizleri yapılarak bunlar arasında nasıl bir denge kurulabileceği deneysel olarak araştırılmıştır. Milyarlarca düğüm ve bunları birbirine bağlayan çok sayıda bağıntıdan oluşan çizge veri setleri her ne kadar çok büyük olsalar da modern ortak bellekli sistemlerin bellek kapasitesine sığabilirler. Bu nedenle, bu tezde, tüm uygulamalar ortak bellekli paralel çok çekirdekli sistemler üzerinde tasarlanmıştır. Aynı zamanda donanım performans sayaçları kullanılarak ortak bellekli sistemlerin performansını sınırlayabilecek noktalar belirlemek için her bir algoritmanın mikro-donanımsal değişkenleri incelenmiştir. Sonuç olarak; bu tezde, geliştiricilerin çizge analiz uygulamaları yazarken, farklı tasarım kararları arasından etkili ve bilinçli seçimler yapabilmeleri hedeflenmiştir.
Özet (Çeviri)
Graph analytics have come to prominence due to their wide applicability to many phenomena of real world such as social networks, protein-protein interactions, power grids, transportation networks, and other domains. Despite the increase in computational capability of current systems, developing an effective graph algorithm is challenging due to the complexity and diversity of graphs. In order to process large graphs, there exist many frameworks adopting different design decisions. Nonetheless, there is no clear consensus among the frameworks on optimum design selections. In this dissertation, we provide various parallel implementations of three representative iterative graph algorithms: PageRank, Single-Source Shortest Path, and Breadth-First Search by considering different design decisions such as the order of computations, data access pattern, and work activation. We experimentally study the trade-offs between performance, scalability, work effciency of each implementation on both real-world and synthetic graphs in order to guide developers in making effective choices while implementing graph applications. Since graphs with billions of edges can fit in memory capacities of modern shared-memory systems, the applications are implemented on a shared-memory parallel/multicore machine. We also investigate the bottlenecks of each algorithm that may limit the performance of shared-memory platforms by considering the micro-architectural parameters. Finally, we give a detailed road-map for choosing design points for effcient graph processing.
Benzer Tezler
- On the analysis and evaluation of sparse hybrid linear solvers
Sparse hibrit doğrusal çözücülerinin analizi ve değerlendirilmesi
AFRAH NAJIB ABDULLAH FAREA
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. MUSTAFA SERDAR ÇELEBİ
- A parallel monolithic approach for the numerical simulation of fluid-structure interaction problems
Akışkan-yapı etkileşimi problemlerinin sayısal simülasyonu için paralel monolitik bir yöntem
ALİ EKEN
Doktora
İngilizce
2016
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HAYRİ ACAR
DOÇ. DR. MEHMET ŞAHİN
- Hibrit üç yönlü periyodik minimal yüzeyli üç boyutlu grafen yapıların mekaniği ve tasarımı
The mechanics and design of hybrid triply periodic minimal surfaces of three dimensional graphene
OSMAN FURKAN YILMAZ
Yüksek Lisans
Türkçe
2022
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. MESUT KIRCA
- Transient analysis of liquid pipeline systems
Sıvı boru hatlarında zamana bağlı akış analizi
NALAN KONCAGÜL
Yüksek Lisans
İngilizce
1996
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. OSMAN CAHİT ERALP
- Mekansal-zamansal hasta hareketlilik verileriyle mekansal etkileşim örüntülerinin analizi ve akış haritaları aracı tasarımı ve geliştirilmesi
Analysis of spatial interaction patterns using spatio temporal patient mobility data, and designing and developing a flow mapping tool
SELMAN DELİL
Doktora
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. RAHMİ NURHAN ÇELİK