Dallanma öngörüsü

Dallanma Öngörüsü, bilgisayar mimarisinde çalıştırılacak programın buyruk kümesi içindeki dallanma buyruklarına gelindiğinde koşula göre atlanacağını ya da atlanmayacağını önceden varsayarak veya geçmişine bakıp tahmin ederek öngörüde bulunma işidir. Bugünkü işlemcilerin tasarımında boru hattı (bilgisayar) yöntemi kullanıldığı ve başarım hedeflerinin yüksek olduğu düşünüldüğünde bir dallanmada hangi yöne gidileceğini yüksek doğrulukta tahmin etmek kaçınılmaz olmuştur. Bu öngörü işlemciye dallanmanın sonucunu beklemeden diğer buyrukları işleme imkânı verir. Bu da zamandan kazanç anlamına gelir ki başarımı yükseltir. Bu arada da işlemcinin şimdiki buyruğun işlenmesi bitmeden sonraki buyruğun adresini bilmesi gerekir.

Dallanmayı öngörme boru hatttındaki denetim sorununu çözme ihtiyacından doğmuştur. Dallanmanın olduğu yerde sonucun ne olduğunu bilmeden hareket etmeye çalışmak denetim sorunu oluşturur. Bu sorunu sonuç belli olana kadar durup bekleyerek çözmek yerine, öngörüde bulunarak (tahmin doğru ise devam edip, yanlış ise baştan tekrar deneyip ) çözmek daha doğru bir karar olacaktır.

Dallanmayı öngörme, program sayacının alt bit(en düşük basamak)leriyle erişilen bir sayaç tablosu kullanılarak yapılır. Bu sayaç tablosuna öngörücü denir. Yüksek doğrulukta öngörü için iki bit gerekir; tek bit yeterli olmayabilir çünkü tek bitle sadece bir önceki durum hatırlanabilir.Tek bit ile bir dallanmanın hem başını hem de sonunu yanlış tahmin etme olasılığımız hep vardır. İki bitle ise yanlış tahmin dallanmanın sonunda olmak üzere bir sefere inmiştir.

Dallanmada öngörü yapılsa bile unutulmaması gereken bir durum vardır: Dallanma buyruğunun sonucu anlaşıldığında çoktan diğer buyruklar boru hattına girmiştir. Tahminin yanlış olması durumunda yanlış yerden yakalanan buyruklar boru hattından geri dönemeyeceğine göre buyrukların boru hattından çıkması beklenir.

Aşağıdaki kodun 5 aşamalı (Getir -G-, Çöz -Ç-, Yürüt -Ü-, Bellek -B-, Yaz -Y-) boru hattındaki görünümü üzerinden açıklayalım. Dallanma buyruklarının koşulları yürütme aşamasında çözüldüğü varsayılsın ve sonuçlar yazmaçlara yazıldıkları vuruşta okunabilsin, yürütme sonraki vuruşta başlasın. Dallanma öngörüsü olarak 'atlamadığı' varsayılan bir tasarımda aslında atlaması gereken bir durum karşımıza çıkmış olsun.

     ADD R3,R3,4; 
     LW R9,(R3); 
     BLE R8,R9,B3; 
     MOVE R3,R7; 
     ADD R3,R3,4;
   B3: 
     ADD R6,R6,1;
     ADD R7,R7,1;  

Burada dallanma buyruğu olan 'BLE R8, R9, B3' ün atlayacağı yürütme vuruşunda çözüldüğü anda ardındaki ve öngörü gereği 'MOVE R3, R7 ve ADD R3, R3,4' buyrukları boru hattına girmiş bulunmaktadır. Burada yapacak bir şey yoktur, bu buyrukların boru hattından çıkması beklenecek, daha sonra 'B3' kısmına atlanacaktır.

Dallanma Öngörüsü genel anlamda iki türlü yapılabilir:

Durağan: Tasarımda en baştan dallanma davranışına karar verilir. Dallanmanın her durumda atlayacağını varsaymak bu türden bir öngörüdür (Tersi, yani her zaman atlamayacağını varsaymak da aynı şekilde). Kuşkusuz hata olacaktır; hata olduğu takdirde boru hattını temizleyip diğer durumun buyruklarını boru hattına almak gerekir. Durağan öngörüler döngülerin bolca kullanıldığı programlarda iyi çalışabilir.

Devingen: Dallanmanın geçmişine bakılarak fikir sahibi olunur, programın gelecekte nasıl bir yön izleyeceğine bu şekilde sonradan karar verilir. Burada bir tahmin söz konusudur, programın geçmiş davranışına ait desen, örnek vs. bir tabloda tutulur, program sayacıyla birlikte bu tablo da kullanılarak karar verilir.
Çift Doruklu:Dallanmaların çoğu zaman atlama ya da atlamama davranışı gibi iki kutuplu özelliği söz konusudur.
İki Aşamalı:Geçmişin tutulduğu bir tablo ve buna göre öngörünün yapıldığı ikinci tablo ile iki seviye söz konusudur.
Melez:Farklı öngörücülerin daha yüksek verim almak adına birleştirilerek dallanmaya göre seçimi söz konusudur.

Tipik bir dallanmanın davranışı aslında rastgele değildir; ya çoğu zaman atlarlar ya da atlamazlar. Çift doruklu öngörü de işte, bir dallanmanın bu iki davranıştan hangisini gösterdiğinin ayrımından faydalanır. Öngörücüsü, program sayacının alt bitleriyle adreslenen bir sayaçlar tablosudur. Her sayaç iki bit uzunluktadır. Her atlandığında uygun olan sayaç bir arttırılır; aynı şekilde atlanmadığında uygun olanı bir eksiltilir. En anlamlı bit öngörüyü belirler. Sayacın sıfırdan (00) ve üçten (11) sonra doyuyor olması (yani 11 den sonra artmaz ve 00 dan sonra eksilmez), tekrarlı atlayan dallanmaların atlayacağı, atlamayanların ise atlamayacağı anlamına gelir. Bu 2-bit öngörücüyle art arda iki kez yanlış tahmin yapıldığında öngörü değişir. Küçük öngörücü tablolarda birkaç dallanma aynı sayacı paylaşabilmesine rağmen daha büyükleri için her bir dallanma tek bir sayaca gider. Tahmindeki doğruluk daha az sayıda paylaşılan sayaç olması koşuluyla öngörücü tablosu boyuyla doğru orantılı olarak artar ve SPEC’89 denektaşları ile %93 civarında doygunluğa ulaşır.

Öngörü gerçekleştirimi için farklı bir yol ise kümeli ilişkilendirme metoduyla her sayaca bir de etiket ekleyerek sayaç-dallanma eşleştirmesinde karşılaştırma yoluna gidilmesidir. Bu yol sabit sayıdaki sayaçlar için daha verimlidir. Öngörüde yapılan yanlışlıkların sebebi ise o dallanma için yanlış tahmin yapılması ya da farklı dallanma buyruğunun geçmişinin okunarak tablo adreslemesinde hata yapılmasıdır.

Dallanmaların çoğunlukla yinelenen örüntü (desen) davranışı gösterdiğini göz önünde bulundurursak, çift doruklu öngörüden daha fazlasını yapabiliriz. Şöyle bir döngümüz olsun: for (i=1; i<=4; i++)
Döngünün testi öbeğin sonunda yapılıyorsa, altlayanlar için 1 atlamayanlar için 0 kullanalım, bu dallanma buyruğu ${\displaystyle n}$ sefer çalıştırıldığında ${\displaystyle (1110)^{n}}$ örüntüsünü yaratacaktır. Bu tahmin yönteminin öngörücüsü, biri önceki dallanmaların geçmişini tutan, diğeriyse yine çift doruklu tahmin yapan iki tablodan oluşur. Geçmiş dallanmaların öyküsünü tutmanın farklı yolları vardır: dallanma buyruğunun adresinin alt bitlerini kullanmak ya da kümeli ilişkili geçmiş tablosu tutmak. Böylece ${\displaystyle n}$ kez çalıştırılan dallanmanın atladı ya da atlamadı öyküsünü tutan tablonun sonucu, tahmin yapacak 2-bit sayaçlar tablosunda kullanılarak tahmin yapılır. Ancak biri diğerini bekleyen böyle iki tablonun birlikte kullanılması işlemi yavaşlatacaktır. Burada geçmiş ve sayaçlar tablolarının girişlerinin aynı sayıda olduğunu düşünebiliriz, zira küçük öngörücüler için eğer aşırı geçmiş girişi varsa geçmişi tutmanın pek bir anlamı olmaz. 128 baytın üstü için yerel öngörü daha iyi bir sonuç verir. Büyük öngörücüler için doğruluk, çift dorukluların yanlış tahminini de yarıya indirerek %97,1 e yaklaşır.

