Pipeline Sorunları ve Out-Of-Order Execution - Bölüm 1

Bu yazı, iki bölümden oluşmaktadır.
İlk bölümde klasik pipeline mimarisindeki sorunlar ve bu sorunlara getirilen çözümlerden; ikinci bölümde ise out-of-order execution mimarisinden detaylıca bahsetmeye çalışacağım.

Yüksek performanslı mikroişlemcilerde ILP (Instruction Level Parallelism)’den olabildiğince yüksek seviyede faydalanmak için in-order işlemcilerde kullanılan klasik pipeline mimarisi yerine out-of-order pipeline kullanılır. Out-of-order execution modelinde işlemci, komutları Instruction Fetch Queue’dan program sırasına göre alır (Bu aşamaya Issue Stage denir.) fakat bu komutları program sırasına göre çalıştırmayabilir. Bu sayede işlemci komutlar arasındaki bağımlılıkların neden olacağı beklemelerden(stall) ve dolayısıyla performans kaybından en az derecede etkilenmeye çalışır. Out-of-order işlemcilerin nasıl çalıştığını incelemeden önce klasik in-order pipeline mimarisinden kısaca bahsetmek istiyorum.

Not:Bu yazıda anlatacağım konuları, RISC-V mimarisini baz alarak anlatmaya çalışacağım. Kullanılan assembly kodları bu mimariye aittir.

In-Order Pipeline

Klasik RISC pipeline’ı aşağıdaki adımlardan oluşur:

1. Komutu bellekten oku (Instruction Fetch-IF)
2. Komuttaki yazmaçları oku ve komutu çözümle. (Instruction Decode-ID)
3. Komutu çalıştır(Execute-EX)
4. Eğer gerekliyse belleğe eriş(load-store komutları). (Memory Access-MEM)
5. Yazmaçların yeni değerlerini Register File’a yaz (Writeback-WB)

Bu adımlarda neler olduğunu aşağıdaki şekil üzerinden inceleyelim:

Fark ettiğiniz üzere her bir çevrimde birden fazla komut işletilmektedir. Mesela 2. çevrimde ilk komut ID aşamasındayken, 2. komut IF aşamasındadır. Böylece 5 aşamalı pipeline’da aynı anda 5 farklı komut işletilebilir. Buradaki aşama sayısı tasarlanan işlemcinin ne kadar yüksek hızda çalışacağına göre değişiyor. Aslında pipeline mimarisi olmayan, dertsiz tasasız tasarımı nispeten kolay Single Cycle CPU da tasarlanabilir. Fakat bu tür bir mimaride, CPU’nun çıkabileceği maksimum hızı, propagasyon gecikmesi en fazla olan komut(Critical Path) belirler; bu komut genellikle ‘load’(Memory Read) komutudur.

Örneğin, ‘load’ komutunun oluşturacağı propagasyon gecikmesi 20 ns olsun. Bu durumda, işlemcinin clock periyodu minimum 20ns olabilir. Daha düşük olursa ‘load’ komutu düzgün çalışamaz. Propagasyon gecikmesini şöyle düşünebilirsiniz: dijital bir devre tasarladınız ve bu devrenin girişinden ne verilirse çıkışından da o okunsun. (Saçma bir devre oldu ama konuyu anlatmak açısından güzel bir örnek :) ) Bu devrede kullanılan mantık kapılarından dolayı, girişten verilen sinyal ile çıkıştan okunan sinyal arasında bir zaman farkı oluşur. İşte bu zaman farkına propagasyon gecikmesi, tasarlanan devredeki en uzun propagasyon gecikmesini oluşturan hatta da Critical Path deniliyor.

Bu sebeple, Critical Path’i küçültmek için pipeline mimarisinden faydalanılıyor. Bu mimaride, her bir aşama arasında IF/ID, ID/EX, EX/MEM ve MEM/WB isimlerinde yazmaçlar bulunur ve o aşamaya ait sonuçlar(register değerleri, kontrol sinyalleri vs.) bu yazmaçlarda saklanır. Bir sonraki aşama da saklanan bu değerleri kullanır.

Örneğin, her bir komutun çalışabilmesi için gereken süreler aşağıdaki tablodaki[1] gibi olsun.

Single Cycle bir CPU’da ‘ld’ komutu için 800 ps gerektiğinde CPU’nun çalışabileceği mininum clock periyodu 800 ps olmalıdır. Fakat 5-stage pipeline’lı bir mimari tasarlanırsa clock periyodu 200 ps’ye kadar düşürülebilir(En uzun aşama 200 ps olduğundan). Yani pipeline ne kadar derinleştirilirse hız o kadar artar. Eğer aşamalar kusursuz dengeli bir şekilde tasarlanırsa 5-stage pipeline’da 5 kat hız artışı elde edilebilir. Yani clock periyodu 160 ps’ye kadar düşürülebilir. Fakat bu tasarımda, yukarıdaki tablodan da görüleceği üzere en uzun aşama 200 ps olduğu için periyot minimum 200 ps olabilir.

“Tamam o zaman, pipeline aşamalarını artırabildiğimiz kadar artıralım, böylece çok yüksek hızlarda çalışabiliriz.”

Gibi bir şey aklınıza gelebilir. Fakat, klasik pipeline mimarisi ilk bakışta mükemmel gibi gözükse de bazı kusurları vardır.

Pipeline Hazards

Komutlar arasındaki bağımlılıklardan dolayı, bazı durumlarda her çevrimde bir komut işlenemeyebilir. Çevrim başına düşen komut sayısı(IPC) pipeline mimarisindeki performans ölçütümüzdür. Yani IPC’yi 1'e yaklaştırmaya çalışıyoruz(Bu,superscalar olmayan mimariler için geçerli. Superscalar mimarilerde 1 den büyük olabiliyor.). Ama bu oran, komutlar arasındaki bağımlılıklardan dolayı genelde 1'den küçük oluyor. Bu bağımlılıklar, bazı komutlar için ekstra gecikme olmadan çözülebilirken bazı durumlarda mecburen pipeline hattını durdurmak(stall) gerekebiliyor. Pipeline derinleştikçe artan ve daha da fazla performans kaybına neden olan ana sebep de bu beklemelerdir. Mesela 5-stage pipeline’da bir hazard’ın çözülebilmesi için 1 çevrim gerekirken 8-stage pipeline’da 3 çevrim gerekebilir.

Klasik Pipeline’da karşımıza çıkabilecek pipeline hazard türlerini inceleyelim.

Structural Hazards

Mesela sistemde tek portlu tek bir bellek olduğu ve ‘load’ komutunun MEM aşamasında olduğunu varsayalım. Bu durumda, bir sonraki komut da bellekten okunacağı için ve sistemde tek bir bellek olduğu için komut okuma işlemi yapılamayacak ve mecburen ‘load’ komutunun bir sonraki aşamaya geçmesi beklenecek.Yani 1 çevrim bekleme oluşacak. Fark ettiğiniz üzere, bu hazard türüne yapılabilecek bir şey yok.

Data Hazards

Bu yazının asıl amacı bu hazard tipinden kurtulmak. Yani out-of-order execution modelinin geliştirilmesindeki en büyük motivasyon, data hazard’lardan kurtulmak. Bu hazard 3 farklı şekilde oluşabilir: RAW(Read After Write), WAR(Write After Read) ve WAW(Write After Write). Fakat klasik integer pipeline’da sadece RAW hazard oluşabilir.(Floating Point Unit gibi Multi Cycle bir Execution Unit olması durumunda WAW hazard da oluşabilir) Bu yüzden biz şimdilik RAW hazard’ı inceleyeceğiz. Aşağıdaki gibi bir kod olduğunu farz edelim:

add x3, x1, x2 # x3 = x1 + x2
sub x4, x3, x2 # x4 = x3 + x2

Bu durumda x3 yazmacından dolayı 2 komut arasında bir bağımlılık oluşuyor. Yani ‘sub’ komutu, ‘add’ komutu x3'e sonucu yazmadan önce ID aşamasına geçemez; çünkü bu aşamada x3'ün değerini Register File’dan okuması gerekir. Ama neyse ki bu hazard hiç bir bekleme olmadan ’forwarding’ yöntemi ile çözülebilir: ‘sub’ komutu ID aşamasında Register File’dan yanlış x3 değerini okur, bu sırada ‘add’ komutu bir sonraki aşama olan EX aşamasındadır. Bu çevrimin sonunda x3 değeri üretilecek fakat WB aşamasına gelinmediği için Register File’a yazılmayacak. “Yazılmasın! Nasıl olsa x3 değeri hesaplandı. Niye kullanmayalım ki!” Bir sonraki çevrimde ‘sub’ komutu ID aşamasında okuduğu x3'ü kullanmak yerine, MEM aşamasında olan ‘add’ komutundan gelecek olan x3'ü kullanarak, bu hazard bertaraf edilir.
“Eee tamam. Abartacak bir şey yokmuş.Bu kadar tantanaya ne gerek var? Nerde performans kaybı?”

Diyebilirsiniz. Ama yukarıdaki kodun aşağıdaki gibi olduğunu farz edelim:

ld x3, 10(x1) # x3 = *(x1 + 10)
sub x4, x3, x2 # x4 = x3 + x2

Yine ‘sub’ eski x3 değerini Register File’dan okuyup EX aşamasına geçmiş olsun. Fakat hâlâ forward edebileceğimiz x3 değeri ortalıkta yok. Çünkü x3'ü ‘ld’ komutu şu an içinde bulunduğu MEM aşaması bittikten sonra elde edecek. Mecburen ‘sub’ komutu ve sonrasındaki tüm komutlar 1 çevrim beklemek zorunda. (Belleğe erişimin 1 çevrim sürdüğünü varsayıyoruz. Cache miss durumunda, yani ana belleğe erişmek zorunda kalındığında bu değer 100 çevrim bile sürebiliyor. Performans kaybını düşünün).

Control Hazards

Bu hazard’a dallanma komutları neden oluyor.Aşağıdaki gibi bir kod olduğunu farz edelim:

sub x1, x4, x5 # x1 = x4 - x5
beq x0, x1, done # if(x0 == x1) goto done
add x3, x4, x5 # x3 = x4 - x5
...
...
done:
...
...

Normalde x0 ve x1'in karşılaştırma işlemi ALU’da yani Execute aşamasında yapılır fakat bu işlem çok fazla propagasyon gecikmesine neden olmayacağı için daha fazla stall olmaması için ID aşamasında yapılır. Fakat böyle olsa bile ‘beq’ ID aşamasına geldiğinde ‘add’ komutu fetch edilmiş olacak. Eğer x1 ve x0 birbirine eşit çıkarsa ‘done’ etiketine dallanılacağı için ‘add’ komutu için yapılmış olan fetch işleminin çöpe atılması gerekecek. Tabi bu karşılaştırma işlemini ID aşamasına almanın bir bedeli var. Karşılaştırma işlemi EX aşamasında yapılmaya devam etseydi ‘sub’ ile ‘beq’ arasındaki bağımlılık forwarding ile çözülebilirdi. Fakat artık ‘beq’ komutu, x1 değerine ID aşamasının başında ihtiyaç duyuyor ve ‘sub’ komutu da bu sırada EX aşamasının başında. Bu durumda da, hazard’ın çözülebilmesi için ekstra 1 çevrime ihtiyaç var.(Aslında ikinci hazard tipi, data hazard.Fakat bu hazard tipi ile ilişkili olduğu için burda anlattık.)

Buraya kadar anlatılanlar, integer pipeline mimarisi ile ilgiliydi.Eğer işlemciye Floating Point Unit gibi Multi Cycle bir execution unit eklenirse işler biraz daha karşırıyor.Microarchitecture’umuzu floating point unit içerecek şekilde genişletelim.

MultiCycle Execution Units

Karşınızda yeni mimarimiz.[2]

Integer pipeline’da EX aşaması 1 çevrim sürüyordu. Bu sayede ‘load’ ve ‘branch’ komutları hariç komutlar arası gecikme bağımlılık olsa bile 0 idi. Ama floating point işlemler 1 çevrimde bitebilecek kadar basit değil. Şekilden de görülebileceği gibi multiply işlemleri 7, floating point add işlemleri 4, divide işlemleri ise 24 çevrim serüyor. Üstelik divide biriminin kendi içerisinde pipeline’ı da yok.Yani peş peşe iki tane divide işlemi varsa ikinci divide 24 çevrim beklemek zorunda. Yani bu durum,24 çevrim gecikmeye neden olan structural hazard oluşturuyor. Bu mimaride birden fazla execution unit olduğundan ve execution unit’lerin çalışma süreleri birbirinden farklı olduğundan, komutlar program sırasına göre tamamlanmayabiliyor(out-of-order completion). Aşağıdaki gibi bir kod olduğunu varsayalım:
(‘f’ ile başlayan komutlar floating point komutları temsil ediyor)

fmul.d f0, f1, f2 # f0 = f1 * f2
add x0, x1, x2 # x0 = x1 + x2

Bu iki komut arasında hiç bir bağımlılık olmadığı ve ‘add’ komutunun EX aşaması 1 çevrim, fmul.d komutunun EX aşaması 7 çevrim sürdüğü için ‘add’ komutu fmul.d komutundan önce tamamlanır.

Execution unit’lerin çalışma süreleri uzun olduğu için hazard oluşması durumda gecikme süreleri integer pipeline’a göre çok daha uzun olabiliyor. Ayrıca komutların tamamlanma süreleri birbirinden farklı olabileceği için yani program sırasına göre tamamlanmayabilecekleri için integer pipeline’dan farklı olarak WAW(Write After Write) hazard oluşma ihmali de var. WAR hazard oluşma ihtimali yok çünkü komutlar her koşulda ID aşamasına program sırası göre giriyor. Aşağıdaki gibi bir kod olduğunu farz edelim:

1. fld f4, 20(x1)   # f4 = *(x1+20)
2. fmul.d f1, f4, f2 # f1 = f4 * f2
3. fsub.d f0, f8, f1 # f0 = f8 - f1
4. fadd.d f0, f2, f3 # f0 = f2 - f3
5. fadd.d f8, f6, f4 # f8 = f6 - f4

fmul.d ile fld arasında f4 yazmaçından kaynaklanan bağımlılıktan dolayı RAW hazard oluşur ve bu da 1 çevrim gecikmeye neden olur. fmul.d ile fsub.d arasında f1 yazmaçından kaynaklanan bağımlılıktan dolayı yine RAW hazard oluşur bu da 5 çevrim gecikmeye neden olur. fsub.d ile fadd.d arasında f0 dan dolayı WAW hazard oluşur ve bu da 3 çevrim gecikmeye sebep olur. 5.satırdaki zavallı fadd.d komutunun da -hiç bir bağımlılığı olmadığı halde- in-order execution’dan dolayı çalışması mecburen gecikiyor.
(“Hiç adil değil! Zaten rivayetlere göre bu fadd.d komutunun çıkardığı isyandan dolayı out-of-order execution’a geçilmiş. :) ”)

Buraya kadar pipeline mimarisinden kaynaklanan hazard’lardan bahsettik. Fakat büyük bir sorunumuz daha var. Exceptions!.

Precise Exceptions

Multicycle Execution Unit’lerin varlığı, daha doğrusu komutların program sırasına göre tamamlanmaması, aşağıdaki gibi bir soruna yol açıyor:

fdiv.d f0, f1, f2 # f0 = f1 / f2
fadd.d f3, f4, f5 # f3 = f4 + f5
fsub.d f6, f7, f8 # f6 = f7 - f8

Aslında bu kodda komutlar arasında hiç bir bağımlılık yok. Fakat fadd.d ve fsub.d komutları, fdiv.d komutundan sonra olmalarıına rağmen, fdiv.d komutu çok uzun sürdüğünden dolayı daha önce tamamlanırlar. (“Eee tamam ne var bunda. Ne güzel bağımlılık da yok.fadd.d komutları fdiv.d’yi beklemek zorunda değil.”). fadd.d komutu tamamlandıktan hemen sonra bir exception oluştuğunu farz edelim. (Burada bahsedilen exception, external ya da internal olabilir. Aslında external exception’lara interrupt da deniliyor; fakat biz burda ayrım yapmıyoruz. Önemli olan exception handler’ın çalıştırılmak zorunda olması. Bazı exception’lar bu duruma sebep olmayabiliyor.)
Bu durumda işlemcinin, fdiv.d ve sonrasındaki komutları pipeline’dan temizlemesi gerekir. Çünkü program,exception handler’a dallanmadan önce işlemcinin o anki durumunun güvenli bir şekilde kaydedilmesi gerekir. Fakat bu durumda fadd.d komutunu çoktan çalıştırdı ve sonuç, Register File’a yazıldı. Bu büyük bir sorun!. Exception handler’da çalıştırılacak kodlar fdiv.d komutunun fadd.d komutundan önce çalıştırılacağını varsayarak yazılmış olabilir.
Bu problemi çözmenin bir kaç farklı yolu var; fakat out-of-order execution’da da kullanacağımız için Reorder Buffer(ROB) çözümünü inceleyelim.

Reorder Buffer

Eğer microarchitecture’a komutların değerini, Register File’a yazılmadan önce tutacak bir buffer eklersek sorunumuzu çözebiliriz. Yeni senaryo şu şekilde:
1. Komutlar Instruction Queue’dan okunur.
2. ROB’da bu komut için bir satır ayrılır.
3. Komut işletilirken bir exception’a neden olmuşsa ROB’da ilgili komuta ait satıra, bu exception bilgisi yazılır.
4. IF,ID,EX,MEM aşamaları daha önce anlatılan gibi tamamlanır.
5. WB aşamasında sonucu, Register File’a yazmak yerine ROB’da ilgili komuta ait satıra yazılır.
6. ROB, komutları program sırasına göre Register File’a yazar.(Bu işleme yeni mimaride Retire ya da Commit adı verilir)

ROB’un her bir satırı, kaba taslak aşağıdaki gibidir. (Normalde store komutu için farklı Result sütunları da olur.)

Komut, Instruction Queue’dan okunduğunda Program Counter bilgisi ve komutunun sonucunun yazılacağı yazmaçın ID’si, gerekli satıra yazılır.Program Counter bilgisi, exception oluştuğunda buradan okunup kaydedilir.
-Bir exception oluşunca, program, exception handler’a dallanmadan önce bazı yazmaçlar (Program Counter,Stack Pointer,bazı genel amaçlı yazmaçlar vs.) donanım tarafından genelde stack’e saklanır. Exception handler’dan çıkıldıktan sonra saklanan bu değerler geri yüklenir ve exception oluşmadan önceki duruma geri dönülür. Bu olaya Context Switching denir ve programcı tarafından hissedilmez.-
Komut işletilirken bir exception oluşursa exception bilgisi ilgili sütuna yazılır. Komutun çalışması bitince de sonuç ROB’un Result sütununa yazılır.ROB da, sonucu yazılmış komutların sonuçlarını sırasıyla Register File’a yazar.
“Bu arada, sonuçlar sanki hep Register File’a yazılıyormuş gibi söylüyoruz ama store komutlarının sonuçları Register File’a yazılmaz bellek’e yazılır. Fakat ‘load-store’ komutlarında yapılan işlemler daha farklı olduğu için bu yazı da onlardan bahsetmek istemedim. ‘Load-Store’ komutlarında yapılan işler başka bir yazının konusu olsun”.
ROB’u circular buffer gibi düşünebilirsiniz.Her komut eklendiğinde ya da retire işlemi yapıldığında head ve tail pointer’ları artar-azalır.Bir komut en başa geldiğinde retire işlemi yapılmadan önce,exception kontrolü yapılır. Eğer exception varsa o komuttan sonraki tüm komutlar silinir ve program exception handler’a dallanır.

