Dallanma öngörüsü

Dallanma öngörüsü, boru hattı kullanan bir işlemcinin, bir dallanma buyruğunun sonucu daha belli olmadan hangi yönden devam edeceğine karar vermesini sağlayan yöntemdir. Boru hattı her çevrimde yeni bir buyruk getirmeyi sürdürür, oysa koşullu bir dallanmanın atlayıp atlamayacağı ancak buyruk yürütme aşamasına ulaştığında belli olur. Aradaki çevrimlerde sonraki buyruğun nereden getirileceğinin bilinmemesine denetim sorunu adı verilir. Dallanma öngörüsü, bu sorunu boru hattını durdurmadan aşmak için geliştirilmiştir.

İşlemci bir yön öngörür ve o yoldaki buyrukları öngörülü olarak işlemeye başlar. Koşul çözüldüğünde öngörü doğru çıkarsa yapılan iş kalıcılaşır ve dallanma boru hattında hiç boşluk bırakmamış olur. Öngörü yanlış çıkarsa yanlış yoldan getirilen bütün buyruklar iptal edilir, boru hattı boşaltılır ve doğru adresten yeniden başlanır. Bu kayba dallanma cezası denir ve bedeli boru hattı derinleştikçe büyür.

Öngörücüler, kararı önceden belirlenmiş sabit bir kurala bağlayan durağan öngörücüler ile dallanmanın çalışma sırasındaki geçmişini tutup ona göre karar veren devingen öngörücüler olarak ikiye ayrılır. Devingen öngörü 1980'lerin başında iki bitlik sayaçlarla başlamış, geçmiş çizelgeleri ve birden çok öngörücüyü birleştiren yapılarla gelişmiştir. Öngörü doğruluğu bugünkü işlemcilerde hem başarımı hem de enerji tüketimini doğrudan etkilediğinden, dallanma öngörücüsü mikromimarinin vazgeçilmez bir bileşeni sayılır.

Boru hattı yöntemiyle çalışan bir işlemci buyrukları birer birer, baştan sona yürütmez. Her buyruğu birkaç aşamaya böler ve her çevrimde boru hattına yeni bir buyruk alır. Böylece birden çok buyruk aynı anda, farklı aşamalarda ilerler. Bu düzenin sürmesi için işlemcinin her çevrimde bir sonraki buyruğun adresini biliyor olması gerekir.

Koşullu dallanma buyrukları bu bilgiyi geciktirir. Beş aşamalı klasik bir boru hattında, getirilen buyruğun dallanma olduğu ancak Çöz aşamasında anlaşılır, koşulun sonucu ise Yürüt aşamasında belli olur. Boru hattı bu sırada durmadığından, arkadan gelen buyruklar koşul bilinmeden çoktan getirilmiş olur ve bunların doğru yoldan gelip gelmediği belirsizdir. Sonraki buyruğun hangi adresten getirileceğinin bilinmemesinden doğan bu duruma denetim sorunu adı verilir.

Sorunu çözmenin en yalın yolu beklemektir. İşlemci koşul çözülene kadar yeni buyruk getirmez ve boru hattına boş çevrimler girer. Bu kesin bir çözümdür ama pahalıdır, çünkü boru hattının sağladığı kazanç her çevrimde bir aşamanın tamamlanmasına dayanır. Dallanma buyrukları programlarda seyrek olmadığından, her dallanmada birkaç çevrim yitirmek toplam başarımı belirgin biçimde düşürür.

Beklemeden çözüm arayan üç yaklaşım geliştirilmiştir. Geciktirilmiş dallanmada, dallanma buyruğunun hemen ardında gecikme yuvası adı verilen bir konum bulunur. Derleyici buraya, dallanma hangi yöne giderse gitsin çalışması sakınca doğurmayan yararlı bir buyruk yerleştirir. Yöntem MIPS gibi eski RISC mimarilerinde kullanılmış, RISC-V'de ise derleyiciyi karmaşıklaştırdığı için bilinçli olarak yer verilmemiştir. Durağan öngörüde dallanmanın hep aynı yöne gideceği varsayılır. Devingen öngörüde ise karar, o dallanmanın çalışma sırasındaki geçmişine bakılarak verilir. Dallanma öngörüsü son iki yaklaşımın ortak adıdır ve bugünkü işlemcilerde denetim sorununun başlıca çözümüdür.

Bir dallanma öngörücüsünün iki ayrı soruyu yanıtlaması gerekir. Birincisi dallanmanın atlayıp atlamayacağı, ikincisi atlayacaksa hangi adrese gideceğidir. Bu iki iş ayrı düzeneklerle yapılır ve ikisi birlikte çalışmadan boru hattı kesintisiz beslenemez.

Öngörünün, buyruk daha çözülmeden Getir aşamasında yapılması gerekir. İşlemcinin o anda elinde yalnızca program sayacının değeri vardır. Program sayacı bu aşamada birden çok birime birden verilir. Buyruk önbelleği o adresteki buyruğu getirirken, dallanma hedef ara belleği ile öngörücü de aynı adrese bakarak dallanmaya ilişkin kararı hazırlar. Öngörücülerin, daha önce görülmüş dallanmalar hakkında tuttuğu bilgiye program sayacı üzerinden erişmesinin nedeni budur.

İşleyiş bir döngü biçimindedir. Öngörücü bir yön üretir, işlemci o yoldan buyruk getirmeyi sürdürür, koşul çözüldüğünde gerçek sonuç ile öngörü karşılaştırılır ve öngörücünün tuttuğu bilgi bu sonuca göre güncellenir. Böylece aynı dallanmaya yeniden gelindiğinde karar, o dallanmanın geçmiş davranışına dayanmış olur.

Öngörü doğru çıkarsa öngörülü olarak yürütülen buyrukların sonuçları kalıcılaşır. Yanlış çıkarsa bu buyrukların yazmaçlara ve belleğe kalıcı bir etki bırakmadan iptal edilmesi gerekir. İşlemci boru hattını boşaltır ve doğru adresten yeniden başlar. Öngörücünün sakladığı bilginin nasıl kodlandığı tasarımdan tasarıma değişir. En yaygın çözüm, her dallanma için iki bitlik doyan bir sayaç tutmaktır.

