Skip to main content

Pipeline

In the field of computer science, a pipeline represents a concept used in the design of processors and hardware equipment to increase the number of instructions executed in a unit of time.

This concept can be extended to MPI, where one process produces intermediate results that are transmitted to the next process. The next process processes and further transmits the received results to the next process, and this process repeats until the last process.

Slides with explanations and examples: slides

Calculating a Polynomial Using a Pipeline​

In mathematics, a polynomial represents an equation of the form: f(x) = x^2 + 2 * x + 1, where x represents the variable in the equation.

In MPI, we can calculate a polynomial using the pipeline technique as follows: the number of coefficients will be equal to the number of processes (which is equal to the number of steps in the pipeline process). In the example above, we will have 3 processes, with each process corresponding to one coefficient from the equation.

Here are attached slides that illustrate step by step: slides

Sorting Using a Pipeline​

Given a vector with n elements in random order, we want to sort it using the pipeline method with MPI. For this, we will use a network with n + 1 nodes (1 master and n workers).

The endpoint is the moment when each worker process stores one of the numbers from the initial vector, and rank[i]→saved_value < rank[i + 1]→saved_value for any i in [1, n).

Each worker is initially initialized with a value (-1 or depending on constraints), will receive (n - rank) numbers from the previous rank, and will send (n - rank - 1) numbers to the next rank.

When it receives a number, the worker will compare it with the stored value:

  • if the number < saved_value, then we save the new value and send the old one to the next process
  • if the number >= saved_value, then we send it directly to the next process

In the end, each worker will send its value to the master, and the master will construct the resulting vector. Follow the slides step by step: slides