Latency-centric models and methods for scaling sparse operations

Seyrek çekirdeklerin ve işlemlerin büyük-ölçekli dağıtık bellekli sistemlerde paralelizasyonu modern yüksek performanslı hesaplama sistemlerinin sürekli artan ölçekleri ve paralel performansı etkileyen birbiriyle çakışan birçok etmenin varlığı nedenleriyle büyük bir zorluk olarak kalmaktadır. Seyrek işlemlerin düşük hesaplama yoğunlukları ve yüksek bellek izleri daha fazla vurgulanan iletişim darboğazlarını işaret ederek bu zorluklara yenilerini eklemekte ve ölçeklenebilir performans için hızlı ve verimli paralelizasyon model ve metotlarını zorunlu kılmaktadır. Seyrek işlemler genelde seyrek matrislerle ilgili veri yapıları üzerinde gerçekleştirilmekte ve matrisler koşma öncesinde işlemcilere dağıtılmak için bölümlenmektedir. Literatür bu alanda çok zengin olmasına karşın, literatürde iletişim performansını belirleyen birçok etmeni bu etmenlere hakedilen önemi atfederek tam anlamıyla aynı anda işleyebilecek yöntemlerin eksikliği bulunmaktadır. Bu tezde iletişim performansının daha doğru bir yakınsamasını elde etmek amacıyla seyrek matrislerin akıllı bölümlenmesini sağlayan model ve metotları incelemekteyiz. Paralel seyrek işlemlerin iletişim performansını arttırmak için bütün iletişim maliyetlerinde başlıca bir bileşen olarak kendisini gösteren gecikim darboğazlarının azaltılmasına odaklanmaktayız. Bunun yanı sıra, önerilen yaklaşımlar literatürde halihazırda kabul görmüş iletişim maliyet ölçütlerini de hesaba katarak olabildiğince fazla ölçütü aynı anda işlemeye çalışmaktadır. Bir-boyutlu (1D) ve iki boyutlu (2D) seyrek matrislerin bölümlenmesinde gecikim maliyetlerini azaltmak için sırasıyla bir-fazlı ve iki-fazlı bölümleme modelleri önermekteyiz. 1D bölümleme için önerilen model sıkça kullanılan özyinelemeli bölümleme metoduna dayanmakta olup gecikim gerektiren ilişkileri gösterebilmek için yeni yapılar kullanmaktadır. 2D bölümleme için önerilen bölümleme modelleri asimetrik lineer sistemler için kullanılan çözücülerin performanslarını, bu çözücülerde kullanılan vektörler üzerinde farklı bölümler aracılığıyla gecikim maliyetlerini azaltarak geliştirmeyi hedeflemektedir. Tezde elde ettiğimiz bulgular dağıtık bellekli sistemlerde ölçeklenebilir performans elde edilebilmesi için gecikim maliyetlerinin kesinlikle düşünülmesi gerektiğini göstermektedir.