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.

S ( P ) = P − α ⋅ ( P − 1 ) {\displaystyle S(P)=P-\alpha \cdot (P-1)}

Burada;
P, işlemci sayısını,
S, hızlanmayı,
α {\displaystyle \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.

Yasa, 1980'lerin sonunda Amdahl yasasının koşut hesaplamaya çizdiği sınırın deneyle çeliştiğinin görülmesi üzerine ortaya konmuştur. Amdahl yasasının yaygın okunuşuna göre, ardışık bölümü yüzde birkaç olan bir programda bile hızlanma birkaç yüzü aşamazdı; bu okuma, çok işlemcili makinelere yapılan yatırımın karşılığını vermeyeceği yönünde bir sav olarak kullanılıyordu.

Sandia Ulusal Laboratuvarları'nda 1024 işlemcili bir bağlaç küpü üzerinde yapılan çalışmalar bu beklentiyi karşılamadı. Üç ayrı bilimsel uygulamada, ardışık bölümü ihmal edilebilir olmayan programlarda binin üzerinde hızlanma ölçüldü. Gustafson bu sonucu, Amdahl yasasının yanlış olduğunu göstererek değil, sorulan sorunun değiştiğini göstererek açıkladı. Uygulamada sorun boyutu sabit tutulmuyor, makine büyüdükçe sorun da büyütülüyordu.

Yasanın çıkış noktası, ölçümün hangi makinede yapıldığıdır. Gustafson yasası süreyi koşut makinede sabitler ve o çalışmayı temel alır.

Koşut çalışmanın toplam süresi birim seçilsin. Bu sürenin a {\displaystyle a} kadarı ardışık, kalan 1 − a {\displaystyle 1-a} kadarı koşut yürütülen bölüme ait olsun. Aynı iş tek bir işlemcide yapılsaydı ardışık bölüm yine a {\displaystyle a} kadar sürecek, koşut bölüm ise p {\displaystyle p} kat uzayarak p ( 1 − a ) {\displaystyle p(1-a)} kadar sürecekti. Hızlanma bu iki sürenin oranıdır:

S ( p ) = a + p ( 1 − a ) a + ( 1 − a ) = a + p ( 1 − a ) = p − a ( p − 1 ) {\displaystyle S(p)={\frac {a+p(1-a)}{a+(1-a)}}=a+p(1-a)=p-a(p-1)}

Elde edilen bağıntı p {\displaystyle p} 'ye göre doğrusaldır ve eğimi 1 − a {\displaystyle 1-a} 'dır. Ardışık bölüm ne olursa olsun, işlemci sayısı artırıldıkça hızlanma sınırsız büyür; Amdahl yasasındaki gibi bir üst sınıra yaklaşmaz. Buradaki a {\displaystyle a} , koşut çalışmada ölçülen ardışık orandır ve sorun büyüdükçe küçülmesi beklenir.

Bu büyüklüğe ölçekli hızlanma denir. Ölçülen şey, sabit bir işin ne kadar hızlandığı değil, sabit bir sürede ne kadar çok işin yapılabildiğidir.

İki yasa çelişmez; aynı bağıntıyı iki ayrı ucundan yazarlar. Aradaki fark, ardışık oranın hangi çalışmada ölçüldüğüdür.

Amdahl yasası sorunu sabitler ve ardışık oranı tek işlemcili çalışmada ölçer. Bu oran f {\displaystyle f} ile gösterilirse hızlanma

S ( p ) = 1 f + 1 − f p {\displaystyle S(p)={\frac {1}{f+{\frac {1-f}{p}}}}}

olur ve p {\displaystyle p} büyüdükçe 1 / f {\displaystyle 1/f} değerine yaklaşır. Gustafson yasası ise aynı oranı koşut çalışmada ölçer. Aynı programın iki ölçümü arasındaki bağ

f = a a + p ( 1 − a ) {\displaystyle f={\frac {a}{a+p(1-a)}}}

bağıntısıyla verilir. Bu değer Amdahl bağıntısında yerine konduğunda doğrudan S = a + p ( 1 − a ) {\displaystyle S=a+p(1-a)} elde edilir; iki ifade cebirsel olarak aynıdır.

Ayrım bu yüzden matematiksel değil, sorulan sorudadır. Amdahl yasası elde bulunan sorunun daha çok işlemciyle ne kadar hızlı biteceğini, Gustafson yasası ise elde bulunan sürede daha çok işlemciyle ne kadar büyük bir sorunun bitirilebileceğini yanıtlar. Sabit tutulan büyüklük birinde iş, ötekinde zamandır.

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.

İki yasanın karşılığı, koşut başarım ölçümünde iki ayrı yöntem olarak yerleşmiştir.

Güçlü ölçekleme (İngilizce: strong scaling) ölçümünde sorun boyutu sabit tutulur ve işlemci sayısı artırılır. Ölçülen şey, aynı işin ne kadar kısa sürede bittiğidir; sonuç Amdahl yasasının çizdiği sınıra doğru düzleşir. İşlemci başına düşen iş küçüldükçe haberleşme ve eşgüdüm payı büyüdüğü için bu ölçüm belirli bir işlemci sayısından sonra doyuma ulaşır.

Zayıf ölçekleme (İngilizce: weak scaling) ölçümünde ise işlemci başına düşen iş sabit tutulur; işlemci sayısı iki katına çıkarıldığında sorun boyutu da iki katına çıkarılır. Beklenen sonuç, çalışma süresinin yaklaşık sabit kalmasıdır. Bu, Gustafson yasasının doğrudan deneysel karşılığıdır.

Hangi ölçümün anlamlı olduğu uygulamaya bağlıdır. Sorun boyutunun dışarıdan belirlendiği ve büyütülemediği durumlarda güçlü ölçekleme geçerli ölçüttür; çözünürlüğün ya da doğruluğun artırılabildiği bilimsel benzetimlerde ise zayıf ölçekleme, makinenin gerçek yararını daha iyi anlatır.

Her iki yasa da ardışık oranı bilinen bir büyüklük sayar; uygulamada ise bu oran doğrudan ölçülemez, hızlanma ölçümünden geri hesaplanır. Karp-Flatt ölçütü bu amaçla tanımlanmıştır ve p {\displaystyle p} işlemcide ölçülen S {\displaystyle S} hızlanmasından deneysel ardışık oranı

e = 1 S − 1 p 1 − 1 p {\displaystyle e={\frac {{\frac {1}{S}}-{\frac {1}{p}}}{1-{\frac {1}{p}}}}}

biçiminde verir.

Ölçütün değeri, hızlanmanın neden beklenenin altında kaldığını ayırt etmeye yarar. e {\displaystyle e} işlemci sayısından bağımsız çıkıyorsa sınırlayan şey gerçekten programın ardışık bölümüdür. e {\displaystyle e} işlemci sayısıyla birlikte büyüyorsa sınırlayan şey ardışık bölüm değil, işlemci arttıkça büyüyen haberleşme ve eşgüdüm yüküdür; bu durumda iki yasanın da dayandığı, koşut bölümün kusursuz bölündüğü kabulü geçerli değildir.

Sorunun neye göre büyütüleceği ayrı bir soru olarak da ele alınmıştır. Amdahl yasası sorun boyutunu, Gustafson yasası ise çalışma süresini sabit tutar; üçüncü bir yaklaşım, sorunu makinenin toplam belleğini dolduracak kadar büyütmeyi ölçüt alır.

Bu bakışın gerekçesi, koşut makinelerde işlemci sayısı artarken toplam belleğin de artmasıdır. İşlemci başına düşen bellek sabit kaldığından, makine iki katına çıktığında saklanabilecek sorun da iki katına çıkar; ama iş yükü, algoritmanın karmaşıklığına göre bellekten daha hızlı büyüyebilir. Karmaşıklık doğrusalsa sonuç Gustafson yasasıyla örtüşür; doğrusalın üstündeyse elde edilen hızlanma daha da yüksek, buna karşılık çalışma süresi sabit değil artan bir büyüklük olur.

Üç ölçüt böylece neyin sabit tutulduğuna göre ayrılır: iş, zaman ya da bellek. Bir koşut makinenin başarımına ilişkin sayı verilirken hangisinin varsayıldığının belirtilmesi gerekir, çünkü aynı program ve aynı makine için üçü farklı sayılar üretir.

Ölçekli hızlanma, koşut makinelerin karşılaştırılmasında kullanılan ölçütlere doğrudan yansımıştır. Yaygın kullanılan yoğun doğrusal cebir denektaşında, çözülen dizey denkleminin boyutu makineye göre seçilir; büyük bir makine ölçüme küçük bir sorunla değil, belleğini dolduracak kadar büyük bir sorunla girer. Bildirilen sayı bu yüzden sabit bir işin ne kadar hızlandığını değil, makinenin birim zamanda ne kadar iş çıkardığını anlatır.

Aynı yaklaşım bilimsel benzetimlerde de geçerlidir. Hava tahmini, iklim benzetimi ve yapısal çözümleme gibi işlerde daha çok işlemci, aynı hesabı daha hızlı bitirmek için değil, ağı sıklaştırmak ya da daha uzun bir süreyi benzetmek için kullanılır. Kazanç sürede değil, elde edilen çözümün ayrıntısındadır.

Yasanın dayandığı varsayım, sorun boyutunun makineyle birlikte büyütülebilmesidir. Bu varsayımın tutmadığı durumlarda ölçekli hızlanma da elde edilemez.

Sorun boyutu her zaman büyütülemez. Kimi hesaplamaların veri kümesi dışarıdan belirlenir ve isteğe göre artırılamaz; böyle bir işte fazladan işlemci, bölünecek iş bulamaz. Sorun boyutunu bellek sığası ya da veri kaynağının kendisi sınırlar.

İş yükü sorun boyutundan hızlı büyüyebilir. Bir algoritmanın karmaşıklığı doğrusalın üstündeyse, sorunu büyütmenin bedeli hızla ağırlaşır. O ( n 3 ) {\displaystyle O(n^{3})} karmaşıklıktaki bir algoritmada sorun boyutu iki katına çıkarıldığında iş yükü sekiz katına çıkar; tersinden bakıldığında, aynı sürede bitirmek koşuluyla işlemci sayısını iki katına çıkarmak sorun boyutunda ancak 2 3 ≈ 1 , 26 {\displaystyle {\sqrt[{3}]{2}}\approx 1{,}26} katlık bir artışa izin verir. Bu tür işlerde makineyi büyütmek, çözülen sorunu ölçülü biçimde büyütür.

Koşut bölümün kusursuz bölündüğü varsayılır. Bağıntı, koşut bölümün p {\displaystyle p} işlemciye tam olarak bölündüğünü kabul eder; haberleşme, eşgüdüm ve yük dengesizliği hesaba katılmaz. Ölçümde bu payların işlemci sayısıyla birlikte büyüdüğü görülür ve doğrusal hızlanmadan sapma buradan doğar.

• 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.