Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Contents

Massively Parallel Computer ArchitectureHigh-Performance Microprocessor
Architecture and ProgrammingThree Major Weapons of HighPerformance Microprocessors
Instruction Pipeline, ILP, and Out-of-Order
Execution

Hiroshi Nakashima(ACCMS, Kyoto University)Branch Prediction and Speculationbasic mechanism of instruction execution
hazards caused by dependency and means tocope with thempredicting branch address and directionmeans to cope with misprediction

Cache and TLBbasics of configurationcache/TLB-awareness and improvement

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Overview (1/4)
Overview (2/4)

Factor to Determine PerformanceFirst-level Approximation =#basic-ops (≈machine insts)×1 ⁄ frequency

for(x=0;x<nx;x++)un[y][x]=u[y][x]+(dt/(h*h))*(u[y][x+1]+u[y][x-1]+
u[y+1][x]+u[y-1][x]FP register
4*u[y][x]);GP (int)  f=u[][]...5, un[][]=f ...1
register f=f+f ...5,f=f*f ...3, f=f/f ...1
 g++ ...1,
g<g ...1, if()goto ...1
 18 ⁄ frequency?
 supercomputer in KU (18core Xeon)
why so small?
≈ 7 ⁄ frequency

Why “#ops ⁄ freq” Overestimates= Parallel Execution of Multiple Instsin KU’s supercomputer
f=mem × 2
mem=f × 1
 f=f+f × 1
 {f=f*f, f=f/f} × 2 (except for f=f/f × 2)
 integer insts ∋ {g++, g<g, if()goto} × 4


can be executed in parallel

3

4

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Overview (3/4)

Overview (4/4)

Why max(...) Underestimates= Latency of Depending Instructionin reality, we havesome other restrictions
max((f=mem)×5 ⁄ 2, (mem=f)×1 ⁄ 1,
(f=f+f)×5 ⁄ 1, ((f=f*f)×3＋(f=f/f)×1) ⁄ 2,((g++)×1＋(g<g)×1＋(if())×1) ⁄ 4)
= 5? (< 7)Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima



2



1st / 2nd / 3rd-level cache missf=mem ... 5 (+7+23+60?)
f=f+f ... 3, f=f*f ... 5, f=f/f ... 14(!!)
and we have to wait
 {g++, g<g} ... 1
5-cycle for next divide if()goto ... 1 (+15?+7+...)
branch misprediction /1st / ... cache miss

g=mem ... 4 (+...)
 g=g+g ... 1, g=g*g ... 3, g=g/g ... 20~26
When un, dt, h are global, a compiler

dthh=dt/(h*h);might unsure that dt and h arefor(t=0;t<tmax;t++){invariant due to update of un[][].
for(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]=u[y][x]+dthh*(u[y][x+1]+u[y][x-1]+ lesson-1: Do a simple
optimization by yourself.
u[y+1][x]+u[y-1][x]- lesson-2: Don’t use
global variables in a loop
4*u[y][x]);if possible. (e.g., move
tmp=un; un=u; u=tmp;
them into local variables)}

in KU’s supercomputer (unit=cycle)

avoid division as much as possible!!
 c.f. other representative ops

Avoiding Division

Loop-invariant code motion is afundamental optimization but not always(able to be) done by compilers.

Performance of Modified Code in KU’s
Supercomputer ≈ 5~6 ⁄ frequency
Reasons why >5 are shown later.
Many pitfalls to make >> 6
  Key issues are to avoid them



5

6

1

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima●

Basics of Instruction Pipeline (1/6)


Basics of Instruction Pipeline (2/6)

Instruction PipelinePart of DE-solver loop (assume latency=1)

Split instruction execution flow into multiple
stages.
 All stages work in parallel.




IF

In Textbooks ...

ID
EX
MA
WB

IF

ID

EX

MA

WB

I-Fetch

I-Decode

ExecuteMem Access

Write Backin parallel.

In Reality ...
≈20 stages (or more) and more complicated (asdiscussed later)

gx=gx+8IFgx<gnx8

Basics of Instruction Pipeline (4/6)
Latency ≥ 2  not always avoidable  Stall

RAW hazard in astraightforward
implementation●



through stages

2

IF

ID

EX

B=
fuzz

M=A+B

MA

WB
EX

MA

fupz=
MM=A-B

WB
fupz=
M

10

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima●

Basics of Instruction Pipeline (6/6)

