Gauss-Seidel algoritmasındaki döngü bağımlılığı cebirsel döngü açma yöntemiyle çözüldü
Öne çıkanlar
- Gauss-Seidel, Jacobi yöntemine göre yarı yarıya az yinelemeyle yakınsasa da döngü bağımlılıkları nedeniyle pratikte 4-5 kat yavaş kaldı.
- OSACA analizleri, Gauss-Seidel çekirdeğinin eleman başına 12 döngülük donanımsal gecikme sınırına takıldığını doğruladı.
- İki adımlı cebirsel döngü açma yaklaşımı, eleman başına düşen döngü aktarımlı bağımlılığı 12 döngüden 2 döngüye düşürdü.
Sayısal analizde Gauss-Seidel yöntemi, Jacobi yöntemine kıyasla yarı yarıya daha az yinelemeyle yakınsamasına rağmen derleyici seviyesindeki döngü içi veri bağımlılıkları yüzünden fiilen 4 ila 5 kat daha yavaş çalıştı. İki boyutlu Poisson denklemi çözümlerinde ortaya çıkan bu performans farkı, derleyicinin Gauss-Seidel kodunu vektörleştirememesinden ve işlemcinin ardışık komut yürütme yeteneklerini kısıtlamasından kaynaklandı.
Open Source Architecture Code Analyzer (OSACA) aracıyla yapılan statik analizler, Gauss-Seidel döngüsünün eleman başına 12 döngülük katı bir gecikme süresine takıldığını ortaya koydu. Jacobi yönteminde bu döngü aktarımlı bağımlılık yalnızca 1 döngü sürerken, Gauss-Seidel yönteminde güncellenen komşu hücre verilerinin hemen bir sonraki adımda okunması işlemciyi gecikme sınırına hapsetti. Standart döngü açma teknikleri bağımlılığı kırmakta tek başına yetersiz kaldı.
Araştırmada ardışık iki adımın bağımlılıkları cebirsel bir özyineleme olarak yeniden modellendi ve formül bağımsız terimler cinsinden çözüldü. İki dereceli bu yeni çekirdek sayesinde eleman başına düşen döngü aktarımlı bağımlılık süresi 12 döngüden 2 döngüye indirildi. Böylece algoritma gecikme darboğazından kurtularak işlem hacmi odaklı bir yapıya kavuştu.
Bu özet yapay zekâ ile hazırlanmıştır; ayrıntılar ve doğrulama için orijinal kaynağa başvurun.