XcalableMP Implementation andPerformance of NAS Parallel Benchmarks
Mitsuhisa Sato
Masahiro Nakao, Jinpil Lee and Taisuke Boku

University of Tsukuba, Japan

What’s XcalableMP?
XcalableMP (XMP for short) is:
A programming model and language for distributed memory , proposed by XMP WG
 http://www.xcalablemp.org


XcalableMP Specification Working Group (XMP WG)
XMP WG is a special interest group, which organized to make a draft on “petascale” parallellanguage.
 Started from December 2007, the meeting is held about once in every month.
 Mainly active in Japan, but open for everybody.


XMP WG Members (the list of initial members)
 Academia: M. Sato, T. Boku (compiler and system, U. Tsukuba), K. Nakajima (app. andprogramming, U. Tokyo), Nanri (system, Kyusyu U.), Okabe (HPF, Kyoto U.)
 Research Lab.: Watanabe and Yokokawa (RIKEN), Sakagami (app. and HPF, NIFS), Matsuo(app., JAXA), Uehara (app., JAMSTEC/ES) Industries: Iwashita and Hotta (HPF and XPFortran, Fujitsu), Murai and Seo (HPF, NEC),AAnzakiki andd Negishi
N i hi (Hitachi),(Hit hi) (many(HPF developers!)
dl!)Funding for development
e science project : “Seamlesse-science
Seamless and Highly-productive
Highly productive Parallel Programming Environment for High
Highperformance computing” project funded by MEXT,Japan
Project PI: Yutaka Ishiakwa, co-PI: Sato and Nakashima(Kyoto), PO: Prof. Oyanagi
2Project Period: 2008/Oct to 2012/Mar (3.5 years)

Agenda

XcalableMP : directive-based language eXtension
for Scalable and performance-aware
performance aware Parallel
ProgrammingConceptp and model directives
 Some examples

XMP implementation of Nas Parallel Benchmark
ES, IS,ESIS CG (1-D,(1 D 22-D)
D) Preliminary performance reports

XMP project3http://www.xcalablemp.org
XcalableMP : directive-based language eXtension
performance-aware Parallel Programminggg
for Scalable and p

Directive-based language extensions for familiar languages F90/C (C++)
To reduce code-rewriting and educational costs.

“Scalable” for Distributed Memory
Programming
SPMD as a basic execution model A thread starts execution in each node
independently (as in MPI) .
 Duplicated execution if no directive specified.
 MIMD for Task parallelism

node0

node1

node2

Duplicated execution



directives
Comm, sync and work
work-sharing
sharing“performance-aware”
ff explicit
forli itcommunication and synchronization.

Work-sharing and communication occurs when directives are encountered All actions are taken by directives for being “easy-to-understand” inperformance tuning (different from HPF)XMP project4

Overview of XcalableMPXMP supportst typicalt i l parallelizationll li ti based
b d on theth datad t parallel
ll l paradigm
diand work sharing under "global view“

An originalgsequentialq
code can be parallelized
pwith directives, like OpenMP.
p

XMP also includes CAF-like PGAS (Partitioned Global Address Space)feature as "local view" programming.

User applications
Gl b l view
Globali
Directives
Dii

MPIInterface•Support common pattern(communication and worksharing) for data parallel
programming•Reduction and scatter/gather•Communication of sleeve area
•Like OpenMPD,
OpenMPD HPF/JA,HPF/JA XFP

Local view
Directives(CAF/PGAS)

XMPruntimelibraries

XMP parallel execution modelT
Two-sided
id d comm. (MPI)XMP projectArray section
in C/C++One-sided commcomm.
(remote memory access)Parallel platform (hardware+OS)

5

Code Examplep
int array[YMAX][XMAX];#pragma xmp nodes p(4)#pragma xmp template t(YMAX)#pragmap g
xmp
p distribute t(block)() on p#pragma xmp align array[i][*] with t(i)(){main(){
int i, j, res;
res = 0;

data distribution

add to the serial code : incremental parallelization#pragma xmp loop on t(i) reduction(+:res)for(i = 0; i < 10; i++)for(j = 0; j < 10; j++){work sharing and data synchronizationarray[i][j] = func(i, j);
res += array[i][j];}}XMP project6

