Emparelhamento Paralelo

Código do geração de emparelhamento máximo em paralelo para Solaris.

Este é o código final que gerei para a minha dissertação de mestrado. Ela gera o Emparelhamento Máximo de grafos usando mais de um processador ao mesmo tempo. No período em que escrevi estes códigos fontes, o equipamento que usava possuía era uma Sparc 1000 com 8 processadores rodando o sistema operacional Solaris. No entanto, o código permite que se utilizem quantos processadores quantos forem necessários.

O algoritmo seqüencial de Micali-Vazirani era o possui a menor curva assintótica entre todos os algoritmos seqüenciais: O(Sqrt(n)m). O principal objetivo do trabalho era verificar se era possível desenvolver um algoritmo encontrasse o emparelhamento máximo que fosse mais rápido do que o algoritmo de Micali-Vazirani. O algoritmo que implementei consegue ser mais rápido em praticamente todos os tipos de grafos gerados. A descrição completa do processo pode ser encontrada na minha dissertação final.

Junto do código fonte dos arquivos eu incluí o arquivo fonte para teste de execução em paralelo. Este teste é feito multiplicando matrizes de forma paralela. Ele realiza os devidos controles das áreas de exclusão mútua para garantir que os resultados sejam devidamente calculados.