Hızlanma

Hızlanma (İngilizce: speedup), bir görevin iyileştirilmiş bir sistemde, başlangıçtaki sisteme kıyasla kaç kat daha hızlı gerçekleştirildiğini gösteren orandır. Başarım değerlendirmesinde, bir mimari iyileştirmenin ya da koşutlaştırmanın sağladığı kazancı nicelemek için kullanılır. Hızlanma iki ayrı büyüklük üzerinden ölçülebilir: tek bir işin tamamlanma süresi (gecikme) ya da birim zamanda tamamlanan iş miktarı (işlem hacmi).

Gecikme, belirli bir iş yükünün baştan sona tamamlanması için geçen süredir. Aynı iş eski sistemde T₁, yeni sistemde T₂ sürede tamamlanıyorsa hızlanma bu iki sürenin oranıdır:

S = T₁ / T₂

Örneğin bir iş eskiden 100 saniyede tamamlanırken yeni sistemde 25 saniyede tamamlanıyorsa hızlanma 4 kattır.

İşlem hacmi, birim zamanda tamamlanan iş miktarıdır. Eski ve yeni sistemin işlem hacmi Q₁ ve Q₂ ise hızlanma şöyle yazılır:

S = Q₂ / Q₁

İş yükü sabit tutulduğunda iki ölçüt birbirinin tersidir; gecikme yarıya inerse işlem hacmi iki katına çıkar. Buna karşılık iş yükü sistemle birlikte büyüdüğünde ikisi farklı sonuç verir: daha büyük bir sistemde daha büyük bir problem çözülüyorsa tek bir işin gecikmesi kısalmayabilir, ama birim zamanda tamamlanan iş miktarı artar.

Aynı program iki işlemcide çalıştırılıyor ve birincisinde 6,75 saniye, ikincisinde 4,50 saniye sürüyorsa ikinci işlemcinin birinciye göre hızlanması:

S = 6,75 / 4,50 = 1,5

İkinci işlemci aynı işi 1,5 kat daha hızlı tamamlamaktadır.

Bir programın yürütme zamanı, buyruk sayısı ile buyruk başına çevrim ve saat çevrim süresinin çarpımına eşittir. İki ölçümde buyruk sayısı ve saat sıklığı değişmiyorsa hızlanma yalnızca buyruk başına çevrim oranına indirgenir:

S = BBÇ₁ / BBÇ₂

Örneğin bir iyileştirme buyruk başına çevrim değerini 3,0'dan 2,0'ye düşürüyorsa hızlanma 1,5 kattır. Bu, yürütme süresiyle yapılan hesapla aynı sonucu verir; hangi ölçütün kullanılacağı elde edilen veriye bağlıdır.

Koşut hesaplamada hızlanma, bir programın birden çok işlem birimiyle tek bir işlem birimine göre kaç kat hızlandığını gösterir. İdeal (doğrusal) durumda n işlemci n kat hızlanma sağlar; ancak gerçekte işin koşut çalıştırılamayan bölümü, eşgüdüm ve iletişim maliyetleri bu kazancı sınırlar.

İş yükü sabit tutulup yalnız işlem birimi sayısı artırıldığında hızlanmanın tavanını işin koşutlaştırılamayan bölümü belirler. Programın p kesri koşut çalışabiliyorsa n işlem birimiyle elde edilecek hızlanma şöyledir:

S = 1 / ((1 − p) + p / n)

n sonsuza giderken bu ifade 1 / (1 − p) değerine yaklaşır. Sonuç çarpıcıdır: programın %95'i koşut çalışsa bile, sonsuz sayıda işlem birimiyle elde edilebilecek en büyük hızlanma 20 kattır. Aynı programda 64 işlem birimi 15,4 kat hızlanma verir; birim sayısını 1024'e çıkarmak bunu ancak 19,6'ya taşır.

Uygulamada daha büyük bir sistem çoğu zaman aynı işi daha hızlı yapmak için değil, daha büyük bir işi aynı sürede yapmak için kurulur. İş yükü işlem birimi sayısıyla birlikte büyütüldüğünde ölçülen hızlanma sabit bir tavana takılmaz:

S = n − (1 − p)(n − 1)

Bu düzende %90'ı koşut çalışan bir iş, 1024 işlem birimiyle 922 kat hızlanabilir; aynı program sabit iş yükünde 10 katın üzerine çıkamazdı. İki yasa çelişmez, farklı soruları yanıtlar: biri sabit bir işin ne kadar hızlandığını, öteki verilen sürede ne kadar büyük bir işin bitirilebileceğini ölçer.

Koşut bir sistemde elde edilen hızlanmanın kullanılan işlem birimi sayısına oranına verim denir:

η = S / s

Burada s işlem birimi sayısıdır. Doğrusal hızlanmada S = s olduğundan verim 1'e eşittir. Uygulamada iletişim, eşgüdüm ve sıralı bölüm maliyetleri yüzünden verim 1'in altında kalır ve işlem birimi sayısı arttıkça düşme eğilimi gösterir. Hızlanma eğrisi artmayı sürdürdüğü için tek başına yanıltıcı olabilir; bu nedenle ölçekleme davranışını değerlendirirken verim eğrisi daha bilgilendiricidir.