Öngörücü dallanmanın atlayacağına karar verse bile, boru hattının bir sonraki çevrimde hangi adresten buyruk getireceğini bilmesi gerekir. Dallanma hedefi normalde buyruk çözüldükten sonra hesaplanır. Oysa Getir aşamasında işlemci, getirdiği buyruğun dallanma olup olmadığını bile henüz bilmez. Bu yüzden yönün öngörülmesi tek başına yetmez, hedef adresin de öngörülmesi gerekir.

Bu iş için dallanma hedef ara belleği (branch target buffer, BTB) kullanılır. Ara bellek, daha önce karşılaşılmış dallanma buyrukları için hedef adresleri saklayan küçük bir çizelgedir ve yapı bakımından bir önbelleğe benzer. Her girdide, dallanma buyruğunu tanıtan bir etiket ile o dallanmanın hedef adresi bulunur. Bazı tasarımlarda yön öngörüsünü tutan sayaç da aynı girdiye gömülür.

İşlemci her çevrimde program sayacıyla bu çizelgeye bakar. Eşleşme bulunursa getirilmekte olan buyruğun daha önce görülmüş bir dallanma olduğu anlaşılır ve saklanan hedef adres, sonraki çevrimde getirilecek adres olarak kullanılır. Eşleşme yoksa akış sıradaki buyrukla sürer. Böylece dallanma, buyruk çözülmeden hem tanınmış hem de hedefi öngörülmüş olur. Çizelgenin boyutu, ilişkilendirme derecesi ve girdi değiştirme yöntemi öngörü doğruluğunu doğrudan etkiler.

Dallanma hedef ara belleği her dallanma için tek bir hedef adres saklar. Koşullu dallanmalarda bu yeterlidir, çünkü hedef buyruğun içinde sabit olarak yazılıdır ve hiç değişmez. Hedefini bir yazmaçtan ya da bellekten alan dolaylı dallanmalarda ise durum başkadır. Aynı dallanma buyruğu her çalıştığında başka bir adrese gidebilir. Sanal işlev çağrıları, işlev göstergeleri üzerinden yapılan çağrılar ve çok dallı seçim yapıları bu türdendir.

Bu dallanmalar için ayrı bir hedef öngörücüsü kullanılır. Yön öngörüsünde olduğu gibi burada da geçmişten yararlanılır. Hedef çizelgesi yalnız dallanmanın adresiyle değil, adres ile dallanma geçmişinin karmasıyla dizinlenir. Böylece aynı dolaylı dallanmanın başka geçmişlerde gittiği başka hedefler ayrı girdilerde tutulabilir ve her biri kendi bağlamında doğru öngörülür.

Altyordam dönüşleri dolaylı dallanmaların özel bir durumudur ve daha kolay çözülür. Bir altyordam programın başka başka yerlerinden çağrıldığından dönüş adresi her seferinde değişir, bu yüzden tek hedef saklayan bir ara bellek dönüşleri kötü öngörür. Ama çağrılarla dönüşler iç içe geçmiş bir düzen kurar, en son çağrılan altyordam ilk döner. Bu düzen bir yığıtla tam olarak karşılanır. Her altyordam çağrısında dönüş adresi bir yığıta itilir, her dönüşte yığıtın tepesinden çekilip hedef olarak kullanılır. Yığıt, iç içe geçen çağrıları tutacak kadar derin olduğu sürece dönüş öngörüsünün doğruluğu çok yüksektir. Bu nedenle bugünkü işlemcilerin öngörü birimlerinde dönüş adresi yığıtı ayrı bir yapı olarak bulunur.

Aşağıdaki RISC-V kodu, aşamaları Getir (G), Çöz (Ç), Yürüt (Y), Bellek (B) ve Sonucu Yaz (S) olan beş aşamalı bir boru hattında yürütülmektedir. Veri yönlendirmesinin bulunmadığı, bir yazmacın Sonucu Yaz aşamasında yazıldığı çevrimde okunabildiği ve dallanma koşulunun Yürüt aşamasında çözüldüğü varsayılmıştır. Öngörücü dallanmanın atlamayacağını öngörmüştür, oysa dallanma atlayacaktır.

        lw    a1, 0(t0)
        ble   a0, a1, ELSE
        li    t0, 1
        j     SON
ELSE:   li    t0, 2
SON:

lw buyruğu a1 yazmacını beşinci çevrimde yazar. ble bu yazmacı okuduğu için Çöz aşamasında üç çevrim bekler ve dallanmanın koşulu ancak altıncı çevrimde çözülür. Bu sırada öngörülen yoldan iki buyruk boru hattına girmiştir. Koşul çözülünce öngörünün yanlış olduğu anlaşılır ve bu iki buyruk iptal edilir, yazmaçlara ve belleğe hiçbir etkileri olmaz. Doğru yoldaki buyruk yedinci çevrimde getirilir ve boru hattı buradan sürer.

Öngörünün tuttuğu ancak dallanma koşulu çözüldüğünde belli olur. O ana dek getirilen buyrukların hepsi koşulludur, çünkü öngörü yanlış çıkarsa hiçbiri kalıcı bir iz bırakmamalıdır.

Yanılma anlaşıldığında üç iş birden yapılır. Yanlış yoldan getirilen buyruklar iptal edilir ve yazmaçlara ile belleğe hiçbir şey yazmadan boru hattından atılır. Buyruk getirme, dallanmanın gerçek hedefinden yeniden başlatılır. Üçüncü olarak öngörücünün kendi durumu onarılır.

