Algoritmi Paraleli si Distribuiti · 2013 · Sesiune
- Profesor
- Valentin Cristea
- Anul examenului
- 2013
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 331,332,333,334
- Adăugat
- 5 februarie 2013 de anonim
Ziua 1:
V1
1. Generali bizantini cu mesaje orale. Algoritm plus enunţate teoreme.
2. Problema cu secvenţă critică pentru calcul distribuit. E in notiţe o problema la care trebuie trimise request-uri si reply-uri. De descris alg in pseudocod pt ea.
3a. Ceva java cu synchronized.
3b. Algoritm undă pentru topologie inel.
V2
1. Stabilirea topologiei cu sondaje cu ecou
2. intr-un graf fiecare nod are o valoare v. Alg pt aflarea maximului dintre aceste valori (la final, fiecare nod stie care e maximul)
3. Complexitate paralela, sau Huang
Varianta 3 : La subiectul de 2 puncte am avut algoritmi unda-algoritmi de tip arbore, la subiectul 2 o problema care se rezolva cu algoritmul pulsatiilor. Si la subiectul 3: producator-consumator cu buffer comun de o unitate (la alegere cu Foster).
V4:
1) Producatori - consumatori cu buffer finit
2) O problema care se rezolva cu algoritmul ecou
3) a) Algortimul LaLann - Chang - Robert
b) Nu mai tin minte sigur, stiu ca cerea oricum implementare SIMD si MIMD si diferenta dintre ele
Ziua 2:
V1 apd: 1) ceasuri logice cu solutia lamport (0.8p pt prezentarea problemei si a regulilor) si semafoare distribuite (1.2p idee, mecanisme, pseudocod, se cerea tot ce era prin curs) 2) aveai n procese intr-un graf conex si un nod putea comunica doar cu vecinii. Se cere ca fiecare nod sa se imperecheze cu un vecin, daca se putea, daca nu, ramanea singur. E acea problema cu imperechere distribuita. Idee 0.3p, pseudocod 0.7 3.1. Suma intr-o retea hipercub de procesoare (nici nu am citit bine ce vroia, cand am vazut hipercub) 3.2. Terminarea intr-o topologie care era un graf cu un ciclu hamiltonian (se facea cu jetoane)
V2 APD: 1.) Căutare paralelă: Proprietăți dorite ale algoritmilor paralei, căutare binară pseudocod si explicat, complexitate, si de ce nu este bine o simplă paralelizare a cautării binare seriale. 2.) Un graf in care fiecare nod își cunoaște vecinii si trebuie sa se afle indicele cel mai mic al nodurilor din graf și să fie transmis nodului inițiator. 3.) Producator-Consumator cu buffer limitat folosind P si V.
V3 APDi : Subiectul1. Algoritmi unda - algoritmul fazelor.Descrieti problema + justificati folosirea algoritmului unda.Idee algoritm + complexitate + pseudocod.Algoritmul pt ciclici. Subiectul2:Un tablou n/n cu pixeli, fiecare pixel[i][j] apartine unui proces P(i,j) si contine ca valoare intensitatea pixelului. Doi pixeli sunt in aceeasi regiune daca sunt vecini(pe orizontala,verticala) si au ac intensitate. Trebuia sa calculezi minimul indexilor i+j ale proceslor pentru fiecare regiune. Toate procesele trebuie sa stie de acest minim.Idee de rezolvare + rezolvare completa in pseudocod. Subiectul3: La alegere intre algoritmul prefixului (bla bla ce se cere) si algoritmi genetici (ceva cu distr calc paralel de genu.. si metoda replicated workers)
V4 APD: 1) Algoritmi de terminare cu marcaje. Descriere (0.5p) Implementare pseudocod + analiză complexitate + corectitudine (1.2p), Comparație cu algoritmul cu mesaje confirmate (0.3p)
2) Problema care calculează diametrul unui graf conex, cunoscând vecinii + nr total de noduri cu un algoritm Heartbeat
3) La alegere între Filozofi și LeLann
V1
1. Generali bizantini cu mesaje orale. Algoritm plus enunţate teoreme.
2. Problema cu secvenţă critică pentru calcul distribuit. E in notiţe o problema la care trebuie trimise request-uri si reply-uri. De descris alg in pseudocod pt ea.
3a. Ceva java cu synchronized.
3b. Algoritm undă pentru topologie inel.
V2
1. Stabilirea topologiei cu sondaje cu ecou
2. intr-un graf fiecare nod are o valoare v. Alg pt aflarea maximului dintre aceste valori (la final, fiecare nod stie care e maximul)
3. Complexitate paralela, sau Huang
Varianta 3 : La subiectul de 2 puncte am avut algoritmi unda-algoritmi de tip arbore, la subiectul 2 o problema care se rezolva cu algoritmul pulsatiilor. Si la subiectul 3: producator-consumator cu buffer comun de o unitate (la alegere cu Foster).
V4:
1) Producatori - consumatori cu buffer finit
2) O problema care se rezolva cu algoritmul ecou
3) a) Algortimul LaLann - Chang - Robert
b) Nu mai tin minte sigur, stiu ca cerea oricum implementare SIMD si MIMD si diferenta dintre ele
Ziua 2:
V1 apd: 1) ceasuri logice cu solutia lamport (0.8p pt prezentarea problemei si a regulilor) si semafoare distribuite (1.2p idee, mecanisme, pseudocod, se cerea tot ce era prin curs) 2) aveai n procese intr-un graf conex si un nod putea comunica doar cu vecinii. Se cere ca fiecare nod sa se imperecheze cu un vecin, daca se putea, daca nu, ramanea singur. E acea problema cu imperechere distribuita. Idee 0.3p, pseudocod 0.7 3.1. Suma intr-o retea hipercub de procesoare (nici nu am citit bine ce vroia, cand am vazut hipercub) 3.2. Terminarea intr-o topologie care era un graf cu un ciclu hamiltonian (se facea cu jetoane)
V2 APD: 1.) Căutare paralelă: Proprietăți dorite ale algoritmilor paralei, căutare binară pseudocod si explicat, complexitate, si de ce nu este bine o simplă paralelizare a cautării binare seriale. 2.) Un graf in care fiecare nod își cunoaște vecinii si trebuie sa se afle indicele cel mai mic al nodurilor din graf și să fie transmis nodului inițiator. 3.) Producator-Consumator cu buffer limitat folosind P si V.
V3 APDi : Subiectul1. Algoritmi unda - algoritmul fazelor.Descrieti problema + justificati folosirea algoritmului unda.Idee algoritm + complexitate + pseudocod.Algoritmul pt ciclici. Subiectul2:Un tablou n/n cu pixeli, fiecare pixel[i][j] apartine unui proces P(i,j) si contine ca valoare intensitatea pixelului. Doi pixeli sunt in aceeasi regiune daca sunt vecini(pe orizontala,verticala) si au ac intensitate. Trebuia sa calculezi minimul indexilor i+j ale proceslor pentru fiecare regiune. Toate procesele trebuie sa stie de acest minim.Idee de rezolvare + rezolvare completa in pseudocod. Subiectul3: La alegere intre algoritmul prefixului (bla bla ce se cere) si algoritmi genetici (ceva cu distr calc paralel de genu.. si metoda replicated workers)
V4 APD: 1) Algoritmi de terminare cu marcaje. Descriere (0.5p) Implementare pseudocod + analiză complexitate + corectitudine (1.2p), Comparație cu algoritmul cu mesaje confirmate (0.3p)
2) Problema care calculează diametrul unui graf conex, cunoscând vecinii + nr total de noduri cu un algoritm Heartbeat
3) La alegere între Filozofi și LeLann