Estudos em Concorrência e Paralelismo na linguagem C e desenvolvimento de algoritmos de alta eficiência.

• Concorrência e Paralelismo, by Fabio Akita pt 1
• Concorrência e Paralelismo, by Fabio Akita pt 2
• Documentação <pthread.h>
• Utilização <pthread.h>
• Mutex Synchronization
• Livro "Algoritmos - Teoria e Prática"
• Mutex
• doc
• doc

A estrutura 'thread_data' é definida nesse código para armazenar os dados que serão passados como argumento para a função linear_search, que será executada por cada thread criada no programa.

Essa estrutura é utilizada para armazenar as seguintes informações:

• thread_id: identificador da thread;
• start_index: índice inicial do trecho do vetor que a thread irá pesquisar;
• end_index: índice final do trecho do vetor que a thread irá pesquisar.
• resut: índice que retorna o index do valor encontrado.
• mutex: índice que se comunica com as demais threads para interromper a busca caso o valor seja encontrado.

Tempo de contrução do array de inteiros de tamanho "1410065408" em média de 27 a 31 segundos, já subtraidos no tempo de processamento.

O valor a ser encontrado está localizado na última posição do array, valor "1981202369", com finalidade de simular o pior cenário do algoritmo.

Complexidade linear, ou sejá, O(N).

Dados de uso de threads em buscas lineares:

Vale a pena ressaltar que são apenas tempos medios, e a criação excessiva de threads pode ter um impacto negativo no desempenho do sistema como um todo, pois cada thread usa recursos do sistema, como memória e CPU. No meu caso (Ryzen 7 2700 e 16gb de ram com Ubuntu 22.04).

https://curc.readthedocs.io/en/latest/programming/OpenMP-C.html

g++ parallel_search.cpp -o parallel -fopenmp

g++ count_sort_parallel.cpp -o count_sort_parallel -fopenmp

O Counting Sort não é naturalmente paralelizável, pois a ordenação é baseada na contagem de ocorrências dos elementos. No entanto, podemos explorar técnicas de paralelização para melhorar o desempenho em algumas etapas do algoritmo.

Uma abordagem para paralelizar o Counting Sort é dividir o array em partes e realizar a contagem paralelamente para cada parte. No entanto, a etapa de combinar os resultados parciais em uma contagem global e atualizar o array original ainda precisa ser feita sequencialmente, o que limita o ganho de desempenho.