Üçüncüsü ilk bakışta görünmez ama gereklidir. Genel geçmiş yazmacı, dallanmanın sonucu beklenmeden Getir aşamasında güncellenir, çünkü hemen ardından gelen dallanmanın öngörüsü bu değere bakılarak yapılacaktır. Yanılma olduğunda yazmaç, yanlış yoldaki dallanmaların bıraktığı bitleri taşır ve bu bitlerin geri alınması gerekir. İşlemciler bunun için dallanma anındaki geçmiş değerinin bir kopyasını saklar. Öngörücü büyüdükçe ve daha uzun geçmiş kullandıkça saklanıp geri yüklenmesi gereken durum da büyür, bu da uzun geçmişli tasarımların ödediği bedellerden biridir.

Sırasız yürütümlü işlemcilerde iptal işini yeniden sıralama belleği üstlenir. Buyruklar hangi sırayla yürütülürse yürütülsün program sırasına göre kalıcılaştığından, dallanmadan sonra başlatılmış buyruklar yanılma anlaşıldığında henüz kalıcılaşmamış olur ve topluca atılabilirler.

İptalin nasıl yapılacağı ayrı bir tasarım kararıdır ve seçenekler yazmaç adlandırma çizelgesinin nasıl eski durumuna döndürüleceğine göre ayrışır. Çizelge, boru hattının sonundan yanılan dallanmaya doğru geriye yürünerek adım adım geri alınabilir. Kalıcılaşmış durumu ayrıca tutan ikinci bir çizelge varsa oradan başlanıp dallanmaya kadar ileri yürünebilir. Ya da her dallanmada çizelgenin bir kopyası alınıp yanılma durumunda tek adımda geri yüklenebilir. Kopya almak en hızlısıdır, karşılığında saklama alanı ister ve boru hattında aynı anda bulunabilecek dallanma sayısını sınırlar. Yürüyerek onarım ucuzdur ama çevrim harcar.

Geri almanın bedeli, dallanma cezasının kendisidir.

Bir öngörücü hangi yönden devam edileceğini söyler, ama o yönden ne kadar emin olduğunu söylemez. Güven kestirimi (İngilizce: confidence estimation) bu ikinci bilgiyi üretir ve verilen öngörünün doğru çıkma olasılığını kestirir. En yalın biçimi, her dallanma için son öngörülerin art arda kaç kez tuttuğunu sayan bir sayaçtır. Sayaç yüksekse öngörüye güvenilir, düşükse güvenilmez.

Bu bilgi çoğu zaman öngörücünün içinde zaten bulunur. TAGE'de öngörüyü hangi çizelgenin verdiği ile o çizelgedeki sayacın değeri birlikte, yanılma olasılığı için ayrıca bir yapı kurmaya gerek bırakmadan kestirim sağlar.

Güven kestirimi birkaç düzeneğin ortak dayanağıdır. Onaylamalı öngörüde ikinci öngörücünün kararına ne zaman başvurulacağı, döngü öngörücüsünün ana öngörüyü ne zaman geçersiz kılacağı ve TAGE'de yeni açılmış bir girdiye ne zaman güvenileceği bu kestirime bağlıdır.

Kestirimin bir başka kullanımı doğrudan enerjiyle ilgilidir. Güven düşükken işlemci, büyük olasılıkla iptal edilecek buyruklarla boru hattını doldurmayı sürdürmek yerine getirmeyi kısabilir ya da durdurabilir. Böylece yanlış yolda harcanacak enerji baştan harcanmamış olur. Getirmenin kısılması başarımdan bir miktar verir, ama güvenin düşük olduğu yerde o işin zaten boşa gitmesi beklendiğinden kayıp sınırlı kalır.

Yanlış öngörünün bedeli, dallanmanın getirildiği çevrim ile koşulun çözüldüğü çevrim arasındaki mesafeye bağlıdır. Bu aralıkta boru hattına giren bütün buyruklar iptal edileceğinden, boru hattı ne kadar derinse kayıp da o kadar büyür.

Bu ilişkinin en bilinen örneği Intel'in NetBurst mikromimarisidir. Pentium 4'te yanlış öngörüden dönüş 20 aşama sürerken, bir önceki P6 mikromimarisinde 10 aşama sürüyordu. Boru hattını daha küçük parçalara bölmek saat sıklığını yükseltmeyi olanaklı kılmış, ama her yanlış öngörünün bedelini iki katına çıkarmıştır. Aynı tasarımda öngörücü de güçlendirilmiş ve yanlış öngörü oranı P6'ya göre yaklaşık üçte bir azaltılmıştır.

İkinci büyütücü etken, işlemcilerin her çevrimde birden çok buyruk başlatmasıdır. Çevrim başına dört buyruk başlatan çoklu buyruk başlatımlı bir işlemcide yirmi çevrimlik bir ceza, seksen buyrukluk yürütme fırsatının boşa gitmesi anlamına gelir. Derinlik ile genişlik birlikte arttığında öngörü doğruluğundaki küçük iyileşmeler bile başarımda belirgin karşılık bulur.

Yanlış yoldan getirilen buyruklar iptal edilse bile getirilmiş, çözülmüş ve çoğu zaman yürütülmüş olur. Harcanan enerji geri kazanılamaz. Öngörü doğruluğu bu nedenle yalnız başarımı değil enerji tüketimini de doğrudan etkiler. Boru hattını derinleştirerek saat sıklığını yükseltme yolunun güç duvarı nedeniyle kapanması, tasarımda çevrim başına yapılan işi artırmayı öne çıkarmıştır.

Dallanma öngörüsünün kökeni, buyrukları örtüşmeli olarak yürüten ilk makinelere uzanır. 1961'de çalışır duruma gelen IBM 7030 (Stretch), koşulu aritmetik yazmaçlara bağlı dallanmaları atlamayacak varsayıyor ve bu yoldaki buyrukları öngörülü olarak yürütmeye başlıyordu. Öngörü yanlış çıktığında, dört düzeyli ileri bakış biriminde saklanan eski dizin yazmacı değerleri kullanılarak makinenin durumu geri alınıyordu. Böylece hem bir öngörü kuralı hem de yanlış öngörüden dönüş düzeneği, bu kavramlara adları konmadan önce donanımda uygulanmış oldu.

