1 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.1

Pipelined Computations

Chapter 5

2 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.2

Pipelined Computations

Problem divided into a series of tasks that have to be completed one after the other (the basis of sequential programming). Each task executed by a separate process or processor.

3 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.3

Example

Add all the elements of array a to an accumulating sum:

for (i = 0; i < n; i++)

sum = sum + a[i];

The loop could be “unfolded” to yield

sum = sum + a[0];

sum = sum + a[1];

sum = sum + a[2];

sum = sum + a[3];

sum = sum + a[4];

4 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.4

Pipeline for an unfolded loop

5 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.5

Another Example

Frequency filter - Objective to remove specific frequencies (f0, f1, f2,f3, etc.) from a digitized signal, f(t).

Signal enters pipeline from left:

6 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.6

Where pipelining can be used to good effect

Assuming problem can be divided into a series of sequential tasks, pipelined approach can provide increased execution speed under the following three types of computations:

1. If more than one instance of the complete problem is to be

Executed

2. If a series of data items must be processed, each requiring

multiple operations

3. If information to start the next process can be passed forward

before the process has completed all its internal operations

7 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.7

“Type 1” Pipeline Space-Time Diagram

8 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.8

Alternative space-time diagram

9 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.9

“Type 2” Pipeline Space-Time Diagram

10 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

“Type 3” Pipeline Space-Time Diagram

Pipeline processing where information passes to next stage before

5.10

11 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

If the number of stages is larger than the number of processors in any pipeline, a group of stages can be assigned to each processor:

5.11

12 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Computing Platform for Pipelined Applications

Multiprocessor system with a line configuration.

Strictly speaking pipeline may not be the best structure for a cluster - however a cluster with switched direct connections, as most have, can support simultaneous message passing.

5. 12

13 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Example Pipelined Solutions

(Examples of each type of computation)

5.13

14 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Pipeline Program Examples

Adding Numbers

Type 1 pipeline computation

5.14

15 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Basic code for process Pi :

recv(&accumulation, Pi-1);

accumulation = accumulation + number;

send(&accumulation, Pi+1);

except for the first process, P0, which is

send(&number, P1);

and the last process, Pn-1, which is

recv(&number, Pn-2);

accumulation = accumulation + number;

5.15

16 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

SPMD program

if (process > 0) {

recv(&accumulation, Pi-1);

accumulation = accumulation + number;

}

if (process < n-1)

send(&accumulation, P i+1);

The final result is in the last process.

Instead of addition, other arithmetic operations could be done.

5.16

17 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Pipelined addition numbers with a master process and ring configuration

5.17

18 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Sorting Numbers

A parallel version of insertion sort.

5.18

19 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.19

Pipeline for sorting using insertion sort

Type 2 pipeline computation

20 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

The basic algorithm for process Pi is

recv(&number, Pi-1);

if (number > x) {

send(&x, Pi+1);

x = number;

} else send(&number, Pi+1);

With n numbers, how many the ith process is to accept is known; it is given by n - i.

How many to pass onward is also known; it is given by n - i - 1

since one of the numbers received is not passed onward.

Hence, a simple loop could be used.

5.20

21 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Insertion sort with results returned to the master process using a bidirectional line configuration

5.21

22 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Insertion sort with results returned

5.22

23 of 33

Prime Number Generation� Sieve of Eratosthenes

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

Next_Prime = 2 ====> Mark multiples of 2 as non-prime.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

Next_Prime = 3 ====> Mark multiples of 3 as non-prime.

24 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Prime Number Generation

Sieve of Eratosthenes

Series of all integers is generated from 2. First number, 2, is prime and kept. All multiples of this number are deleted as they cannot be prime. Process repeated with each remaining number. The algorithm removes nonprimes, leaving only primes.

Type 2 pipeline computation

5.23

25 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

The code for a process, Pi, could be based upon

recv(&x, Pi-1);

/* repeat following for each number */

recv(&number, Pi-1);

if ((number % x) != 0) send(&number, P i+1);

Each process will not receive the same amount of numbers and the amount is not known beforehand. Use a “terminator” message, which is sent at the end of the sequence:

recv(&x, Pi-1);

for (i = 0; i < n; i++) {

recv(&number, Pi-1);

If (number == terminator) break;

(number % x) != 0) send(&number, P i+1);

}

5.24

26 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Solving a System of Linear Equations

Upper-triangular form

where a’s and b’s are constants and x’s are unknowns to be found.

5.25

27 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Back Substitution

First, the unknown x0 is found from the last equation; i.e.,

Value obtained for x0 substituted into next equation to obtain x1; i.e.,

Values obtained for x1 and x0 substituted into next equation to obtain x2:

and so on until all the unknowns are found.

5.26

28 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Pipeline Solution

First pipeline stage computes x0 and passes x0 onto the second stage, which computes x1 from x0 and passes both x0 and x1 onto the next stage, which computes x2 from x0 and x1, and so on.

Type 3 pipeline computation

5.27

29 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

The ith process (0 < i < n) receives the values x0, x1, x2, …, xi-1 and computes xi from the equation:

5.28

30 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Sequential Code

Given the constants ai,j and bk stored in arrays a[ ][ ] and b[ ], respectively, and the values for unknowns to be stored in an array, x[ ], the sequential code could be

x[0] = b[0]/a[0][0]; /* computed separately */

for (i = 1; i < n; i++) { /*for remaining unknowns*/

sum = 0;

For (j = 0; j < i; j++

sum = sum + a[i][j]*x[j];

x[i] = (b[i] - sum)/a[i][i];

}

5.29

31 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

Parallel Code

Pseudocode of process Pi (1 < i < n) of could be

for (j = 0; j < i; j++) {

recv(&x[j], Pi-1);

send(&x[j], Pi+1);

}

sum = 0;

for (j = 0; j < i; j++)

sum = sum + a[i][j]*x[j];

x[i] = (b[i] - sum)/a[i][i];

send(&x[i], Pi+1);

Now we have additional computations to do after receiving and resending values.

5.30

32 of 33

Slides for Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,

5.31

Pipeline processing using back substitution

1 of 33

2 of 33

3 of 33

4 of 33

5 of 33

6 of 33

7 of 33

8 of 33

9 of 33

10 of 33

11 of 33

12 of 33

13 of 33

14 of 33

15 of 33

16 of 33

17 of 33

18 of 33

19 of 33

20 of 33

21 of 33

22 of 33

23 of 33

24 of 33

25 of 33

26 of 33

27 of 33

28 of 33

29 of 33

30 of 33

31 of 33

32 of 33

33 of 33