Geri Dön

Analysis of parallel iterative graph applications on shared memory systems

Ortak bellekli sistemler üzerinde çalışan paralel tekrarlayan çizge uygulamalarının analizi

  1. Tez No: 486730
  2. Yazar: FUNDA ATİK
  3. Danışmanlar: DOÇ. ÖZCAN ÖZTÜRK
  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: 2018
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    İngilizce

    2018

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

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    PROF. DR. MUSTAFA SERDAR ÇELEBİ

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

    İngilizce

    2016

    Havacılık Mühendisliğiİstanbul Teknik Üniversitesi

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

    YRD. DOÇ. DR. HAYRİ ACAR

    DOÇ. DR. MEHMET ŞAHİN

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

    Türkçe

    2022

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MESUT KIRCA

  4. Transient analysis of liquid pipeline systems

    Sıvı boru hatlarında zamana bağlı akış analizi

    NALAN KONCAGÜL

    Yüksek Lisans

    İngilizce

    İngilizce

    1996

    Makine MühendisliğiOrta Doğu Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. OSMAN CAHİT ERALP

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

    Türkçe

    2019

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

    Bilişim Uygulamaları Ana Bilim Dalı

    PROF. DR. RAHMİ NURHAN ÇELİK