The same code written in MPI
int array[YMAX][XMAX];
main(int argc, char**argv){
int i,j,res,temp
i,j,res,temp_res,res, dx,llimit,ulimit,size,rank;
MPI_Init(argc, argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI C
MPI_Comm_size(MPI_COMM_WORLD,i (MPI COMM WORLD &size);& i )dx = YMAX/size;
llimit = rank * dx;
if(rank !=! (size - 1)) ulimit = llimit + dx;
else ulimit = YMAX;
temp_res = 0;f (i = llimit;
for(illi it i < ulimit;li it i++)i )for(j = 0; j < 10; j++){array[i][j] = func(i, j);temp res += array[i][j];temp_res}
MPI_Allreduce(&temp_res, &res, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);MPI Fi li ()MPI_Finalize();}
XMP project7

Nodes, templates and data/loop
distributions

Idea inherited from HPF
Node is an abstraction of pprocessor and memoryy in distributed memoryy
environment, declared by node directive.
#pragma xmp nodes p(32)#pragma xmp nodes p(*)

Template is used as a dummy array distributed on nodes#pragma xmp template t(100)#pragma distribute t(block) onto pA global data isaligned to the template

variableV2variable
i bl
V1
Align
directive

Loop iteration must also bealigned to the templateby on-clause.

loop
L2

Align
directive

variable
V3

Loop
di ti
directive#pragma xmp align array[i][*] with t(i)
loop
L1

Loop
directive
templateT2

Distribute directive
Distribute directive#pragma xmp loop on t(i)XMP project

Loop
directive

Align
directive

template
T1

loop
L3

nodes
P8

Array data distribution
Th following
Thef ll i directives
di ti
specify
if a datad t distribution
di t ib ti among nodesd#pragma xmp nodes p(*)#pragma xmp template T(0:15)#pragma xmp distribute T(block) on p
#pragma xmp align array[i] with T(i)

     array[]
node0
ode0
node1
node2node3
Reference to assigned toother nodes may causeserror!!
XMP project

Assign loop iteration
as to compute own data
Communicate data between other nodes
9Parallel Execution of “for” loop
E
Executet ffor lloop tto computet on array#pragma xmp loop on t(i)for(i=2; i <=10; i++)










#pragma xmp nodes p(*)#pragma xmp template T(0:15)#pragma xmp distributed T(block) onto p#pragma xmp align array[i] with T(i)D t region
Dataitto b
be computedt dby for looparray[]
Execute “for” loop in parallel with affinity to array distribution by on-clause：#pragma xmp loop on t(i)

node0
node1
odenode2
node3

XMP project

distributed array10

Data synchronization of array(shadow)Exchange data only on “shadow” (sleeve) region
If neighbor data is required to communicate, then only sleevearea can be considered
considered.
example：b[i] = array[i-1] + array[i+1]#pragma xmp align array[i] with t(i)
















array[]##pragmaxmp shadow
h darray[1:1]
[1 1]
node0
node1
node2
node3
Programmer specifies sleeve region explicitly

Directive：#pragma xmp reflect array
XMP project11

Data synchronization of array (full shadow)F ll shadowFullh dspecifies
ifi wholeh l data
d t replicatedli t d ini allll nodesd#pragma xmp shadow array[*]reflect operation
pto distribute data to everyy nodes#pragma reflect array
Execute communication to get data assigned to other nodes
Most easy way to synchronize→ But,
But communication is expensive!
array[]
node0
node1
node2
node3

XMP projectNow, we can access correct data bylocal access !!

12

gmove directiveThe "gmove" construct copies data of distributed arrays inglobal-view.
When no option is specified,specified the copy operation is performed collectively
by all nodes in the executing node set.
If an "in" or "out" clause is specified, the copy operation should be doneby one-side communication ("get" and "put") for remote memory
access.

!$xmp
p nodes pp(*)!$xmp template t(N)!$xmp distribute t(block) to p
real A(N,N),B(N,N),C(N,N)!$xmp align A(i,*),A(i *) B(i,*),C(*,i)
B(i *) C(* i) with t(i)Anode
1A(1) = B(20)// it may cause error!$xmp gmove
A(1:N-2,:) = B(2:N-1,:) // shift operation!$xmp gmove
C(:,:) = A(:,:)// all-to-all!$xmp gmove out
X(1:10) = B(1:10,1) // done by put operation
XMP projectnode
2Bnode
3node
1node
4node
2node
3node
4

C
node1
node2
node3
node4

13

XcalableMP Global view directives
Execution only master node

Broadcast from master node#pragma xmp bcast (var)Barrier/Reduction#pragma xmp block on master#pragma xmp reduction (op: var)#pragma xmp barrier

Task parallelism#pragma xmp task on node-set

XMP project14

XcalableMP Local view directives
XcalableMP also includes CAF-like PGAS (Partitioned Global Address Space)feature as "local view" programming.

The basic execution model of XcalableMP is SPMD

We adopt Co-Array as our PGAS feature.

In C language, we propose array section construct.
Each node executes the program independently on local data if no directive

Can be useful to optimize the communication

Support alias Global view to Local view
Array section in C

Co-array notation in C

int A[10]:int B[5];int A[10], B[10];#pragma xmp coarray [*]: A, B…
A[:] = B[:]:[10]; // broadcast[] = B[0:4];[];
A[5:9]XMP project15

Experience with NPB in XcalableMPThe following three benchmarks are selected for the XMPbenchmark
EPISwith a histogram (buckets) without a histogram (buckets)CG
one-dimensional parallelization
 two-dimensional parallelization


Check
Programmability/Expressivenessog aab y/ p ess e ess ((Howo too writeepprograms)
og a s)Performance (How fast the written programs run)NPB-EP#pragma xmp nodes p(*)#pragma xmp template t(1:NN)#pragma xmp distribute t(brock) onto p…
Parallelized by#pragma xmp loop on t(k)“for statement”
for(k=1; k<=NN; k++){/* pseudorandom number generation*/}NPB-IS without a histogram
3 51
1 5 62074 3 2 49Initialize array
Count the number of keys
having the same value
Accumulate the counted
number at each node and sum
the accumulated number
using the reduction operation

NPB-IS without a histogram
key_array[]k[] isi a distributed
di t ib t d array.
Prv_buff1 is local#pragma xmp loop on t(i)for( i=0; i<NUM_KEYS; i++ ){key_buff2[i] = key_array[i];prv_buff1[key_buff2[i]]++;}Count the number
off keyskhavingh i
the same value

for( i=0; i<MAX_KEY-1;i<MAX KEY 1; i++ )prv_buff1[i+1] += prv_buff1[i];accumulate#pragma xmp reduction(+:prv_buff1)

reduction

NPB-IS with a histogram
3 51
1 5 6207
4 3 2 4
9
Initialize array

Create a histogram

Exchangec a ge tthee keyseys(local view)
If the value of the key is small,the key is moved to left node.

NPB-IS with a histogramkey_array[] is distributed array.
#pragma xmp coarray key_buff2…
##pragma
xmp lloop on t(i)for(i=0; i<NUM_KEYS; i++)bucket size[key array[i] >> shift]++;bucket_size[key_array[i]…
for(i=0;i<NUM_PROCS;i++)key_buff2[a[i]:b[i]]:[i] = key_buff1[c[i]:d[i]];declare coarray
create a histogramcommunicationwith coarray

Copy theCth range fromfc[i][i] tot d[i] off key_buf2
kb f2 tot
the range a[i] to b[i] of key_buff2 in proc [i]((equivalenti l t tot MPI_allgather_v)
MPI ll th)Implementation of NPB-CG
two-dimensional
sparse matrixa[ ]How do arrays
y are
distributed to each node ?
Conjugate Gradient

two-dimensional
parallelization

template(1:N, 1:N)

one-dimensional
parallelization

template(1:N)

NPB-CG One-Dimensional Parallelizationp[] q[],p[],q[] and w[] are distributed arrays
arrays.
#pragma xmp template t(0:N-1)#pragma xmp distribute t(block) on proc##pragma
xmp alignli p[i],q[i],w[i][i] [i] [i] withith t(i)#pragma xmp shadow p[*]…
for( ….){){#pragma xmp reflect p#pragma xmp loop on t(j)for (j = 1; j <= lastrow-firstrow+1;
lastrow firstrow+1; j++) {sum = 0.0;
for (k = rowstr[j]; k < rowstr[j+1]; k++) {sum = sum + a[k]*p[colidx[k]];a[k] p[colidx[k]];}w[j] = sum;}#pragma xmp loop on t(j)for (j = 1; j <= lastrow-firstrow+1; j++)q[j] = w[j];[j];… update p with q and w ….
}

declaredl
full shadowSynchronization
byy reflectP[] is declared with full shadow
p[]

a[]

Full shadow
[]
w[]

p[]

×

reflect
XMP project24

2D-Parallelization of NPB-CG(data distribution)
 Declaration of replicatedpArraysycolw is replicated at the first dimension of t, anddistributed for the second dimension in block
distribution.

 Matrix data a[], rowstr[], colidx[]

1. Declared as local arrays
2. Arranged as to access each element locally.

p(4,*)

p(*,11)#pragma xmp align [i] with t(i,*):: x,z,p,q,r#pragma xmp align [i] with t(*,i):: w

p(3,*)p(1,1)

p(2,1)

p(3,1)

p(4,1)

p(**,2)x[na], z[na], p[na],q[na],q[], r[na],[ ], w[na];[ ];p(2,*)

p(1 2)
p(1,2)p(2 2)p(2,2)p(3 2)
p(3,2)

p(4 2)
p(4,2)

pp(*,3)

doublep(1,*)

p(1,3)

p(2,3)p(3,3)

p(4,3)

p(*,4)#pragma xmp nodes on n(NPCOLS,NPROWS) row#pragma xmp template t(0:na-1,0:na-1)#pragma xmp distribute t(BLOCKt(BLOCK,BLOCK)BLOCK) on nq[]p(1,4)

n(2,4)

p(3,4)

p(4,4)w[]

template t()

NPB-CG Two-Dimensional Parallelization#pragma xmp template t(0:N
t(0:N-1,0:N-1)
1 0:N 1)p[], q[], and w[] are#pragma xmp distribute t(block, block) on p
#pragma xmp align A[j][i] to t(i,j)
distributed arrays.
#pragma xmp align p[i] to t(i,t(i *))#pragma xmp align w[j] to t(*,j)….
p[i], q[i] with t(i, *)for(){w[i] with t(t(*, i)…
#pragma xmp loop on t(*, j)for (j = 1;; j <= lastrow-firstrow+1;; j++)j ){sum = 0.0;
for (k = rowstr[j]; k < rowstr[j+1]; k++) {sum = sum + a[k]*p[colidx[k]];}w[j] = sum;
Reduction operation}#pragma xmp reduction(+:w) on p(*, :)on replicatedli t d array#pragma xmp gmove
q[:] = w[:];
copy
py arrays
y with….
different distributions….. Update p with q ….
}

w[j][j] with t(*,j)( ,j)t（i,j)
a[][]ip[i] with t(i,*)×j

XMP project

reduction
reduction(+:w) on p(*, :)gmove q[:] = w[:];transpose27Performance Evaluation
T2K Tsukuba SystemyPC Cluster

AMD Opteron Quad 2.3GHz

Intel Core2 Quad 3GHz

Infiniband DDR 4rails (8GB/s)

Gigabit EthernetPerformance Results : NPB-EP
T2K Tsukuba System

PC Cluster
500
400

XMP
MPI

200

Mop/s

Mop/ss

300

100

300
200
100
001248

Number of Node16124816

Number of Node

The difference in performance at 1 node is because theperformance of the C compiler is poor than that of Fortran.

Evaluation Results : NPB-IS
T2K Tsukuba System
800

180
XMP(without histgram)
XMP(with histgram)

120

MPI

Mop/ss

Mop/ss600

PC Cluster

400
2000600
1248

Number of Node161248

Number of NodeThe results indicate that the performance ofXMP with a histogram is comparable to that of MPI.

16

Performance Results : NPB-CG
T2K Tsukuba System
2500

4000

XMP(1d)XMP(2d)
MPI

2000

2000

Mop//s3000

Mop//sPC Cluster

1500
1000

1000

500

00
124816

Number of Node

1248N
Numberb off NodeN d

16

The results for CG indicate that the performance of2D. parallelization in XMP is comparable to that of MPI.

Short SummaryPreliminary performance report NPB results

We found XMP can be a ggood solution to describe these benchmarks.
Performance looks reasonable, but much performance tuning is requiredMore experience is needed in real apps.

XcalableMP project: status and schedule

http://www.xcalablemp.org

A draft of XcalableMP specification 0.7
 http://www.xcalablemp.org/xmp-spec-0.7.pdf
3Q/10 beta release, C language version compiler (at SC10)
Fortran version compiler after SC10

Issues under discussionMulticores (SMP) Cluster and Hybrid programming with OpenMP
Parallel IO
Extension to GPGPUGPGPU, Manycore
Manycore, Fault tolerant?
tolerant?, Others …

XMP project32

Thank you for your attention!!!

Q & A?
http://www.xcalablemp.org/

Acknowledgements:
W wouldWe
ld likelik tot thankth k XMP-WG
XMP WG membersbffor
Valuable discussions and comments
XMP project33