1980'lerin boru hattı temelli işlemcilerinde denetim sorunu çoğunlukla daha yalın yollarla ele alındı. Dallanmanın hep aynı yöne gideceğini varsayan durağan kurallar ile derleyicinin dallanmanın ardındaki boşluğu yararlı bir buyrukla doldurduğu geciktirilmiş dallanma yöntemi yaygındı.

Alanı bugünkü biçimine getiren çalışma, James E. Smith'in 1981'de yayımladığı karşılaştırmalı incelemedir. Smith, o güne kadar önerilmiş öngörü stratejilerini aynı ölçütlerle sınayarak her dallanma için iki bitlik doyan bir sayaç tutmanın, karmaşıklığına göre çok iyi sonuç verdiğini gösterdi. Bu yapı çift doruklu öngörücünün temeli oldu.

1991'de Tse-Yu Yeh ve Yale Patt, tek bir sayaç yerine dallanmanın son sonuçlarını bir yazmaçta saklayıp bu deseni ayrı bir çizelgeyle eşleyen iki aşamalı uyarlanır öngörücüyü tanıttı. Ertesi yıl Shien-Tai Pan, Kimming So ve Joseph Rahmeh, birbirinden ayrı dallanmaların sonuçları arasındaki ilişkinin de öngörüde kullanılabileceğini gösterdi. 1993'te Scott McFarling, genel geçmiş ile buyruk adresini özel veya işleminden geçirerek çizelge çakışmalarını azaltan gshare öngörücüsünü ve birden çok öngörücüyü bir seçiciyle birleştirme fikrini önerdi.

Devingen öngörü 1990'larda yaygın ürünlere girdi. 1993'te tanıtılan Intel Pentium, dallanma hedef ara belleği (branch target buffer, BTB) üzerinden çalışan bir devingen öngörücü içeriyordu. 1998'de tanıtılan Alpha 21264, McFarling'in birleştirme fikrini doğrudan uyguladı. İşlemcide yerel geçmişe ve genel geçmişe dayanan iki ayrı öngörücü ile bu ikisi arasında seçim yapan üçüncü bir çizelge bulunuyordu.

2001'de Daniel A. Jiménez ve Calvin Lin, algılayıcı adı verilen basit bir yapay sinir ağı birimini dallanma öngörüsüne uyguladı ve uzun geçmiş dizilerinin, sayaç çizelgelerini büyütmeye gerek kalmadan kullanılabileceğini gösterdi.

Alanın ölçütlerini belirleyen gelişme, Journal of Instruction-Level Parallelism dergisinin düzenlediği Dallanma Öngörüsü Yarışması oldu. Yarışmada bütün katılımcılar aynı benzetim altyapısını ve aynı buyruk izlerini kullandığından, önerilen öngörücüler ilk kez birebir karşılaştırılabildi. Yarışmalar büyük bilgisayar mimarisi konferanslarıyla birlikte düzenlenmektedir.

İlk yarışmayı Hongliang Gao ile Huiyang Zhou'nun algılayıcı temelli öngörücüsü kazandı. 2006'da André Seznec ve Pierre Michaud, farklı uzunluktaki geçmişleri etiketli çizelgelerde tutan TAGE öngörücüsünü tanıttı. Aynı yılın yarışmasında Seznec'in TAGE türevi L-TAGE öngörücüsü sınırlı boyutlu kategoriyi kazandı. Sonraki yarışmaların hepsinde birinciliği TAGE ailesinden öngörücüler aldı ve bu tasarım alanın başat çözümü oldu.

Öngörücü, aynı işlemciyi paylaşan süreçler arasında ortak bir kaynaktır ve bunun güvenlik sonuçları daha önce de bilinmekteydi. 2007 yılında yayımlanan bir çalışmada, RSA imzalamasıyla koşut çalışan bir casus sürecin öngörücünün durumunu izleyerek tek bir imzalama sırasında gizli anahtar bitlerinin neredeyse tamamını çıkarabildiği gösterilmiş, saldırı OpenSSL üzerinde denenmiştir. 2018 başında açıklanan Spectre saldırıları, dallanma öngörüsünün yalnızca bir başarım düzeneği olmadığını gösterdi. Saldırgan öngörücüyü eğiterek işlemciyi, normal akışta erişemeyeceği verilere öngörülü olarak dokunmaya yöneltebiliyordu. Öngörü geri alınsa bile bu erişimin önbellekte bıraktığı iz, bir yan kanal saldırısıyla okunabiliyordu. Bu bulgudan sonra öngörücü tasarımı, başarımın yanı sıra yalıtım gereklerini de gözetmek zorunda kaldı.

Öngörü yöntemleri, kararın nasıl verildiğine göre durağan ve devingen olmak üzere iki öbekte toplanır.

Durağan öngörüde karar çalışma sırasında değişmez. En yalın biçimi bütün dallanmaların atlayacağını ya da hiçbirinin atlamayacağını varsaymaktır. Bu kural ek donanım gerektirmez, çünkü saklanan bir geçmiş yoktur.

Daha iyi sonuç veren bir kural dallanmanın yönüne bakar. Geriye doğru dallanmaların çoğu bir döngünün sonundadır ve genellikle atlar, ileriye doğru dallanmalar ise çoğunlukla atlamaz. Buyruk kümesinde dallanmanın beklenen yönünü bildiren bir alan bulunuyorsa, derleyici bu alanı kodun yapısına ya da önceden toplanmış bir çalışma profiline bakarak doldurabilir.

Durağan öngörü, bir dallanmanın davranışı program boyunca değiştiğinde buna uyum sağlayamaz. Devingen yöntemler bu sınırı aşmak için geliştirilmiştir.

Devingen yöntemler, sakladıkları geçmişin türüne göre birbirinden ayrılır. Çift doruklu öngörücü yalnız o dallanmanın kendi son sonuçlarını kullanır. İki aşamalı öngörücüler buna bir geçmiş deseni ekler. Birleşik öngörücüler ise birden çok öngörücüyü birlikte çalıştırıp aralarından seçim yapar.

