Exerciții

1. Compilați fișierul mutex.c din scheletul de laborator și rulați de mai multe ori programul obținut (puteți folosi scriptul test_mutex.sh). Veți observa că rezultatul nu este întotdeauna cel așteptat. Rezolvați problema de sincronizare folosind un mutex.
2. Pornind de la fișierul barrier.c din scheletul de laborator, folosiți o barieră pentru a vă asigura că output-ul va fi întotdeauna "1\n2". Verificați sugestia 1 de mai jos pentru informații suplimentare.
3. Pornind de la fișierul multiply_outer.c din scheletul de laborator, paralelizați programul prin împărțirea iterației exterioare la mai multe thread-uri. Verificați corectitudinea și scalabilitatea programului rezultat. Verificați sugestia 2 de mai jos pentru informații suplimentare.
4. Pornind de la fișierul multiply_middle.c din scheletul de laborator, paralelizați doar cea de-a doua buclă de iterație. Verificați corectitudinea și scalabilitatea programului rezultat.
5. Pornind de la fișierul multiply_inner.c din scheletul de laborator, paralelizați doar bucla interioară. Verificați corectitudinea și scalabilitatea programului rezultat. Verificați sugestia 3 de mai jos pentru informații suplimentare.
6. Pornind de la fișierul strassen.c din scheletul de laborator, paralelizați înmulțirea unor matrice cu algoritmul Strassen folosind 7 thread-uri (de recomandat într-un fișier separat, numit strassen_par.c, pentru a putea testa corectitudinea folosind scriptul test_strassen.sh, care compară versiunea serială cu cea paralelizată). Verificați sugestia 4 de mai jos pentru informații suplimentare.

sugestie

1. Pe sisteme MacOS, biblioteca de Pthreads nu conține implementarea pentru barieră. Pentru a putea face totuși acest exercițiu, există în scheletul de laborator un fișier numit pthread_barrier_mac.h pe care trebuie să-l includeți în fișierul vostru sursă.

sugestie

2. Pentru a putea testa corectitudinea paralelizării de la exercițiile 3, 4 și 5, găsiți în arhiva de laborator un script numit test_multiply.sh. Acesta face următorii pași:

• verifică să existe un binar numit multiply_seq pentru implementarea secvențială a înmulțirii de matrice, pentru care aveți fișierul sursă multiply_seq.c în arhiva de laborator (acesta va servi drept etalon pentru corectitudinea implementării paralele)
• verifică să existe binare pentru implemenările voastre paralele (multiply_outer pentru exercițiul 3, multiply_middle pentru exercițiul 4, multiply_inner pentru exercițiul 5) rulează programul secvențial
• rulează cele trei programe paralele
• compară rezultatele rulărilor paralele cu rularea secvențială folosind diff; dacă nu există diferențe, scriptul nu afișează nimic; dacă implementarea paralelă este incorectă, se vor afișa diferențele dintre rularea implementării secvențiale și a celei paralele.

În mod implicit, scriptul rulează pe matrice de 1000×1000 de elemente, cu două thread-uri pentru implementarea paralelă. Dacă doriți să modificați aceste valori (și vă recomandăm să o faceți, pentru o testare cât mai completă), puteți modifica valorile variabilelor N și P din script.

sugestie

3. Veți observa la acest exercițiu că, dacă paralelizați bucla interioară așa cum ați făcut la precedentele două exerciții, rezultatele nu vor fi întotdeauna corecte. De ce? Ce trebuie să faceți pentru o implementare corectă?

sugestie

4. Algoritmul lui Strassen este un algoritm pentru înmulțire de matrice mai rapid decât metoda standard, având o complexitate de O(N^2.8074). În acest algoritm, la primul pas se definesc 7 matrice adiționale obținute prin înmulțiri ale matricelor bloc obținute din matricele inițiale. La al doilea pas, aceste 7 matrice noi sunt folosite pentru a calcula (prin operații de adunare și scădere) componentele bloc ale matricei finale.

Pentru exercițiul 6, aveți deja implementat calculul matricelor adiționale și calculul final, așa că voi trebuie doar să paralelizați aceste operații.