Minimizing communication through computational redundancy in parallel iterative solvers

y=Ax biçimindeki seyrek matris-vektör çarpımı (SMxV) bilimsel uygulamalardayinelemeli doğrusal denklem çözümleyicilerinde kullanılan bir çekirdekoperasyondur. Bu çözümleyicilerde, yinelemeler vasıtasıyla yakınsayıncaya kadaraynı seyrek matris ile SMxV operasyonu tekrarlanarak uygulanır. Paralel ortamdaparalel SMxV operasyonu matrise ve onun ayrışımına göre işlemcilerarasında haberleşmeye ihtiyaç duyar. Bu haberleşme akıllı ayrışımlar ileazaltılabilinir. Fakat, biz veri replikasyonu ve fazla hesaplama ile bu haberleşmeyidaha da fazla azaltabiliriz. Satır-paralel SMxV hesaplamada bu haberleşme x vektörelemanlarının transferi yüzünden oluşur. Bir sonraki yinelemenin girdivektörü x, bazı doğrusal operasyonlar vasıtasıyla yürürlükteki yinelemenin çiktivektörü y ile hesaplanır. Bundan dolayı, bir işlemci başka bir işlemciden bir x vektörelemanı almak yerine fazla bir y vektör elemanını, ki bu y vektör elemanıbir sonraki yinelemenin x vektör elemanına öncülük eder, hesaplayabilir. Böylece,fazla y vektör elemanı hesaplamak haberleşmenin azalmasına yol açabilir.Bu tezde, biz yukarıda bahsedilen yinelemeli denklem çözümlayiciler içinhesaplama ve haberleşme desenini doğru yakalayan yönlü çizge tabanlı modeltasarladık. Bundan başka, biz fazla y vektör elemanı hesaplaması sebebiylehaberleşme azalışını yönlü çizge modeli uzerinde bir kombinatoriyal problemolarak formülledik. Biz bu kombinatoriyal problemi çözmek için iki tane buluşsalyöntem önerdik. Deneysel sonuçlar göstermektedir ki fazla hesaplama yaparakhaberleşme azaltma stratejisi gelecek vaat etmektedir.