anti-dependent:usedefine
dependencyRemedy=Static Scheduling (2/2)
2

2 fuzm=*(guy+gx-8)

4 fuzp=fuzp+fuzm

2

3 fupz=*(guyp+gx)

6 fuzp=fuzp+fupz

2

5 fumz=*(guyp+gx)

8 fuzp=fuzp+fumz

2

7 fuzz=*(guy+gx)

7 fuzp=fuzp+fumz

2

8 fuzz=*(guy+gx)

2
2
2

2

9 ftmp=fuzz*ffour

2

10 fuzp=fuzp+ftmp

9 ftmp=fuzz*ffour

2

11 fuzp=fuzp+ftmp

2

●

WB

1 fuzp=*(guy+gx+8)2

13 fuzp=fuzp*fdthh

12 fuzp=fuzp+fuzz

15 gx<gnx8

15 fuzp=fuzp+fuzz

13 *(guny+gx)=fuzp

16 if(<)goto

16 *(guny+gtmp)=fuzp*(guny+gx)=fuzp

2

10 gtmp=gx

2

14 gx=gx+8

2

WB
MA

2 fuzm=*(guy+gx-8)

6 fumz=*(guyp+gx)

2

MA
EX

fuzz= fuzz=
M=A*BM=A*B
M
M

2
2

11 fuzp=fuzp*fdthh

EX

ID

A=
fuzz

●

5 fuzp=fuzp+fupz

2

WB

9

4 fupz=*(guyp+gx)

2MA

detect RAW hazard
and stallflow dependent2

IF

fupz=fupz-fuzz

EX

Remedy=Static Scheduling (1/2)

3 fuzp=fuzp+fuzm

EXEX

Basics of Instruction Pipeline (5/6)

1 fuzp=*(guy+gx+8)ID

A=... D=A+B M=*D fuzz=B=...
M

fuzz=fuzz*ffour

Massively Parallel Comp. Arch. (2) © 2010-2017 H. NakashimalatencyIF

fuzz=*(guy+gx)

WB
gx=M

ID
A=gx

●



Even when latency of f=mem, f=f+f, f=f*f is 2 ...
cannot be bypassed

ID
EX
MA
WB
A=gx D=A-B M=D c=M<0
ID
A=gx

fuzp=
fuzp+fupz
I=*PC++;
A=fuzp;
B=fupz;
D=A+B;
M=D
fuzp=M;

true/flow dependence= output of predecessor is used by successor
 RAW (read-after-write) hazard
avoid hazard by= generate/use-timing is reversed. bypassing data
ID
EX
MA
A=gx D=A+B M=D#+u[y+1][x]fupz=*(guyp+gx)
I=*PC++;
A=guyp;
B=gx;
D=A+B;
M=*D
fupz=M;

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

●



IF

#u[y+1][x]8

Hazard due to Instruction Dependence
and Remedy for itbypassing / forwarding#u[y][x+1]+#u[y][x-1]fuzp=
fuzp+fuzm
I=*PC++;
A=fuzp;
B=fuzm;
D=A+B;
M=D
fuzp=M;●

Basics of Instruction Pipeline (3/6)
fuzm=*(guy+gx-8)
I=*PC++;
A=guy;
B=ux;C=8
D=A+B-C;
M=*D;
fuzm=M;

7

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima●#u[y][x-1]fuzp=*(guy+gx+8)
I=*PC++;
A=guy;
B=gx;C=8
D=A+B+C;
M=*D;
fuzp=M;