İki ölçüt her zaman aynı sayıyı vermez. Bir iyileştirme işin tamamını hızlandırıyorsa ikisi örtüşür; iyileştirme işleri üst üste bindirmekten geliyorsa ayrışırlar. En bilinen örnek boru hattıdır.

Aşamaları 200, 100, 200, 200 ve 100 pikosaniye süren bir işlemci, boru hattı kullanmadığında bir buyruğu 800 pikosaniyede tamamlar. Aynı işlemci beş aşamalı boru hattına dönüştürüldüğünde her aşama en yavaş aşamaya göre 200 pikosaniyeye çekilir ve tek bir buyruğun baştan sona geçmesi 1000 pikosaniyeye çıkar. Gecikme üzerinden hızlanma 800 / 1000 = 0,8'dir; buyruk başına süre kısalmamış, uzamıştır. Buna karşılık boru hattı her 200 pikosaniyede bir buyruk tamamladığından işlem hacmi üzerinden hızlanma 800 / 200 = 4 kattır.

Bazı durumlarda ölçülen hızlanma işlem birimi sayısından da büyük olabilir; buna süper doğrusal hızlanma denir. Başlıca nedenleri şunlardır:

• Bellek etkisi: işlem birimi sayısı arttıkça toplam önbellek boyutu da artar; veri kümesinin daha büyük bir bölümü işlemciye yakın katmanlara sığdığından erişim süresi kısalır.
• Arama uzayının erken elenmesi: geri izleme (backtracking) ve dal-sınır (branch and bound) gibi arama algoritmalarında, koşut çalışan birimlerden biri çözümü erken bulduğunda arama uzayının büyük bir bölümü hiç incelenmeden elenebilir.

Bellek etkisi somut sayılarla görülebilir. Çalışma kümesi 8 megabayt olan bir program, 2 megabaytlık son düzey önbelleğe sahip tek bir işlemcide çalışırken verinin ancak dörtte birini önbellekte tutabilir. Aynı program dört işlemciye bölündüğünde her birime 2 megabayt düşer, her birimin payı kendi önbelleğine sığar ve erişimlerin çoğu ana bellek yerine önbellekten karşılanır. Kazanç işlem birimi sayısından değil, bellek erişim süresindeki düşüşten gelir; bu yüzden dört katı aşabilir.

Süper doğrusal hızlanma, koşutlaştırmanın kendisinden değil bu yan etkilerden kaynaklandığından, ölçüm sonuçları yorumlanırken nedeninin belirtilmesi gerekir. Çoğu durumda böyle bir ölçüm koşutlaştırmanın olağanüstü başarısını değil, karşılaştırma tabanının elverişsizliğini gösterir: sıralı sürüm, koşut sürümün yararlandığı bellek koşullarından yoksun çalıştırılmıştır.

Hızlanma bir orandır ve değeri, paydaya hangi ölçümün konduğuna bağlıdır. Koşut bir programın tek işlem birimindeki süresi taban alınırsa elde edilen değer göreli hızlanma olur. Bu ölçüm iyimser yönde saparak sonucu abartabilir, çünkü koşut program tek birimde çalışırken de görev bölme ve eşgüdüm yükünü taşır; bu yük paydayı büyütür.

Bilinen en iyi sıralı algoritmanın süresi taban alınırsa elde edilen değer mutlak hızlanma olur ve koşutlaştırmanın gerçek kazancını gösterir. İki taban arasındaki fark büyük olabileceğinden, bildirilen bir hızlanma değerinin hangi tabana göre ölçüldüğü belirtilmedikçe karşılaştırılabilir değildir.

Hızlanma tek bir iş yükü için ölçülür. Bir sınama programı paketinde onlarca program bulunduğunda bunların tek bir sayıyla özetlenmesi gerekir, ancak hızlanma bir oran olduğundan bu özet aritmetik ortalamayla alınamaz.

İki program ile iki makine üzerinden görülebilir:

İki programın iki makinedeki süreleri ve hızlanmalar

Program	A'da süre	B'de süre	B'nin A'ya göre hızlanması	A'nın B'ye göre hızlanması
Birinci	10 s	10 s	1	1
İkinci	100 s	20 s	5	0,2
Aritmetik ortalama	3	0,6
Geometrik ortalama	2,236	0,447

Bir özet ölçütün tutarlı sayılması için, makinelerin rolü değiştirildiğinde sonucun tersine dönmesi beklenir. Aritmetik ortalama bu koşulu sağlamaz: B'nin hızlanması 3 çıkarken tersi 1 / 3 = 0,333 olmalıyken ölçülen 0,6'dır. Geometrik ortalama sağlar: 2,236'nın tersi 0,447'dir ve öteki yönde ölçülen değer de 0,447 çıkar. Hangi makinenin taban alındığı sonucu değiştirmediğinden, sınama programı paketlerinin sonuçları geometrik ortalamayla bildirilir; SPEC paketleri bu yolu izler.

Geometrik ortalamanın karşılığı olmayan yanı da vardır: toplam yürütme süresini yansıtmaz. Çizelgedeki örnekte iki programın toplam süresi A'da 110, B'de 30 saniyedir ve bu orandan çıkan değer 3,667'dir. Paket sonuçlarının bir toplam süre ölçümü değil, ölçüm tabanından bağımsız bir özet olduğu bu yüzden akılda tutulmalıdır.

• Bilgisayar başarımı
• Buyruk başına çevrim
• Ölçeklenebilirlik
• Paralel hesaplama