Um Estudo sobre a Paralelização do algoritmo MergeSort In-place

Resumo

Grande parte dos problemas resolvidos computacionalmente requerem a ordenação de elementos como parte de sua solução. Embora existam vários algoritmos de ordenação com implementações e graus de complexidade diferenciados, este é um problema que ainda não pode ser considerado resolvido. Geralmente um algoritmo é eficiente apenas para situações específicas, por exemplo, para ordenar entradas de dados pequenas ou quando há disponível uma grande quantidade de memória. Investiga-se nesse trabalho, o desempenho de algoritmos Mergesort, os quais ordenam elementos numa abordagem divisão e conquista. Nela, inicialmente divide-se o conjunto dados até atingir subconjuntos que possam ser ordenados facilmente, após faz-se a concatenação (merge) dos subconjuntos ordenadas para compor o resultado final. Outro aspecto importante na ordenação é a quantidade de memória necessária para realizar a ordenação. Para garantir menor alocação de memória extra em vetores auxiliares no processo de ordenação utilizamos a técnica In-place. No Mergesort In-place o vetor inicial possui suas metades pré-ordenadas, o In-place apenas fará com que a ordenação dos elementos ocorra no mesmo vetor. Para melhorar o desempenho, este trabalho investiga o uso da paralelização buscando tirar proveito das arquiteturas multiprocessadas. Já foram implementadas duas abordagens: delegação total e delegação parcial. Em ambas, a paralelização é realizada por threads na linguagem de programação Java. Na delegação total a thread principal cria duas threads filhas para as quais delega todo o seu trabalho, ou seja, cada thread filha recebe metade do trabalho total e a thread principal permanece ociosa. Esta divisão se repete recursivamente até estabelecer o número de regiões paralelas. Na delegação parcial, apenas uma nova thread é criada sendo que a thread principal computa metade do trabalho. Assim, nenhuma thread permanecerá ociosa. No cenário de testes utilizamos vetores de tipo inteiro de tamanhos: 100 mil, 1 milhão e 10 milhões. A execução dos testes ocorreu em um computador com 4 gigabytes de memória RAM, processador Intel CoreTM i7 com 4 núcleos físicos e sistema operacional Windows 7 ultimate 64 bits. Para os vetores com 100 mil elementos utilizando 64 threads paralelas, a delegação parcial obteve cerca de 50% de desempenho a mais que a delegação total. Para vetores de 100 mil e 10 milhões de elementos a delegação parcial mostrou melhor desempenho sobre a total, no melhor caso de nível 4 da árvore (8 threads paralelas) o ganho foi de 5%, já na execução de um vetor de 10 milhões que ocorre também em nível 4 (15 threads paralelas) obteve-se ganho de 17% da delegação parcial sob a delegação total. O próximo passo do estudo será a execução do framework de testes em uma arquitetura mais robusta recentemente adquirida pelo grupo de pesquisa, a qual possibilitará utilizar vetores maiores que os já testados. Adicionalmente serão buscados métodos para medir o consumo de memória em tempo de execução.