Greedy algorithms for distance-2 graph coloring and bipartite graph partial coloring

oşut bir uygulamanın görev etkileşim çizgesi komşu görevlerin farklı renklerle boyandığında birbirleri ile aynı renkteki görevler aynı anda pahalı bir senkronizasyon veri yapısı kullanılmadan aynı anda çalıştırılabilmektedir. Bu tür bir çalıştırmada bir renkteki görevler bitirilmeden, başka bir renkteki görev koşut halde şlenemeyeceğinden boyama esnasında kullanılan renk sayısı koşut uygulamanın çalıştırılması esnasında karşılaşılacak senkronizasyon adım sayısını belirtmektedir. Literatürde çizge boyama problemi ''bir çizgeyi mümkün olan en az sayıda renk kullanarak komşu noktalara farklı renkler vermek'' olarak tanımlanmıştır ve bir optimizasyon problemi olarak görüldüğünde NP-Hard sınıfındadır. Çizge boyama probleminin farklı çeşitleri de paralel hesaplama, özellikle paralel bilimsel hesaplama alanında önemlidir. Problemin yukarıda bahsedilen basit halinde 1-uzaklık kullanılırken, k-uzaklık tanımı da özellikle k = 2 için pratikte kullanılmaktadır. Bu tezde de bu problem üzerine yoğunlaşılmıştır. Problemin genel hali ''bir çizgeyi mümkün olan en az sayıda renk kullanarak birbirinden k ve daha az uzaklıktaki nokta ikililerine farklı renkler vermek'' olarak tanımlanabilir. Literatürde bu problem için az renk kullanan buluşsal yöntemler önerilmiştir ve bu yöntemler k = 1 için oldukça hızlıdır. Fakat k = 2 için özellikle büyük çizgelerde bu buluşsal yöntemler dakikalar mertebesinde zaman alabilmektedirler. Çizge boyamanın bir uygulamanın çalışması için sadece bir ön işlem olduğu düşünüldüğünde bu işlemin getirdiği ekstra zamanın mümkün olduğu kadar az olması işlemin uygulanabilirliği için önemlidir. Bu tezde 2-uzaklık çizge boyama ve bu problemin farklı bir türü olan iki parçalı çizge boyama problemleri için iyimser ve açgözlü buluşsal yöntemler önerilmiştir. Bu yöntemler çok çekirdekli işlemcilerde ve Grafik İşleme Ünitelerinde koşut olarak gerçeklenmiş, ve ölçeklenebilirlikleri analiz edilmiştir. Yapılan deneylerde önerilen yöntemlerin ölçeklenebilir ve 16 çekirdek kullanıldığında literatürdeki yöntemlerden ortalama 25 kat hızlı oldukları görülmüş, özellikle sosyal ağ karakteri taşıyan çizgeler için büyük performans artışı sağladığı saptanmıştır. Yine bu tez çerçevesinde aynı renge sahip nokta kümelerinin eleman sayılarının birbirine yakın olması üzerine de çalışılmıştır. Bu tür dengeli dağılımlı bir boyama, uygulamanın çok çekirdekli işlemciler ve özellikle GİÜ'ler üzerinde çalışması esnasında her senkronizasyon adımında bütün çekirdekleri doyuracak kadar iş yükü olmasını sağlayacağından yüksek performans için önemli olabilmektedir. Bu tezde neredeyse hiç ekstra külfet getirmeden bunu sağlayabilecek iki yöntem önerilmiştir. Yapılan deneylerde bu yöntemlerin başarılı olduğu sonucuna varılmıştır.