Dallanmaların davranışı rastgele değildir. Çoğu dallanma ya neredeyse her zaman atlar ya da neredeyse hiç atlamaz. Çift doruklu öngörücü bu iki kutuplu davranıştan yararlanır.

Öngörücü, program sayacının alt bitleriyle adreslenen bir sayaç çizelgesidir ve her sayaç iki bit uzunluğundadır. Dallanma atladığında ilgili sayaç bir artırılır, atlamadığında bir eksiltilir. Sayacın en anlamlı biti öngörüyü verir. Sayaç uçlarda doyar, 11 değerinden sonra artmaz ve 00 değerinden sonra eksilmez. Böylece sürekli atlayan bir dallanmanın atlayacağı, sürekli atlamayan bir dallanmanın ise atlamayacağı öngörülür.

Öngörünün yön değiştirmesi için sayacın art arda iki kez yanılması gerekir. Tek bitlik bir sayaç yalnızca son sonucu hatırlar. Çok kez dönen bir döngüde bu sayaç iki kez yanlış öngörür, döngüden çıkarken bir kez ve döngüye yeniden girerken bir kez daha. İki bitlik sayaç son sonuca hemen uymadığı için bu iki yanlıştan birini ortadan kaldırır.

Çizelge küçük olduğunda birden çok dallanma aynı sayacı paylaşır. Çizelge büyüdükçe paylaşım azalır ve doğruluk artar. SPEC'89 denektaşlarıyla yapılan ölçümlerde doğruluk yaklaşık %93 düzeyinde doyuma ulaşmaktadır. Yanlış öngörüler ya o dallanmanın davranışının gerçekten değişmesinden ya da başka bir dallanmanın aynı sayacı kullanmasından kaynaklanır.

Sayaç çizelgesi, her sayaca bir etiket eklenerek küme ilişkili bir önbellek gibi de kurulabilir. Bu düzenleme, sayaç sayısı sabitken hangi dallanmanın hangi sayacı kullandığını kesinleştirir ve paylaşımdan doğan yanlışları azaltır.

Dallanmaların çoğu yinelenen bir örüntü gösterir. Çift doruklu öngörücü bu örüntüyü göremez, çünkü yalnız son sonucu saklar. İki aşamalı öngörücü bu sınırı, her dallanmanın son birkaç sonucunu ayrı bir çizelgede tutarak aşar.

Dört kez dönen bir döngü buna örnektir. Döngünün sonundaki geri dallanma üç kez atlar, dördüncüde atlamaz. Atlamaya 1, atlamamaya 0 denirse ortaya 1110 örüntüsü çıkar ve bu örüntü döngüye her girildiğinde yinelenir.

Öngörücü iki çizelgeden oluşur. Birincisi her dallanmanın son sonuçlarını bir kaydırmalı yazmaçta tutar. İkincisi, bu geçmiş değeriyle adreslenen ve çift doruklu öngörücüdeki gibi iki bitlik sayaçlar taşıyan örüntü çizelgesidir. Geçmiş çizelgesine dallanma buyruğunun adresinin alt bitleriyle ya da küme ilişkili bir düzenlemeyle erişilir.

Birinci çizelgenin sonucu ikincisini adreslediğinden erişimler art arda yapılır ve bu, öngörüyü tek çizelgeli bir öngörücüye göre yavaşlatır. Geçmiş ve örüntü çizelgelerinin girdi sayıları genellikle birbirine yakın tutulur, çünkü küçük bir öngörücüde gereğinden uzun geçmiş saklamanın kazancı olmaz.

Yerel geçmişe dayanan öngörü, 128 baytın üzerindeki öngörücü boyutlarında çift dorukludan daha iyi sonuç verir. Büyük öngörücülerde doğruluk yüzde 97,1'e yaklaşır ve çift dorukluların yanlış öngörülerini yarıya indirir.

Bir dallanmanın yönü, kendi geçmişinden çok başka dallanmaların sonucuna bağlı olabilir. Aşağıdaki üç koşuldan tam olarak biri doğrudur.

if (x < 10)  { ... }   // bu dallanma atlamazsa
if (x > 10)  { ... }   // bu atlar
if (x == 10) { ... }   // bu da atlar

Derleyici bu yapıları, koşul yanlış olduğunda gövdenin üzerinden atlayan birer dallanmaya çevirir. Buna göre birinci koşul doğru olduğunda birinci dallanma atlamaz, geri kalan ikisi ise kesinlikle atlar. Üç dallanmanın yönü birbirine bağlıdır ve sonraki ikisi, birincisinin sonucuna bakılarak öngörülebilir. Genel geçmişe bağlı öngörücü bu ilişkiden yararlanır. Son yürütülen dallanmaların sonuçları genel geçmiş yazmacı adı verilen bir kaydırmalı yazmaçta toplanır ve bu değer iki bitlik sayaç çizelgesinde kullanılır. Bir dallanma çoğunlukla aynı yöne gittiğinde ondan önce gelen dallanma dizisi de yinelenir, bu sayede öngörücü farklı dallanmaları birbirinden ayırabilir.

Genel geçmişi dallanma adresiyle birlikte kullanmanın iki yolu vardır. Gselect adı verilen yöntemde dallanma adresinin ve genel geçmişin birer bölümü yan yana getirilerek dizin oluşturulur. Gselect 4/4 düzenlemesi adresin dört bitini geçmişin dört bitiyle birleştirir ve 1 KB'tan küçük öngörücülerde iyi sonuç verir.

Gshare adı verilen yöntemde ise adres ile geçmiş yan yana konmaz, özel veya işleminden geçirilir. Böylece iki bilgi de dizinin tamamına yayılır ve gselect 4/4 düzenlemesinin ayırt edemediği durumlar ayrılabilir. Gshare, 256 bayttan büyük öngörücülerde iyi çalışır.

