F    D   EXE MEM WB
c=a+b  I1 
d=c+e  I2  I1
g=h-i  I3  I2   I1
           I2   o    I1
           I2 	o     o I1 | ΟΛΟΚΛΗΡΩΣΗ ΤΗΣ Ι1  
                I2     

CPI = Cycles Per Instruction
χωρίς διασωλήνωση CPI=5
με διασωλήνωση 5 σταδίων *ΙΔΑΝΙΚΑ* CPI=1
---------------------------------------------
ΠΡΟΒΛΗΜΑΤΑ:
1) Εξάρτήσεις
c=a+b
d=c+e   (read για το c μετά από write στο c)=> RAW
--> TRUE DEPENDECY

pipeline hazard=> pipeline bubble
WAW (write after write)
b=z+w
c=a+b (2)
c2=d*e (1) | Πρέπει το WB να περιμένει το WB της (2)
..=c2..    |(διαρκεία ζωής)
c=

WAR (Write after Read)
b=z+w
c=a+b (2)
a2=d+e (1)  Πρέπει το WB να περιμένει το WB της (2)
...=a2
a=
FALSE DEPENDENCIES


RR (register renaming)
RAT (register allocation table)
user register|physical register
c	     |c2
....

2) Structural (Resources)
π.χ. αν έχουμε Register file με 1 port Read=>2 port R
π.χ. αν έχουμε 1 ALU=> 4 ALU
π.χ. αν έχουμε 1 FPU=> 3 FPU
vectoring units=> 2 VU
load/store unit (RAM) => 2 LS

3) control hazards
π.χ. CALL function
π.χ. conditional (if-then-else)


Η τεχνική REGISTER RENAMING απομακρύνει WAR WAW.
H τεχνική Out Of order execution βοήθαει στο RAW.
Η τεχνική Forwarding Paths βοήθαει στο RAW.
Με έξτρα hardware αντιμετωπίζουμε δομικούς κινδύνους.
Η τεχνική Branch Prediction βοηθάει στο control hazards.

-EXERCISE-
=>5 stage pipeline, forwarding paths, out of order (OOO)
=>Να σημειωθούν οι κύκλοι EXE/WB για κάθε εντολή (start=0)
=>Κάθε στάδιο ως 8 εντολές να έχει 
               F     D   EXE  MEM WB
MUL R2,R2,R2   0     1    2    3  4(R2)
ADD R1,R1,R2   0     1    3    4  5(R1)
MUL R3,R3,R3   0     1    2    3  4(R3)
;το R1 διαθέσιμο στον κύκλο 4 (μετά το execute 3)
;το R3 διαθέσιμο στον κύκλο 3 (μετά το execute 2)
ADD R1,R1,R3   0     1    4    5  6(R1)           
MUL R4,R4,R4   0     1    2    3  4(R4)
;το R1 διαθέσιμο στον κύκλο 5 (μετά το execute 4)
;το R4 διαθέσιμο στον κύκλο 3 (μετά το execute 2)
ADD R1,R1,R4   0     1    5    6  7(R1)

CPI=cycles / total_instructions = 8 / 6 ->1.xx
IPC= instructions / per_clock = 6/8


=>5 stage pipeline, χωρίς forwarding paths, OOO
=>Να σημειωθούν οι κύκλοι EXE/WB για κάθε εντολή (start=0)
=>Κάθε στάδιο ως 2 εντολές να έχει
               F    D  EXE   MEM   WB
MUL R2,R2,R2   0    1   2     3     4(R2)
;περιμένει το R2 μετά το WB 4 (άρα διαθέσιμο στο 5)
ADD R1,R1,R2   0    1   5     6     7(R1)
MUL R3,R3,R3   1    2   3     4     5(R3)
ADD R1,R1,R3   1    2   8     9     10(R1)
MUL R4,R4,R4   2    3   4     5     6(R4)
ADD R1,R1,R4   2    3   11    12    13(R1)

CPI = 14 / 6 => 2.XX
IPC = 6 / 14



=>5 stage pipeline, χωρίς forwarding paths, in-order
=>Να σημειωθούν οι κύκλοι EXE/WB για κάθε εντολή (start=0)
=>Κάθε στάδιο ως 2 εντολές να έχει
	      F   D   EXE MEM WB
MUL R2,R2,R2  0   1   2    3   4(R2)
ADD R1,R1,R2  0   1   5    6   7(R1)
MUL R3,R3,R3  1   2   5    6   7(R3)
ADD R1,R1,R3  1   2   8    9   10(R1)
MUL R4,R4,R4  2   3   8    9   10(R4)
ADD R1,R1,R4  2   3   11   12  13(R1)