fuzp=*(guy+gx+8) IF ID EX MA WB
fuzm=*(guy+gx-8)
IF ID EX MA WB
fuzp=fuzp*fuzm
IF ID EX MA WB
fupz=*(guyp+gx)
IF ID EX MA WB
fuzp=fuzp+fumz
IF ID EX MA WB

 (up to) 5 (=#stages) instructions are executed#u[y][x+1]

1

2

1

2

16+8=24/iteration

11
●

2

12 gx=gx+8

1

14 gx<gnx8

1
1

removing antidependence
by register
renaming

17 if(<)goto

17+1=18/iteration

122

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (1/13)
 ILP: Instruction Level Parallelism

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (2/13)


KU’s Supercomputer

Execution order of mutually independent
instructions can be modified arbitrarily.
 They can be executed in parallel Execute multiple instructions in parallelwith multiple function units (e.g. ALUs)
scalar means “not vector (processor)” Variants

Issue Rate = 7 (#operations which can start at
every cycle)
 #Function Units








super scalar: execute ordinary instructions

Instructions per Cycle

static: in-order execution of compiled code (1990’s)
 dynamic: change order at run time (out-of-order, now)

very longinst. word
single inst.
multiple data{g,f}=mem × 2, mem={g,f}× 1{f=f*f[+f],f=f+f} × 1, {f=f*f[+f],f=f/f} × 1,
 {g++,g<g} × 2, {g++,g<g,if()goto} × 2(remark: #FP-ops + #int-ops ≤ 4)

maximum execution throughput (IPC)＝7
(16inst ⁄ 7) ⁄ iteration = 2.3 cycle ⁄ iteration ?

VLIW: one instruction performs multiple
operations (e.g. Itanium) SIMD: one instruction operates on multiple data
13
(SSEx: streaming SIMD extension, AVX)

14

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (3/13)

ILP (3/13)

Static Scheduling





2

1 fuzm=*(guy+gx-8)

3 fuzp=fuzp+fuzm

2

2 fupz=*(guyp+gtmp)

4 fuzp=fuzp+fupz

2

2 fumz=*(guym+gtmp)

5 fuzp=fuzp+fumz

2

3 fuzz=*(guy+gtmp)

22loop unrolling

for(x=0;x<nx;x++) un[y][x]=u[y][x]+...;
4-way unrollingfor(x=0;x<(nx/4)*4;x+=4){
un[y][x+0]=u[y][x+0]+...;
un[y][x+1]=u[y][x+1]+...;
un[y][x+2]=u[y][x+2]+...;
un[y][x+3]=u[y][x+3]+...;}
for(;x<nx;x++) un[y][x]=u[y][x]+...;

4 ftmp=fuzz*ffour

2

6 fuzp=fuzp+ftmp

1

1 gtmp=gx

2

7 fuzp=fuzp*fdthh

22 gx=gx+8

8 fuzp=fuzp+fuzz

1

3 gx<gnx8

2

2

1
1

9 *(guny+gtmp)=fuzp*(guny+gx)=fuzp

9 if(<)goto

9+6=15/iteration  IPC=17/15=1.13

15

16

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (5/13)

ILP (6/13)

Dependence Graph of 4-way Unrolled Loop

x=4i+0x=4i+1x=4i+2

1 [x-1]2 [x+1]

2 [x-1]3 [x+1]

3 [x-1]4 [x+1]

4 [x-1]3

5 [y+1]4

5 [y+1]5

6 [y+1]

6

6 [y+1]

+

+

+

7

+

7 [y-1]8+

7 [y-1]9+8 [y-1]10+

8 [y-1]

11

+

9 [x]

12

+

9 [x]

13

+

10 [x]

14+

10 [x]

11

*

12

*

13

*

14

15

+

1 gtmp

16

+

17

+

17

*

2

18

*

19

*

19

+

21 [x]=

3

gx
<

24 if

20

21

+

22 [x]=+

23 [x]=



x=4i+3

1 [x+1]+

Expand k iterations to have one iteration
Improve parallelism in loop body (& reduce loopcontrol overhead)

1 fuzp=*(guy+gx+8)

2

2



Latency of f=mem, f=f{+,*}f = 2

Limitation of Static Scheduling (incl.
Loop Unrolling) = Insufficient
Parallelism inside one or k Iterations
1 [x+1][x-1] gtmp
2 [y+1][y-1] gx
+
[x]
<
3
4

+

5

+

*

6

+

18

+

7

*

20

*

8

+

22

+

24 [x]=

if #registers is
sufficient

24/(4・iteration)  IPC=56/24=2.33 (68/24=2.83)

179 [x]=*

decliningparallelism

if

1 [x+1][x-1] gtmp
2 [x+1][x-1] gx+ [x+1][x-1]3+ [x+1][x-1]4
5 [y+1][y+1] +6 [y+1] + [y+1]+ [y-1][y-1]7+ [y-1][y-1]8+9 [x] [x]+[x]
10 [x]
*
11 +
*
12 +
*
13 +
*
14 +
15 +

<

16 +
17 +
18 +
19 +
20 +
21 [x]=
22 [x]=
23 [x]=
24 [x]=

Scheduling across Iterations= Software Pipelining

*
*
*
*
+
+

decliningparallelism

if

x=4i+0x=4i+1x=4i+2x=4i+318

3

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (7/13)
Software Pipelining
1 [x+1]2 [x+1]
3 [x-1][y+1]4 [x-1][y+1]
+
[x]
5
+
[x]
6
* [y-1]7* [y-1]
8
+
9
10 +
gtmp
11 +
gx
12 +
13 +
14 +
15 *
16 *
17 +
18 +
<
19 [x]=
20 [x]= if

combine withnext iteration
with shift

[x+1]
[x+1]
[x-1][y+1][x-1][y+1]
+
[x]
+
[x]
* [y-1]* [y-1]+++ gtmp
+
gx
+
+
*
*
+
+
[x]= <[x]= if10

10

10/(2・iteration) 
IPC=30/10=3.0(34/10=3.4)

2way-unroll and performscheduling a little bit loosely

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (8/13)

[x+1]
[x+1]
[x-1][y+1][x-1][y+1]
+
[x]
+
[x]
* [y-1]* [y-1]+++ gtmp [x+1]+gx [x+1]+ [x-1][y+1]+ [x-1][y+1]
*
+
[x]
*
+
[x]
+
* [y-1]+* [y-1][x]= <+[x]= if++ gtmp [x+1]+gx [x+1]+ [x-1][y+1]+ [x-1][y+1]
*
+
[x]
*
+
[x]
+
* [y-1]+* [y-1][x]= <+[x]= if++ gtmp
+
gx
+
+
*
*
+
+
<
[x]=
[x]= ifDynamic Scheduling= dynamic execution ordering
automatically done by microprocessor
Out-of-order issue of executable instructions withready-to-use operands irrespective of theirprogram order Dynamic register renaming to remove
unnecessary restriction of execution order Speculative execution of instructions given bybranch predictor
 Reordering for in-order completion to cope with
branch misprediction, exception, interrupt, etc.


19

20

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (8/13)

ILP (9/13)
multiple issue of (e.g.) 4 instrunctions

fuzp=*(guy+gx+8) m
fuzm=*(guy+gx-8) m
fuzp=fuzp+fuzm+
fupz=*(guyp+gx)
m
fuzp=fuzp+fupz+
fupm=*(guym+gx)
m
fuzp=fuzp+fumz+
fuzz=*(guy+gx)
mfuzz=fuzz*ffourxfuzp=fuzp-fuzz+
fuzp=fuzp*fdthhxfuzp=fuzp+ftmp+*(guny+gx)=fuzp
gx=gx+8igx<gnx8iif(<)gotoi
fuzp=*(guy+gx+8)m
fuzm=*(guy+gx-8)
m
fuzp=fuzp+fuzm+
fupz=*(guyp+gx)
m
fuzp=fuzp+fupz+
fupm=*(guym+gx)
m
fuzp=fuzp+fumz+
fupm=*(guym+gx)m●

out-of-order issue
add： wait for loaded dataload： not wait for add
register renaming:
dynamic mapping from logicalregisters (f=16/g=16) to physicalregisters of larger amountm

speculation:
execute predicted insts
before branch target
is determined
reordering:
complete when
all predecessors
complete(e.g. up to 4 insts)

actual latency (e.g. in KU) of
load/FP-ops > 2
buffers exhaust frequentlyhard to find executable insts
likely to be > 5/iteration

5/iteration 
IPC=116/5=3.2
21

22

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (11/13)

Exploiting SIMD (AVX) Mechanism

5/iteration>4/iteration
 #instructions to start/complete
increases monotonically reservation station (60@KU) for inst
to start and/or reorder buffer (192@KU)
for inst to complete will be exhausted
 effective fetch/issue rate becomes
3.2/cycle eventually

4/iteration

ILP (10/13)


How Out-of-Order Execution Progressesymm: 256-bit media registerchar × 32, short × 16, int × 8, long long × 4
 float × 8, double × 4
 perform a particular operation on multiple data 4-way unroll and perform 4 ops by one inst
for(x=0;x<nx;x+=4) {un[y][x] =u[y][x]+1+
dthh*(u[y][x+1]+u[y][x-1]+u[y+1][x]-1+u[y-1][x]+1-4*u[y][x]);un[y][x+1]=u[y][x+1]+
dthh*(u[y][x+2]+u[y][x]-1+u[y+1][x+1]+u[y-1][x+1]-4*u[y][x+1]);
un[y][x+2]=u[y][x+2]+
dthh*(u[y][x+3]+u[y][x+1]+u[y+1][x+2]+u[y-1][x+2]-4*u[y][x+2]);
un[y][x+3]=u[y][x+3]+
dthh*(u[y][x+4]+u[y][x+2]+u[y+1][x+3]+u[y-1][x+3]-4*u[y][x+3]);}

 but compilers often fail to SIMD-vectorize

23

Why Compilers Fail to SIMD-vectorize

for(x=0;x<nx;x+=4) {un[y][x] =u[y][x] +dthh*(...);...
un[y][x+3]=u[y][x+3]+dthh*(...);}
this transformation does
not preserve semantics
if dependent&un[y][x]==&u[y][x+3]mutually dependentactually they are
independent definitely
but compilers are often
ignorant of itfor(x=0;x<nx;x+=4) {double t0=u[y][x] +dthh*(...);...
this code means
double t3=u[y][x+3]+dthh*(...);
they are independent
un[y][x] =t0;...
SIMD-vectorizable if
un[y][x+3]=t3
this transformation is}correct

24●

4

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

ILP (12/13)


ILP (13/13)

How to Make Loop SIMD-Vectorizablefor(t=0;t<tmax;t++){double (*restrict uu)[NX]=u,(*restrict uun)[NX]=un;for(y=0;y<ny;y++) for(x=0;x<nx;x++)uun[y][x]=uu[y][x]+dthh*(uu[y][x+1]+uu[y][x-1]+
uu[y+1][x]+uu[y-1][x]-4*uu[y][x]);tmp=un; un=u; u=tmp;
may run incorrectly if}

Fine Tuning and Caution
uun[y][x]=uu[y][x]+dthh*(uu[y][x+1]+uu[y][x-1]+
uu[y+1][x]+uu[y-1][x]-4*uu[y][x]);This transformation does not preserve
program semantics
FP operations are not associative

uun[y][x]=uu[y][x]+dthh*((uu[y][x+1]+uu[y][x-1])+(uu[y+1][x]+uu[y-1][x])-4*uu[y][x]);assurance is incorrect*restrict p＝*p or *(p+exp) is not be updated by a pointer other than p
programmer assures &uun[y][x]!=&uu[y'][x']SIMD-vectorizable  1.8 cycle/iteration (> lower bound=1.25)

operation result of tuned code
may be slightly different fromoriginal one

reduce total latency of RHS
reduce #-of in-flight instructions andpossibility of buffer exhaustion
increase chance to find executable
instructions

25

26

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Branch Prediction (1/8)
Branch Prediction (2/8)

Control Dependency

Target of branch instruction (& its successors)depends on the branch.
 Control hazard makes pipeline stalled during fetch
and decode of branch target which takes place
after calculation of branch address and direction.


gx=gx+8igx<gnx8iif(<)gotoi
fuzp=*(guy+gx+8)

Predicting Branch AddressCorrespondence of (address of) branch instruction
and target address is usually invariant (if taken).
0x124C:if(<)goto xloop(=PC-94=0x11E0)

Branch Target Buffer (BTB)
A kind of cache to keep (inexact) correspondence ofbranch instruction address and target address.
 On the fetch of (branch) instruction, simultaneously
lookup BTB to get “maybe target address”.
 Branch latency = 1 if success.
 BTB@KU: 4K(??) entry (+ for indirect branches)branch address anddirection are determinedmfetch and decodeof branch target≈ 15 cycle

Return Address Stack (RAS)
Stack to predict return address:
push by call / pop by return RAS@KU: 16(??) entry

27

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Branch Prediction (3/8)
Branch Prediction (4/8)

Predicting Branch DirectionDirections of a conditional branch (are expectedto) have temporal locality
e.g. loop terminator: #taken=n−1 / #not-taken=1
 Simple prediction mechanism = 1-bit predictor

1bit vs 2bitfor(y=0;y<4;y++) for(x=0;x<4;j++)un[y][x]=u[y][x]+dthh*(...);



1-bit array indexed by a segment of branch inst address Record 0 (not-taken) / 1 (taken) for each branch inst
predict (not) taken if it was (not) taken last timesensitive to noise (e.g. miss twice for loop terminator)




28

2-bit saturate-counter predictor
2-bit array indexed by a segment of branch inst address not-taken  −1 / taken  +1 (min=0 / max=3)
 0 or 1  predict as not-taken ／ 2 or 3  predict as taken
one miss does not change its mind
(e.g. #miss of loop terminator = 1)29

prediction
x actual 1bit 2bit
1TN

c=2  T2TT

c=3  T3T

T

c=3  T4NT

c=3  T

accuracy = 50%

T : taken
N : not-taken

accuracy = 75%

30

5

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Branch Prediction (5/8)
Branch Prediction (6/8)

Very Dangerous Codefor(i=0;i<N;i++) {if(i&1){for odd i}else{for even i}}Using Global history (GH)

2-bit prediction is too local
accuracy for TNTNTN...
= 1/2 at most, 0 at worst

GH: remember all directions of last n branches(e.g. n = 8)
 Mix GH into index of 2-bit predictor for(i=0;i<N;i+=2) {for even i}for(i=1;i<N;i+=2) {for odd i}orfor(i=0;i<N;i+=2) {{for even i}{for odd i+1}}

spatial: only aware of a particular branch
temporal: remember almost nothing of actions except forlast four

recode as them
if possible

gselect (64K)
pred_table[gh][branch_inst_addr&0xFF]
gshare (64K)
pred_table[gh^(branch_inst_addr&0xFFFF)];in KU, gshare or its variant
is used (n =32?)

31

32

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Branch Prediction (7/8)
Branch Prediction (8/8)

Effect of GH (1/2)

for(t=0;t<tmax;t++) {for(y=0;y<4;y++) for(x=0;x<4;j++)un[y][x]=u[y][x]+dthh*(...);
tmp=un; un=u; u=tmp;}
for(t):T
T
for(y):
T
T
T
N
T
T
T
N
for(x):TTTN TTTN TTTN TTTN TTTN TTTN TTTN TTTN
y==0

for(p=h;p!=NULL;p=p->next){
if (p->data==x) break;}if (p==NULL) ...


actualT

Truth value of p==NULLlast branch is for p->data==x (true)  false
last branch is for p!=NULL (false)
 true predictable as GH=?????T  false / ?????N  true

y!=0

x GH
for(x) pred
1 TTTNNT TTT...
Tx GH
for(x) pred actual
1 TTTTNT TTT...
T
T

2 TTNNTT TTT...

TT

2 TTTNTT TTT...

T

T

3 TNNTTT TTT...

T

T

3 TTNTTT TTT...

T

T

4 NNTTTT NNN...

NN

4 TNTTTT NNN...

N

N



if(i&1){...}else{...} is also predictable but ...

33

34

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Predicated Instruction (1/2)


Effect of GH (2/2)

Predicated Instruction (1/2)

Conditional Branch & SIMD (1/2)

Conditional Branch & SIMD (1/2)

for(i=0;i<n;i++){if (a[i]<0) a[i]=-a[i]; /* a[i]=abs(a[i]);}definitely correct transformation

for(i=0;i<n;i++){if (a[i]<0) a[i]=-a[i];}for(i=0;i<n;i+=4){
if (a[i+0]<0) a[i+0]=-a[i+0];
if (a[i+1]<0) a[i+1]=-a[i+1];
if (a[i+2]<0) a[i+2]=-a[i+2];
if (a[i+3]<0) a[i+3]=-a[i+3];}

for(i=0;i<n;i+=4){
int c0=a[i+0]<0;
int c1=a[i+1]<0;
int c2=a[i+2]<0;
int c3=a[i+3]<0;

How SIMD-vectorize
these branches??

SIMD-vectorizable of course/* a[i]=abs(a[i]);double t0=-a[i+0];
double t1=-a[i+1];
double t2=-a[i+2];
double t3=-a[i+3];a[i+0]= c0 ? t0 : a[i+0];a[i+1]= c1 ? t1 : a[i+1];a[i+2]= c2 ? t2 : a[i+2];a[i+3]= c3 ? t3 : a[i+3];

 transform latency from branch to arithmetic
 no misprediction because
 not predicting
 efficient (usually)}
35

conditional move36

6

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Basics of Cache (1/7)


Basics of Cache (2/7)

Overview of Cache (≠ Cash)High-speed memory to fill the access speed gap
between CPU and main memory

L = 64B

CPU : cache : memory = 1 : 1~20 : 50~100Keep data to be likely accessed in near future

temporal： repeated access to data accessed recently

spatial:access to data proximate to recently accesseddataaccesses against expectation result in very
poor performance

S = 128

exploiting/expecting locality

Configuration Parameter：
L × S × W ＝capacity (e.g. 32KB)
cache

0000 2000 4000 6000 8000 A000 C000 E000

00
01
02
03

0000
0040
0080
00C0

7C
7D
7E
7F

1F00
1F40
1F80
1FC0

e.g. skipping accesses in a huge array37

line size (≈32~256B)
line: unit of bookkeeping & data transfer memory

W=4

#sets

#ways (≈1~16) = #lines in a set
conflict if #lines > W  (LRU) replacement

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Basics of Cache (3/7)


L > 8B (= sizeof(double))

Exploiting/expecting spatial locality

Basics of Cache (4/7)

miss rate = 8 ⁄ L

L ＝ 2l, S ＝ 2s  L × S ＝ 2l ＋saccess to u[x] accesses to u[x+1], u[x+2], ...

Efficient transfer from/to memory by contiguous
accesslatency = 50~100cycle, bandwidth = 5~10B/cycle
 for(y=0;y<ny;y++) for(x=0;x<nx;x++)betterun[y][x]=u[y][x]*dthh*(...);
for(x=0;x<nx;x++) for(y=0;y<ny;y++)worse
un[y][x]=u[y][x]*dthh*(...);
for(i=0;i<N;i++){ j=f(i);obj[j].x+=obj[j].vx; obj[j].y+=obj[j].vy;}
for(i=0;i<N;i++){ j=f(i);obj.x[j]+=obj.vx[j]; obj.y[j]+=obj.vy[j];}Data pair conflict with each other if their address
difference is 2(l ＋s)n.
Arrays of power-of-two size are dangerous.

#define N 1024
conflict with each other
L×S＜8192 & W＜4double u[N][N],un[N][N]; misses always...
for(x=1;x<N-1;x++)un[y][x]=u[y][x]+dthh*(u[y][x+1]+u[y][x-1]+
u[y+1][x]+u[y-1][x]+4*u[y][x]);

struct {double x[N],y[N],z[N],vx[N],vy[N],vz[N];} obj;...
for(i=0;i<N;i++){obj.x[i]+=obj.vx[i]; obj.y[i]+=obj.vy[i];obj.z[i]+=obj.vz[i];L×S＜8192 & W＜6} misses always

betterworse 39

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Basics of Cache (6/7)

3C of Cache Misses(Representative) Memory Hierarchy
64?×64?×8?
＝32KB(+1.5K? μop)

data is not in cache on its first accessinevitable

CPU coreIF#-of lines accessed after last access > capacity
poor temporal (and/or spatial) locality

ID
EX

Conflict miss

@KU’s supercomputer#-of competing lines accessed after last access > #ways
e.g. discontiguous accesses (esp. with 2n stride)

64B/c?

64B/c

MA
WB
32B/c
64×64×8
＝32KB

41

≈100

lat = 50~200

L2=12(+) L3=34(++)

Capacity missCompulsory miss40

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Basics of Cache (5/7)
38

lat = 5~30
lat = 1~4(+)
L1 I-cache(10~100KB)

64B/c (L2)
L1 D-cache 32B/c (L3)
(10~100KB)

36B/c
L2 cache(18core)(1MB)(& L3 cache)
WB

memory(1GB~)
128GB

WT
or
WB

Write Through: immediately write to lower level
Write Back:write to lower level at replacement

L2: 64×512×8＝256KB/core
L3: 64×2048?×20?×18
42＝45MB/18core

7Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Basics of Cache (7/7)


TLB (1/2)

Prefetch = Load a line to cache if the line is
expected to be accessed in near future

Virtual/Physical Address Translation

Hardware Prefetch= prefetch based on detection of particular access patternvirtual space
232 or 264/ process

e.g. in KU’s supercomputer contiguous access to L1Dprefetch next line last k addresses of a load = b + s  i (0 ≤ i < k)
prefetch line including b + s  k to L1D
 a 64B-line in L2 is loaded to L1
prefetch next line to L2 if absent
 watch 32(?) contiguous access streams
if L1 require a line in a stream, prefetch next line to L2/L3




page
(≈4KB)

prefetch a line to L1 by a dedicated instruction
compiler inserts prefetch instructions estimating accesspatterns and effectivenesscache to keep
recent translation

43

Massively Parallel Comp. Arch. (2) © 2010-2017 H. NakashimaCache of PA translated from VARelatively small ≈ 10~1000 entries@KU: L1-ITLB = 32  4way = 128 (+α)
L1-DTLB = 16  4way = 64 (+α+β)L2-TLB = 256  6way = 1536 (+α)

miss  page table lookup  large overheadmany accesses with long stride  miserableu[][]un[][]

L2/L3 cache is accessed by PAcontiguous in VA ≠ contiguous in L2/L3

45

46

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Performance with Cache & TLB (2/7)
exec time / iter [ns]
5

L1T
L1C

L2C

Performance with Cache & TLB (3/7)

nx or ny = 216  k − 2
 u[x][y]&un[x][y]are in a set of L3C

L2T
L3C

#L3C misses=4 / 8 iteration

4

3
overhead of
inner loop2

ny=200

Optimization for Large nx : x-dim Tilingfor(xx=0;xx<nx;xx+=TX) {int nxx=(xx+TX<nx)?xx+TX:nx
for(y=0;y<ny;y++) for(x=xx;x<nxx;x++) {uun[y][x]=uu[y][x]+dthh*(uu[y][x+1]+uu[y][x-1]+
uu[y+1][x]+uu[y-1][x]-4*uu[y][x]);
}


1

0
100
3.2K

nx is small thanks to u[y+1][x],u[y][x] and u[y-1][x]hit cachenx+2

for(x=0;x<1000;x++) for(y=0;y<1000;y++)un[y][x]=u[y][x]+dthh*(...);
2000 pages are accessed in inner loop  2 misses ⁄ iteration



Memory Access Patternfor(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]=u[y][x]+dthh*(u[y][x+1]+u[y][x-1]+
u[y+1][x]+u[y-1][x]-4*u[y][x]);key = virtual page number (high-order bits of VA)
 data = physical page number (high-order bits of PA)




44

Performance with Cache & TLB (1/7)

Translation Look-aside Buffer

TLB

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

TLB (2/2)


physical space
230 ~ 240+

Software Prefetchtranslation
tablelarge nx: #misses / 8-iteration = 4  2
TX

L1T
L2C
L1C
101
32K

102
320K

L2T
L3C
103
104
3.2M
32M
nx or ny
nx×ny

nx=200#L3C misses=2 / 8 iteration
105
320M

106
3.2G

107
32G [B]
47

48

8

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima●

Performance with Cache & TLB (4/7)
Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Performance with Cache & TLB (5/7)

Super Optimization = Temporal Tilingbaseline

x-tiling(TX=1000)

exec time / iter [ns]~ 1.20

2.0

perimeter+0 (or +1)
t=+1 (&+0)

1.5~ 2.55
1.0

perimeter+1 (or +2)
t=+2 (&+1)

temporal tiling(TX=500,TY=120,TT=25)

0.5

perimeter+2 (or +3)
t=+3 (&+2)

tile ≤ cachealmost hit

0.0
0
0

perimeter+3 (or +4)
t=+4 (&+3)

5
0.4

10
1.6

15
3.6
nx = ny
nx  ny

20
6.4

25
10.0

30 [×103]
14.4 [GB]49

50

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima●

Performance with Cache & TLB (6/7)
Performance with Cache & TLB (7/7)

Contiguous vs Discontiguous Accesses
for(y=0;y<ny;y++) for(x=0;x<nx;x++)uun[y][x]=uu[y][x]+dthh*(uu[y][x+1]+uu[y][x-1]+
uu[y+1][x]+uu[y-1][x]-4*uu[y][x])exec time / iter [ns]1510for(x) for(y)#cache-misses = 2~4 ⁄ 8-iteration#TLB-misses = 2~4 ⁄ 256K-iteration

 5.4
5

for(x=0;x<nx;x++) for(y=0;y<ny;y++)uun[y][x]=uu[y][x]+dthh*(uu[y][x+1]+uu[y][x-1]+
uu[y+1][x]+uu[y-1][x]-4*uu[y][x])#cache-misses = 2.25 ⁄ 1-iteration#TLB-misses = 2 ⁄ 1-iteration

for(y) for(x)

0
101
1.6K
51

102
160K

103
16M
nx = ny
nx  ny

104
1.6G

105
160G [B]52

Massively Parallel Comp. Arch. (2) © 2010-2017 H. Nakashima

Conclusion: Key Issues of HPC
Pipeline / ILP / out-of-order / SIMD

Branch Prediction / Speculation

Relying on compiler/hardware is almost safe.
Remember restrict in C programming
Loops with many iterations are usually OK.
Some if-else in loops are really dangerous.

Cache / TLB
Dominant performance factor.
Don’t let down your stupid hardware.
 Small care can improve performance significantly.






As much contiguous as possible.
Avoid access conflict if possible.
53

9