Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Bilimsel Hesaplama Anabilim Dalı, Türkiye
Tezin Onay Tarihi: 2020
Tezin Dili: İngilizce
Öğrenci: EDA OKTAY
Asıl Danışman (Eş Danışmanlı Tezler İçin): Murat Manguoğlu
Eş Danışman: Hamdullah Yücel
Özet:Grafik temsiline sahip bilimsel problemlerin paralel çözümleri, verimli görev ve veri bölümleme gerektirir. Bu tezde, çeşitli paralel grafik bölümleme algoritmaları incelenmiştir. Bu algoritmalar hem yönlendirilmiş hem de yönsüz grafiklere uygulanabilir olsa da, bu çalışmada, matris gösterimleri seyrek ve simetrik olmayan, hesaplamalı akışkanlar dinamigi ve termal problemler gibi çeşitli uygulama alanlarını temsil eden dogrusal denklem sisteminde ortaya çıkan yönlendirilmiş duruma odaklanıyoruz. Bu çalışmada incelenen stratejiler, Çok Seviyeli Kernighan-Lin algoritmasına sahip ParMETIS, k-ortalamalı kümeleme algoritması ile birlikte kullanılan spektral bölümleme (SPEC), ve CHACO içerisinde kullanılan spektral bölümleme algoritmasıdır. PETSc ve SLEPc kitaplıkları kullanılarak C programlama dilinde SPEC algoritması uygulanmış olup, CHACO ve ParMETIS ise PETSc’den çagrılmaktadır. Grafi ğin kenar agırlıkları dikkate alınarak a ğırlıklı bölümlendirme yapılır. A ğırlıklı bölümleme ya- pıldıgında kitaplıkların sınırlamaları nedeniyle SPEC, kitaplıklarla yalnızca a ğırlıksız bölümleme yapıldıgında karşılaştırılır. Bu nedenle, ağırlıklı bölümleme için, sadece SLEPc’deki çeşitli özdeger çözücü toleransları, kenar kesme ve bölümleme süresi açı- sından incelenir. Başka bir araştırma ise MATLAB içerisinde k-ortalamalı kümeleme algoritması tarafından kullanıldıgında, özde ğer çözücü toleransına dayalı spektral bö- lümleme algoritması için yapılmıştır. Karşılaştırma, bölümlemenin kalitesine (kenar kesimi ve bölüm dengesizligi) ve yineleme sayısı cinsinden maliyete dayanmaktadır. Bir bölümlemenin kalitesi, uygulamaya baglı olarak bölümlerin kenar ve tepe denge- sizlik oranlarına baglı olabilecek yük dengesizli ğinin yanı sıra kesilen kenar sayısı ile belirlenir. Bir grafigin bitişik matrisi yapısal olarak simetrik oldu ğundan, matris si- metrik olmadıgında özde ğer problemi ancak yaklaşık olarak çözülebilir. Bu nedenle, bu çalışmada yalnızca yaklaşık sonuçlar verilmiştir. Simetrik olmayan matrislerin agırlıksız bölümlemesinde kenar kesim sayısı karşılaş- tırıldıgında, SPEC kullanımının mevcut yazılım kitaplıklarından daha iyi performans gösterdigi sonucuna varılmıştır.