Dallanma Tahmini P4 Pentium 4

Dallanma  tahmin  algoritmalarının  ne  olduklarını , nasıl  bir yapıya sahip  olduğunu  anlayabilmek  için  öncelikli  olarak  dallanma  yapıları  ile  ortak  platform ve  zaman işleyişine  sahip  diğer  yardımcı  birimlerin  tanıtılması  gerekir.  İzleme Cache (Trace Cache)  Pentium-4’ün belki de en ilginç ve yeni özelliği klasik L1 komut cache’ i yerine özel bir izleme cep belleği (trace cache) taşımasıdır.

İzleme cache’i, mikroişlemcinin işletmesi için bekleyen komutlar yerine onların çözüldükten sonraki halleri olan mikroopları (komut parçacıkları) işletim sırasına göre depolayan bir cep bellektir.

Klasik durumda, P-III veya Athlon işlemcileri L1 cep belleklerinde çalıştırılacak olan programın derleyici tarafından belirlenmiş olan makina kodunu depolarlar. Pentium-4 ise bu komutları işletmeye başlamadan önce çözüyor ve depoluyor.

Amaç, program içerisinde çok sıklıkla erişilen alanlardaki verinin işlemciye göre çok yavaş olan ana hafıza yerine çok hızlı çalışan ara belleklerde (cache) bulundurulmasıdır.

P6 (PentiumPro’dan P-III’e kadar) işhattı (pipeline) Pentium-III ve AMD Athlon gibi işlemcilerin komutları işletirken sürekli tekrarlayarak izlediği yolda komutun L1 cache’ inde aranması, getirilmesi, dallanma tahmininin yapılması, kodunun çözülmesi aşamaları da her seferinde tekrarlanır. Oysa Pentium-4, cep belleğinde önceden zaten çözülmüş olan komut parçacıklarını taşıdığından bu zaman alıcı aşamalardan geçmek zorunda kalmaz, kısacası Pentium-4’ün kritik işletim safhası Pentium-3 ve Athlon’dan daha kısadır (en azından yapılan işlerin çeşidi açısından). Tabi bu pentium-4’ün bu işlemcilere göre daha kısa bir iş hattına sahip olduğunu göstermiyor, bu işlemci 20 kademeli inanılmaz uzun bir iş hattına sahip.

v  20 kademeli Pentium-4 (Williamette) İşhattı 20 kademeli bir iş  hattı varsa (hatta daha önceki safhalarda da bazı kademeler gizliyse) en çok problem  olan konu dallanma tahminidir. Dallanma tahmini konusuna açıklık getirmek için  basit bir örneğe başvuralım ve küçük ve sembolik bir program parçası düşünelim:
1. A=0
2. A=A+1
3. IF A>3 GOTO 8
4. B=C
5. D=F+4
6. G=3
7. GOTO 2
8. …

Programımız önce aslında 3’e kadar sayan bir sayıcıdan ibaret, A sayısı önce 0’a eşitleniyor, sonra da bir arttırılıp 3 sayısına erişip erişmediği kontrol ediliyor, eğer erişmemişse işleme devam ediliyor, ve tekrar 2. Aşamaya dönülüyor. Erişilmişse, sisteme 6. Komuta geçilmesi söyleniyor. Bu tür durumlarda, yani bir karşılaştırma yapılıp program içerisindeki başka bir alana dallanma yapılması gerektiğinde, mikroişlemciyi de zor bir karar bekliyor demektir. Düşünelim, işlemcimiz komutlar için gerekli olan cep bellekten alma, çözme , sıralama gibi işlemleri sırayla yapmaya başladı, tabi bu sırada IF komutunun olduğu satır ve sonraki satırlar da sırayla iş hattına girdiler, ancak işletim sırasında (Execution) A değerinin 3 değerini aştığı görüldü, bu durumda işlemcinin daha önceden iş hattına soktuğu 4,5,6,7. Komutların değil, 8. Komuttan itibaren başlayan komutların işletimde olması gerektiği farkedildi. İşlemci acele  olarak o ana kadar doldurduğu iş hattını boşaltır ve 8. Komuttan itibaren sırayla diğer komutları da iş hattına sokar.  Bu durumun işhattına getirdiği yük en kötü ihtimalle işhattının boyu kadar olacaktır. Bu duruma işhattı boşaltılması (pipeline flush) adı verilir. İşlemciler bu yüzden herhangi bir dallanma komutu ile karşılaştıkları anda, daha kod çözme aşamasında bir tahmin yapmak zorundadırlar, bu karşılaştırma komutunun sonucu doğru mu olacak, yoksa yanlışı mı? (biraz önceki örnek için, 4. Komuttan itibaren mi işletmeliyim, yoksa 8.den itibaren mi?) Dallanma tahmini konusunda pek çok metod mevcut, bazı ilkel metodlarda her zaman doğru olan veya her zaman yanlış olan taraf seçilirken daha gelişmiş olan işlemcilerde o adresteki karşılaştırma sonucunda daha önceden hangi adrese gidildiği bir tabloda tutulur ve çeşitli yöntemlerle bu tablo sürekli güncellenir. Örneğin AMD Athlon 2048 girişli bir dallanma hedef tamponu (Branch Target Buffer) taşımaktadır. Bu tahmin tamponları %80-90 arası bir başarı sağlamaktadır ancak %10-20’lik yanlış tahmin işlemci performansının teorik maksimumundan epeyce düşük olmasına sebep olmaktadır.

