Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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 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 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.
Örnek
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 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; | buyruk | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ADD R3,R3,4; | G | Ç | Ü | B | Y | ||||||||||
| LW R9, (R3); | G | Ç | Ç | Ç | Ü | B | Y | ||||||||
| BLE R8,R9,B3; | G | G | G | Ç | Ç | Ç | Ü | B | Y | ||||||
| MOVE R3,R7; | G | G | G | Ç | Ü | B | Y | ||||||||
| ADD R3,R3,4; | G | Ç | Ü | B | Y | ||||||||||
| ADD R6,R6,1; | G | Ç | Ü | B | Y | ||||||||||
| ADD R7,R7,1; | G | Ç | Ü | B | Y |
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örme Yöntemleri
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.
Çift Doruklu Dallanma Öngörüsü
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. ö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 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.
Yerel Geçmişe Bağlı 2 Aşamalı Dallanma Öngörüsü
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 
sefer çalıştırıldığında 
ö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 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 ü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.
Genel Geçmişe Bağlı 2 Aşamalı Dallanma Öngörüsü
Ş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 dallanmanın hareketini bir 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ı erişilir, daha küçük bir yanlış tahmin oranına ulaşılır.
Dallanma Öngörücülerini Birleştirme
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 . Bir 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).
Onaylamalı Dallanma Öngörüsü
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 , 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 işlemiyle bulunur. DHB’den gelecek yargı biti ile birlikte bu sonuç kullanılarak öngörü yapılır.
Filtrelemeli Dallanma Öngörüsü
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ı Kullanarak Dallanma Öngörüsü
Yapay sinir ağları kullanılarak ve işlem kodu bilgisi gibi program özellikleri yardımıyla 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 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 tarafından önerilmiştir. Vintan burada bir sinirsel yöntem olan kullanmıştır.
(Perceptron) Dallanma Öngörüsü: ref: Dynamic Branch Prediction with Perceptrons 5 Eylül 2008 tarihinde Wayback Machine sitesinde . Burada, donanımsal gerçekleştirimi verimli, bir basit doğrusal olan 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 için umut vadeden bir bileşendir. Bir algılayıcı bir hedef öğ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ü: Burada dallanmanın adresinden ziyade dallanmaya ulaşmak için izlenen yolu taban alan 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 dinamik olarak seçilebilirse öngörü daha da hızlanmış olur.
Parçalı Doğrusal Dallanma Öngörüsü: 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.
Ayrıca bakınız
- N. Eden, The YAGS Branch Prediction Scheme 12 Mayıs 2008 tarihinde Wayback Machine sitesinde .
- R. Sendağ, Branch Misprediction Prediction: Complementary Branch Predictors[]
- O. Acıiçmez, On the Power of Simple Branch Prediction Analysis 24 Ağustos 2007 tarihinde Wayback Machine sitesinde .
Dış bağlantılar
- İşlemcilerde dallanma tahmini üzerine algoritmalar 22 Aralık 2007 tarihinde Wayback Machine sitesinde .
- Terimler hakkında kısa bilgiler[]
- Dallanma öngörüsü üzerine bildiriler27 Aralık 2007 tarihinde Wayback Machine sitesinde .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Dallanma Ongorusu bilgisayar mimarisinde calistirilacak programin buyruk kumesi icindeki dallanma buyruklarina gelindiginde kosula gore atlanacagini ya da atlanmayacagini onceden varsayarak veya gecmisine bakip tahmin ederek ongorude bulunma isidir Bugunku islemcilerin tasariminda boru hatti bilgisayar yontemi kullanildigi ve hedeflerinin yuksek oldugu dusunuldugunde bir dallanmada hangi yone gidilecegini yuksek dogrulukta tahmin etmek kacinilmaz olmustur Bu ongoru islemciye dallanmanin sonucunu beklemeden diger buyruklari isleme imkani verir Bu da zamandan kazanc anlamina gelir ki basarimi yukseltir Bu arada da islemcinin simdiki buyrugun islenmesi bitmeden sonraki adresini bilmesi gerekir Dallanmayi ongorme boru hatttindaki denetim sorununu cozme ihtiyacindan dogmustur Dallanmanin oldugu yerde sonucun ne oldugunu bilmeden hareket etmeye calismak denetim sorunu olusturur Bu sorunu sonuc belli olana kadar durup bekleyerek cozmek yerine ongorude bulunarak tahmin dogru ise devam edip yanlis ise bastan tekrar deneyip cozmek daha dogru bir karar olacaktir Dallanmayi ongorme program sayacinin alt bit en dusuk basamak leriyle erisilen bir sayac tablosu kullanilarak yapilir Bu sayac tablosuna ongorucu denir Yuksek dogrulukta ongoru icin iki bit gerekir tek bit yeterli olmayabilir cunku tek bitle sadece bir onceki durum hatirlanabilir Tek bit ile bir dallanmanin hem basini hem de sonunu yanlis tahmin etme olasiligimiz hep vardir Iki bitle ise yanlis tahmin dallanmanin sonunda olmak uzere bir sefere inmistir Dallanmada ongoru yapilsa bile unutulmamasi gereken bir durum vardir Dallanma buyrugunun sonucu anlasildiginda coktan diger buyruklar boru hattina girmistir Tahminin yanlis olmasi durumunda yanlis yerden yakalanan buyruklar boru hattindan geri donemeyecegine gore buyruklarin boru hattindan cikmasi beklenir OrnekAsagidaki kodun 5 asamali Getir G Coz C Yurut U Bellek B Yaz Y boru hattindaki gorunumu uzerinden aciklayalim Dallanma buyruklarinin kosullari yurutme asamasinda cozuldugu varsayilsin ve sonuclar yazmaclara yazildiklari vurusta okunabilsin yurutme sonraki baslasin Dallanma ongorusu olarak atlamadigi varsayilan bir tasarimda aslinda atlamasi gereken bir durum karsimiza cikmis 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 buyrukADD R3 R3 4 GCUBYLW R9 R3 GCCCUBYBLE R8 R9 B3 GGGCCCUBYMOVE R3 R7 GGGCUBYADD R3 R3 4 GCUBYADD R6 R6 1 GCUBYADD R7 R7 1 GCUBY Burada dallanma buyrugu olan BLE R8 R9 B3 un atlayacagi yurutme vurusunda cozuldugu anda ardindaki ve ongoru geregi MOVE R3 R7 ve ADD R3 R3 4 buyruklari boru hattina girmis bulunmaktadir Burada yapacak bir sey yoktur bu buyruklarin boru hattindan cikmasi beklenecek daha sonra B3 kismina atlanacaktir Dallanma Ongorme YontemleriDallanma Ongorusu genel anlamda iki turlu yapilabilir Duragan Tasarimda en bastan dallanma davranisina karar verilir Dallanmanin her durumda atlayacagini varsaymak bu turden bir ongorudur Tersi yani her zaman atlamayacagini varsaymak da ayni sekilde Kuskusuz hata olacaktir hata oldugu takdirde boru hattini temizleyip diger durumun buyruklarini boru hattina almak gerekir Duragan ongoruler dongulerin bolca kullanildigi programlarda iyi calisabilir Devingen Dallanmanin gecmisine bakilarak fikir sahibi olunur programin gelecekte nasil bir yon izleyecegine bu sekilde sonradan karar verilir Burada bir tahmin soz konusudur programin gecmis davranisina ait desen ornek vs bir tabloda tutulur program sayaciyla birlikte bu tablo da kullanilarak karar verilir Cift Doruklu Dallanmalarin cogu zaman atlama ya da atlamama davranisi gibi iki kutuplu ozelligi soz konusudur Iki Asamali Gecmisin tutuldugu bir tablo ve buna gore ongorunun yapildigi ikinci tablo ile iki seviye soz konusudur Melez Farkli ongoruculerin daha yuksek verim almak adina birlestirilerek dallanmaya gore secimi soz konusudur Cift Doruklu Dallanma OngorusuTipik bir dallanmanin davranisi aslinda rastgele degildir ya cogu zaman atlarlar ya da atlamazlar Cift doruklu ongoru de iste bir dallanmanin bu iki davranistan hangisini gosterdiginin ayrimindan faydalanir Ongorucusu program sayacinin alt bitleriyle adreslenen bir sayaclar tablosudur Her sayac iki bit uzunluktadir Her atlandiginda uygun olan sayac bir arttirilir ayni sekilde atlanmadiginda uygun olani bir eksiltilir ongoruyu belirler Sayacin sifirdan 00 ve ucten 11 sonra doyuyor olmasi yani 11 den sonra artmaz ve 00 dan sonra eksilmez tekrarli atlayan dallanmalarin atlayacagi atlamayanlarin ise atlamayacagi anlamina gelir Bu 2 bit ongorucuyle art arda iki kez yanlis tahmin yapildiginda ongoru degisir Kucuk ongorucu tablolarda birkac dallanma ayni sayaci paylasabilmesine ragmen daha buyukleri icin her bir dallanma tek bir sayaca gider Tahmindeki dogruluk daha az sayida paylasilan sayac olmasi kosuluyla ongorucu tablosu boyuyla dogru orantili olarak artar ve SPEC 89 denektaslari ile 93 civarinda doygunluga ulasir Ongoru gerceklestirimi icin farkli bir yol ise metoduyla her sayaca bir de etiket ekleyerek sayac dallanma eslestirmesinde karsilastirma yoluna gidilmesidir Bu yol sabit sayidaki sayaclar icin daha verimlidir Ongorude yapilan yanlisliklarin sebebi ise o dallanma icin yanlis tahmin yapilmasi ya da farkli dallanma buyrugunun gecmisinin okunarak tablo adreslemesinde hata yapilmasidir Yerel Gecmise Bagli 2 Asamali Dallanma OngorusuDallanmalarin cogunlukla yinelenen oruntu desen davranisi gosterdigini goz onunde bulundurursak cift doruklu ongoruden daha fazlasini yapabiliriz Soyle bir dongumuz olsun for i 1 i lt 4 i Dongunun testi obegin sonunda yapiliyorsa altlayanlar icin 1 atlamayanlar icin 0 kullanalim bu dallanma buyrugu n displaystyle n sefer calistirildiginda 1110 n displaystyle 1110 n oruntusunu yaratacaktir Bu tahmin yonteminin ongorucusu biri onceki dallanmalarin gecmisini tutan digeriyse yine cift doruklu tahmin yapan iki tablodan olusur Gecmis dallanmalarin oykusunu tutmanin farkli yollari vardir dallanma buyrugunun adresinin alt bitlerini kullanmak ya da kumeli iliskili gecmis tablosu tutmak Boylece n displaystyle n kez calistirilan dallanmanin atladi ya da atlamadi oykusunu tutan tablonun sonucu tahmin yapacak 2 bit sayaclar tablosunda kullanilarak tahmin yapilir Ancak biri digerini bekleyen boyle iki tablonun birlikte kullanilmasi islemi yavaslatacaktir Burada gecmis ve sayaclar tablolarinin girislerinin ayni sayida oldugunu dusunebiliriz zira kucuk ongoruculer icin eger asiri gecmis girisi varsa gecmisi tutmanin pek bir anlami olmaz 128 ustu icin yerel ongoru daha iyi bir sonuc verir Buyuk ongoruculer icin dogruluk cift doruklularin yanlis tahminini de yariya indirerek 97 1 e yaklasir Genel Gecmise Bagli 2 Asamali Dallanma OngorusuSu an islenen bir dallanmanin yonu eger baska dallanma buyruklarinin sonucuna kuvvetli bir bicimde bagliysa bu onceki dallanmalarin sonucu ongorude kullanilabilir Su ornegi ele alalim if x lt 10 if x gt 10 Burada eger birinci kosul alindiysa ikinci kosulun alinmayacagini biliriz yani ikinci kosulun yonunu birinci kosulun yonune bakarak soyleyebiliriz Her bir dallanma cogunlukla ayni yone gittigi zaman bundan onceki dallanma dizileri de ayni sekilde tek bir dallanma icin yinelenen ama diger dallanmalar icin farkli bir davranis gosterir Boylelikle bu ongorucu farkli dallanmalari ayirt edebilir Ongoru en son yurutulen n displaystyle n dallanmanin hareketini bir Genel Gecmis Yazmaci kullanilarak saklanip bu degerin de 2 bit sayaclar tablosunda kullanilmasiyla yapilir Adresleme Secmeli Genel Gecmisli Ongorucu Dallanma buyrugu adresi ve genel gecmis birlikte kullanilarak daha verimli bir ongoru yapilabilir Gselect denilen bu yaklasimla adres bitleriyle gecmis bitleri secilerek karsilastirilir daha cok adres biti mi kullanmali yoksa gecmis biti mi karar verilir Ornek olarak gselect 4 4 hem adres hem de dallanma bitlerinin 4 alt bitini karsilastirir 1KB tan daha kucuk ongorucu boyutlarinda daha iyi isler Adresleme Paylasmali Genel Gecmisli Ongorucu Ayni sekilde ama bu kez dallanma buyrugu adresi ve genel gecmis bitlerinin ozel veya islemine tutulmasi her birinin tek basina sagladigi yarardan daha fazlasini verir gshare 8 8 ile gselect 4 4 un fark edemedigi durumlari ayit etmis oluruz Bu Gshare yaklasimi 256 bayttan buyuk ongoruculerde iyi isler Adresleme Bolmeli Genel Gecmisli Ongorucu Coklu tablo girisi iki farkli dallanmanin ayni girise eslenmesi gibi bir sorun yaratir Aslinda bu durum oruntu gecmis tablosunun kucuk olmasindan ziyade bu tablodaki iliskilendirme sorunundan kaynaklanir Gskew yontemi ile gecmis tablosu parcalara bolunup her birine farkli erisilir daha kucuk bir yanlis tahmin oranina ulasilir Dallanma Ongoruculerini BirlestirmeHer dallanma ongoru yonteminin her ayri durumda farkli avantajlari vardir Secimin duruma gore yapilmasi gerekir Peki bu ongoruculeri birlestirerek yerel gecmis ongorusu kadar dogru ama genel gecmis ongorusu kadar hizli bir sonuc elde edilebilir mi ref McFarling Combining Branch Predictors 21 Kasim 2008 tarihinde Wayback Machine sitesinde Bir devre kullanilarak her bir dallanma icin hangi ongorucu daha iyiyse onun secilmesi mumkundur Burada secici yine bir 2 bitli doygunluga ulasabilen bir sayactir Ornek olarak X1 ve X2 olarak iki tane ongorucu kullaniyor olalim Sayac X1 X2 islemine gore artar eksilir ya da degismez Secilen ongorucunun sonucuyla tahmin yapilir Yapilan denemeler sonucu birlestirilmis ongoruculerin sonucu ayri ayri olanlardan daha tatmin edici cikmistir Sonuc dallanma ongorusunun dogruluk orani yukselmis olur sayma sayisi programlarinda 96 dan yuksek Onaylamali Dallanma OngorusuBu yontem yine birden fazla dallanmanin tabloda birden fazla girise eslenmesi sorununa cozum olarak ortaya cikmistir Ongorucusunde bir dallanmanin yonune gore Dallanma Hedef Bellegindeki her bir dallanma icin DHB ne yazilmadan once atanir Bu yargi bitinin ongorusune gore artik dallanma atladi ya da atlamadi dan onaylandi ya da onaylanmadi ya donusur Burada gecmis tablosundan alinacak onay degil sonucu ayni gshare deki gibi adres ve gecmis bitleri islemiyle bulunur DHB den gelecek yargi biti ile birlikte bu sonuc kullanilarak ongoru yapilir Filtrelemeli Dallanma OngorusuBu yontemle ana amac gecmis tablolarindaki fazla bilgiyi azaltmaktir Tek bir bitle yuksek egilimli dallanmalari yuksek dogrulukta tahmin etmek mumkundur Bu tip dallanmalari gecmis tablosundan filtrelemek bir yargi biti ve doyan bir sayacla her bir dallanma icin yapilabilir DHB ne dallanma tanitilirken yargi biti dallanmanin yonune kurulur ve sayac baslatilir Dallanma cekilirken eger yargi biti dallanma yonu ile ayniysa sayac arttirilir Eger degilse sayac sifirlanir Eger sayac doymamissa ongoru gecmis tablosu kullanilarak yapilir ama doymussa ongoru icin yargi biti yonunde olacaktir Yapay Sinir Aglari Kullanarak Dallanma OngorusuYapay sinir aglari kullanilarak ve islem kodu bilgisi gibi program ozellikleri yardimiyla duragan bir dallanma ongorusu yapilabilir Duragan dallanmalarin 75 lik dogruluga sahip oldugu dusunuldugunde yukaridaki gibi program bilgileriyle egitilmesi ile 80 lik gibi bir dogruluga ulasilmasi sevindiricidir Sinirsel aglarla ilk kez devingen dallanma ongorusu ise 1999 da tarafindan onerilmistir Vintan burada bir sinirsel yontem olan kullanmistir Perceptron Dallanma Ongorusu ref Dynamic Branch Prediction with Perceptrons 5 Eylul 2008 tarihinde Wayback Machine sitesinde Burada donanimsal gerceklestirimi verimli bir basit dogrusal olan kullanilir Ayrica agirliklarini inceleyerek ogrendikleriyle matematiksel iliski kurup verdikleri karari anlamak kolaydir Algilayicilar ongoruculere kulfet olan uzun gecmisleri de emerek tum zamanlarin en etkili tek parca ongorucusu olarak gelecegin icin umut vadeden bir bilesendir Bir algilayici bir hedef ogrenir Burada islenenler genel gecmis kaydirmali kaydedicisinin bitleridir Hedef islev de belli bir dallanmanin alinip alinmayacagini tahmin eder Yol Tabanli Sinirsel Dallanma Ongorusu Burada dallanmanin adresinden ziyade dallanmaya ulasmak icin izlenen yolu taban alan secilir Yani bir dallanma oruntu gecmisiyle ilgili oldugu kadar yol gecmisiyle de ilgilidir Hatta bir algilayici kullanilarak dinamik olarak secilebilirse ongoru daha da hizlanmis olur Parcali Dogrusal Dallanma Ongorusu Bir dallanma atlar olarak ongorulebilir tersi durumda ise ongorusu atlamaz olur Bu dallanmaya giden birden fazla yolun olmasi tahmin icin birden fazla dogrusal fonksiyon olmasi anlamina gelir Bu yontem ile atlamasi ongorulen yollar ile atlamamsi ongorulen yollar ayrilir Ayrica bakinizN Eden The YAGS Branch Prediction Scheme 12 Mayis 2008 tarihinde Wayback Machine sitesinde R Sendag Branch Misprediction Prediction Complementary Branch Predictors olu kirik baglanti O Aciicmez On the Power of Simple Branch Prediction Analysis 24 Agustos 2007 tarihinde Wayback Machine sitesinde Dis baglantilarIslemcilerde dallanma tahmini uzerine algoritmalar 22 Aralik 2007 tarihinde Wayback Machine sitesinde Terimler hakkinda kisa bilgiler olu kirik baglanti Dallanma ongorusu uzerine bildiriler27 Aralik 2007 tarihinde Wayback Machine sitesinde