Amdahl yasası

Bilgisayar mimarı Gene Amdahl'ın ismini alan Amdahl Yasası, sistemin bir parçasının hızlandırılması sonucunda, sistemin bir bütün olarak ele alındığında toplam hızlanmasının ne olacağını hesaplamak için kullanılır. Sıklıkla, birden fazla işlemci kullanıldığında erişilebilecek azami hızlanmayı tahmin etmek için paralel hesaplamalarda da kullanılır.

Amdahl Yasası'nın genelleştirilmiş hali:

Burada;
P_k: Hızlandırılacak ya da yavaşlatılacak buyrukların, tüm buyruklara oranı.
S_k: Hızlandırma çarpanı. Bu çarpan için, 1 temel kabul edilir. Çarpan 1 olduğunda, hızlanma ya da yavaşlama yoktur.

Her bir oran ve hızlandırma için bir etiket görevi görür.

Sistem değişikliğinden kaynaklanan hızlanma veya yavaşlamaların sayısı.

Tanım

Amdahl Yasası, bir algoritmanın paralel gerçeklemelerinin, seri gerçeklemesi ile arasındaki beklenen hızlanma değerlerinin ilişkisi için bir modeldir. Örneğin, eğer bir algoritmanın paralel gerçeklemeleri, algoritmanın işlemlerinin 12%'sini keyfi olarak hızlı çalıştırabiliyorsa ve işlemlerin geri kalan 88%'i paralelleştirilebilir değilse, Amdahl Yasası'na göre, paralelleştirilmiş versiyonun azami hızlanması, paralelleştirilmemiş gerçeklenmelerden

${\frac {1}{1-0.12}}=1.136$ kadar hızlıdır.

Daha teknik olmak gerekirse bu yasa, işlemlerin P'lik bir oranının etkilenerek S kadar hızlandırıldığı bir noktada erişilebilecek hızlanmayı hesaplamada kullanılır. Örneğin, eğer bir iyileştirme süreci, işlemlerin 30%'unu hızlandırabiliyorsa, P 0,3; ve eğer bu süreç, etkilenen bölümü eskisine göre iki kat daha hızlı çalıştırabiliyorsa, S 2 olacaktır. Amdahl Yasası'na göre, bu iyileştirmenin toplam hızlandırması;

${\frac {1}{(1-P)+{\frac {P}{S}}}}$ olacaktır.

Bu formülün nasıl çıkarıldığını görmek için; eski işlem süreci süresinin 1 birim olduğunun varsayalım. Yeni işlem sürecinin alacağı zaman, hızlandırılmamış buyrukların işlenmesi için gerek süre (yani 1 - P) ile hızlandırılmış buyrukların işlenmesi için gereken sürenin toplanmasıyla elde edilir. Hızlandırılmış buyrukların işlenmesi için gereken süre, hızlandırılmış bölümün, hızlanmadan önce aldığı sürenin hızlanma katsayısına bölünmesi ile elde edilir. Yani P/S ile hesaplanır. Toplam hızlanma ise, hızlanmadan önce işlem için gereken sürenin, hızlanmadan sonra gereken süreye bölünmesi ile bulunur. Amdahl Yasası'nın gerektirdiği formül de tam olarak bunu yapmaktadır.

Başka bir örneği ele alacak olursak: Bize, dört bölüme ayrılmış bir işlem verilmiş olsun ve bu bölümlerin toplam buyruk sayısına oranları şu şekilde olsun: P1 = 11%, P2 = 18%, P3 = 23%, P4 = 48%. Görüldüğü gibi, bu oranların toplamı 100%'e ulaşmaktadır. Verilere göre, P1'de hızlanma veya yavaşlama olmamaktadır, buna göre S1 = 1 alınır. P2 5 kat hızlanmaktadır, yani S2 = 5, P3 20 kat hızlanmaktadır, yani S3 = 20, P4 ise 1.6 kat hızlanmaktadır ve S4 = 1.6 alınmaktadır. ${\frac {P1}{S1}}+{\frac {P2}{S2}}+{\frac {P3}{S3}}+{\frac {P4}{S4}}$ formülünü kullanarak, çalışma zamanını ${{\frac {.11}{1}}+{\frac {.18}{5}}+{\frac {.23}{20}}+{\frac {.48}{1.6}}}=.4575$ olarak hesaplarız. Buna göre çalışma zamanı, hızlanmadan önceki zamanın yarısından biraz daha azdır. Eski çalışma zamanı, elbette ki 1 birim olarak kabul edilmiştir. Toplam hızlanmayı hesaplamak için, ${\frac {1}{.4575}}=2.186$ formülünü kullanırız ve toplam hızlanmanın, 2 kattan biraz daha fazla olduğunu görürüz. 20 kat ve 5 kat hızlanan buyrukların, toplam işlem içindeki oranlarının az olması nedeniyle, toplam hızlanmaya fazla bir etkisi olmadığını görebiliyoruz.

Ardışık Bir Programda Hızlanma