Pentium-4 20 kademeli işhattını bu durumdan nasıl koruyacak? Bu konu henüz Intel tarafından açıklanmadı, ancak muhtemelen, dallanma tahmin oranını %95’lere kadar çekecek çok gelişmiş ve bir o kadar da karmaşık dallanma tahmin yöntemlerinin kullanılmasına kesin gözüyle bakılıyor. İzleme Cache’nin komutlar yerine mikroopları taşıdığını daha önce ifade  edilmişti. İzleme cache’ inin bir en ilginç yönlerinden biri de komutları derleyicinin oluşturduğu statik sırada değil, işlenilişleri sırasına göre üzerinde taşımasıdır.

İzleme cache’ inin işleyişinde iki kademe göze çarpar, birinci kademe segment oluşturma (segment build) adını alır, bu aşamada işlemci komutları çözerek elde edilen mikroopları gruplar halinde (trace segment) depolar. İzleme gruplarının oluşmasından sonra, sistem işletim moduna geçer (execute mode). Bu modda izleme önbelleğinde depolanmış olan mikrooplar alınıp işletilmeye başlanır. Bu noktada Pentium-4’ün P-III ve Athlon’a göre avantajı komut çözüm işleminin herhangibir komutun her işletilişinde tekrarlanmamasıdır. Bu da,yazılımlarda çoğu zaman karşımıza çıkan döngülerde (loops) sık sık meydana gelir.

Pentium-4’ün dallanma tahmin sistemindeki ilginç noktalardan biri de sistemin dallanma komutlarını aslında iki kez inşa edilmesidir. Bunlardan birincisi izleme segmenti oluşumu sırasında program akışının dallanma sonrasındaki durumunun tahmin edilmesi ve segmentin bu tahmine göre inşa edilmesinde, ikincisi de programın işletimi sırasında dallanmanın gerçek yönünün belirlenmesinde gerçekleşir, eğer tahmin yanlış yapıldıysa, sistem izleme önbelleği içerisinde diğer yön için yapılmış başka bir segmenti arar, eğer bulamazsa L2 cep belleğinden doğru yön için gerekli komutları okumaya ve gerekli mikroop segmentlerini oluşturmaya başlar. İlk durumda sistem 20 saat darbesi kaybederken ikinci durumdaki kayıp çok daha büyük olacaktır.

Pentium-4 içerisindeki izleme segmentinin boyunun 90KB civarında olacağı tahmin ediliyor. Tabi bu rakam yalnızca spekülatif bir tahmin, daha sonraki açıklamalarda bu boyutun 16KB kadar küçük olabileceği iddia edildi.

 BRANCH PREDICTION  (Dallanma Tahmini)

Dallanma tahmini konusunda pek çok metot bulunmaktadır.Bazı  yöntemler  kullanılırken  her zaman doğru olan veya her zaman yanlış olan taraf seçilirken daha gelişmiş olan işlemcilerde o adresteki karşılaştırma sonucunda daha önceden hangi adrese gidildiği bir tabloda tutulur ve çeşitli yöntemlerle bu tablo sürekli güncellenir.

Sekil1 :Pentium III işlemcisinin mimari olarak blok diyagramı.

Sekil2 :Pentium III işlemcisinin dallanma tahmin bloğu

Tüm komutların Decoding ve Execution olarak iki basamakta elendiği bir mikroişlemci düşünülsün. Dallanan komut icra halindeyken diğer komutun çözümüyle mikroişlemci zaman kazanabilir. Bu assembly çizgi-prensibi Popline olarak adlandırılır. Gelişmiş mikroişlemcide Popline birçok komutların assembly çizgisinin ayni anda bulunacak şekilde bir çok basamakta oluşabilir.

