Implementação do algoritmo QuickSort multithreading em Java

Anderson Abner de Carvalho1, Luciano Brasil Cardoso1, Mário Paulo Alves Hennrichs1

1Departamento de Ciência da Computação – Universidade Federal de Lavras (UFLA) – Lavras – MG – Brasil

{acarvalho,lucianobc,mphennrichs}@comp.ufla.br

Resumo. A programação paralela busca acelerar a resolução de problemas dividindo a computação, permitindo que os recursos disponíveis sejam utilizados ao máximo. Esse trabalho apresenta uma comparação entre soluções seqüenciais e paralelas para um mesmo problema, a ordenação de vetores utilizando o algoritmo QuickSort.

1. Introdução

A evolução no processo de desenvolvimento de software permite gerar sistemas cada vez mais complexos …exibir mais conteúdo…

O método Executors.newFixedThreadPool(numberOfThreads) é responsável por garantir que não sejam criadas mais threads do que as definidas pelo usuário. Essa não foi a melhor abordagem encontrada, contudo para fins didáticos é interessante analisar como a variação na quantidade de threads utilizadas influência a performance do programa.

2.2 Problemas encontrados

Inicialmente os vetores de teste possuíam poucas posições, isso foi feito para verificar se o algoritmo estava ordenando corretamente os dados de entrada. Quando os testes utilizando vetores com muitas posições (mais de 10.000 posições) o programa sempre era interrompido por um estouro de pilha. Isso acontece quando a quantidade de memória alocada para a JVM é menor do que o necessário para a execução do programa. Esse problema foi resolvido aumentando a memória dedicada a JVM.

Posteriormente quando já executávamos os testes percebeu-se que os valores estavam muito diferentes do esperado. Foi então que se percebeu que o programa seqüencial estava demorando muito para executar a ordenação em relação ao paralelo. O que podemos identificar é que durante o desenvolvimento do algoritmo seqüencial foram utilizados muitos laços desnecessários, isso fez com que a complexidade do algoritmo aumentasse muito prejudicando a sua performance.

Começamos a desenvolver uma interface gráfica para ambos os programas, porém a geração e monitoração da