İki yöntemin ortak amacı, genel geçmişi kullanırken o dallanmanın kimliğini de dizine katmaktır. Özel veya işleminin burada aritmetik bir anlamı yoktur. İşlem iki ayrı bilgiyi birbirine karıştırarak yeni bir dizin türetir ve bu yönüyle bir karma işlevi gibi çalışır. Gselect adres ile geçmişi yan yana koyduğundan dizinin bir bölümü yalnız adresi, öteki bölümü yalnız geçmişi taşır. Gshare'de ise her dizin biti hem adresten hem geçmişten beslenir, böylece aynı sayıda bitle iki bilginin daha büyük bir kısmı kullanılmış olur.

Sayaç çizelgesi sınırlı büyüklükte olduğundan iki ayrı dallanma aynı girdiye düşebilir. Bu çakışma her zaman zarar vermez. İki dallanma da aynı yöne eğilimliyse ortak sayacı aynı yöne çekerler ve birbirlerini bozmazlar. Zarar, ters yönlere eğilimli iki dallanma çakıştığında ortaya çıkar. Her biri sayacı ötekinin gerektirdiğinin tersine sürükler ve ikisi birden yanılır.

Uzlaşma öngörücüsü çakışmayı önlemeye çalışmak yerine onu zararsız duruma getirir. Bunun için çizelgede saklanan bilgi değiştirilir. Sayaç artık dallanmanın atlayıp atlamayacağını değil, dallanmanın kendi eğilimiyle uyuşup uyuşmayacağını tutar. Her dallanma için ayrıca bir eğilim biti bulunur ve bu bit dallanmayla ilk karşılaşıldığında gözlenen yöne kurulur. Öngörü yapılırken sayacın verdiği uyuşma değeri eğilim bitiyle birleştirilerek son yön elde edilir.

Çoğu dallanma zamanın büyük bölümünde kendi eğilimine uyduğundan sayaçların çoğu aynı yöne, uyuşma yönüne doğru dolar. Ters eğilimli iki dallanma aynı girdiye düşse bile artık ikisi de sayacı aynı yöne çeker. Böylece çakışmanın zarar verdiği durumların sayısı azalır.

Öngörü yöntemlerinin her biri farklı dallanmalarda üstün gelir. Scott McFarling 1993'te yayımladığı çalışmada, iki öngörücüyü aynı anda çalıştırıp her dallanma için hangisinin kullanılacağına bir seçicinin karar vermesini önerdi.

Seçici, her dallanma için iki bitlik doyan bir sayaç tutar. Dallanmanın sonucu belli olduğunda iki öngörücü de doğru ya da ikisi de yanlış çıkmışsa sayaç değişmez. Yalnız biri doğru çıkmışsa sayaç o öngörücüden yana bir adım kayar. Sayacın en anlamlı biti, bir sonraki karşılaşmada hangi öngörücünün sonucunun kullanılacağını belirler.

Böylece yerel geçmişin güçlü olduğu dallanmalarda yerel geçmişe bağlı öngörücü, genel geçmişin güçlü olduğu dallanmalarda genel geçmişe bağlı öngörücü kullanılmış olur. Birleştirilmiş öngörücülerin, aynı donanım bütçesinde tek başına çalışan öngörücülerin ikisinden de yüksek doğruluk verdiği ve tamsayı programlarında doğruluğun %96'nın üzerine çıktığı belirtilmiştir.

Bu düzenleme turnuva öngörücüsü olarak da anılır. 1998'de tanıtılan Alpha 21264 işlemcisinde yerel, genel ve seçici olmak üzere üç çizelgeyle uygulanmıştır.

Öngörü çizelgesinde birden çok dallanmanın aynı girdiyi paylaşması, bu dallanmaların eğilimleri birbirine ters olduğunda öngörüyü bozar. Onaylamalı öngörü, paylaşımın bu yıkıcı etkisini gidermeyi amaçlar.

Her dallanma için, dallanma hedef ara belleğine yazılırken bir yargı biti belirlenir ve bu bit dallanmanın büyük olasılıkla gideceği yönü tutar. Geçmiş çizelgesi artık dallanmanın atlayıp atlamayacağını değil, sonucun yargı bitiyle uyuşup uyuşmayacağını öngörür. Çizelgeye, gshare'de olduğu gibi adres ile geçmiş bitlerinin özel veya sonucuyla erişilir.

Dallanmaların çoğu kendi yargı bitiyle uyuştuğundan, aynı girdiyi paylaşan iki dallanma da çoğunlukla uyuşma yönünde sayaç işletir. Böylece paylaşım öngörüyü bozmak yerine destekler duruma gelir. Öngörü, çizelgeden gelen uyuşma kararı ile dallanma hedef ara belleğinden gelen yargı biti birlikte değerlendirilerek üretilir.

Bu yöntemin amacı geçmiş çizelgesindeki gereksiz bilgiyi azaltmaktır. Neredeyse her zaman aynı yöne giden dallanmalar tek bir bitle yüksek doğrulukta öngörülebilir. Bu tür dallanmaları çizelgeden filtrelemek, her dallanma için bir yargı biti ve bir sayaç tutmakla olanaklıdır.

Bir dallanma dallanma hedef ara belleğine ilk yazıldığında yargı biti o dallanmanın yönüne kurulur ve sayaç sıfırlanır. Dallanmanın sonucu her belli olduğunda bu sonuç yargı bitiyle karşılaştırılır. Uyuşuyorsa sayaç bir artırılır, uyuşmuyorsa sıfırlanır. Sayaç doymadığı sürece öngörü geçmiş çizelgesinden alınır. Sayaç doyduğunda ise dallanma çizelgeden filtrelenmiş olur ve öngörü doğrudan yargı bitine göre yapılır.

Denetim akışı ve işlem kodu bilgisi gibi program özellikleriyle eğitilen bir yapay sinir ağı, derleme zamanında durağan öngörü üretmekte kullanılabilir. Bu yaklaşımda öngörü kuralı elle belirlenmez, derlenmiş programlardan toplanan örneklerle öğrenilir.