Dallanmış komutların olduğu zaman problem ortaya çıkar. Dallanmış komut ise if then else (eğer değilse) yapısının uygulamasından oluşur. Koşulun doğru olduğu durumda ise diğer komutla devam eden durumdur. Bu, durum Popline boyunca takip giden komutlara istenmeyen bir ara verir, çünkü mikroişlemci dallanma komutunun icrasını bitirmeden bir sonraki komutun bilmemektedir.    Popline uzunluğu ölçüsünde, popline bir sonra girecek komuttan ne olacağının tahmini için gereken zaman uzayacaktır. Modern mikroişlemciler daha uzun Popline kullanmayı tercih ettiklerinden, bu problemi çözümü için bir şeyler yapılmalıdır.

Çözüm dallanma tahminidir. Mikroişlemciler dallanma komutunun dallanıp dallanmayacağını bir önceki dallanmaya göre tahmin etmeye çalışır. Eğer en son 4 uygulamada dallanmışsa bu seferde dallanma şansının büyük olduğu açıktır. Mikroişlemci emir almadan önce bu tahmini baz alarak popline’ in bir sonraki komutu yükleyip yükleyemeyeceğine karar verir. Buna spekülatif icra adi verilir. Eğer tahminde yanılgı söz konusu ise mikroişlemci bu tahmini baz alarak son yaptığı işlemleri iptal eder. Eğer tahmin doğru ise bu tahminle bir çok zaman kazanılmış olur.

SAPTAMA ÇALISMASI

Pentium işlemcisi daha önceki iki işlemde her hangi bir dallanma olup olmadığını anlamak için tahmini bir dallanma yapısına dalar. Her üç işlemde sıçrayan bir dallanma altı seferde bir tahmin edilir, ama asla doğru tahmin edemez. Bu işlemin iki şekli vardır: asimetrik ve simetrik. İlk önceleri asimetrik dallanmanın daha üstün olduğu kabul edilmiş, fakat simetrik dallanmanın asimetrik dallanmadan çok daha güvenilir olduğu kabul edilmiştir.

Pentium bütün dallar için tarih bilgisi saklayan alanın içine direk olarak yazmanın veya okumanın mümkün kılan bir test kaydediciler setine sahiptir, buna BTB (Branch Target Buffer). Bir dalın BTB’ ye girişi yoksa dallanmaması beklenir. İlk atlayışında BTB’ ye yapar ve 3.duruma geçer. Tasarımcılar 0.durumunu bos BTB’ ye girişi ile eşit tutukları için sorun çıkmaktadır. Bu anlamlıdır çünkü 0.durumunu hiçbir şekilde atlamaması beklenmektedir. Fakat 0.durumu ile boş BTB dal sıçrama göstermediğinde bir birinden ayıramadığı için 1.duruma gitmek yerine 3.duruma gider. Gariplikte buradan kaynaklanmaktadır. Açıkça tasarım laboratuarında bazı kimseler iyi bir dallanma tahmin şemasını bulmak için bir çok araştırmalar yaptı ve daha sonra bunlardan bazıları sonuçların farkına varmaksızın 0.durumun boş BTB girişini kastederek sıçrayan dallanmanın simetrik tasarımının da 3 kat daha fazla yanlış tahminlere sahip olacağıdır.

Şekil 3:Pentium’larda BTB (Branch Target Buffer) yapısı.

Karki J.Bahadur (Colorado üniversitesinde arastırmacı) ve Terje Mathisen (Norveçli araştırmacı) bu tasarının bir hata olduğunu göz önünde bulundurmamaktaydı. Dikkate alınan kanıt Agner Fog ismindeki araştırmacı sıkı bağlantıların farklı hareket ettiğini keşfettiğinde ortaya çıktı. Bir küçük bağlantıda mikroişlemci aynı dal komutuyla tekrar karşılaşmadan önce bir dal komutunda BTB girişini yenilemek için yeterli zamana sahip değil. Bir ertelemeden kaçınmak için o BTB’ yi es geçer ve dallanma tahmin durumunu direk olarak popline’ den okur ve bu durumda 5.şekilde gösterildiği gibi 0.durumundan 1.durumuna gidebilir.

Dallanma tahmini mekanizması için durum diyagramı

Şekil 4:Pentium’larda asimetrik tasarımı.

Dallanma komutu dallandığında (+) okları, dallanmadığında (-) okları takip eder. Dallanma komutu 2. ve 3.’üncü durumda iken bir üst basamağa atlamayı, eğer durum 0. ve 1.’de ise bir sonraki basamağa atlamamayı karar verir.