CPI = 14/6=>2.xx

CPI εξαρτάται ΚΑΙ από τον επεξεργαστή ΚΑΙ από το software

-> Vectorization 
for(i=0;i<43;i++)==>for(i=0;i<40;i++)
{
A[i]=B[i]+C[i];    // scalar (βαθμωτή) 
}

for(i=40;i<43;i++)
{A[i]=B[i]+C[i];   }
Loop peeling


το vectorization ΔΕΝ είναι τεχνική ILP αλλά τεχνική παραλληλοποίησης στάθμης δεδομένων.

ILP=>Instruction Level Parallelism (ιδεατό MAX)
Παραλληλοποίηση στάθμης Εντολών
=>Αφορα τον Τέλειο επεξεργαστή
->ΔΕΝ έχει structural hazards
->είναι OOO με άπειρο instruction window
->Υποστήριζει Register Renaming με άπειρο πλήθος καταχωρ.
->Έχει τέλειο Branch Prediction (100% success)
->Όλα τα στάδια σε 1 cycle ανά εντολή (F-D-EXE-MEM-WB)
(ρεαλιστικοί CPU σε αστοχία cache memory >1cycle)
->Έχει όλες τις τεχνικές αντιμετωπίσης εξαρτήσεων

θέλουμε το IPC να πλησιάζει το ILP
το ILP εξαρτάται ΜΟΝΟ από το software.

=> Ποιο είναι το ILP?
=> Ποιο το IPC για in order, 3 ALUs, 3 issue, 5-stage
3 Write Ports (στο WB)
(κοιτάμε τα ALUs στο EXE, κοιτάμε τα issue στο F)
(στο ΜΕΜ κοιτάμε τα Load/Store units)
              F    D    EXE  MEM   WB
ADD R1,R2,R3  0    1     2    3    4(R1)
ADD R2,R3,R4  0    1     2    3    4(R2)
ADD R3,R1,R2  0    1     3    4    5(R3)
ADD R7,R8,R9  1    2     3    4    5(R7)
ADD R1,R7,R7  1    2     4    5    6(R1)
ADD SR1,R4,R5 1    2     4    5    6(SR1)
IPC=instructions/cycle=6 / 6=1
ίδια αποτελέσματα αν ALUs=2, Write Ports=2
-----------------------------------
αν θεωρήσουμε ιδεατός 1 cycle για όλη την εντολή
                   ΕΚΤΕΛΕΣΗ
ADD R1,R2,R3          0
ADD R2,R3,R4          0
ADD R3,R1,R2              1
ADD R7,R8,R9          0
ADD R1,R7,R7              1
ADD SR1,R4,R5         0
=> 6 εντολές σε 2 κύκλους=>6/2=3 ILP

wide issue   >=4 
narrow issue <4

CALL &function

είναι απαραίτητο να αποθηκεύεται και η δ/ση στόχου του branch

-----------
c=a+d
e=c+5  ;μονοπάτι προώθησης EX/MEM
-------
c=a+d
b=a+30
e=c+x ; μονοπάτι προώθησης ΜΕΜ/WB
----------------------------------------------

Υπερβαθμωτοί Επεξεργαστές - Superscalar
(για 1 core)
-OOO
-RR
-Branch Prediction
-Multiple EXE units
-Wide Issue
-Dependencies are discovered from hardware
IPC>1 έως 8
Multicore=> * nr_cores

PMU -> Power management unit
----------
VLIW/EPIC βασίζονται στον compiler
-Multiple EXE units
-Dependencies are discovered from compiler
-Very very big CACHE memory
very long instruction word
I1: c=a+b | e=d+f | j=a+d
κυρίως σε dedicated hardware==> ενσωματωμένα συστήματα
IPC>1

TLP -> Thread Level Parallelism

backwards compatibility 



for(i=0;i<5;i++)
{ a[i]=i+b;}

--->loop unrolling
a[0]=0+b;
a[1]=1+b;
a[2]=2+b;
a[3]=3+b;
a[4]=4+b;

++αποφεύγουμε το control hazard
++εμφανίζεται παραλληλία (αυξάνει το ILP)
--μειώνεται το instruction cache miss (μείωση επιδόσεων λόγων αυξμένων προσβάσεων στην εξωτερική instruction memory)
--αυξάνεται το μέγεθος του κώδικα