CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A utilizaÃÃo de vetores de bits à prÃtica corrente na representaÃÃo
de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits.
Nesta dissertaÃÃo, examinamos implementaÃÃes para
representaÃÃo de conjuntos por endereÃamento direto.
A estrutura bÃsica nessas implementaÃÃes à o vetor de bits.
No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas
variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de
vetores de bits, enquanto a segunda emprega uma tabela de
dispersÃo.
As operaÃÃes associadas Ãs estruturas implementadas sÃo a
inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou
interseÃÃo de dois conjuntos. Especial atenÃÃo à dada ao uso
de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das
diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma
implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo
especificadas e o paralelismo em bits à explorado. A diferenÃa entre
as implementaÃÃes està apenas na estrutura utilizada. Uma comparaÃÃo
experimental à realizada entre as diferentes estruturas utilizando
algoritmos enumerativos para
o problema de conjunto independente mÃximo.
Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos
enumerativos para o problema de conjunto independente mÃximo,
ambas explorando o potencial de paralelismo em bits na
representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices.
A primeira delas à um algoritmo do tipo {em branch-and-boound}
proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas à mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo
de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas. / The use of bit vectors is a usual practice for represent sets by
direct addressing with the aim of reduce memory consumed and improve
efficiency of applications with the use of bit parallel techniques.
In this text, we study implementations for represent sets by
direct addressed. The basic structure in this implementations is
the bit vector. Besides that basic implementation, we implement two
variations also. The first one is a stratification of the bit vector, while
the second uses a hash table.
The operations linked to the implemented structure are include and
remove an element and the union and intersection of two sets. Especial
attention is given to the use of bit parallel in this condition. The
implementation of the different structures in this work use an
base interface and a base abstract class, where the operations
are defined and the bit parallel is used. An experimental comparative
between this structures is carry out using enumerative algorithms for
the maximum stable set problem.
Two approaches are used in the implementation of the enumerative
algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations
with subsets of vertices. The first one is a known branch-and-bound algorithm
and the second uses the Russian dolls method. In both cases, the use of
bit parallel improve efficiency when the lower bounds are calculated
based in a clique cover of the vertices. The results of computational experiments are presented as
comparison between the two algorithms and as an assessment of the structures
implemented. These results show that the algorithm based on the method
Russian Dolls is more efficient regarding runtime and the memory consumed.
Furthermore, the experimental results also show that the use
stratification and hash tables also allow
more efficiency in the case of sparse graphs.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7510 |
| Date | 13 September 2013 |
| Creators | Marcio Costa Santos |
| Contributors | Ricardo Cordeiro CorrÃa, Manoel Bezerra Campelo Neto, Philippe Yves Paul Michelon, Carlos Diego Rodrigues |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0093 seconds