Sekil 5:Pentium’larda simetrik tasarımı.

Bu şekil dallanma tahminin nasıl çalışmalıdır gösterir. Dallandığı zaman durum artıyor (+ oklar) ve dallanmadığı zaman durum azalıyor (- oklar).

DAHA FAZLA KARIŞIKLIK.

Daha sonra da Pentium dal tahmini hakkında daha çok acayip şeyler olduğu fark edildi. Daha fazla dal komutları biri diğerinden sonra yakın geldiği zaman ne olduğunu anlaşılmadı. Agner Fog arkadaşlarıyla BTB bilgisinin onun referans ettiği dalın muhtemel komutlarını depolaya bileceğini buldular. Eğer arasında başka bir dal olursa BTB bilgisi muhtemelen yanlış dalda herhangi yerde yanlış kullanılırdı bu bir çok eğlenceli olaya neden olabilir, bu dal komutu bir BTB girişinden daha fazlasına sahip olabilir, iki komutun ayni BTB girişini paylaşabilir, böylece bir dalın diğerinin hedefine gideceğini tahmin edilir, bir uygunsuz atlama komutu dallanma olarak tahmin edebilir ve bir atlamama komutu dallanma olarak tahmin edilebilir. Bu acayipliklerin hiç biri tehlikeli değil, çünkü sonuçta bütün yanlış tahminler düzeltilebilir.

EN KUVVETLI MEKANIZMA

Pentium ailesindeki son işlemcileri (Pentium MMX, Pentium Pro, Pentium II, Celeron, Pentium III ve Xeon) dallanma tahmini mekanizmasinda baya ilerlemişler. Şekil 5’deki durum diyagramındaki ona temel fikirler bu mekanizmanın tabanıdır. Bu basitçe iki bitlik sayaçlı doyumdur. Dallandığında sayaç artıyor ve dallanmadığında ise sayaç azalıyor. Eğer sayaç 2. veya 3. durumundaysa dal komutu bir sonraki dallanmayı tahmin eder ve 0. veya 1. durumundaysa dallanmaz.

Bu mekanizma tahmin değiştirmeden önce çoğu zaman dalın iki yola sapacağından emin olur. Bir sonraki ilerlemede işlemciler,sözde iki seviyeli dallanma tahmininden gelir.

Şekil 6:Pentium III’ de iki seviyeli dallanma tahmini.

İkinci kademe üsteki şekilde olduğu gibi 16 tane iki bitlik sayaçtan oluşur. Birinci kademe son dört işlemin sürecini kaydedildiği yerdir. Bu dört bitlik kalıp  bir sonraki tahminde 16 tane iki bitlik sayacın hangisinin kullanılacağını seçmek için kullanılır.

Bir sonraki işlemcideki ilerleme iki kademeli olarak adlandırılan dallanma tahminden kaynaklanır. Birinci kademe herhangi bir dallanma tahminindeki son dört durumun kaydedildiği yerdir ve olası 16 bitlik kalıp verir. Eğer dallanma son dört islemde dallanmadiysa 0000 kalibi elde edilir ve eger dört işlemde dallandıysa 1111 kalibi elde edilir. Dallanma tahmini mekanizmasindaki ikinci kademe iki bitlik 16 tane sayaçtan olusmustur

Bu mekanizmanin avantaji, defalarca tekrarlanmis kaliplari taniyabilmesidir. Her ikinci zamanda bir dalin atlamasini düsünelim. Biz bu kalibi 01010101 olarak yazsak ve yol0 oldugunda atlamiyor, 1 oldugunda ise atliyor. Daha sonra 0101’den sonra genelde 0geldiklerini görürüz. Bu her zaman olur ve binary [0101] numarali sayaç azalmasi durumunda onu decremente götürene kadar uzaklasir. Bu mekanizma simdi 0101’den sonra 0’in geldigini ögrenir ve bu nedenle bir sonraki zaman dogru tahmin eder. Ayni sekilde [1010] numarali sayaç üçüncü durumda increment olana kadar mekanizma1010’dan sonra her zaman 1 tahmin edecek. Bu dal için geriye kalan ondört sayaç, kaliplari ayni kaldikça hiç kullanilmayacak.