Şu an işlenen bir dallanmanın yönü eğer başka dallanma buyruklarının sonucuna kuvvetli bir biçimde bağlıysa, bu önceki dallanmaların sonucu öngörüde kullanılabilir. Şu örneği ele alalım:
if (x<10) : : :
if (x>10) : : :
Burada eğer birinci koşul alındıysa ikinci koşulun alınmayacağını biliriz, yani ikinci koşulun yönünü birinci koşulun yönüne bakarak söyleyebiliriz. Her bir dallanma çoğunlukla aynı yöne gittiği zaman, bundan önceki dallanma dizileri de aynı şekilde tek bir dallanma için yinelenen ama diğer dallanmalar için farklı bir davranış gösterir. Böylelikle bu öngörücü farklı dallanmaları ayırt edebilir. Öngörü, en son yürütülen ${\displaystyle n}$ dallanmanın hareketini bir kaydırmalı kaydedici Genel Geçmiş Yazmacı kullanılarak saklanıp, bu değerin de 2-bit sayaçlar tablosunda kullanılmasıyla yapılır.

Adresleme Seçmeli Genel Geçmişli Öngörücü: Dallanma buyruğu adresi ve genel geçmiş birlikte kullanılarak daha verimli bir öngörü yapılabilir. Gselect denilen bu yaklaşımla adres bitleriyle geçmiş bitleri seçilerek karşılaştırılır, daha çok adres biti mi kullanmalı yoksa geçmiş biti mi karar verilir. Örnek olarak gselect 4/4: hem adres hem de dallanma bitlerinin 4 alt bitini karşılaştırır. 1KB’tan daha küçük öngörücü boyutlarında daha iyi işler.

Adresleme Paylaşmalı Genel Geçmişli Öngörücü: Aynı şekilde ama bu kez, dallanma buyruğu adresi ve genel geçmiş bitlerinin özel veya işlemine tutulması, her birinin tek başına sağladığı yarardan daha fazlasını verir; gshare 8/8 ile gselect 4/4 ün fark edemediği durumları ayıt etmiş oluruz. Bu Gshare yaklaşımı 256 bayttan büyük öngörücülerde iyi işler.

Adresleme Bölmeli Genel Geçmişli Öngörücü: Çoklu tablo girişi, iki farklı dallanmanın aynı girişe eşlenmesi gibi bir sorun yaratır. Aslında bu durum örüntü geçmiş tablosunun küçük olmasından ziyade bu tablodaki ilişkilendirme sorunundan kaynaklanır. Gskew yöntemi ile geçmiş tablosu parçalara bölünüp her birine farklı hash fonksiyonuyla erişilir, daha küçük bir yanlış tahmin oranına ulaşılır.

Her dallanma öngörü yönteminin her ayrı durumda farklı avantajları vardır. Seçimin duruma göre yapılması gerekir. Peki, bu öngörücüleri birleştirerek yerel geçmiş öngörüsü kadar doğru ama genel geçmiş öngörüsü kadar hızlı bir sonuç elde edilebilir mi? ref: McFarling Combining Branch Predictors 21 Kasım 2008 tarihinde Wayback Machine sitesinde arşivlendi. Bir seçici devre kullanılarak her bir dallanma için hangi öngörücü daha iyiyse onun seçilmesi mümkündür. Burada seçici yine bir 2-bitli doygunluğa ulaşabilen bir sayaçtır. Örnek olarak X1 ve X2 olarak iki tane öngörücü kullanıyor olalım. Sayaç, X1-X2 işlemine göre artar, eksilir ya da değişmez. Seçilen öngörücünün sonucuyla tahmin yapılır. Yapılan denemeler sonucu birleştirilmiş öngörücülerin sonucu ayrı ayrı olanlardan daha tatmin edici çıkmıştır. Sonuç: dallanma öngörüsünün doğruluk oranı yükselmiş olur(sayma sayısı programlarında %96 dan yüksek).

Bu yöntem, yine birden fazla dallanmanın tabloda birden fazla girişe eşlenmesi sorununa çözüm olarak ortaya çıkmıştır. Öngörücüsünde bir yargı biti, dallanmanın yönüne göre Dallanma Hedef Belleğindeki her bir dallanma için, DHB’ne yazılmadan önce atanır. Bu yargı bitinin öngörüsüne göre artık dallanma atladı ya da atlamadı’dan onaylandı ya da onaylanmadı’ya dönüşür. Burada geçmiş tablosundan alınacak onay/değil sonucu aynı gshare’deki gibi adres ve geçmiş bitleri özel veya işlemiyle bulunur. DHB’den gelecek yargı biti ile birlikte bu sonuç kullanılarak öngörü yapılır.

