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

Static Scheduling

fmul.d f0,f1,f2
fdiv.d f4,f0,f3
fadd.d f7,f8,f9
fadd.d f7,f8,f9
fmul.d f0,f1,f2
fdiv.d f4,f0,f3

Loop Unrolling

for (i=999; i>=0; i=i1)
x[i] = x[i] + s;
#f2'de 's' ve x2'de 0. indeksteki elemanın değeri saklı. Bir eleman #8 byte uzunluğunda
Loop: fld f0, 0(x1) #f0=dizi elemanı
fadd.d f4, f0, f2 #f4 = x[i] + s
fsd f4, 0(x1) #f4'ü x[i] adresine yükle
addi x1, x1, -8 #indeks'i 8 azalt
bne x1, x2, Loop #if(x1 != x2) goto Loop
Loop: fld f0, 0(x1) #f0 = dizi elemanı
stall #bekle
fadd.d f4, f0, f2 #f4 = x[i] + s
stall #bekle
stall #bekle
fsd f4, 0(x1) #f4 x[i] adresine yükle
addi x1, x1, -8 #index'i 8 azalt
bne x1, x2, Loop #if(x1 != x2) goto Loop
Loop: fld f0, 0(x1) #f0 = dizi elemanı
addi x1, x1, -8 #index'i 8 azalt
fadd.d f4, f0, f2 #f4 = x[i] + s
stall #bekle
stall #bekle
fsd f4, 8(x1) #f4 x[i] adresine yükle
bne x1, x2, Loop #if(x1 != x2) goto Loop
Loop:
fld f0, 0(x1)
stall
fadd.d f4, f0, f2
stall
stall
fsd f4, 0(x1)
fld f6, -8(x1)
stall
fadd.d f8, f6, f2
stall
stall
fsd f8, -8(x1)
fld f0, -16(x1)
stall
fadd.d f12, f0, f2
stall
stall
fsd f12, -16(x1)
fld f14, -24(x1)
stall
fadd.d f16, f14, f2
stall
stall
fsd f16, -24(x1)
addi x1, x1, 32
bne x1, x2, Loop
Loop:fld f0, 0(x1)
fld f6, -8(x1)
fld f0, -16(x1)
fld f14, -24(x1)
fadd.d f4, f0, f2
fadd.d f8, f6, f2
fadd.d f12, f0, f2
fadd.d f16, f14, f2
fsd f4, 0(x1)
fsd f8, -8(x1)
fsd f12, 16(x1)
fsd f16, 8(x1)
addi x1, x1, -32
bne x1, x2, Loop

Dynamic Scheduling

  • Bir microarchitecture için yazılmış bir binary başka bir microarchitecture’da da, gayet efektif bir şekilde çalışabilir. Mesela Arm Cortex-A9 ile Arm Cortex-15 aynı Instruction Set Architecture’a(ARMv7-A) sahip olmalarına rağmen pipeline derinlikleri birbirinden farklıdır. Dynamic scheduling sayesinde ARMv7-A için yazılmış bir kod her iki işlemcide de optimize bir şekilde çalışabilir.
  • Bazı bağımlılık derleme zamanında çözülemeyebiliyor. Mesela bellek referansları(birazdan buna değineceğiz.), ya da dynamic linking’den kaynaklanan bağımlılıklar.(Dynamic library, run time’da hali hazırda çalışan executable’a linklendiğinde dynamic libraryden kaynaklanan bir bağımlılık ortaya çıkabilir. Bunun derleme zamanında çözülme ihtimali yok tabi ki.)
  • En önemlisi de bu aslında; derleme zamanında çözülemeyecek, cache miss’lerden kaynaklanan gecikmeler, dynamic scheduling sayesinde çözülebilir. Mesela bir ‘load’ komutunun sonucu bellekten beklenirken başka bir komut çalıştırılabilir.
fdiv.d f6, f2, f4 #f6 = f2/f4
fmul.d f6, f0, f8 #f6 = f0 * f8
fadd.d f0, f10, f14 #f0 = f10 + f14

Tomasulo Algoritması

fdiv.d f0,f2,f4 # f0 = f2 / f4
fadd.d f6,f0,f8 # f6 = f0 + f8
fsd f6,0(x1) #*(x1) = f6
fsub.d f8,f10,f14 #f8=f10-f14
fmul.d f6,f10,f8 #f6=f0*f8
fdiv.d f0,f2,f4
fadd.d S,f0,f8
fsd S,0(x1)
fsub.d T,f10,f14
fmul.d f6,f10,T
fld f0, 8(x2)
fsd f2, 16(x5)
  1. Issue: Bu aşamada komutlar instruction queue’dan program sırasına göre okunurlar ve uygun reservation station’a yerleştirilirler. Eğer boş reservation station yoksa bu durum structural hazard oluşturur ve komut uygun bir reservation station boşalana kadar bekletilir. Register renaming bu aşamada yapılır. Eğer ihtiyaç duyulan yazmaçlar mevcut değilse bunu belirtecek şekilde reservation station’a yerleştirilirler.
  2. Execute: Eğer bir ya da her iki operand mevcut değilse, common data bus, bu operandlar mevcut olana kadar izlenir. Bir operand üretildiğinde onu bekleyen reservation station’a yerleştirilir. Tüm operand’lar mevcut olduğu anda ise o işlem ilgili execution unit’de çalıştırılır.
  3. Write Result: Execution unit çalışmasını bitirdikten sonra sonucu common data bus’a yazar. Sonuc buradan tüm reservation station’lara ve register file’a gider. Bu sonuca ihtiyaç duyan reservation station bu sonucu alır kaydeder.
  • Op — Hangi komutun işletileceği bilgisi.(Örn:sub,mul,add ..)
  • Qj,Qk — Beklenilen operandlar, j ve k olarak isimlendirilir. Qj, j operand’ını, Qk, k operandını hangi reservation station’ın üreteceği bilgisini tutar. Eğer operandlar zaten mevcutsa buradaki değer 0 olur.
  • Vj,Vk — Operandların değerlerini tutar. Bir operanda ait bilgi ya V alanında ya Q alanında bulunabilir. Yani bir operand bekleniyorsa Q alanında o operandı kimin üreteceği bilgisi tutulur. Operand üretildiğinde ise Q alanı 0 yapılır, değer V alanına yazılır. Load ve store işlemleri için V alanı offset bilgisini tutar.
  • A — Store ve load komutları için adres bilgisi bu alanda tutulur.
  • Busy — Reservation station ve ona ait execution unit’in meşgul olduğu gösterir.
  • Qi — Bu register’ın değerini üretecek reservation station’ın id’si. Bir komut instruction queue’dan okunup reservation station’a yerleştirileceği zaman bu alanı okuyarak, yazmaçın değerini hangi reservation station’ın üreteceğini öğrenir. Eğer bu alanın değeri 0 ise aktif hiç bir komut bu yazmaçın değerini üretmeyeceği anlamına gelir. Yani direkt register file’dan okunup kullanılabilir.