Bu mekanizma 00101-00101-00101 gibi defalarca tekrarlanmis kompleks kaliplari kontrol altinda tutabildigi için tamamen güçlüdür. Gerçekten bu mekanizma azda olsa tekrarlanmis kaliplari bes ,alti ve yedi periyotta ve bazen onalti periyottan daha yüksek kaliplari kontrol altinda tutabiliyor. Eger bir kalip n periyodu yanlis tahminsiz kontrol edine biliniyorsa, n kalibini dördüncü bit takip eder. Eger bu kaliplar hepsi farkli ise, o halde baslangiçtaki iki periyottaki kaliplari ögrendikten sonra yanlis tahmin olmayacak.

Fakat iki seviyeli mekanizma ondan daha güçlüdür. O,düzenli kaliptan sapmayi kontrol elinde tutmasinda son derece iyidir. Eger dal komutu neredeyse düzenli kalibi sirali sapmaya sahipse, o zaman islemci hemen sapmanin benzedigini ögrenecek, böylece o herhangi bir çesit yinelenen sapma ile sadece bir yanlis tahmin yapacak.

İlaveten o iki farkli tekrarlanan kalibin arasinda degiserek olusan bir durumun üstesinden gelebilir. O yanlis tahminsiz üstesinden gelmeyi ögrenene kadar bir tekrarlanan kalip islemcisi verdigini farz edelim. Sonra diger kalibi ve sonra birinci kaliba dönülür. Eger iki kalip her hangi sonraki dört bite genelde sahip degilse onlar ayni sayicilari kullanmazlar, bundan dolayi islemci birinci kalibi tekrar ögrenmek zorunda degil. Böylece o minimum yanlis tahminle iki kalibin arasindaki ileri geri geçisleri yönlendirebilir.

[2]5 BTB DÜZENLEYICI.

Pentium III’ün BTB’si 512 girisli iken 16 yollu, 32 sete sahiptir. Her giris, 4-31 bitlerin sahip olduklari adresin son byte’lerinin kontrol transfer komutlari tarafindan tanimlanir. 4-8 bitleri seti tanir ve tüm bitler BTB’de iken etikete kaydedilir. 512 byte dizilen kontrol transfer komutlari bazi farkli set degerlerine sahipler ve bunun için bazen  BTB’nin disina  kontrol transfer komutu her digerini itebilirler. Bundan önce orda set basina 16 yol düsüyordu ve gelecekte bu olay sik sik olmayacak. Pentium III ; BTB girisini, herhangi bir kontrol transfer komutunun uygulanacagi ilk zamana göre ayirir, fakat PMMX ilk dallandigi zamanda ayirir. Dal komutu hiç  dallanmadan PMMX deki BTB’nin disinda kalacaktir.

[2,5]6 YANLIS TAHMIN CEZASI.

Pentium III’de yanlis tahminin cezasi Popline’nin uzunlugundan dolayi çok yüksektir. Genelde yanlis tahminin birinin degeri 10 ve 20 saykilla arasindadir. Zayif olan dallanma tahminlerinin Pentium III’e gidisinin fakinda olmasindan dolayi, yanlis tahminin cezasi çok önemlidir.

Sekil 7:Popline’de dogru ve hatali tahmin. Sol taraftaki Popline dogru tahmin yapildigi durum, sag taraftaki Popline ise hatali tahmin yildigi durum.

Komut Ceza(Zamani)
jcc

jmp         (dolaysiz)

jmp         (dolayli)

ret

call         (dolaysiz)

call         (dolayli)

U-pipe V-pipe
33

3

3

3

3

43

NP

NP

3

NP

Tablo 1:Popline’de hatali tahmin Popline’de hatali tahmin sonucu zaman kayibi.

Benzer Yazılar
MEB nın resmi web adresinde yayınlanan bilgilere göre direksiyon sınavında 4 defa başarısız olanlar için
Taşımacılık basit bir iş değildir. Her ne kadar ev eşyası ve ya farklı eşya taşımacılığı
13 Mart 2016 tarihi 2016 YGS Soru Kitapçığı ile Cevap Anahtarına, 14 Mart 2016 günü
2015 Best Free Magazine, News and Personel Blog WordPress Themes SmartLine WordPress Theme Smartline Demo 
Evde çocukların oyun oynarken veya anne babalarının haberi olmadan yaptıkları komik davranışlar ve yaramazlıkları  
Soru1.: Meslek Lisesi mezunları mühendis olabilir mi? Cevap:Meslek Lisesi mezunları Mühendislik Fakülteleri veya Teknoloji Fakülteleri´nin
Her zaman teknoloji, internet ve web tasarımı bilgileri verirken, dünyada başka şeylerin de öenmli olduğunu
Please follow and like us:
0

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir