- Limit the use of Message Passing to reduce message passing latency
- Locality + high BLAS algorithms to reduce cache miss latency
- Instruction level parallelism to reduce decode latency
- Unrolling is not portable option
Introduction
Bad news:
Some computers used a shared-memory model, others used a distributed-memory model. Some used a special parallel languages or special language extensions ( directives ), while others used standard Fortran or c with special message passing package. Some computers used large cache with high bandwidth, the others used small.
It often happened that even one did invest long time to write a parallel program for some computer, before one get much use to get his job done, either the environment changed or the computer company goes out. So the users always dreams that one can write a program which works on any kind supercomputers with almost the sam high efficiency. That is the potable program.
Good news:
All the computer companies accepted MPI as the Message Passing Interface
Standard.
Today, the portable programming is not only considerable dream but also possible.
Portablility
- Machine independence:
- without special language or directives dependence;
- without special library dependence (cps)
- less dependence on the special architecture
- cache lenth,
- number of the processors,
- number of the functional units within processor.
- works on both shared memory machines and distributed memory machines.
- reasonable efficiency.
|
MPI --- Large and Small
Point to group communication
Group to point communication
Note: Not accessible from outside *.uky.edu domain.
- Large: 128 MPI library routines ( MPI2 will have more routines ).
- Small: 6 of the 128 functions are enough for most of the applications.
- MPI_INIT( arguments )
- MPI_COMM_RANK( arguments )
- MPI_COMM_SIZE( arguments )
- MPI_FINALIZE( arguments )
- MPI_SEND( arguments )
- MPI_RECV( arguments )
|
SPMD parallel model
Example 1: Computing
. 
f(a) = 4.d0 / (1.d0 + a*a)
call MPI_INIT(ierr)
call MPI_COMM_RANK(MPI_COMM_WORLD, myid, ierr)
call MPI_COMM_SIZE(MPI_COMM_WORLD, numprocs, ierr)
n=numprocs*1000000
call MPI_BCAST(n, 1, MPI_INTEGER, 0, MPI_COMM_WORLD, ierr)
h = 1.0d0 / n
sum = 0.0d0
do i = myid + 1, n, numprocs
x = h * (dble(i) - 0.5d0)
sum = sum + f(x)
enddo
mypi = h * sum
call MPI_REDUCE(mypi, pi, 1, MPI_DOUBLE_PRECISION,
& MPI_SUM, 0, MPI_COMM_WORLD, ierr)
if (myid .eq. 0) then
write(6, 97) pi, abs(pi - 3.141592653589793238462643 )
endif
call MPI_FINALIZE(ierr)
The same program runs on each processor, with "myid" to compute in different area.
|
Data Decomposition
Example 2: Computing matrix-matrix multiplication A
B = C
- data decomposition 1:
- data decomposition 2:
call MPI_INIT(ierr)
call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr )
call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr )
IF ( myid .eq. root ) then
call MPI_BCAST(a,count,MPI_INTEGER,root,MPI_COMM_WORLD,ierr)
do j=1,numprocs-1
do i = 1,nrows
buf(i) = b(i,j+1)
enddo
call MPI_SEND(buf,nrows,MPI_INTEGER,j,tag,MPI_COMM_WORLD,ierr)
enddo
do i=1,nrows
ans(i) = 0
do j=1,ncols
ans(i) = ans(i) + a(i,j) * b(i,1)
enddo
c(i,1) = ans(i)
enddo
do j=1,numprocs-1
call MPI_RECV(ans, nrows, MPI_INTEGER, MPI_ANY_SOURCE,
& MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr)
do i=1,nrows
c(i,sender+1) = ans(i)
enddo
enddo
ELSE
call MPI_BCAST(a,count,MPI_INTEGER,root,MPI_COMM_WORLD,ierr)
call MPI_RECV(buf, nrows, MPI_INTEGER, root,
& MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr)
do i=1,nrows
ans(i) = 0
do j=1,ncols
ans(i) = ans(i) + a(i,j) * buf(j)
enddo
enddo
call MPI_SEND(ans,nrows,MPI_INTEGER,root,0,MPI_COMM_WORLD,ierr)
ENDIF
call MPI_FINALIZE(ierr)
|
Matrix to vector
Example 3: Computing matrix-vector multiplication M
v
- Data decomposition 1:
- Data decomposition 2:
|
Lattice
Example 4:
|
c preprocessor --- possible to work on workstation or PC
Most of C, Fortran 77 and Fortran 90 have c preprocessor which is invoked as the first pass when the compiler works. Its purpose is to process #include and conditional compilation instructions and macros.
On NCX, whenever you use f77, f90, mpif77, or mpif90, the file types that end in the .F extension (but not those ending in .f or .f90) will be processed by the C preprocessor as long as the +ccp option is set to its default value of "yes"; that is, if +ccp = default or +ccp = yes. In contrast, specifying +ccp = no will tell the compiler not to invoke the C preprocessor for any file on the command line, including those ending in .F.
Example:
#ifdef MPI
call MPI_INIT( ierr )
call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr )
call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr )
#endif
#ifdef Single
myid=0
numprocs=1
#endif
mpif77 -DMPI +O2 ....
f77 -DSingle +O2 ....
|
Reducing latencies --- the principles of writing a good MPI program
Limit the use of Message Passing to reduce message passing latency
Principle 1: Use message passing process as infrequently as possible.
|
Locality + high BLAS algorithms to reduce cache miss latency
- Locality --- against the memory hierarchy and cache
shortage
That means decompose large array to a number of sub-arrays which located
on different processors.
- High BLAS algorithm --- large cache use ratio
The VECLIB test with 3000 x 3000 matrix
Table 3: BLAS level and cache miss latency
The QCD test (1000,000 x 1000,000 sparse matrix):
That means decompose large array to a number of sub-arrays which located on different processors.
The VECLIB test with 3000 x 3000 matrix
Table 3: BLAS level and cache miss latency
The QCD test (1000,000 x 1000,000 sparse matrix):
Principle 2: Use high BLAS level algorithm and decompose large arrays.
|
Instruction level parallelism to reduce decode latency
The RISC processor can get high performance is because of:
where F is the frequency, m called dimension, the number of the functional units inside of the processor.
Loop unrolling
C$DIR UNROLL[UNROLL_FACTOR=4]
DO I=1,100
A(I)=A(I)+B(I)*C
ENDDO
Compiler makes this loop unrolled as:
DO I=1,100,4
A(I)=A(I)+B(I)*C
A(I+1)=A(I+1)+B(I+1)*C
A(I+2)=A(I+2)+B(I+1)*C
A(I+3)=A(I+3)+B(I+1)*C
ENDDO
|
Unrolling is not portable option
Instruction level parallel programming:
Unroll the most important loop as fine as possible by programmer's hand.
Example on QCD program: SU(3) 
SU(3) routine
COMPLEX w(3,3,N), u(3,3,N), v(3,3,N)
w=0.0d00
DO I=1,N
DO J1=1,3
DO J2=1,3
DO J3=1,3
w(J2,J1,I)=w(J2,J1,I)+u(J2,J3,I)*v(J3,J1,I)
ENDDO
ENDDO
ENDDO
ENDDO
REAL routine
Principle 3: Write instruction level parallel program by hand