Pipelined Computations

The program consists in a series of tasks that have to be computed repeatedly in order.

Task_n(Task_n-1(...(Task₂( Task₁(data)))...));

Sequential algorithm
while (data) {
  Task_1();
  Task_2();
  ...
  Task_n();
}

Parallel algorithm. We are going to assign each task to a different process: no_proc = n.

Features

• The tasks or stages in a pipeline are inter-dependent.
• The output of each task is the input of the next task in the pipeline.
• The average time taken per piece of data is approximately the duration of the slowest task.
• Pipelining doesn't improve the execution time for a single piece of data, but the average for a large number of processed data.
• Maximum speedup = number of tasks.

Pipeline Performance

• Pipeline throughput: the amount of data processed in a unit of time.
• Pipeline latency: how long does it take for a piece of data to be completely processed.
• To increase the throughput of a pipeline, one can attempt to balance the division into tasks.
• Fill or startup: the time it takes initially to supply one piece of data per task or process.
• Drain: the time it takes for the last pieces of data to filter through.

More Examples

• CPU level: the components of each instruction (fetch, decode, execute) accomplished by various parts of the CPU.
• Signal processing: a signal that is passed through several filters for analysis.
• Graphics: from the raw geometric data to rendering using shaders and a GPU, various stages that can form a pipeline.
• Linux commands: cat sampleFile | grep "word" | wc

Pipeline_Process(id) { // process id
  while (data) {
    if (id == 0)
      input data;
    else
      Get(data, id-1);
    Execute_Task(data);
    if (id == no_proc - 1)
      output data;
    else 
      Send(data, id+1);
  }
}

Example: the sieve of Eratosthenes

• To find all the prime numbers between 2 and n², start by marking all the numbers as prime.
• Pick the lowest number marked as prime and eliminate all of its multiples (mark them as not primes). The pick the next number marked as prime and repeat the procedure up to n.
• In parallel this will work as a pipeline: each process is sending the numbers it has filtered to the next process.
• The first number received by each process is prime and will be output.
• The Task_i() will consist in verifying that a number is divisible by the ith prime number.

Note: If x is the next prime number, then the first multiple of x to be eliminated is x² because all the multiples of x less than x² are obtained by multiplying x with a number smaller than it, so they must have been eliminated in the previous steps.

Eratosthenes(n*n)
{
  for (i=0; i<n*n; i++)
    mark[i] = true;
  x = 2;
  while (x <= n) {
    m = x*x;
    while (m < n*n) {
      mark[m] = false;
      m = m+x;
    }
    do
      ++x;
    while (!mark[x]);
  }
}

Parallel algorithm
The first process starts with 2 as its prime number, eliminates all of the even numbers, and sends all of the odd numbers to the next one.

First_process() // np = no_proc; 
{
  x = 2; 
  cout << x << endl;
  for (m=3; m < np*np; m++)
    if (m % x != 0)
      Send(m, 1);
  Send(terminator, 1);
}

The intermediate processes receive a set of numbers from the previous one. The first number they receive is a prime, so they output it. Then they check each of the subsequent numbers to see if they are multiples of the first one (x), and if they are not, then they send them to the next process in the pipeline.

Intermediate_process(id) {
  Get(x, id-1);
    cout << x << endl;
  do {
    Get(m, id-1);
    if (m==terminator || m%x != 0)
      Send(m, id + 1);
  } while (m != terminator);
}

The last process receives a first number that will be a prime (x). It checks all the other numbers it receives after that to see if they are multiples of x, and if they are not, then it outputs them. If the range of number is the square of the number of processes, then all the numbers output by the last process should be prime.

Last_process() 
{
  Get(x, id-1);
    cout << x << endl;
  do {
    Get(m, id-1);
    if (m!=terminator && m%x != 0)
      cout << m << endl;
  } while (m != terminator);
}

MPI Implementation
Sequential algorithm
eratosthenes.h
eratosthenes.cc
main.cc
Makefile