Arhitecturi Paralele - Solutions (C04_solutii paralele.pdf)

Arhitecturi Paralele Abordări probleme paralele Prof. Ciprian Dobre [email protected] Paralelism: modele Pipeline  Pipeline CPU Instruction pipeline Graphics pipeline Various algorithms Step1 Step2 Step3 St...

Arhitecturi Paralele Abordări probleme paralele Prof. Ciprian Dobre [email protected] Paralelism: modele Pipeline  Pipeline CPU Instruction pipeline Graphics pipeline Various algorithms Step1 Step2 Step3 Step4 Un pas poate fi executat de: thread process element hardware Task 6 Task 5 Task 4 Task 3 Task 2 Task 1 Step1-4 Without Pipeline Task 6 Task 5 Task 4 Task 3 Task 2 Step1-4 Without Pipeline Task 1 Task 6 Task 5 Task 4 Task 3 Step1-4 Without Pipeline Task 2 Task 1 Task 6 Task 5 Task 4 Step1-4 Without Pipeline Task 3 Task 2 Task 1 Task 6 Task 5 Step1-4 Without Pipeline Task 4 Task 3 Task 2 Task 1  Without Pipeline Task 6 Task 5 Task 4 Task 3 Task 2 Task 1 Step1-4 𝑡𝑜𝑡𝑎𝑙_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 = 𝑡𝑎𝑠𝑘_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 ∗ 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜𝑓_𝑡𝑎𝑠𝑘𝑠  Task 6 Task 5 Task 4 Task 3 Task 2 Step1 Task 1 Step2 Pipeline Step3 Step4  Task 6 Task 5 Task 4 Task 1 Task 3 Task 2 Step1 Step2 Pipeline Step3 Step4  Task 6 Task 5 Task 4 Task 2 Task 3 Step1 Task 1 Step2 Pipeline Step3 Step4  Task 6 Task 5 Task 4 Task 3 Step1 Task 2 Step2 Pipeline Task 1 Step3 Step4  Task 6 Task 5 Task 4 Step1 Task 3 Step2 Pipeline Task 2 Step3 Task 1 Step4  Task 6 Task 5 Step1 Task 4 Step2 Pipeline Task 3 Step3 Task 2 Step4 Task 1  Task 6 Step1 Task 5 Step2 Pipeline Task 4 Step3 Task 3 Step4 Task 2 Task 1  Step1 Task 6 Step2 Pipeline Task 5 Step3 Task 4 Step4 Task 3 Task 2 Task 1  Step1 Step2 Pipeline Task 6 Step3 Task 5 Task 4 Step4 Task 3 Task 2 Task 1  Pipeline 𝑡𝑎𝑠𝑘_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 Ideal: 𝑠𝑡𝑒𝑝_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 = 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜𝑓_𝑠𝑡𝑒𝑝𝑠 Step1 Step2 Step3 Step4 Task 6 După 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜𝑓_𝑠𝑡𝑒𝑝𝑠 tascuri: 𝑡𝑜𝑡𝑎𝑙_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 = 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜𝑓_𝑡𝑎𝑠𝑘𝑠 ∗ 𝑠𝑡𝑒𝑝_𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛_𝑡𝑖𝑚𝑒 Task 3 Task 2 Task 1 Task 4 Task 5 Un task se termină la fiecare “step tick” Sortare...  Sorting 9 4 2 7 6 5 6 1 1 2 4 5 6 6 7 9  Sorting with pipeline 9 4 2 7 6 5 6 1 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 2 7 6 5 6 1 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 2 7 6 5 1 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 2 7 6 1 5 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 2 7 1 6 6 5 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 2 1 5 7 6 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 4 1 5 6 2 7 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 9 1 5 6 4 2 7 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 6 6 9 4 5 7 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 5 6 9 4 6 7 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 6 7 9 5 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 9 6 7 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 7 9 6 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 6 9 7 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 6 7 9 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 6 7 9 S1 S2 S3 S4 S5 S6 S7 S8  Sorting with pipeline 1 2 4 5 6 6 7 9 S1 S2 S3 S4 S5 S6 S7 S8  Pașii algoritmului de sortare 0 1 2 3 5 Pentru N valori, faza 1 durează 2N-1 pași  Faza a doua ▪ Valorile ordonate sunt scoase prin celula din stânga ▪ Variante: 1. fiecare procesor începe să transmită spre stânga, imediat ce numerele sunt sortate; 2. cunoscând poziţia sa din vector şi numărând valorile inspectate, fiecare procesor calculează momentul când începe să transmită spre stânga; 3. procesorul din dreapta începe să transmită spre stânga imediat ce primeşte o valoare; toate celelalte încep să transmită spre stânga imediat ce primesc o valoare din dreapta; 4. fiecare procesor începe să transmită spre stânga imediat ce nu mai primeşte o valoare dinspre stânga. Complexitate: Variantele 1 și 2 impun cunoașterea  metoda 3 → 4N-3 pași  Pozitiei procesoarelor in vector  metoda 4 → 3N-2 pași  Contorizarea valorilor  Metoda 4 faza 2 0 1 2 3 5 sfarsit faza 1 0 un pas - procesoarele observa 1 2 3 5 ca nu mai primesc din stanga si transmit in stanga 1 2 3 5 un pas – valoarea din dreapta trece la iesirea din stanga 2 3 5 3 5 5 Calcule polinomiale...  Polynomial 𝑛 𝑃 𝑥 = ෍ 𝑎𝑖 𝑥 𝑖 = 𝑎0 𝑥 0 + 𝑎1 𝑥1 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑛−1 𝑥 𝑛−1 + 𝑎𝑛 𝑥 𝑛 , 𝑛 ≥ 0 𝑖=0  Pipeline Step1 Step2 Step3 Step4  Polynomial calculation + Pipeline 0 1 2 3 4 𝑃 𝑥 = 1 + 8𝑥 + (−4)𝑥 3 +𝑥 4 a 1 8 0 -4 1 Step1 Step2 Step3 Step4  Polynomial calculation + Pipeline 𝑃 𝑥 = 1 + 8𝑥 + (−4)𝑥 3 +𝑥 4 0 1 2 3 4 a 1 8 0 -4 1 S1 S2 S3 S4 S5  Polynomial calculation + Pipeline 𝒙𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 0 1 2 3 4 a 1 8 0 -4 1 S1 S2 S3 S4 S5  Polynomial calculation + Pipeline 𝒙𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 0 1 2 3 4 a 1 8 0 -4 1 S1 S2 S3 S4 S5 𝒙𝟓  Polynomial calculation + Pipeline 𝒙𝟏 𝒙 𝟐 𝒙 𝟑 0 1 2 3 4 a 1 8 0 -4 1 1 S1 S2 S3 S4 S5 𝒙𝟒 𝒙𝟓 𝒙𝟎𝟓  Polynomial calculation + Pipeline 𝒙𝟏 𝒙 𝟐 0 1 2 3 4 1 + 8𝑥5 a 1 8 0 -4 1 1 S1 S2 S3 S4 S5 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟎𝟒 𝒙𝟏𝟓  Polynomial calculation + Pipeline 𝒙𝟏 0 1 2 3 4 1 + 8𝑥5 1 + 8𝑥4 a 1 8 0 -4 1 1 S1 S2 S3 S4 S5 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟎𝟑 𝒙𝟏𝟒 𝒙𝟐𝟓  Polynomial calculation + Pipeline 1 + 8𝑥5 + (−4)𝑥53 0 1 2 3 4 1 + 8𝑥4 1 + 8𝑥3 a 1 8 0 -4 1 1 S1 S2 S3 S4 S5 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟎𝟐 𝒙𝟏𝟑 𝒙𝟐𝟒 𝒙𝟑𝟓  Polynomial calculation + Pipeline 1 + 8𝑥4 + (−4)𝑥43 0 1 2 3 4 1 + 8𝑥3 1 + 8𝑥2 a 1 8 0 -4 1 1 S1 S2 S3 S4 S5 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟎𝟏 𝒙𝟏𝟐 𝒙𝟐𝟑 𝒙𝟑𝟒 𝟏 + 𝟖𝒙𝟓 + (−𝟒)𝒙𝟑𝟓 + 𝒙𝟒𝟓  Polynomial calculation + Pipeline 1 + 8𝑥3 + (−4)𝑥33 0 1 2 3 4 1 + 8𝑥2 1 + 8𝑥1 a 1 8 0 -4 1 S1 S2 S3 S4 S5 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟏𝟏 𝒙𝟐𝟐 𝒙𝟑𝟑 𝟏 + 𝟖𝒙𝟒 + (−𝟒)𝒙𝟑𝟒 + 𝒙𝟒𝟒 𝟏 + 𝟖𝒙𝟓 + (−𝟒)𝒙𝟑𝟓 + 𝒙𝟒𝟓  Polynomial calculation + Pipeline 1 + 8𝑥2 + (−4)𝑥23 0 1 2 3 4 1 + 8𝑥1 a 1 8 0 -4 1 S1 S2 S3 S4 S5 𝒙𝟏 𝒙𝟐 𝒙𝟐𝟏 𝒙𝟑𝟐 𝟏 + 𝟖𝒙𝟑 + (−𝟒)𝒙𝟑𝟑 + 𝒙𝟒𝟑 𝟏 + 𝟖𝒙𝟒 + (−𝟒)𝒙𝟑𝟒 + 𝒙𝟒𝟒 𝟏 + 𝟖𝒙𝟓 + (−𝟒)𝒙𝟑𝟓 + 𝒙𝟒𝟓  Polynomial calculation + Pipeline 1 + 8𝑥1 + (−4)𝑥13 0 1 2 3 4 a 1 8 0 -4 1 S1 S2 S3 S4 S5 𝒙𝟏 𝒙𝟑𝟏 𝟏 + 𝟖𝒙𝟑 + (−𝟒)𝒙𝟑𝟑 + 𝒙𝟒𝟑 𝟏 + 𝟖𝒙𝟒 + (−𝟒)𝒙𝟑𝟒 + 𝒙𝟒𝟒 𝟏 + 𝟖𝒙𝟐 + (−𝟒)𝒙𝟑𝟐 + 𝒙𝟒𝟐 𝟏 + 𝟖𝒙𝟓 + (−𝟒)𝒙𝟑𝟓 + 𝒙𝟒𝟓  Polynomial calculation + Pipeline 0 1 2 3 4 a 1 8 0 -4 1 S1 S2 S3 S4 S5 𝟏 + 𝟖𝒙𝟑 + (−𝟒)𝒙𝟑𝟑 + 𝒙𝟒𝟑 𝟏 + 𝟖𝒙𝟏 + (−𝟒)𝒙𝟑𝟏 + 𝒙𝟒𝟏 𝟏 + 𝟖𝒙𝟒 + (−𝟒)𝒙𝟑𝟒 + 𝒙𝟒𝟒 𝟏 + 𝟖𝒙𝟐 + (−𝟒)𝒙𝟑𝟐 + 𝒙𝟒𝟐 𝟏 + 𝟖𝒙𝟓 + (−𝟒)𝒙𝟑𝟓 + 𝒙𝟒𝟓 Aplicație: problema Damelor N Queens Problem Q Q Q Q  N Queens Problem No more then one queen per line Q Q Q Q  N Queens Problem No more then one queen per column Q Q Q Q  N Queens Problem No more then one queen per diagonals Q Q Q Q N Queens Problem 0 1 2 3 0 1 2 3 0 Q 1 3 0 2 1 Q 2 Q These two mean the 3 Q same thing N Queens Problem - Solution 0 1 2 3 0 1 2 3 0 Q 0 1 2 3 N Queens Problem - Solution 0 1 2 3 0 1 2 3 0 QQ 0 0 1 2 Line conflict 3 N Queens Problem - Solution 0 1 2 3 0 1 2 3 0 Q 0 1 1 Q 2 Diagonal conflict 3 N Queens Problem - Solution 0 1 2 3 0 1 2 3 0 Q 0 2 1 2 Q OK. 3 And so on… N Queens Problem – Parallel Solution 0 1 2 3 0 1 2 3  N Queens Problem – Parallel Solution 0 1 2 3 0 1 2 3 0 0 X 1 0 X 0 1 X 1 1 X 0 2 1 2 X 0 3 1 3 0 1 2 3 And so on… 0 1 2 3 2 0 3 0 2 1 X 3 1 2 2 X 3 2 X 2 3 X 3 3 X Cautare binara  Binary Search Searching for 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 3 5 5 6 6 7 7 7 8 8 9 9 9  Binary Search Searching for 3 Interest area 0 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 3 5 5 6 6 7 7 7 8 8 9 9 9 3