Loop: fld f0,0(x1) # f0=*(x1)
fmul.d f4,f0,f2 # f4=f0*f2
fsd f4,0(x1) # *(x1)=f4
addi x1,x1,-8 # x1-=8
bne x1,x2,Loop if(x1!=x2) goto Loop
  • Sadece birinci ve ikinci iterasyondaki fld komutları execute aşamasını geçebildi ve A alanına adresler yazıldı. Diğerleri bu bağımlılıklardan dolayı bekliyor. Bellekten okuma uzun sürdüğü için diğer komutlar henüz execute aşamasına geçebilmiş değil.
  • ‘fmul’ komutlarının ikinci operand’ı olan ‘f2’ mevcut olduğu için direkt olarak değerleri reservation station’a yazıldı. Diğer operand’ı ise ‘fld’ komutu üreteceği için ilgili load buffer id’leri(Load1,Load2) Qj alanına yazıldı. Load1 ilk iterasyondaki fld’yi Load2 ise ikinci iterasyondaki fld’yi ifade ediyor.
  • ‘fsd’ komutu, ‘fmul’ sonucunu beklediği için reservation station id’leri(Mult1,Mult2) Qk alanına yazıldı. Diğer operand x1 ve x1 mevcut olduğundan Vj alanına X1 ve X1–8 (İkinci iterasyonda X1'in değeri 8 azalıyor) yazıldı.
  • Tabi bu sırada register file’ın Qi alanı da güncelleniyor. Farkettiyseniz en son hangi reservation station üretecekse o yazıyor(Load2, Mult2). Aslında o değerler ilk başta Load1 ve Mult1 idi ama ikinci iterasyonda sonuç yine aynı yazmaça yazılacağı için güncellendiler.
fld f0,0(x1)
fld S,-8(x1)
fmul.d f4,f0,f2
fmul.d T,S,f2
fsd f4,0(x1)
fsd T,-8(x1)
addi x1,x1,-16 # x1-=8
bne x1,x2,Loop if(x1!=x2) goto Loop

Speculative Execution

  • Instruction Type: Bu alanda komutun tipi tutulur. Yani dallanma komutu mu(Bu komutların hedef bir yazmacı yoktur.), store komutu mu(Bu komutların hedefi register file yerine bellektir), diğer yazmaç komutları mı(load ya da alu işlemileri; her iki tip komutun da hedefi register file’dır)
  • Destination: Bu alanda load ve alu(fadd,add,fmul,…) komutları için hedef yazmaç numarası, store komutları için hedef bellek adresi tutulur.
  • Value: Komutun sonucu bu alanda tutulur
  • Ready: Bu alan komutun çalışmasını tamamladığını ve sonucun hazır olduğunu belirtir.
  1. Issue: Bu adımda komut instruction queue’dan okunur. Eğer reorder buffer ve uygun reservation station varsa, komut reservation station’a yerleştirilir ve reorder buffer’da bu komut için bir satır ayrılır. Ayrılan satır numarası da reservation station’daki ilgili alana yazılır. Eğer uygun reservation station ya da reorder buffer’da boş alan yoksa bu durum structural hazard oluşturur ve uygun alan oluşana kadar beklenir.
  2. Execute: Bu adımda operand’lar CDB izlenerek beklenir. Her iki operand uygun olduğunda çalıştırılmak üzere execution unit’e gönderilir. Store komutuları, adres hesaplama işleminden sonra; load ise adres hesaplanıp, bellek okuması işleminden sonra bir sonraki aşamaya geçer. Yani load orjinal Tomasulo’daki gibi yine iki adımda execution aşamasını tamamlar.
  3. Write Result: Bu aşamada execute aşamasındaki sonuçlar CDB’ye ve oradan da reorder buffer’a yazılır. (Tabi CDB’ye yazılan sonuçlar diğer reservation station’lara da gider.Isteyen bu sonucları kullanır.) Az önce de bahsettiğimiz gibi store komutu için bir istisna vardır, eğer CDB’ye yazılan sonuç reorder buffer’daki herhangi bir store komutuna aitse Value alanına bu sonuç yazılır.
  4. Commit: Final aşamasında komutların sonuçlar gerekli yerlere yazılır. Burada üç farklı durum gerçekleşebilir: komutun yanlış tahmin edilmiş dallanma komutu olması, store komutu olması ve diğer komutlardan biri olması. Reorder buffer’ın en başına gelen komut, normal komutsa yani sonucu register file’a yazılacak bir komutsa sonuc register file’a yazılır, store komutu ise yine aynı işlemler yapılır fakat sonuc belleğe yazılır, yanlış tahmin edilmiş dallanma komutu ise reoder buffer’daki diğer tüm pipeline boşaltılır(Reorder buffer ve reservation station’lar). Ayrıca precise excpetion’ın sağlanması için exception kontrolü yapılır eğer herhangi bir komutda exception oluşmuşsa yine pipeline boşaltılır. Bir komut commit edildiğinde sonuç ilgili hedef ile birlikte CDB’ye de yazılır. Böylece bu sonucu bekleyen reservation station’lar alabilir.
Loop:fld f0,0(x1)
fmul.d f4,f0,f2
fsd f4,0(x1)
addi x1,x1,8
bne x1,x2,Loop

--

--

--

Computer Architecture, C++, Linux

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Yusuf Yamak

Yusuf Yamak

Computer Architecture, C++, Linux

More from Medium

How PVS-Studio prevents rash code changes, example N3

Oracle 19c “library cache load lock”

SaharaCloud.io: Virtually prototype hardware on the cloud

Edge Computing for manufacturing with Onteon