Fakat karşımıza başka bir sorun daha çıktı! Aşağıdaki gibi bir kod olduğunu düşünün.

fadd.d f0 , f1 , f2 # f0 = f1 / f2
fdiv.d f3 , f2 , f4 # f3 = f2 / f4
….
….
….
fsub.d f5 , f0 , f1 # f5 = f0 - f1

Bu kodda fadd.d komutu çalışmasını tamamladıktan sonra fdiv.d komutu tamamlanana kadar ROB’da bekler. fdiv.d komutu işletilirken hiç bir bağımlılık olmadığı için fsub.d komutu çalıştırılır. Fakat bir sorun var! fsub.d, f0 yazmaçını okumak isteyecek; ama fadd.komutu, henüz retire aşamasına gelmediği için f0'ın güncel değerini Register File’a yazamamış olacak. Bu durumda ya fadd.d’nin retire edilmesi beklenecek ya da daha akıllıca bir çözüm olan bu değeri ROB’dan okunacak.

”- Böyle anlatınca kolay gibi gözüküyor ama her çözüm başka bir sorun doğuruyor.
- Yine ne oldu?
- Daha ne olsun! ROB’daki komutlar yazmaç id’lerine göre sıralanmıyor; program sırasına göre sıralanıyor. Yani mecburen istenilen yazmaçın değerini ROB’da aramak zorundayız. Bu da çok fazla gecikme yaratır.
- Haydaaa”

Bunu yapabilmek için Register File’ın yapısında da biraz değişiklik yapmak gerekiyor. ROB’da okumak istediğimiz değeri hızlıca bulabilmek için Register File’da her bir yazmaçın bulunduğu satıra bir sütun ekleyip, bu sütuna o yazmaçın güncel değerinin ROB’un hangi satırında tutulduğunu yazmamız gerekir.
Şimdi yeni tasarımımız şöyle:
ID aşamasına gelindiğinde, komut çözülüp, gerekli yazmaçlar, Register File’dan okunur. Register File okunan yazmaçın satırına bakar. Eğer güncel değer ROB’da ise ROB okur; değilse kendi tuttuğu değeri çıkışına yazar. Tabi komutlar için ROB’da satır ayrıldığında, ayrılan satır numarası,Register File’da, sonucun yazılacağı yazmaçın satırındaki ilgili sütuna yazılır.Örneğin aşağıdaki komut okunduğunda, ROB’da ayrılan satır numarası 3 ve f1 ve f2 ROB’da olsun.

fadd.d f0 , f1 , f2 # f0 = f1 + f2

Bu durumda, Register File, f1 ve f2 değerlerinin bulunduğu satırı kontrol eder bu yazmaçların değerlerini ROB’dan okur ve çıkışa yazar. f0'ın bulunduğu satırdaki ilgili sütuna 3 yazar.
“Peki ya f1 ya da f2 nin değeri henüz belli olmamışsa?”
Gibi bir soru aklınıza gelebilir. Bu durum zaten RAW hazard oluşturur. Yani mecburen bu değerler ROB’a yazılana kadar beklenir.
Ya da bir komut okunduğunda ROB dolu da olabilir. Bu da structural hazard oluşturur.Yine, bu hazard çözülene kadar komutun çalıştırılması bekletilir.

İlk bölümü burada bitirebiliriz. Bir sonraki bölümde görüşmek üzere.

Hoşçakalın…

Not: Bu yazıda kullandığım görseller, “Computer Organization and Design: The Hardware/Software Interface” ve “Computer Architecture: A Quantitative Approach” kitaplarından alınmıştır.

İkinci Bölüm…

Kaynaklar:

[1] Computer Organization and Design: The Hardware/Software Interface
[2] Computer Architecture: A Quantitative Approach
[3]James E. Smith,Andrew R. Pleszkun 1998.Implementation of Precise Interrupts in Pipelined Processors.
[4]Onur Mutlu Lectures: Digital Design & Computer Architecture — Lecture 14: Pipelining Issues (ETH Zürich, Spring 2020)