26 subiecte
Algoritmi Paraleli si Distribuiti
2016 · Sesiune · CA
2017 de fapt, nu exista optiunea :)) a doua tura nr. 3 1. cautare paralela 2. se dau mai multe procese, fiecare are cate 2 valori; in final sa se afle cea mai mare valoare 3.1. prioritate pt cititori 3.2 nu mai stiu, ceva obscur oricum stiu ca la nr 4. a fost la 1 terminarea cu marcaje si pe la nr 1 sau 2 bizantinii
27 august 2017
Algoritmi Paraleli si Distribuiti
2016 · Sesiune · 335CA, 332CA CA
V1 1. [2p] Problema generarilor bizantini. Descriere. Solutia cu mesaje orale.Teoreme. Pseudocod. Complexitate. Exemplu cu 3 generali. 2. [1p] Procesul A are un set S de numere intregi, iar procesul B un set T. Cele doua procese schimba cate o pereche de numere intre ele. Sa se scrie un algoritm care sa obtina toate valorile din S mai mici decat toate din T. 3. [1p] La alegere intre: a) Inmultirea paralela a matricilor. b) Sfarsitul listei (algoritm paralel - cel din curs).
28 ianuarie 2017
Algoritmi Paraleli si Distribuiti
2016 · Sesiune · 331/334 CB
Varianta 4 1. Ceasuri logice (problema care o rezolva, cum se aplica si se modifica ceasurile, pseudocod excludere mutuala distribuita) 2. Problema sa stabilesti arborele de acoperire fara sa faci topologia 3. La alegere: 3. 1 Excludere mutuala pentru K procese (pe thread-uri nu distribuit) 3. 2 Algoritmul LeLann-Chang-Robert Varianta3 1. Stabilirea topologiei folosind mesaje de sondaj cu ecou. 2. Sortarea paralela folosind unvector de procese 3.1 Calculul complexitatii algoritmilor paraleli (metrici si algoritmul de cautare folosind un vector de procese = aprox acelasi lucru cu subiectul 2 cred !?!?!?!) 3.2 Ceva cu difuzarea variabilelor intr-un sistem SIMD - EREW (sau ceva de genu) Varianta 2: 1.1 algoritmi unda justificare folosire 1.2 algoritm faze : pseudocod, justificare corectitudine, complexitatea 1.3 caz particular clica 2 .n procese și trebuia aflat numărul maxim de vecini din graf 3.1 lelann ChangRObert 3.2 filosofi : descriere, pseudocod, justificare corectitudine Varianta 1: 1. Cititori scriitori cu prioritate scriitori 2. Fiecare nod al unui arbore contine k numere distincte. Se cere ca la final, initiatorul sa aiba toate numere comune. Pe legaturi se poate transmite doar un int odata. 3.2 Terminarea in inel. 3.1 inmultirea a 2 matrici in paralel
1 februarie 2016
Algoritmi Paraleli si Distribuiti
2016 · Sesiune · 332+333 CB
1. Ceasurile logice vectoriale: a) explicarea necesitatea implementarii lor b) cum se pot implementa acestea c) regulile ceasurilor logice vectoriale d) descrierea ordonarii cauzale multicast 2. Se dau trei procese. Fiecare contine o secventa de numere sortate in ordine crescatoare, iar in cadrul acestora exista un numar comun. Se cere determinarea acestuia. In momentul in care un proces face operatia de send, acesta poate trimite doar un mesaj. a) pseudocodul algoritmului folosit pentru a gasi numarul comun b) justificarea solutiei 3. La alegere: 3.1 Difuzarea unei valori in cadrul sistemelor de tip SIMD ( pentru EREW ): a) explicare si modul de implementare al difuzarii b) pseudocodul algoritmului 3.2 Terminarea programelor distribuite: explicare, pseudocod si complexitate .
30 ianuarie 2016
Algoritmi Paraleli si Distribuiti
2016 · Sesiune · 331, 334, 335 CA
Examen 21.01.2016 Varianta 1 1. Generali bizantini cu mesaje semnate. 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. Varianta 2 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 1. Algoritmi de tip unda.Algoritmul arbore 2. O problema care se rezolva cu algoritmul pulsatiilor 3. Producator-consumator cu buffer comun de o unitate (la alegere cu Foster). Varianta 4 1. Cititori si scriitori cu split binary semaphore. 2. Se dau n procese asociat unui graf cu n noduri,iar fiecare proces cunoaste cine sunt vecinii sai. Sa se stabileasca pentru fiecare nod cine este parintele sau si care sunt fiii acestuia inainte ca ei sa afle topologia 3. a) Algortimul LaLann b) Produse prefix cu mimd
28 ianuarie 2016
Algoritmi Paraleli si Distribuiti
2015 · Sesiune · CB
Varianta2 - 01.02.2015 1. Terminarea programelor distribuite. Detectia terminatii folosind marcaje 1.1 Prezentarea generala a problemei si a ideii de rezolvare (0.5p) 1.2 Descrierea solutiei in pseudocod, justificarea corectitudinii solutiei, analiza complexitatii - strict cate mesaje de terminare se trimit (1.2p) 1.3 Diferenta fata de detectia teminarii folosind confirmarile mesajelor (0.3p) 2. n procesoare - fiecare corespunde unui nod din graf. Fiecare proces detine o valoare intreaga v si poate comunica cu vecinii sai din graf. Scrieti pseudocodul pentru calcularea maximului dintre cele n valori. Fiecare proces va detine valoarea maxima. (solutia sa nu fie fiecare proces sa trimita valorile tuturor celorlalte procese si fiecare sa calculeze maximul) 2.1 idee (0.3p) 2.2 pseudocod (0.7p) 3.1 Algoritmi unda pentru topologie inel(1p) 3.2 Problema filosofilor (1p)
4 februarie 2016
Algoritmi Paraleli si Distribuiti
2015 · Sesiune · 332 CA
1. Algoritmul arbore. 1. De explicat ce este o unda. 2.Care sunt cunostintele initiale ale proceselor in cadrul agoritmului? 3. Pseudocod + explicatii 4. De precizat si demonstrat cele trei proprietati ale algoritmului 4. Complexitate 5.De aplicat pe un exemplu dat de prof 2. O problema in care se cerea determinarea gradului fiecarui nod intr-un graf. 3. Producator consumator cu buffer limitat.
18 februarie 2015
Algoritmi Paraleli si Distribuiti
2015 · Sesiune · cc
2015: Subiecte APD - Varianta C 1. Aflarea topologiei: algoritmul pulsatiilor si algoritmul cu mesaje de sondaj cu ecou. 2. Pentru n procesoare care vor sa intre intr-o zona critica trebuie sa se realizeze o prioritizare in asa fel incat va intra in zona critica procesorul care a asteptat cel mai mult (FIFO). 3. La alegere producator - consumator sau problema barbierului [APD] Varianta A 1. Alegerea liderului. Descriere + pseudocod pentru algoritmul tree și algoritmul Hirschberg Sinclair. Rulare pe un graf pentru Hirschberg Sinclair. 2. Problemă cu semafoare. Sunt N procese și fiecare primește la început câte un număr. În zona critică poate intra doar procesul cu numărul primit minim. Dacă 2 procese au același număr, are prioritate cel cu id-ul mai mic. 3.1 Modelul Foster. Modelul revizuit. Floyd paralel 1d. 3.2 Cititori - Scriitori. Predarea ștafetei. Subiecte APD - varianta B. 1. Bizantini - mesaje scrise 2. O problema cu o topologie arbore si k numere in fiecare nod. Se cerea un algoritm pentru a afla numerele comune. 3. La alegere LogP vs Semafoare distribuite. Varianta D 1. Algoritmi de unda: Caracteristici generale, proprietati, schema de transmitere mesaje. Algoritmul fazelor si arbore cod + explicatii si de aplicat algoritmul fazelor pe un graf. 2. Aveai o topologie cu n sisteme distribuite si fiecarea avea o valoare maxima si una minima, iar in final trebuia ca pe nodul initiator sa afli care este valoarea maxima si minima din topologie. 3.1 Cititori - Scriitori 3.2 Terminarea programelor
2 februarie 2015
Algoritmi Paraleli si Distribuiti
2015 · Sesiune · CB
V3 1. Ceasuri logice vectoriale. Necesitatea introducerii ceasurilor logice vectoriale(0.5p). Explicatie + exemplu (0.5p). Ordonarea evenimentelor (0.5p). Multicast (0.5p). 2. Avem 3 procese. Fiecare din cele trei procese au cate o secventa de numere ordonate crescator. Stiind ca exista cel putin un element comun sa se scrie un algoritm care gaseste cel mai mic element comun. Pseudocod (0.7p). Justificare(0.3p) 3. Algoritmul de difuzare pe sisteme SIMD cu memorie partajata de tip EREW. Explicatie model + exemplu (0.4p). Pseudocod (0.6p) V4: 1) Algoritm de tip unda - algoritmul Finn a) descriere algoritm unda b) pseudocod Finn c) corectitudine si complexitate 2) Ai 2 procese a,b, fiecare cu cate un set de intregi. Procesele fac schimb intre ele de cate o pereche de numere pana cand setul lui a are toate elementele mai mici decat elementele setului lui b. Descriere + pseudocod 3) Mecanisme de sincronizare, utilitate, exemple pseudocod, intructiunea "cel mult o data"
28 ianuarie 2015
Algoritmi Paraleli si Distribuiti
2015 · Restanțe · restanta CC
1. Topologie 1.1 Algoritmi de alegere lider. Prezentare(0.2p) 1.2 Algoritm pulsatii + Alg cu mesaje ecou.Prezentare algoritmi + pseudocod (1.4p) 1.3 S-a dat o topologie si a cerut sa aplici ala ecou cu mesaje pe topologie (0.4p) 2. P procese vor accesul la o zona critica. Faceti un alg a.i. procesoul care a asteptat cel mai mult sa intre primu in zona critica. 3.1 Producator - Consumator cu un buffer limitat: - scrieti pseudocodul pt 1 prod si 1 consumator (0.3p) - scrieti peducocod pt mai multi prod si mai multi consumatori (0.3p) Prezentarea problemei si a solutiei (0.4p) 3.2 Probleme barbierului prezentare problema (0.2p) pseudocod (0.5p) sa arati pe alg care el fol excludere mutuala si care sincronizare conditionata (0.3p)
31 august 2015
Algoritmi Paraleli si Distribuiti
2015 · Restanțe · CC
Var A 1. Topologie 1.1 Algoritmi de alegere lider. Prezentare(0.2p) 1.2 Algoritm pulsatii + Alg cu mesaje ecou.Prezentare algoritmi + pseudocod (1.4p) 1.3 S-a dat o topologie si a cerut sa aplici ala ecou cu mesaje pe topologie (0.4p) 2. P procese vor accesul la o zona critica. Faceti un alg a.i. procesoul care a asteptat cel mai mult sa intre primu in zona critica. 3.1 Producator - Consumator cu un buffer limitat: - scrieti pseudocodul pt 1 prod si 1 consumator (0.3p) - scrieti peducocod pt mai multi prod si mai multi consumatori (0.3p) Prezentarea problemei si a solutiei (0.4p) 3.2 Probleme barbierului prezentare problema (0.2p) pseudocod (0.5p) sa arati pe alg care el fol excludere mutuala si care sincronizare conditionata (0.3p)
31 august 2015
Algoritmi Paraleli si Distribuiti
2014 · Sesiune · 331-332 CB
Varianta 2 Subiectul 1. Algoritmul de alegere a liderului Hirchberg-Sinclair (2p) a) Descrierea generala a problemei (0.3p) b) Descrierea algoritmului si a primitivelor sale (0.4p) c) Scrierea algorimtului in pseudocod (0.8p) d) Specificarea complexitatii in numar de mesaje si timp cu justificarea rezultatelor (0.5p) Subiectul 2. Problema (1p) Se da o retea de procese sub forma unui graf. Fiecare proces poate comunica doar cu vecinii sai. Fiecare proces dispune de doua valori: una minima - v1 si una maxima - v2. Se cere sa se scrie un algoritm prin care fiecare proces sa ajunga la final sa cunoasca minimul si maximul celor 2n valori. Subiectul 3. De ales intre: 3.1 Calcul paralel de inmultire a doua matrici a) Ce operatii pot fi realizate in paralel? (0.3p) b) Scrieti pseudocodul pentru calculul paralel de inmultire a doua matrici. (0.7p) 3.2 Complexitatea algoritmilor distribuiti a) Descrieti modelul Foster b) Scrieti formula pentru n procese a timpului c) Explicati care este particularitatea modelului
3 februarie 2014
Algoritmi Paraleli si Distribuiti
2014 · Sesiune · 331 CB
1 generali bizantini cu mesaje semnate pseudocod + teoreme + prezentare problema + schema 3 generali 2 n procesoare dispuse sub forma de inel . ficare contine cate 2 valori diferite(orice 2 valori din multimea de 2n sunt diferite) . sa se scrie alg care gaseste cele mai mari 2 valori . pseudocod + idee . 3.1 de explicat ceva atomicitate si sincronizare 3.2 sa se afle topologia intr-un graf aciclic. pseudocod +idee
1 februarie 2014
Algoritmi Paraleli si Distribuiti
2014 · Sesiune · 334&331 CA
V1 1. Generali bizantini cu mesaje orale. Schema pentru 3 generali. Pseudocod. 2. Algoritmi pentru intrarea intr-o regiune critica. Se emit mesaje de tip request. Se asteapta primirea merajelor de tip reply de la toti vecinii. Idee si pseudocod. 3. 3.1. Sincronizare si excludere mutuala in Java. Cum functioneaza. Exemplu de cod. 3.2. Algoritmi unda pe topologii inel. Complexitate si pseudocod. V2 1. Stabilirea topologiei prin mesaje de sondaj cu ecou - cazul general. De ce sunt potriviti algoritmii unda? Idee. Pseudocod. Complexitate. Ce alte variante mai cunoasteti de stabilire a topologiei? 2. Se considera o topologie de procesoare, fiecare continand un numar. Sa se gaseasca o modalitate prin care fiecare procesor cunoaste maximul din retea. Idee si pseudocod(s-a punctat rezolvarea prin mesaje de sondaj cu ecou, in care se transmit numerele in ecouri, iar initiatorul difuzeaza maximul). 3. 3.1. Complexitatea algoritmilor paraleli. Metrici folosite. Exemplificare pe sortarea pe un vector de procesoare(exemplul din curs). 3.2. Terminarea prin algoritmul Huang. Idee, tipuri de mesaje folosite, pseudocod. V3 1. Algoritm unda - topologie arbore 1.1. Descriere generala, de ce este potrivit algoritmul unda? 1.2. Explicatie algoritm, pseudocod, justificarea corectitudinii, complexitate 1.3. Aplicatie pe un graf dat 2. Se da o matrice de procesoare, fiecare continand un numar. Trebuia scris un algoritm care sa gaseasca regiuni de noduri adiacente ce aveau aceleasi valori, astfel incat la final fiecare nod sa stie din ce regiune face parte. 3. 3.1. Problema producator-consumator cu tampon unitar. Descriere problema, pseudocod, explicatie notatii de sincronizare. 3.2 Modelul Foster V4 1. Producatori consumatori cu buffer limitat. 1.1 Prezentarea problemei (0.3) 1.2 Algoritmul folosind primitivele P, V (de explicat primitivele) + pseudocod (1.2) 1.3 explicat algoritmul (0.5) 2. Avand un graf cu N noduri, fiecare isi cunoaste vecinii, sa se gaseasca arborele minim de acoperire fara a se calcula topologia. La sfarsitul algoritmului fiecare nod stie care din legaturile cu vecinii sai sunt in arborele minim de acoperire. Idee 0.3 + algoritm 0.7 3. 3.1. LeLann Chang Robert a) Prezentarea problemei 0.3p b) pseudocod + explicatii 0.5p c) calcul complexitate 0.2p 3.2.Sume prefix
21 ianuarie 2014
Algoritmi Paraleli si Distribuiti
2013 · Sesiune · CA
332CA,334CA - 4.02.2012 Varianta 1 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. Varianta 2 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 1. Algoritmi de tip unda.Algoritmul arbore 2. O problema care se rezolva cu algoritmul pulsatiilor 3. Producator-consumator cu buffer comun de o unitate (la alegere cu Foster). Varianta 4 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 331CA,333CA - 5.02.2013 Varianta 1 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) Varianta 2 1. Căutare paralelă: Proprietăți dorite ale algoritmilor paraleli, pseudocod si explicat algoritmul de cautare paralela, complexitate, si de ce nu este buna 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 la alegere cu complexitatea algoritmilor distribuiti (foster) Varianta 3 1. Algoritmi unda - algoritmul fazelor.Descrieti problema + justificati folosirea algoritmului unda.Idee algoritm + complexitate + pseudocod.Algoritmul pt clici. 2. 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. 3. La alegere intre algoritmul prefixului (bla bla ce se cere) si algoritmi genetici (ceva cu distr calc paralel de genu.. si metoda replicated workers) Varianta 4 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 intre problema filozofilor si LeLann
9 februarie 2013
Algoritmi Paraleli si Distribuiti
2013 · Sesiune · 331,332,333,334 CA
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
5 februarie 2013
Algoritmi Paraleli si Distribuiti
2013 · Sesiune · 331 CB
(2p)1. Dezvoltarea aplicatiilor pentru SIMD. Cautarea paralela. Ce proprietati de performanta ar trebui sa aiba SIMD? Algoritmul de cautare paralela. De ce nu merge simpla paralelizare a cautarii binare? Complexitate. (1p)2. n procese intr-un graf conex. Fiecare nod isi cunoaste toti vecinii. Sa se dezvolte un program(pseudocod) pentru determinarea gradului minim al nodului grafului care va fi comunicat unuia dintre procese desemnat ca initiator. (2p)3. Producator-Consumator cu tampon limitat si mai multe procese producator, mai multe rpocese consumator, folosind PV
3 februarie 2013
Algoritmi Paraleli si Distribuiti
2012 · Sesiune · 331 CB
1. (2p) Algoritm care rezolva urmatoarea problema (pseudocod sau orice altceva): Se dau n procese, fiecare corespunzator unui nod intr-un graf. Fiecare poate comunica numai cu vecinii sai. Fiecare incearca sa se imperecheze cu un vecin. La terminare fiecare proces poate fi imperecheat sau singur, dar sa nu existe 2 procese vecine singure. 2. (1.5p) Algoritmul arbore de tip unda - descriere, demonstratie ca este algoritm unda, aplicare pe un exemplu dat. 3. (2p) Ceasuri logice si vectori de ceasuri logice - descriere, diferenta dinte cele 2. Un exemplu cu 4 procese care isi trimit niste mesaje - se cer ceasurile si vectorii pentru fiecare eveniment Problema recuperare parcurs: Algoritm pipeline in MPI care verifica daca o functie polinomiala este injectiva pe o multime discreta de valori. Se stiu valorile si coeficientii a0,...,an (pentru f(x) = an*x^n + ... + a1*x + a0)
28 ianuarie 2012
Algoritmi Paraleli si Distribuiti
2012 · Sesiune · 334 CA
Pe un rand a fost : ( APD, 21.01.2012 ) 1) Algoritmi unda - algoritmul arbore. 2) Problema cu o matrice de pixeli si heartbeat. 3) Analiza complexitatii algoritmilor distribuiti - Modelul Foster la alegere cu ceva de atomicitate si Producatori - Consumatori ( partea aia in care foloseste <await S->B> prin curs ) Pe alt numar au fost: - Algoritmi de descoperire a topologiei cu sondaj-ecou. Descriere, implementare, complexitate, alternative. - Se da o retea de procese aranjate in forma de grila n x n, care pot comunica la N, S, E, V. Se cere, sa afle fiecare rank-ul maxim al unui proces. - Alegere intre complexitate (cum apare prin subiectele alea), si algo. Huang. Varianta 4 1. Problema M producatori –N consumatori cu un buffer limitat.Sa se explice P si V, ideea algoritmului, pseudocod. 2. Un graf de N noduri. Sa se afle arborele de acoperire fara a stabili topologia.Fiecare nod stie identitatea vecinilor si stabileste cu acestia ce legaturi sunt in arbore ( Algoritm sondaj-ecou) 3. Algoritmul LeLann-Chang-Robert (idee+pseudocod cu comentarii+complexitate) Sau Prefix in SIMD si MIMD .
21 ianuarie 2012
Algoritmi Paraleli si Distribuiti
2011 · Sesiune · CA/CB
Vezi attach! Subiect preluat de pe http://andrei.clubcisco.ro/
20 septembrie 20111 fișier
Algoritmi Paraleli si Distribuiti
2011 · Sesiune · 331 CB
Subiecte examen APD 22ian seria CB Varianta A (tot de azi) 1. Detectia terminarii in procesele distribuite 1. Enuntarea problemei. Algortimul de terminare pentru o topologie inel. 2. Algortimii Dikstra-Scholten si Huang. Descriere. Pseudocod. 3. Fie algoritmul de detectie terminare, folosind culori si jetoane: (se dadea un pseudocod pentru un proces...). Sa se determine daca algortimul este corect. Daca da, sa se determine si sa se explice conditia de terimnare. Daca nu, sa se justifice de ce si sa se spuna ce imbunatatiri se pot aduce pentru a face algortimul corect. 2. Consideram o topologie dinamica de procese, in care dorim stabilirea topologiei. Nodurile pot “pica” in timpul algoritmului de aflare topologie. Un nod picat face ca toate legaturile sale sa pice, iar un mesaj trimis pe o legatura picata este pierdut fara a se primi avertisment. Sa se determine daca algortimul clasic cu sondaj-ecou da rezultate corecte pentru o astfel de topologie dinamica. Daca da, sa se scrie algoritmul sau partea relevanta din acesta care face ca rezultatele obtinute sa fie corecte si in acest caz. Daca nu, sa se stabileasca un algoritm imbunatatit de aflare a topologiei. 3. 1. Cautarea paralela a) Descrierea problemei b) Algoritm (descriere + pseudocod) c) Complexitate (sau) 2. Algoritmul pulsatiilor a) Varianta pentru un diametru D al retelei; b) Varianta pentru o retea conexa. ---------------------------------------------------------------------- Varianta B 1. problema generalilor bizantini - descrierea problememei - de toata: conditii de consistenta interactiva - solutia cu mesaje scrise: conditii, descriere, pseudocod, teorema care dem corectitudinea - un exemplu practic 2. o problema cu etichetare zonelor, banuiesc ca ai auzit de ea 3. 3.1 sa scrie suma prefix atat ca SIMD cat si ca MIMD 3.2 problema terminarii - descrierea problemei - algoritmul Dijkstra - Scholten - complexitate ------------------------------------------------------------------------------ Varianta C 1. problema generalilor bizantini - descriere, consistenta interactia, solutia cu mesaje orale, un exemplu practic 2. sa explicam daca merge si in cazul in care nu merge, cum am modifica algoritmul de stabilire a topologiei sondaj-ecou pentru un graf care are topologie dinamica (unele noduri pot sa pice si pot sa revina) 3. 3.1 producator consumator cu buffer limitat, cazul simplu si cazul cu mai multi producatori + consumatori (parca asa suna) 3.2 Lelann-Chang-Roberts ------------------------------------------------------------------------- Varianta D 1. stabilire topologie 1.1 prezentare 1.2. ambii algoritmi pseudocod + explicatii 1.3. de executat pe un graf 2. o problema cu etichete dar schimbata cumva urat... 3. algoritmi genetici sau 3. modelul foster (cel pe care e facut algoritmul floyd)
20 septembrie 2011
Algoritmi Paraleli si Distribuiti
2011 · Sesiune · CA/CB/CC
Jan 17 S-a dat pe patru numere(V1, V2, V3, V4), postez aici numarul meu: V3 1. Algoritmi unda: arbore a) Explicatia alegerii algoritmului unda. Descrierea algoritmului. (0.5p) b) Descrierea algoritmului in pseudocod. Justificarea corectitudinii. Complexitate. (1.1p) c) Era un desen langa enunt. Se cerea aplicarea algoritmului pe acel desen (desen identic cu cel din notitele de curs). (0.4p) 2. Etichetarea regiunilor Se da un tablout[1:n,1:n] cu valoarea inte pixelului respectiv. Sa se descrie un algoritm heartbeat care eticheteaza regiunile cu intensitati egale. Descriere = 0.3p Pseudocod = 0.7p 3.1 Modelul work-depth - nu am retinut defalcarea - Trebuia să zici ceva despre modelul respectiv și complexitate și să exemplifici printr-un algoritm de calculare a sumei elementelor unui vector. Ceva de genul. 3.2 Hirschberg-Sinclair: - Descriere 0.3 p - Pseducod 0.4p - Complexitate 0.3p ---------------------------------------------------------------------- Numarul meu,varianta 4: 1.1. Problema producatori-consumatori. Descriere. 1.2. De explicat primitivele P siV cu notatiile de atomicitate si sincronizare. 1.3. Pseudocod cu comentarii 2. De aflat un arbore de acoperire fara a afla mai intai topologia (un fel de sonda-ecou zic eu...) . 3. 1. Complexitate: numar de mesaje. Descriere si aplicatie pe algoritmul pulsatiilor. la alegere cu: 3.2 Problema produs prefix ,implementare SIMD si MIMD si de explicat diferentele intre ele. --------------------------------------------------------------------- Varianta 2: 1. Comunicari sincrone si asincrone prin mesaje a) Prezentarea generala a problemei. Cum se realizeaza partajarea datelor? Cum se realizeaza sincronizarea? (0.5p) b) Constructii pseudocod pt transmitere sincrona si asincrona. Exemple (1p) c) Cum se reprezinta transmiterea sincrona si asincrona a mesajului in MPI. (0.5p) 2. Se dau doua seturi S si T cu valori intregi. La fiecare pas, se interschimba o valoare din S cu una din T. Descrieti (0.3p) si scrieti (0.7p) algoritmul astfel incat, la final, valorile din S sa fie mai mari decat orice valoare din T. 3.1 Algoritmul de detectare a terminarii folosind confirmarile mesajelor - Dijkstra-Scholten. a) Descrierea problemei (0.3p) b) Pseudocod (0.4p) c) Complexitate (0.3p) 3.2 Algoritmul lui Finn. a) Descrierea algoritmului (0.3p) b) Pseudocod (0.4p) c) Complexitate (0.3p) -------------------------------------------------------------------------- Iata si ultima varianta (1) :) 1. Problema generalilor bizantini a) Prezentarea generala a problemei (0.5 p) b) Prezentarea solutiei ce foloseste mesaje orale (aici cerea cam tot : teoreme, pseudocod, demonstratie ca algoritmul functioneaza, etc. 1.2 p) c) De reprezentat grafic problema generalilor pentru 3 generali (unul din locotenenti, la alegere, era neloial) (0.3 p) 2. Se dau n numere si o secventa de n procesoare organizate in linie de asamblare (de fapt se dorea o structura vectoriala). Prezenta functionarea algoritmului: P[0] are toate cele n numere, pastreaza valoarea cea mai mica si trimite mai departe restul numerelor lui P[1]. Procesul se repeta pana cand la procesorul P[n] ajungea ultima variabila (cea mai mica valoarea). Cerinte : 2.1 Prezentarea solutiei (care, paradoxal, era prezenta in enunt :D - mi s-a spus sa fac un desen, sa detaliez putin pe pasi) (0.5 sau 0.3 p) 2.2 Implementarea algoritmului in limbaj pseudocod 3.1 Complexitatea algoritmilor paraleli. a) Metrici b) Exemplificare pe sortarea unui vector, folosind o structura de N procesoare 3.2 Huang Explicarea mesajelor, a modului de functionare, pseudocod (Nu am citit cu mare atentie) ----------------------------------------------------------------------------
20 septembrie 2011
Algoritmi Paraleli si Distribuiti
2011 · Sesiune · CA/CB/CC
Jan 25 Varianta A: 1. Alg prefix -> lista inlantuita cu valorile end[i] setate initial la leg[i] (unde leg[i] e urmatorul din lista dupa i). La sf end[i] trebuia sa contina referinta catre ultimul element. 2. -Pseduocod + Analiza complexitate ptr problema urmatoare din curs (din cursuri de ceasuri logice, a 5-a pagina) : Un proces care doreşte să intre în secţiunea critică trimite mesaje de cerere request tuturor celorlalte procese. Pentru a putea intra efectiv în secţiunea critică, este necesar să primească de la fiecare câte un mesaj de răspuns reply. La recepţia unui mesaj request, un proces poate determina dacă el sau procesul care a facut cererea ar trebui să intre în secţiunea critică. Când el are prioritate, mesajul reply este întârziat; altfel, el este transmis imediat procesului ce a generat cererea. 3. La alegere intre a) modelul Foster. Replicated workers cu exemplificare pe Floyd b) terminarea in inel prezentare + pseudocod + complexitate ----------------------------------------------------------------------- Varianta B: 1. Stabilirea topologiei. Mesaje de sondaj cu ecou. Enuntarea problemei, pseudocod, analiza complexitatii. Mentionati si alte metode de stabilire a topologiei. 2. Avem n*n procese dispuse pe un grid periodic de numere intregi. Fiecare casuta are vecini la nord, sud, est, vest. Pseudocodul algoritmului de aflare a maximului din matrice, astfel incat in final, toate casutele din matrice sa aibe valoarea maxima. Complexitate. 3. La alegere intre: 3.1. Calcul prefix. Pseudocod, analiza complexitatii. 3.2. Algoritmi genetici... something...(nici nu l-am citit pana la capat) --------------------------------------------------------------------
20 septembrie 2011
Algoritmi Paraleli si Distribuiti
2011 · Sesiune · 332/333 CA
Jan 26 2011 333 + 332 CA V6 1. Atomicitate si Sincronizare. De ce sunt importante pentru algoritmi paraleli care folosesc variabile partajate...sau ceva de genul. Cum se scrie in pseudocod si semantica. Exemplu de folosire cu P si V. Cum se evidentiaza in java atomicitatea? Dar sincronizarea? 2. O problema in care se considera un tablou de procese. Fiecare proces are o valoare intreaga si o trimite celorlalte procese. Cand termina de trimis, se termina si procesul. Ultimul proces ramas detine valoarea minima din tabloul initial. (0,3 p) ideea. (0,7) pseudocod 3. 3. 1. Alegerea liderului intr-o topologie inel, in care se trimite doar in sensul acelor de ceasornic si pot fi mai multi initiatori 3. 2 . Stabilirea topologiei cu sondaj. (cred) Nu-mi amintesc exact enunturile, dar in mare cam asa au fost. ----------------------------------------------------------------------- V8 1. Alegerea liderului. De ce sunt potriviti algoritmii unda. Idee,pseudocod. Alte metode de alegere a liderului 2. Se da o matrice de N^2 procese. Fiecare proces detine cate un vector de P elemente. Se cere suma elementelor cu acelasi index de la toate procesele. 3. La alegere intre: - Producator cosumator . varianta cu mai multi producatori si un consumator, mai mult consumatori si un producator. Diferentele dpdv al sincronizarii - Algoritmul de terminare intr-o topologie care admite un ciclu de lungime nc care trece prin toate nodurile. Pseudocod + idee ----------------------------------------------------------------- V7: 1. Ceasuri Logice 1.1 De ce ? 1.2 Cum sunt implementate ? 1.3 Desen cu 3 procese si schimb de mesaje intre ele: de specificat ceasul fiecarui eveniment 1.4 Descrierea algoritmului de excludere mutuala cu semafor distrbuit 1.5 Pseudocodul de la 1.4 2. 3 procese paralele detin fiecare cate o secventa ordonata de numere. Cele trei secvente au cel putin un numar comun. Sa se determine acest element comun minim. 1.1 Ideea 1.2 Pseudocod 3.1. Algoritmul Heartbeat 3.1.1 Idee 3.1.2 Pseudocod 3.2 Cititori Scriitori : idee, pseudocod. Pot aparea situatii in care accesul scriitorilor este blocat de cititori? Explicati. Ideea de baza la 2 era aceea ca procesele isi transmiteau primul element din secventa (elementul minim). se facea maximul intre acestea si fecare proces stergea primele elemente din secventa sa mai mici decat acesta (fiindca nu aveau cum sa se regaseasca in celelalte secvente ale celorlalte procese). Se repeta acest pas pana cand se ajungea ca elementul comun minim sa fie primul element in fiecare secventa. Poate ca exista si alte implementari, dar aceasta solutie a fost punctata la minim 2 persoane. --------------------------------------------------------------------
20 septembrie 2011
Algoritmi Paraleli si Distribuiti
2009 · Sesiune · CA/CB/CC
Vezi attach!
21 septembrie 20112 fișiere
Algoritmi Paraleli si Distribuiti
2008 · Sesiune · CA/CB/CC
Vezi attach! Subiect preluat de pe http://andrei.clubcisco.ro/
20 septembrie 20111 fișier