Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by samara castro (sammy_roberta7@hotmail.com) on 2009-11-04T15:46:48Z
No. of bitstreams: 1
2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2009-11-15T19:38:34Z (GMT) No. of bitstreams: 1
2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5) / Made available in DSpace on 2009-11-15T19:38:34Z (GMT). No. of bitstreams: 1
2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5)
Previous issue date: 2006 / Sistemas distribuídos têm sido cada vez mais utilizados na resolução de problemas
que demandam grande quantidade de tempo de processamento, por permitirem
a utilização simultânea de vários recursos computacionais. Diversas máquinas
com arquiteturas distribuídas foram propostas ao longo dos anos. Entre essas
arquiteturas, estão os clusters de computadores, que são sistemas distribuídos
formados por estações de trabalho interligadas e que podem atingir um bom
desempenho a um custo relativamente baixo.
Entretanto, para que a utilização de tais sistemas seja proveitosa, é necessário
que a utilização dos recursos disponíveis seja feita de maneira a permitir a otimização
de algum critério. A alocação de tarefas em um sistema distribuído visa
determinar como serão utilizados os processadores do sistema de modo a otimizar
um critério, que grande parte das vezes é o tempo de execução de uma aplicação.
Diversas abordagens já foram propostas para o problema de alocação de tarefas,
que é um problema NP-Completo, incluindo algoritmos heurísticos e estratégias
específicas para determinadas aplicações.
Uma aplicação para qual existem diversas implementações em sistemas distribuídos
é a comparação de seqüências biológicas, uma operação básica da biologia
computacional que visa determinar o grau de similaridade entre seqüências. Os
algoritmos ótimos existentes possuem complexidade de tempo e espaço de O(n2),
sendo baseados na técnica de programação dinâmica e apresentando dependências
de dados do tipo wavefront. O alto custo desses algoritmos justifica a utilização
de sistemas distribuídos na resolução do problema, sendo que a maioria das implementações
distribuídas busca utilizar todos os processadores disponíveis no
sistema distribuído, de modo a minimizar a tempo de execução.
A presente dissertação propõe um framework de alocação de tarefas de aplicações
de comparação de seqüências biológicas baseadas em programação dinâmica,
além de quatro estratégias de alocação de tarefas. O framework e as estratégias
de alocação foram implementados em um cluster de 10 máquinas. Os resultados
mostram que, para seqüências relativamente pequenas, a utilização de todos
os processadores disponíveis não é a opção mais vantajosa. Por isso mesmo, a
utilização de políticas de alocação que levem em consideração o tamanho das
seqüências e as características das máquinas disponíveis pode permitir a redução
no tempo de execução da aplicação. ____________________________________________________________________________________________ ABSTRACT / Distributed systems have been widely used in the resolution of problems that
demand a large amount of processing time, because they allow the simultaneous
utilization of many computational resources. Many machines with a distributed
architecture have been proposed during the years. Among these are computer
clusters, which are distributed systems composed of interconnected workstations
and that may achieve a good performance at a relatively low cost.
However, in order to take advantage of distributed systems, the available resources
must be used in such a way that some criteria can be optimized. Task
allocation in distributed systems aims at determine how the processors available
in the system are going to be used, so that a criteria, which in many cases is the
execution time of an application, is optimized. Many approaches have been proposed
to the task allocation problem, which is NP-Complete, including heuristic
algorithms and application specific strategies.
There are many proposed distributed implementations of the biological sequence
comparison application, which is a basic operation in computational biology
that determines the similarity degree between sequences. The optimal algorithms
available have time and space complexities in O(n2) , are based in the
dynamic programming technique and present data dependencies that follow the
wavefront pattern. The high costs of these algorithms justifies the utilization of
distributed systems. Most of the known distributed implementations try to use all
available processors in the system, so that the execution time can be minimized.
The present document proposes a framework for task allocation for biological
sequence comparison applications based on dynamic programming, as well
as four task allocation strategies. The framework and the strategies have been
implemented in a 10 machine cluster. The results show that, when the sequences
are relatively small, using all available processors is not the best decision. For
this reason, the utilization of task allocation policies that take into account the
sequences size and the machines characteristics may cause the execution time of
the application to be reduced.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/2175 |
| Date | January 2006 |
| Creators | Santana, Marcelo Nardelli Pinto |
| Contributors | Melo, Alba Cristina Magalhães Alves de |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0028 seconds