Bu yöntemle ana amaç geçmiş tablolarındaki fazla bilgiyi azaltmaktır. Tek bir bitle yüksek eğilimli dallanmaları yüksek doğrulukta tahmin etmek mümkündür. Bu tip dallanmaları geçmiş tablosundan filtrelemek bir yargı biti ve doyan bir sayaçla her bir dallanma için yapılabilir. DHB’ne dallanma tanıtılırken yargı biti dallanmanın yönüne kurulur ve sayaç başlatılır. Dallanma çekilirken eğer yargı biti dallanma yönü ile aynıysa sayaç arttırılır. Eğer değilse sayaç sıfırlanır. Eğer sayaç doymamışsa öngörü, geçmiş tablosu kullanılarak yapılır; ama doymuşsa öngörü için yargı biti yönünde olacaktır.

Yapay sinir ağları kullanılarak kontrol-akış ve işlem kodu bilgisi gibi program özellikleri yardımıyla derleme zamanında durağan bir dallanma öngörüsü yapılabilir. Durağan dallanmaların %75 lik doğruluğa sahip olduğu düşünüldüğünde, yukarıdaki gibi program bilgileriyle sinirsel ağların eğitilmesi ile %80 lik gibi bir doğruluğa ulaşılması sevindiricidir.

Sinirsel ağlarla ilk kez devingen dallanma öngörüsü ise 1999’da Lucian Vintan tarafından önerilmiştir. Vintan burada bir sinirsel yöntem olan vektör nicemleme kullanmıştır.

Algılayıcılı(Perceptron) Dallanma Öngörüsü: ref: Dynamic Branch Prediction with Perceptrons 5 Eylül 2008 tarihinde Wayback Machine sitesinde arşivlendi. Burada, donanımsal gerçekleştirimi verimli, bir basit doğrusal yapay sinir hücresi olan algılayıcılar kullanılır. Ayrıca ağırlıklarını inceleyerek öğrendikleriyle matematiksel ilişki kurup verdikleri kararı anlamak kolaydır. Algılayıcılar, öngörücülere külfet olan uzun geçmişleri de emerek tüm zamanların en etkili tek parça öngörücüsü olarak geleceğin mikroişlemcileri için umut vadeden bir bileşendir. Bir algılayıcı bir hedef Boole işlevi öğrenir. Burada işlenenler genel geçmiş kaydırmalı kaydedicisinin bitleridir. Hedef işlev de belli bir dallanmanın alınıp alınmayacağını tahmin eder.

Yol Tabanlı Sinirsel Dallanma Öngörüsü:ref:Jimenez,Fast Path-Based Neural Branch Prediction Burada dallanmanın adresinden ziyade dallanmaya ulaşmak için izlenen yolu taban alan sinirsel ağırlıklar seçilir. Yani bir dallanma örüntü geçmişiyle ilgili olduğu kadar yol geçmişiyle de ilgilidir. Hatta bir algılayıcı kullanılarak ağırlıklar vektörü dinamik olarak seçilebilirse öngörü daha da hızlanmış olur.

Parçalı Doğrusal Dallanma Öngörüsü: ref:Jimenez,Piecewise Linear Branch Prediction Bir dallanma atlar olarak öngörülebilir, tersi durumda ise öngörüsü atlamaz olur. Bu dallanmaya giden birden fazla yolun olması, tahmin için birden fazla doğrusal fonksiyon olması anlamına gelir. Bu yöntem ile atlaması öngörülen yollar ile atlamamsı öngörülen yollar ayrılır.

• N. Eden, The YAGS Branch Prediction Scheme 12 Mayıs 2008 tarihinde Wayback Machine sitesinde arşivlendi.
• R. Sendağ, Branch Misprediction Prediction: Complementary Branch Predictors^[]
• J.T: Strasser, EVALUATION OF BRANCH PREDICTION ON PROCESSOR ENERGY CONSUMPTION
• O. Acıiçmez, On the Power of Simple Branch Prediction Analysis 24 Ağustos 2007 tarihinde Wayback Machine sitesinde arşivlendi.

• Branch Prediction in the Pentium Family
• İşlemcilerde dallanma tahmini üzerine algoritmalar 22 Aralık 2007 tarihinde Wayback Machine sitesinde arşivlendi.
• Terimler hakkında kısa bilgiler^[]
• Dallanma öngörüsü üzerine bildiriler27 Aralık 2007 tarihinde Wayback Machine sitesinde arşivlendi.