Create Presentation
Download Presentation

Download Presentation
## Parallel Programming in C with MPI and OpenMP

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Parallel Programmingin C with MPI and OpenMP**Michael J. Quinn**Chapter 12**Solving Linear Systems**Outline**• Terminology • Back substitution • Gaussian elimination • Jacobi method • Conjugate gradient method**Terminology**• System of linear equations • Solve Ax = b for x • Special matrices • Upper triangular • Lower triangular • Diagonally dominant • Symmetric**Upper Triangular**4 2 -1 5 9 2 0 -4 5 6 0 -4 0 0 3 2 4 6 0 0 0 0 9 2 0 0 0 0 8 7 0 0 0 0 0 2**Lower Triangular**4 0 0 0 0 0 0 0 0 0 0 0 5 4 3 0 0 0 2 6 2 3 0 0 8 -2 0 1 8 0 -3 5 7 9 5 2**Diagonally Dominant**19 0 2 2 0 6 0 -15 2 0 -3 0 5 4 22 -1 0 4 2 3 2 13 0 -5 5 -2 0 1 16 0 -3 5 5 3 5 -32**Symmetric**3 0 2 2 0 6 0 7 4 3 -3 5 5 4 0 -1 0 4 2 3 -1 9 0 -5 0 -3 0 0 5 5 6 5 4 -5 5 -3**Back Substitution**• Used to solve upper triangular systemTx = b for x • Methodology: one element of x can be immediately computed • Use this value to simplify system, revealing another element that can be immediately computed • Repeat**Back Substitution**1x0 +1x1 –1x2 +4x3 = 8 – 2x1 –3x2 +1x3 = 5 2x2 – 3x3 = 0 2x3 = 4**Back Substitution**1x0 +1x1 –1x2 +4x3 = 8 – 2x1 –3x2 +1x3 = 5 2x2 – 3x3 = 0 2x3 = 4 x3 = 2**Back Substitution**1x0 +1x1 –1x2 = 0 – 2x1 –3x2 = 3 2x2 = 6 2x3 = 4**Back Substitution**1x0 +1x1 –1x2 = 0 – 2x1 –3x2 = 3 2x2 = 6 2x3 = 4 x2 = 3**Back Substitution**1x0 +1x1 = 3 – 2x1 = 12 2x2 = 6 2x3 = 4**Back Substitution**1x0 +1x1 = 3 – 2x1 = 12 2x2 = 6 2x3 = 4 x1 = –6**Back Substitution**1x0 = 9 – 2x1 = 12 2x2 = 6 2x3 = 4**Back Substitution**1x0 = 9 – 2x1 = 12 2x2 = 6 2x3 = 4 x0 = 9**Pseudocode**fori n 1 down to 1 do x [ i ] b[ i] /a[ i, i ] for j 0 to i 1 do b [ j ] b [ j ] x [ i ] × a [ j, i ] endfor endfor Time complexity: (n2)**Data Dependence Diagram**We cannot execute the outer loop in parallel. We can execute the inner loop in parallel.**Row-oriented Algorithm**• Associate primitive task with each row of A and corresponding elements of x and b • During iteration i task associated with row j computes new value of bj • Task i must compute xi and broadcast its value • Agglomerate using rowwise interleaved striped decomposition**Interleaved Decompositions**Rowwise interleaved striped decomposition Columnwise interleaved striped decomposition**Complexity Analysis**• Each process performs about n / (2p) iterations of loop j in all • A total of n -1 iterations in all • Computational complexity: (n2/p) • One broadcast per iteration • Communication complexity: (nlog p)**Gaussian Elimination**• Used to solve Ax = b when A is dense • Reduces Ax = b to upper triangular system Tx = c • Back substitution can then solve Tx = cfor x**Gaussian Elimination**4x0 +6x1 +2x2 – 2x3 = 8 2x0 +5x2 – 2x3 = 4 –4x0 – 3x1 – 5x2 +4x3 = 1 8x0 +18x1 – 2x2 +3x3 = 40**Gaussian Elimination**4x0 +6x1 +2x2 – 2x3 = 8 – 3x1 +4x2 – 1x3 = 0 +3x1 – 3x2 +2x3 = 9 +6x1 – 6x2 +7x3 = 24**Gaussian Elimination**4x0 +6x1 +2x2 – 2x3 = 8 – 3x1 +4x2 – 1x3 = 0 1x2 +1x3 = 9 2x2 +5x3 = 24**Gaussian Elimination**4x0 +6x1 +2x2 – 2x3 = 8 – 3x1 +4x2 – 1x3 = 0 1x2 +1x3 = 9 3x3 = 6**Numerical Stability Issues**• If pivot element close to zero, significant roundoff errors can result • Gaussian elimination with partial pivoting eliminates this problem • In step i we search rows i through n-1 for the row whose column i element has the largest absolute value • Swap (pivot) this row with row i**Row-oriented Parallel Algorithm**• Associate primitive task with each row of A and corresponding elements of x and b • A kind of reduction needed to find the identity of the pivot row • Tournament: want to determine identity of row with largest value, rather than largest value itself • Could be done with two all-reductions • MPI provides a simpler, faster mechanism**MPI_MAXLOC, MPI_MINLOC**• MPI provides reduction operators MPI_MAXLOC, MPI_MINLOC • Provide datatype representing a (value, index) pair**Example Use of MPI_MAXLOC**struct { double value; int index; } local, global; ... local.value = fabs(a[j][i]); local.index = j; ... MPI_Allreduce (&local, &global, 1, MPI_DOUBLE_INT, MPI_MAXLOC, MPI_COMM_WORLD);**Communication Complexity**• Complexity of tournament: (log p) • Complexity of broadcasting pivot row:(n log p) • A total of n - 1 iterations • Overall communication complexity:(n2 log p)**Column-oriented Algorithm**• Associate a primitive task with each column of A and another primitive task for b • During iteration i task controlling column i determines pivot row and broadcasts its identity • During iteration i task controlling column i must also broadcast column i to other tasks • Agglomerate tasks in an interleaved fashion to balance workloads • Isoefficiency same as row-oriented algorithm**Comparison of Two Algorithms**• Both algorithms evenly divide workload • Both algorithms do a broadcast each iteration • Difference: identification of pivot row • Row-oriented algorithm does search in parallel but requires all-reduce step • Column-oriented algorithm does search sequentially but requires no communication • Row-oriented superior when n relatively larger and p relatively smaller**Problems with These Algorithms**• They break parallel execution into computation and communication phases • Processes not performing computations during the broadcast steps • Time spent doing broadcasts is large enough to ensure poor scalability**Pipelined, Row-Oriented Algorithm**• Want to overlap communication time with computation time • We could do this if we knew in advance the row used to reduce all the other rows. • Let’s pivot columns instead of rows! • In iteration i we can use row i to reduce the other rows.**Communication Pattern**Reducing Using Row 0 0 Row 0 3 1 2**Communication Pattern**Reducing Using Row 0 0 3 Reducing Using Row 0 1 Row 0 2**Communication Pattern**Reducing Using Row 0 0 3 Reducing Using Row 0 1 Row 0 Reducing Using Row 0 2**Communication Pattern**Reducing Using Row 0 0 Reducing Using Row 0 3 Reducing Using Row 0 1 Reducing Using Row 0 2**Communication Pattern**0 Reducing Using Row 0 3 Reducing Using Row 0 1 Reducing Using Row 0 2**Communication Pattern**0 Reducing Using Row 0 3 Reducing Using Row 1 1 Row 1 Reducing Using Row 0 2**Communication Pattern**0 Reducing Using Row 0 3 Reducing Using Row 1 1 Row 1 Reducing Using Row 1 2**Communication Pattern**0 Row 1 Reducing Using Row 1 3 Reducing Using Row 1 1 Reducing Using Row 1 2**Communication Pattern**Reducing Using Row 1 0 Reducing Using Row 1 3 Reducing Using Row 1 1 Reducing Using Row 1 2**Analysis**• Total computation time: (n3/p) • Total message transmission time: (n2) • When n large enough, message transmission time completely overlapped by computation time • Message start-up not overlapped: (n) • Parallel overhead: (np)**Sparse Systems**• Gaussian elimination not well-suited for sparse systems • Coefficient matrix gradually fills with nonzero elements • Result • Increases storage requirements • Increases total operation count