Bir görevin, iki birbirinden bağımsız parçası (A ve B) olduğunu varsayalım. B, toplam yürütme zamanının hemen hemen 25%'ini almaktadır. Yoğun bir çaba sarf ederek, bu B bölümünü 5 kat hızlandırılsa bile, bu hızlandırmanın, toplam yürütme zamanına etkisi çok fazla olmayacaktır. Diğer yandan, A bölümünü 2 kat hızlandırmak bile toplam yürütme zamanını büyük oranda düşürecektir. Buna ek olarak, A bölümünü 2 kat hızlandırmak, B bölümünü 5 kat hızlandırmaktan çok daha az bir çabayla gerçekleştirilebilir.

Bir bölümü $p$ kat kadar hızlandırılmış bir ardışık programın azami hızlanması,

Azami Hızlanma

\leq {\frac {p}{1+f*(p-1)}}

olarak bulunur.

Burada

f

(

0.0<f<1.0

), hızlandırmadan önce, hızlandırılmamış bölümün tuttuğu süredir. Örneğin:

Eğer B bölümü (mavi) 5 kat hızlandırılırsa, p = 5 $t_{n}$ (kırmızı) = 3 saniye, $t_{i}$ (mavi) = 1 saniye ve
$f=t_{n}/(t_{n}+t_{i})=0.75$

Azami hızlanma $\leq {\frac {5}{1+0.75*(5-1)}}=1.25$
Eğer A bölümü (kırmızı) 2 kat hızlandırılrsa, p = 2, $t_{n}$ (mavi) = 1 saniye, $t_{i}$ (kırmızı) = 3 saniye ve
$f=t_{n}/(t_{n}+t_{i})=0.25$

Azami hızlanma $\leq {\frac {2}{1+0.25*(2-1)}}=1.60$ (Daha iyi!)

Buna göre, A'yı 2 kat hızlandırmak, B'yi 5 kat hızlandırmaktan daha iyi sonuç vermektedir.

A'yı 2 etmeniyle hızlandırmak, toplam program hızında +60% 'lık bir artış sağlamaktadır.
B'yi 5 etmeniyle hızlandırmak ise ki bu süreç A'yı hızlandırmaktan daha fazla efor gerektirecektir, toplam program hızında yalnızca +25%'lik bir artış sağlayacaktır.

Paralellik

Paralelliğin özel bir durumunda Amdahl yasası der ki; eğer F ardışık (paralel değil) bir işlemin bir parçasıysa ve (1 - F) paralelleştirilebilir kısımsa, N işlemcili kullanarak azami hızlanma:

${\frac {1}{F+{\frac {1-F}{N}}}}$ ‘dır.

Limitini aldığımızda N sonsuza yönelir, azami hızlanma 1/F’e yönelir. Uygulamada maliyet/başarım oranı, (1-F)/N, F’ten küçük olduktan sonra N arttıkça düşer.

Örneğin, F %10 ise problemin azami hızlanması 10’un çarpanları kadar olabilir. N’in büyüklüğünün bir önemi yoktur. Bunun için, paralel işlem sadece ya az sayıda işlemci için ya da F‘in çok küçük olduğu problemlerde kullanışlıdır. Paralel programlamanın büyük bir kısmı F değerini olabilecek en küçük değerde tutmayı amaçlar.

Sınırlamalar

Amdahl’ın yasasına göre, kuramsal azami hızlanma, N işlemci ile N olur. Bu doğrusal (lineer) hızlanma olarak adlandırılır. Ancak uygulamada N işlemcisi olan bir makinede N’den fazla hızlanma olması görülmeyen bir durum değildir. Buna üstün doğrusal hızlanma denir. Bunun olası bir nedeni önbellek toplanmasıdır. Paralel bilgisayarlarda, sadece işlemci sayılarının değiştirilmesiyle değil, farklı işlemcilerin toplanan önbelleklerin büyüklüğü ile yapılır. Daha büyük toplanan önbellek boyutu ile daha fazla veri kümesi veya veri kümesinin tamamı önbelleklere sığabilir. Böylece bellek erişim zamanı düşer ve ek hızlanma sağlanır.

Amdahl’ın Başparmak Kuralı

Amdahl’ın başparmak kuralı, bilgisayarın desteklediği her saniye başına buyruk için 1 bayt bellek ve 1 bit/saniye G/Ç gerektiğidir. Bu Amdahl’ın Diğer Kanunları başlığı altında işlenmektedir.

Kaynakça

Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483–485, 1967. Note: Gene Amdahl has approved the use of his complete text in the Usenet comp.sys.super news group FAQ which goes out on the 20th of each month.

Dış bağlantılar

Wikimedia Commons'ta Amdahl yasası ile ilgili ortam dosyaları bulunmaktadır.

Reevaluating Amdahl's Law
Reevaluating Amdahl's Law and Gustafson's Law
A simple interactive Amdahl's Law calculator
"Amdahl's Law" 10 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi. by Joel F. Klein, The Wolfram Demonstrations Project, 2007.