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

Introduction (1/2)
Contents of the Lecture

Massively Parallel
Computer Architecture

Components & technologies in highperformance systems
high-performance microprocessors
shared memory systems
 distributed memory systems
 accelerators

Hiroshi Nakashima(ACCMS, Kyoto University)

Methodologies of high-performancecomputing for;explicit solver of diffusion equations(& matrix-matrix multiply, linear solvers, ...)
 Skills in high-performance programming withdeep understanding of parallel systems


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

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

Introduction (2/2)
Solving Diffusion Equation (1/4)

Course Management

Course materials (Slides)
pptx/pdf files has been (or will be) distributedby graduate school office.
 Paper-version handout is only for the firstportion.

t 2 u  2u
 2  2  2xy 2u u( x  x , y, t )  2u( x , y, t )  u( x  x , y, t )
x 2
x 2
u u( x , y, t  t )  u( x , y, t )tt

Achievement evaluation
By exercise report.
Theme will be given on the last day.
 Theme will be on high-performance
programming (rather than “impression oflecture”).


3u( x , y,tt )  u( x , y, t ) t( u( xh, y, t )  u( xh, y, t )  u( x , yh,t )  u( x , yh,t ) h2
44u( x , y, t ))Massively Parallel Comp. Arch. (1) © 2010-2017 H. Nakashima

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

Solving Diffusion Equation (1/4)

Solving Diffusion Equation (1/4)

u( x , y,tt )  u( x , y, t ) t( u( xh, y, t )  u( xh, y, t )  u( x , yh,t )  u( x , yh,t ) h24u( x , y, t ))for(t=0;t<tmax;t++) {for(y=0;y<ny;y++) 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]4*u[y][x]);tmp=un; un=u; u=tmp;}

Discretized & Approximated Solver ofInitial/Boundary-Value Problem of
2-dimensional 2    u( x , y, t )2

c.f. Similar Code (1)Jacobi/red-black SOR solver of  2  gfor(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]=a*(u[y][x-1]+u[y][x+1]+u[y-1][x]+u[y+1][x]);5for(odd=0;odd<2;odd++)for(y=0;y<ny;y++)for(x=odd^(y&1);x<nx;x+=2)
u[y][x]=a*u[y][x]+b*(u[y][x-1]+u[y][x+1]+u[y-1][x]+u[y+1][x]);61Massively Parallel Comp. Arch. (1) © 2010-2017 H. Nakashima

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

Solving Diffusion Equation (1/4)
Parallelism & Locality (1/4)

c.f. Similar Code (2) E 

B
t

in: instructions/operations,innermost loops, outer loops,functions/procedures, programs, ...
 by:hardware, compilers, programmersfor(z=0;z<nz;z++) for(y=0;y<ny;y++)for(x=0;x<nx;x++){b[z][y][x].x+=e[z+1][y][x].y - e[z][y][x].ye[z][y+1][x].z + e[z][y][x].z;
b[z][y][x].y+=...;
b[z][y][x].z+=...;}

temporal: an event which happens now will
likely happen again in near future; and spatial: a series of temporally proximate eventsare likely proximate spatially;
and thus codes against the belief/expectation
should run very slowly.
8

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

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

iterative execution ofParallelism & Locality (2/4)
Locality: Systems believe/expect that ...


7●Principle of High-Performance = P + L Parallelism

Parallelism & Localityinstructions(3/4) in loop bodyhit to instruction cache

Parallelism in DE-solver loop

innermost loopfor(t=0;t<tmax;t++) {for(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]= outer loop
instruction/operationlevel parallelism
u[y][x]+(dt/(h*h))*(u[y][x+1]+u[y][x-1]+
u[y+1][x]+u[y-1][x]4*u[y][x]);tmp=un; un=u; u=tmp;}

Temporal Locality in DE-solver loopfor(t=0;t<tmax;t++) {for(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]= continually accessed local scalaru[y][x]+ variables  on-register(dt/(h*h))*(u[y][x+1]+u[y][x-1]+
continual access tou[y+1][x]+u[y-1][x]an array element
4*u[y][x]);on-register？
tmp=un; un=u; u=tmp;
continuous establishmentof branch condition} not easily done in C

u and un have loop-carry dependence
outermost loop cannot be parallelized
9●●basics of branch prediction
the element can be updated
by another assignment between
two references10safely done in this case

Massively Parallel Comp. Arch. (1) © 2010-2017 H. Nakashima●Parallelism & Locality (4/4)
Spatial Locality in DE-solver loop

thus x is innerfor(t=0;t<tmax;t++) {for(y=0;y<ny;y++) for(x=0;x<nx;x++)un[y][x]=continuous inside/outside
an iteration ( Fortran)
u[y][x]+(dt/(h*h))*(u[y][x+1]+u[y][x-1]+u[y+1][x]+u[y-1][x]4*u[y][x]);tmp=un; un=u; u=tmp;
instructions are ranked}
continuously11●2