Problema : Implementarea unui index inversat folosind multithreading folosind map-reduce pentru procesarea unor fisiere si analizarea frecventei cuvintelor gasite. Programul trebuie impartit in 2 parti : mapare si reducere, fiind executate secvential, dar thread-urile fiind pornite in paralel.
Solutie : Citesc pe rand numele fisierelor de procesat si salvez intr-un vector de tupluri urmatoarele date : numele fisierului, dimensiunea sa si numarul de ordine. Apoi calculez in functie de numarul de mapperi, care este workload-ul fiecaruia, adica ce dimensiune are de procesat fiecare mapper. Acest calcul este efectuat static dar este calculat eficient astfel incat fiecare mapper sa proceseze aproximativ acelasi numar de date. In fiecare mapper salvez un vector de perechi nume_fisier-id_fisier, si incep procesarea in paralel. In momentul in care pornesc thread-urile mapper, pornesc si thread-urile reducer. Fiecare mapper va avea la final cate o lista de cuvinte, rezultata in urma analizarii fisierelor sale. Lista este de forma cuvant-id_fisier. La final, o bariera asteapta ca toate thread-urile sa isi termine de executat sarcinile inainte de operatia de reduce. Pentru pentru fiecare dintre thread-urile de reducer, folosesc un vector de pointeri care pointeaza catre toate structurile de mapper, pentru a putea prelucra datele analizate si un pointer catre un vector(de 26 de elemente) de vectori de perechi cuvant-vector. Vectorul are 26 de bucket-uri ce reprezinta de fapt cele 26 de litere ale alfabetului, iar ceilalti vectori de perechi sunt de fapt cuvintele ce incep cu litera respectiva si fisierele in care apar. O alta bariera va astepta ca toate thread-urile sa fi terminat executia inainte de a incepe operatia de reduce. Am impartit in mod (aproximativ) egal workload-ul reducerilor, folosind o formula pentru start si end. Fiecare reducer va prelucra datele din mapperele asignate si le va adauga in vectorul comun de vectori de perechi (map-ul). Se foloseste un mutex de 26 de elemente, fiecare pentru fiecare cifra a alfabetului, deoarece mapa este shared memory si se evita astfel folosirea aceleiasi resurse de catre mai multe thread-uri. Dupa ce mapa a fost construita si terminata, se asteapta ca toti reducerii sa isi termine treaba folosind o alta bariera. Se recalculeaza pozitiile de start si end, fiecare reducer isi va aloca bucket-uri (litere), si va sorta cuvintele in functie de numarul de fisiere in care apar si lexicografic. Daca un cuvant apare de mai multe ori, se sterg duplicatele si se concateneaza listele de fisiere in care apare. In final, folosind aceleasi pozitii de start si de end, fiecare reducer parcurge bucket-urile si pune cuvintele in fisierele corespunzatoare literei sale. Chiar daca bucket-ul e gol (nu sunt cuvinte care incep cu acea litera) fisierul tot va fi creat. La final se dealoca resursele, barierele si mutex-uri.