Programação paralela e distribuida - divisão e conquista

Avaliação da disciplina de Programação Paralela e Distribuída
Divisão e Conquista
Introdução
A segunda avaliação desta disciplina consistiu na implementação de um algoritmo paralelo para ordenação dos valores pseudoaleatórios contidos em um vetor com 600000 elementos, para tanto foi utilizado à técnica de divisão e conquista com uso da linguagem de programação C e o padrão para comunicação interprocessos da biblioteca de programação paralela MPI. O ambiente de execução é caracterizado por máquinas com processador Core i7 3,40 Ghz com 8gb RAM e sistema operacional Fedora 2.3 de 32bits.
O Algoritmo
Esta técnica consiste em sub-dividir um problema em atividades a serem executadas concorrentemente pelos processadores, sob uma estrutura de árvore, até atingir uma granularidade mínima, mantendo a forma do problema original. O processamento foi dividido de acordo com o número de processos exigidos conforme o delta dos níveis estipulados e a cada processo foi tentado atribuir um núcleo físico de um processador .Podemos exemplificar a ideia do algoritmo implementado da seguinte forma: cada núcleo recebe seu conjunto de dados a ser trabalhado uma única vez, verifica se irá dividir ou conquistar aqueles dados através de uma comparação com o valor atual do delta, se for dividir chama uma função que divide o vetor em duas partes homogêneas, se possível, e as envia para seus 2 processos filhos, aguarda o retorno destes, e após o recebimento de cada vetor ordenado independentemente aplica uma função de merge formando um novo vetor ordenado, se este for o processo zero, chama uma função que verifica a ordenação e finaliza o algoritmo, senão envia para seu processo pai. Os processos cujo tamanho do subvetor é menor ou igual ao delta, conquistam seus dados ordenando-os através do método Bubble Sort e posteriormente enviam esses dados aos seus respectivos processos pai. O nodo 0, corresponde ao processo onde foi iniciada a execução do programa paralelo, divide o conjunto de