[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