Çalışma sırasında yapay sinir ağı kullanan dallanma öngörüsünü 1999'da Lucian Vintan ve Mihaela Iridon önerdi. Kullandıkları yöntem, bir yapay sinir ağı öğrenme algoritması olan öğrenmeli vektör nicemlemesiydi.

Algılayıcı temelli öngörüde, donanımda verimli biçimde gerçeklenebilen basit doğrusal bir yapay sinir hücresi kullanılır. Algılayıcı bir Boole işlevi öğrenir. İşlenenler genel geçmiş kaydırmalı yazmacının bitleri, hedef işlev ise dallanmanın atlayıp atlamayacağıdır. Yapının iki üstünlüğü vardır. Uzun geçmişler, sayaç çizelgesini büyütmeye gerek kalmadan kullanılabilir. Ayrıca öğrenilen ağırlıklara bakılarak öngörünün hangi geçmiş bitlerine dayandığı izlenebilir.

Yol tabanlı yapay sinir ağı öngörüsünde ağırlıklar, dallanmanın adresine göre değil, dallanmaya ulaşmak için izlenen yola göre seçilir. Bir dallanmanın davranışı yalnız örüntü geçmişiyle değil, oraya hangi yoldan gelindiğiyle de ilgilidir. Ağırlıklar yol boyunca önceden toplanabildiğinden öngörünün gecikmesi de gizlenebilir.

Parçalı doğrusal öngörüde ise bir dallanmaya birden çok yoldan ulaşılabildiği için her yol ayrı bir doğrusal işlevle temsil edilir. Böylece atlaması öngörülen yollar ile atlamaması öngörülen yollar birbirinden ayrılır.

Döngülerin sonundaki geri dallanma öngörücüler için kendine özgü bir güçlük çıkarır. Döngü N kez döndüğünde bu dallanma N eksi bir kez atlar, sonuncuda atlamaz. Yerel geçmişe bakan bir öngörücü bu örüntüyü ancak geçmiş yazmacı N bitten uzunsa tutabilir. Genel geçmişin de ya N'den uzun olması ya da döngüden çıkmadan önce ayırt edici bir dallanma dizisinin bulunması gerekir. Uzun süren döngülerde bunların hiçbiri sağlanmaz ve döngüden her çıkışta bir yanılma olur.

Çözüm örüntüyü ezberlemek yerine saymaktır. Bir döngü dallanması için önemli olan sonuçların dizilişi değil, kaç kez atlandığıdır.

Timothy Sherwood ve Brad Calder'ın 2000 yılında önerdiği düzenekte, ana öngörücünün yanıldığı geri dallanmalar ayrı bir çizelgeye alınır. Her girdide üç alan bulunur. Tur sayısı, dallanmanın son atlamama olayından önce art arda kaç kez atladığını tutar. Sayaç, içinde bulunulan turda dallanmanın art arda kaç kez atladığını izler. Güven biti ise aynı tur sayısının art arda en az iki kez gözlendiğini gösterir. Sayaç tur sayısına eşitlendiğinde ve güven biti kurulu olduğunda döngüden çıkılacağı öngörülür. Dallanmanın sonucu belli olduğunda tur sayısı ile güven biti güncellenir.

Döngü öngörücüsü tek başına kullanılmaz, ana öngörücünün yanına konur ve güveni yüksek olduğunda onun öngörüsünü geçersiz kılar. Bu yönüyle onaylamalı dallanma öngörüsüne benzer. Kısa bir ısınma döneminden sonra tur sayısı değişmeyen döngülerde doğruluğu tama yakın çıkabilir. Tur sayısı sık değişen döngülerde ise hem kapsamı hem doğruluğu düşer.

Bugünkü işlemcilerde kullanılan TAGE-SC-L öngörücüsünün adındaki L bu bileşeni gösterir.

Gshare ve benzeri yöntemler tek bir genel geçmiş uzunluğu kullanır, oysa bu uzunluk bir uzlaşmadır. Kısa tutulursa uzaktaki ilişkiler kaçırılır. Uzun tutulursa kısa örüntülü dallanmalar için gereğinden çok sayaç harcanır ve çizelge geç ısınır. Her dallanmanın kendine göre uygun bir geçmiş uzunluğu vardır.

2006'da André Seznec ve Pierre Michaud'nun önerdiği TAGE (İngilizce: tagged geometric history length, etiketli geometrik geçmiş uzunluğu) bu uzlaşmayı ortadan kaldırır. Öngörücü tek çizelge yerine birden çok çizelge tutar. Bunlardan T0 etiketsiz bir çift doruklu çizelgedir ve her koşulda bir öngörü verir. Üstündeki çizelgelerin her biri başka uzunlukta bir genel geçmişle dizinlenir. Uzunluklar geometrik bir dizi oluşturur ve L ( i ) = α i − 1 × L ( 1 ) {\displaystyle L(i)=\alpha ^{i-1}\times L(1)} biçimindedir. Burada L(1) en kısa geçmiş uzunluğu, α {\displaystyle \alpha } ise birden büyük bir çarpandır. Geometrik artış sayesinde az sayıda çizelgeyle hem birkaç bitlik hem de yüzlerce bitlik geçmişler taranabilir. Sekizden çok etiketli çizelge kullanmanın ek yarar sağlamadığı bildirilmiştir.

Etiketli çizelgelerin her girdisinde üç alan bulunur. Bir sayacın işareti öngörüyü verir, bir etiket girdinin gerçekten aranan dallanmaya ait olduğunu doğrular, bir yararlılık sayacı da girdinin ne ölçüde işe yaradığını tutar. Öngörü sırasında bütün çizelgeler koşut olarak okunur. Etiketi tutturan çizelgelerden en uzun geçmişli olanı öngörüyü verir. Hiçbiri tutturmazsa T0'ın öngörüsü kullanılır. Tutturanlar arasında ikinci sırada gelenin öngörüsüne alternatif öngörü denir.

