Gustafson Yasası

Gustafson yasası


Gustafson yasası (Gustafson-Barsis yasası adıyla da bilinir), yeterince büyük bir sorunun verimli bir biçimde koşutlaştırılabileceğini öngören bir bilgisayar mühendisliği yasasıdır 1988 yılında John L Gustafson'un geliştirdiği bu kural, bir programın koşutluk derecesine bağlı olarak ne ölçüde hızlandırılabileceğini belirleyen Amdahl yasası ile yakından ilintilidir

Burada;
P, işlemci sayısını,
S, hızlanmayı,
α, işlemin koşutlaştırılamayan bölümünü belirtmektedir

Gustafson yasası, çok büyük makineler için gerekli olan yüksek hesaplama gücünü karşılayamayan Amdahl yasasının zayıf noktalarını öne çıkarmaktadır Koşut işlemciler üzerindeki sabit hesaplama yükünü kaldıran yasa, bunun yerine ölçekli hızlanmayı sağlayan sabit zaman kavramını getirmiştir

Sabit hesaplama yükünü temel alan Amdahl yasası, bir programın ardışık bölümünün işlenmesi için gereken sürenin makine boyutuna (işlemci sayısı) bağlı olmadığını öne sürmektedir Buna karşın, koşutlaştırılmış bölüm n işlemciye dağıtılmış durumdadır

Gustafson yasası, koşutlaştırılabilir derleyicilerin tasarımını gündeme getirmiş ve bir soruna yönelik çözümün ardışık bölümünü küçültüp koşut sistemlerin başarımını artırmaya yönelik çalışmaların önünü açmıştır

Uygulaması

n, sorunun büyüklüğünü belirten bir birim olsun Bu durumda, programın bir koşut bilgisayardaki çalışma süresi şöyle özetlenebilir:

a(n) + b(n) = 1

Burada;
a, ardışık bölümü,
b, koşut bölümü göstermektedir

Bu ifadenin ardışık bilgisayardaki karşılığı dir Burada p, koşut hesaplamadaki işlemci sayısını göstermektedir

Hızlanma ise

ve

biçiminde gösterilebilir Burada a(n), ardışık işlevi belirtmektedir

Ardışık işlev a(n)'nin n sonsuza yaklaştıkça küçüldüğü varsayılırsa hızlanma p'ye yakınsar Böylece Gustafson yasası, koşut işlemeyi Amdahl yasasından bağımsız kılmaktadır

Gustafson yasası; ardışık bölümün, çok sayıda işlemcinin kullanıldığı koşut sistemlerde bile sabit kaldığını öne sürmektedir Amdahl yasasının savı ise ardışık bölümün başarım üzerindeki etkisinin işlem sayısıyla doğru orantılı biçimde artış gösterdiğidir

Bir sürüş benzetmesi

Amdahl yasası şöyle örneklendirilebilir:
“ Bir aracın birbirlerinden 60 km uzaklıkta bulunan iki kent arasında yolculuk yaptığını ve aracın, yolun yarısını 30 km/sa hızla geçtiğini varsayalım Bu araç, yolun ikinci yarısını ne denli hızlı geçerse geçsin yol boyunca ulaşılan ortalama hız 90 km/sa'i bulamayacaktır ”

Gustafson yasası ise şöyle örneklendirilebilir:
“ Bir aracın 90 km/sa'ten az bir hızla bir süre yol aldığını varsayalım Ne var ki, yeterli süre ve yol varsa bu aracın hızı 90 km/sa'i bulabilir Örneğin, bir saat boyunca 30 km/sa hızla yolculuk eden bir araç iki saat boyunca 120 km/sa hızla yol yaparak ortalama hızını istenen düzeye çıkarabilir ”

Kısıtlamalar

Bazı sorunlar yeterince büyük veri kümelerine sahip değillerdir Dünya üzerinde yaşayan insan sayısıyla birebir eşlenebilen bir işlevin bir yıl içindeki büyüme oranının düşüklüğü bu olguya örnek olarak gösterilebilir

Doğrusal olmayan algoritmalar, Gustafson yasasının "dayattığı" koşutlaştırmaya engel oluşturabilmektedirler Snyder'a göre O(n3)'lük bir algoritma; koşutzamanlılığın, sorun büyüklüğünün iki katına çıktığı durumda bile yalnızca %9 büyüyebilmektedir Bu, yüksek koşutzamanlılık değerlerine sahip hesaplamaların özgün soruna göre kaydadeğer bir avantaj oluşturmayacağı anlamına gelmektedir Ne var ki, uygulama bunun tam tersini göstermektedir Kümesel hesaplama ve Condor gibi dağıtık hesaplama sistemleri bu konuda verimli sonuçlara ulaşmıştır