Gustafson yasası

Gustafson Yasası'na göre hızlanma

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.

$S(P)=P-\alpha \cdot (P-1)$

Burada;
P, işlemci sayısını,
S, hızlanmayı,
$\alpha$, 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ığı $a(n)+p\cdot b(n)$'dir. Burada p, koşut hesaplamadaki işlemci sayısını göstermektedir.

Hızlanma ise

$(a(n)+p\cdot {}b(n))$

ve

$S=a(n)+p\cdot {}(1-a(n))$

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(n³)'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 kayda değ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.

Dış bağlantılar

• Amdahl yasasını yeniden değerlendirmek - John Gustafson'un yasasını ilk kez ortaya koyduğu makale, Communications of the ACM 31(5), 1988. sf. 532-533
• Lawrence Snyder, "Tür Mimarileri, Paylaşımlı Bellek ve Gösterişsiz Potansiyelin Doğal Sonucu" 8 Haziran 2011 tarihinde Wayback Machine sitesinde arşivlendi.