[SOLVED] CS Fortran data structure compiler High Performance Computing

High Performance Computing
Models of Parallel Programming
Dr Ligang He

Models of Parallel Programming
Different approaches for programming on a HPC system include:
Smart compilers, which automatically parallelise sequential codes
Data parallelism: multiple processors run the same operation on different elements of a data structure
Task parallelism: multiple processors run different operations
Dedicated languages designed specifically for parallel computers
Computer Science, University of Warwick
2

Dependency and Parallelism
Dependency: If instruction A must finish before instruction B can run, then B is dependent on A
Two types of Dependency
Control dependency: waiting for the instruction which controls
the execution flow to be completed
IF (X!=0) Then Y=1.0/X: Y=1.0/X has the control dependency on X!=0 Data dependency: dependency because of accessing the same
data
Flow dependency: A=X+Y; B=A+C;
Anti-dependency: B=A+C; A=X+Y;
Output dependency: A=2; X=A+1; A=5;
When two instructions access the same memory location and one of the instructions write to the location, there exists data dependency.
Computer Science, University of Warwick
3

Compiler Approach
Computer Science, University of Warwick
4

Compiler Approach
Automatically parallelize the sequential codes Very conservative
Re-implementing the code in a more efficient way
Can remove the dependency if possible
Computer Science, University of Warwick
5

Re-implement the code in compilation
Before:
A=SQRT(B)
D=A*B A=0.0
C=2*A
After:
A=SQRT(B) C=2*A
A=SQRT(B) D=A*B
A=0.0
Computer Science, University of Warwick
6

Removing the dependency
Anti-dependency and output-dependency can be removed by renaming the variables
Anti-dependency: Before:
Y=2 * X X= 5
After: Y=2 * X
X1= 5
Output-dependency Before:
X=A/B Y=X+2.0 X=D E
After: X=A/B
Y=X+2.0 X1=D E
Anti-dependency and output dependency exist because the instructions requires to use the same memory location
Remove the anti- and output dependency by creating another place In flow dependency, the instructions depend on both place and data
Computer Science, University of Warwick
7

Examples of automatic parallelization by compiler
The code is written in a standard language (e.g. C or Fortran)
Compiler automatically compiles it to be run in parallel (e.g. by
parallelizing loops)
Example 1: for(i=1; i