Pipeline

În domeniul de computer science, un pipeline reprezintă un concept folosit în proiectarea procesoarelor și al echipamentelor hardware prin care se crește numărul de instrucțiuni ce sunt executate într-o unitate de timp.

Acest concept poate fi extins în MPI, unde un proces produce rezultate intermediare, care sunt transmise către procesul următor, care procesează și prelucrează rezultatele primite, pe care le trimite mai departe, către procesul următor, totul repetându-se până la ultimul proces.

Slides cu explicații și exemple: slides

Calculul unui polinom folosind pipeline

Un polinom, în matematică, reprezintă o ecuație de tipul: f(x) = x^2 + 2 * x + 1, unde x reprezintă variabila din ecuație.

În MPI, putem calcula un polinom folosind tehnica pipeline în felul următor: numărul de coeficienți va fi egal cu numărul de procese (care este egal cu numărul de pași din procesul de pipeline). În cazul exemplului de mai sus, o să avem 3 procese, fiecare proces corespunzând cu câte un coeficient din ecuație.

Aici aveți atașate slide-uri, care ilustrează pas cu pas: slides

Sortarea folosind pipeline

Dându-se un vector cu n elemente în ordine aleatoare, dorim să-l sortăm prin metoda pipeline, folosind MPI. Pentru aceasta, vom folosi o rețea cu n + 1 noduri (1 master și n workeri).

Punctul final este momentul în care fiecare proces worker deține stocat unul din numerele din vectorul inițial, iar rank[i]→saved_value < rank[i + 1]→saved_value pentru orice i din [1, n).

Fiecare worker este inițializat la început cu o valoare (-1 sau depinde de restricții), va primi (n - rank) numere de la rank-ul anterior și va trimite mai departe rank-ului următor (n - rank - 1) numere.

Atunci când primește un număr, worker-ul îl va compara cu valoarea stocată:

• dacă nr < saved_value, atunci salvăm noua valoare și o trimitem pe cea veche procesului următor
• dacă nr >= saved_value, atunci o trimitem direct procesului următor

La final, fiecare worker va trimite către master valoarea lui, iar master-ul va construi vectorul rezultat. Urmăriți slide-urile pas cu pas: slides