Güncelleme, hangi bilginin saklanmaya değdiğini ayıklamak üzerine kuruludur. Alternatif öngörü ile verilen öngörü birbirinden ayrıldığında, öngörü doğru çıkmışsa yararlılık sayacı artırılır, yanlış çıkmışsa azaltılır. Böylece yalnız fark yaratan girdiler korunur. Bu sayaçlar belirli aralıklarla sıfırlanır, yoksa bir girdi sonsuza dek yararlı damgası taşır. Yanılma olduğunda, öngörüyü veren çizelgeden daha uzun geçmişli bir çizelgede yeni bir girdi açılır. Böylece öngörücü, tutturamadığı dallanmalar için kendiliğinden daha uzun geçmişe yönelir. Yeni açılan girdi bir süre eğitimsiz kaldığından güvenilmez, bu yüzden olgunlaşana dek onun yerine alternatif öngörü kullanılır.

Bu yapı, aynı donanım bütçesinde çok daha uzağa uzanan ilişkileri yakalar. Gshare'in yaklaşık 20, perceptron temelli öngörücülerin yaklaşık 60 dallanmalık geçmişle ilişki kurabildiği koşullarda TAGE'nin yaklaşık 2000 dallanmaya ulaştığı bildirilmiştir. TAGE tek başına en doğru öngörücü sayılmakta, yan öngörücülerle birleştirildiğinde doğruluğu daha da artmaktadır. Bugünkü işlemcilerde kullanılan TAGE-SC-L bu birleşimin örneğidir. TAGE çekirdeğine, geçmişle ilişkisi bulunmayan ve neredeyse her zaman aynı yöne giden dallanmaları düzelten bir istatistiksel düzeltici (statistical corrector) ile döngü çıkışlarını öngören bir döngü öngörücüsü eklenmiştir.

Devingen öngörü yöntemleri birbirinin yerine geçen seçenekler değildir. Her biri, kendinden öncekinin çözemediği bir dallanma türü için ortaya çıkmıştır.

Aynı ayrımı sayıyla göstermek için birkaç örnek örüntü kullanılabilir.

A atlamayı, Z atlamamayı gösterir. Değerler öngörücü örüntüyü öğrendikten sonraki kararlı durumu verir; tek bir dallanma varsayılmış, çizelge çakışması hesaba katılmamıştır. Yeşil hücreler öngörücünün örüntüyü tam çözdüğü, kırmızı hücreler ise yazı tura atmaktan daha iyi sonuç vermediği durumları gösterir. İkinci ve üçüncü satırdaki koşullu dallanmaların bu örüntüyü vermesi, kuşatan döngüde i değerinin her turda bir artmasına bağlıdır. Çizelgedeki örüntü kaynak koddaki koşulun sonucunu gösterir. Derlenmiş kodda dallanma buyruğu genellikle bunun tersine kurulur, koşul sağlandığında dallanma atlamaz ve gövdeye girilir, sağlanmadığında ise gövdeyi atlar. Örüntü iki durumda da dönüşümlü olduğundan doğruluk değerleri değişmez.

Çağdaş bir işlemcide dallanma öngörüsü tek bir devre değil, birlikte çalışan birkaç birimden oluşan bir öngörü birimidir. Koşullu dallanmaların yönünü veren ana öngörücünün yanında, hedef adresleri saklayan dallanma hedef ara belleği ile altyordam dönüşlerini ayrıca öngören dönüş adresi yığıtı bulunur. Pentium 4'ün öngörü birimi örneğin iki ayrı dallanma hedef ara belleği ve on altı girdilik bir dönüş adresi yığıtı içeriyordu.

Ana öngörücü tarafında TAGE ailesi baskındır. 2006'dan sonra düzenlenen Dallanma Öngörüsü Yarışmalarının hepsini bu aileden tasarımlar kazanmıştır.

Algılayıcı temelli öngörücüler de araştırmadan üretime geçmiştir. Samsung'un Austin'deki tasarım merkezinde geliştirilen ve Exynos yongalarında kullanılan özel Arm çekirdekleri, algılayıcı temelli dallanma öngörüsüne dayanır.

Öngörücü, üreticilerin ürün tanıtımlarında öne çıkardığı bir başlık haline de gelmiştir. Apple, 2024'te M4 yongasını duyururken başarım çekirdeklerinde geliştirilmiş dallanma öngörüsü bulunduğunu belirtmiş, 2026'da M5 Pro ve M5 Max'i duyururken de tek iş parçacıklı başarımın kısmen iyileştirilmiş dallanma öngörüsüne dayandığını bildirmiştir. Bu duyurular öngörücünün ticari önemini gösterir, ancak tasarımın ayrıntısını vermez.

Ulaşılan doğruluk çok yüksek olsa da sorun kapanmış değildir. Chit-Kwan Lin ve Stephen Tarsa, bugünün en iyi öngörücülerinden TAGE-SC-L'nin SPECint 2017 üzerinde yaptığı yanlışların giderilmesinin, çevrim başına buyruk sayısında bir üretim süreci kuşağı atlamaya denk kazanç sağlayacağını göstermiştir. Kalan yanlışlar büyük ölçüde öngörülmesi güç dallanmalardan ve seyrek yürütülen kod parçalarından kaynaklanır.

• Öngörüye dayalı yürütme
• Buyruk penceresi
• Buyruk önyüklemesi
• Retbleed

• Agner Fog, The Microarchitecture of Intel, AMD and VIA CPUs (PDF). Üçüncü bölümü, Pentium ailesinden bugünkü mimarilere dallanma öngörücülerinin ayrıntılı karşılaştırmasını verir.
• Daniel A. Jiménez, Reconsidering Complex Branch Predictors (PDF, HPCA-9, 2003). Büyük ve karmaşık öngörücülerin gecikmesinin derin boru hatlarında kazancı nasıl yediğini gösterir, gecikmeyi tümüyle gizleyen bir tasarım önerir.
• Alpha EV8 dallanma öngörücüsü üzerine geriye dönük değerlendirme (PDF). Tasarımcıların kendi kaleminden, kararların 1999 yazında nasıl alındığı ve işlemcinin iptal edilmesinin ayrıntıları nasıl kamuya açtığı.