Analysis of parallel iterative graph applications on shared memory systems

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