Implementação do quicksort co o uso de threads em java

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2468 palavras )
  • Download(s) : 0
  • Publicado : 21 de novembro de 2011
Ler documento completo
Amostra do texto
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 acomputaçã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 e exigentes. O custo computacional das aplicaçõestem aumentado cada vez mais, e essas aplicações exigem a resposta em um tempo cada vez menos.

Inicialmente na computação a tecnologia de hardware disponível fornecia apenas um núcleo de processamento, dessa forma a computação era executada de forma seqüencial. Contudo esse modelo já não consegue atender a crescente demanda pelo alto desempenho.

Hoje em dia já temos disponíveis novastecnologias de processamento que permitem que atividades independentes sejam executadas paralelamente desde que o software esteja preparado para tal. O processo de paralelizar atividades independentes do softwares tem apresentado um bom resultado no ganho de performance.

1.1. Programação paralela

A capacidade de hardware tem crescido muito nesses últimos anos, mas somente esses avanços não sãocapazes de sanar a necessidade de computação existente. Buscando aproveitar de forma cada vez mais eficiente o hardware disponível em uma máquina a comunidade cientifica tem investido em pesquisas que criam e melhoram modelos de computação paralela.

Segundo Almasi,1994, a computação paralela é definida como: “uma coleção de elementos de processamento que se comunicam e cooperam entre si e com issoresolvem um problema de maneira mais rápida.”, e segundo Quinn 1987 como: “o processamento de informações que enfatiza a manipulação concorrente dos dados, que pertencem a um ou mais processos que objetivam resolver um único problema.”.

Nesse contexto podemos identificar vantagens na computação paralela como: o alto desempenho para programas lentos, soluções mais naturais para programasintrinsecamente paralelos, maior tolerância a falhas e melhor aproveitamento da modularidade.

Ao passo que podemos citar desvantagens como: maior dificuldade em criar programas, necessidade de balancear as cargas, intensa comunicação entre os processos, dificuldade para sincronizar processos dependentes.

1.2. Algoritmo QuickSort

2. O trabalho desenvolvido

O nosso trabalho foi desenvolver umalgoritmo paralelo para a proposta QuickSort. Todos os testes fora executados em uma máquina que usa um processador Intel I3 M330 com dois núcleos de 2.13GHz, 4GB de memória RAM e sistema operacional Windows 7 de 64 bits. É importante salientar que o processador em questão possui dois núcleos, contudo o mesmo consegue simular quatro núcleos.

O programa foi desenvolvido utilizando a linguagem Javacom o auxilio da IDE NetBeans versão 7.0. A escolha da IDE foi a possibilidade de utilizar um plugin chamado profiler que fornece informações, em tempo de execução, sobre a criação de threads, uso de memória, uso do processador, tempo de execução, memória alocada para a JVM (Java virtual machine) e outros parâmetros que são relevantes para o projeto.

2.1 O código fonte
Para criar as threadsimplementamos a interface Runnable que é definida como:

public interface Runnable {
public abstract void run();

}

A classe QuickSortMultiThread implementa a classe abstrata Runnable. O método run() contém a descrição do comportamento de cada thread, sendo assim é esse método que possui o algoritmo paralelo QuickSort, desde a comparação entre os valores até as chamadas...
tracking img