QuickSort Paralelo - OmpSCR

Revisão do algoritmo QuickSort

QuickSort é um método de ordenação atualmente considerado como o mais eficiente e mais rápido dos métodos de ordenação interna. Este método é uma melhoria substancial do método de intercambio direto e recebe o nome de QuickSort pela velocidade com a qual ordena os elementos de um vetor, proposto por Senhor Charles Antony Richard Hoare em 1960.

QuickSort divide o vetor em dois partes que se ordenam recursivamente. Pode-se resumir em três passos:

1. Escolher um elemento como pivô
2. Particionar o vetor em duas partes: uma que contenha os números que são menores que o pivô, e outra parte onde os números são maiores que o pivô.
3. Ordenar cada partição de maneira recursiva. O resultado final é a concatenação ordenada das duas partes com o elemento pivô.
   
   
   
   
   
   A eleição do pivô
   
   
   Pode-se fazer de varias maneiras, entre elas:
   • Eleger o primeiro elemento
   • Escolher aleatoriamente
   • Pegar mediana de três elementos.
   • A mediana entre o primeiro o ultimo e o elemento central.
   Ex: 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 (pivô = 6)
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   Escolhendo a mediana entre o primeiro, o último e o elementro central pode-se evitar o pior dos casos do Quicksort: selecionar o maior ou menor elemento, num conjunto de números que já estão ordenados ou parcialmente ordenados.
   
   
   O algoritmo QuickSort normal se baseia em grande medida na recursividade para repetir a mesma função nos pedaços do vetor que se está ordenando, ele e um bom candidato para o processamento em paralelo. Já que o algoritmo sempre funciona em uma parte independente do vetor, em um contexto paralelo, faz sentido fazer paralelizar algoritmo trabalhando no problema de forma simultânea.
   
   
   Analise de desempenho
   
   
   Executamos o algoritmo do Quicksort paralelizado do pacote OmpSCR_v2.0 em um ambiente multi-core avaliando o desempenho com diferentes números de threads.
   Executando o algoritmo QuickSort paralelo  que em teoria deveria  primeiro ordenação e particiona o vetor dividindo a carga em dois threads chamando a si recursivamente. Mas ao finalizar uma analise exaustiva do algoritmo original, com 10 execuções em seqüencial, 10 execuções para 2, 4, 8 e 16 threads cada uma em paralelo, pode-se observar que porem o tempo de execução em paralelo a não sofre muita variação com o aumento da quantidade e threads designados, esta muito acima do tempo de execução em seqüencial, chegando ate a triplicar o tempo de execução.
   
   
   Não se obtendo grandes variações de tempo no desempenho em paralelo com o aumento de threads como esperado. Orientados pela professora buscamos uma explicação para esse comportamento, se descobriu que todo o trabalho de ordenação era realizado por uma única thread.Uma causa possível desse comportamento pode ser uma falha na configuração da OpenMP. ( estamos investigando )
   Executando o programa c_QuickSort em forma seqüencial o com um vetor de tamanho: 9 Mega (9437184) obtivemos que o tempo de execução que oscila entorno dos 29 segundos, embora a execução em paralelo levasse uma media de 88 segundos no algoritmo com dois threads , para uma máquina quadi-core rodando linux.

   
   

   
   

   
   
   
   

   
   

   
   

   Paralelo com 2 Threads, Vetor 9437184
   	T Alg	T real	T usr	T sys
   1	86,4099	92,2820	90,4200	29,7100
   2	85,1804	90,937	90,9000	28,9100
   3	85,2180	90,9460	90,5300	29,6500
   4	85,7442	91,4230	89,1200	31,0400
   5	84,4476	90,0460	90,5800	28,6500
   6	85,1745	90,8070	88,7000	30,9000
   7	86,0238	91,8580	90,6500	30,1700
   8	84,3184	89,8810	89,5500	29,1500
   9	85,2126	91,1870	90,1700	29,8300
   10	87,8829	93,7730	92,7600	29,7600

   
   
   
   

   

   
   
   
   
   
   
   
   

   Paralelo com 4 Threads, Vetor 9437184
   	T Alg	T real	T usr	T sys
   1	84,8592	90,4720	95,6200	29,7000
   2	86,0559	94,372	95,0200	30,4400
   3	85,9893	91,6900	95,6700	30,1600
   4	86,2956	92,1440	95,6800	30,3000
   5	86,1209	91,8980	94,4500	31,6400
   6	81,6040	87,0360	95,6700	30,1600
   7	82,4650	86,1400	94,4500	30,4400
   8	82,5470	88,0670	95,6200	29,7000
   9	82,4150	87,9370	95,6700	30,1600
   10	81,8810	87,3250	94,4500	30,1600

   
   
   
   

   

   
   
   
   
   
   
   
   

   Paralelo com 8 Threads, Vetor 9437184
   	T Alg	T real	T usr	T sys
   1	87,0657	93,2460	113,4100	30,6200
   2	91,5567	97,598	117,7800	31,1900
   3	85,0793	91,0400	109,1300	30,3000
   4	84,2768	90,3100	108,3900	29,4400
   5	86,1226	91,9500	109,8200	31,1500
   6	86,0948	92,1300	110,1600	30,5200
   7	84,9022	90,7690	108,4800	30,1400
   8	85,2885	91,5100	110,2000	30,4300
   9	85,0735	90,8880	109,5600	29,6700
   10	84,2429	89,9920	108,2200	29,5900

   
   
   

   

   
   
   
   
   
   
   
   
   

   Paralelo com 16 Threads, Vetor 9437184
   	T Alg	T real	T usr	T sys
   1	86,8395	92,5850	87,1400	31,0000
   2	85,0989	90,868	87,2100	29,5700
   3	85,7491	91,3770	87,0200	31,0900
   4	84,8824	90,4630	85,9700	30,1500
   5	83,4984	89,0570	85,8900	29,3300
   6	85,0611	90,6600	86,4200	30,8000
   7	82,9493	88,4760	84,8900	28,9700
   8	82,8813	88,3730	84,1700	29,7100
   9	83,6409	89,2530	85,6600	29,1400
   10	83,9403	89,6080	86,6400	28,8900

   
   
   

   

   
   
   
   
   
   
   
   

   Sequencial, Vetor 9437184
   	T Alg	T real	T usr	T sys
   1	30,206	32,1930
   2	30,712	32,476
   3	30,9450	32,6270
   4	29,6980	31,3230
   5	29,2330	30,8340
   6	29,8320	31,4650
   7	29,3640	30,9710
   8	29,2740	30,8770
   9	29,3240	30,9290
   10	29,3540	30,9700

   
   

   
   
   
   
   

   

   
   
   
   
   
   
   Na tentativa de melhorar o tempo de desempenho se propôs modificações no código original, para realizar uma melhor distribuição do trabalho em vários threads e assim conseguir um melhor desempenho do programa e, portanto um melhor tempo de execução.

   
   

   Porem nos testes do programa com o algoritmo alterado, o resultado não foi o esperado, porque o tempo de execução aumentou em 33% com relação ao tempo de execução em paralelo no algoritmo original. Mas ainda não desistimos!!!

 
Volte em breve, faltou algumas imagens e comentários

Lizzi Villalba
Sandro Oliveria