Arquitetura e Organização de Computadores - Atividade Discursiva

Resumo

Este trabalho apresenta um novo algoritmo para paginação de árvores binárias de pesquisa que frequentemente ocorrem em biologia compoutacional. O algoritmo visa reduzir o número de páginas visitadas em pesquisas e aumentar a taxa de preenchimento das páginas utilizadas. O algoritmo constrói a paginação ótima quando possível e, utilizando empacotamento unidimensional, apresenta uma política eficiente para o preenchimento das páginas de árvores binárias desbalanceadas. A complexidade computacional do algoritmo é apresentada. O algoritmo foi implementado e resultados experimentais, comparativos com outras estratégias de paginação são apresentados. A comparação mostrou que a abordagem proposta é a única que apresenta, simultaneamente,  a quantidade média  de páginas acessadas em pesquisas e a taxa de preenchimento das páginas próximas do ótimo.

1. Introdução

As árvores binárias são estruturas de dados que permitem a realização de busca ou pesquisa de forma eficiente l1J. Uma árvore binária pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores.

Muitas aplicações em biologia computacional envolvem o processamento de strings utilizando árvores binárias não balanceadas l2J. Tais árvores são originadas de seqüências biológicas que não podem ser balanceadas, por isso, árvores B não podem ser aplicadas l3J. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso remoto em redes de computadores, por intermédio de pacotes que possuem tamanho máximo pré-fixado.

Os algoritmos para tratamento da paginação de estruturas de dados são utilizados em diversos sistemas de informação. Com isso, os critérios para alocação dos dados nas páginas são essenciais para a eficiência destes sistemas. Neste trabalho apresenta-se um algoritmo para realizar a paginação de árvores binárias baseado em empacotamento unidimensional l4J. O algoritmo visa reduzir o número de páginas visitadas em buscas e, ao mesmo tempo, aumentar a taxa de preenchimento das páginas utilizadas.

O algoritmo proposto atinge o ideal de paginação quando a árvore binária é completa e o número de nodos é múltiplo do tamanho da página, conforme ilustrado na figura 1. Além disso, estabelece uma política eficiente de preenchimento de páginas, para a hipótese das árvores degeneradas.

[pic 1]

Figura 1: A alocação ideal de páginas.

---

O algoritmo inicia pela raiz da árvore a ser paginada alocando, sempre que possível, subárvores em páginas. Pode ser considerado guloso no sentido que procura armazenar em uma mesma página subárvores que a preencham completamente.

Quando sobram subárvores que não preenchem completamente uma página, ditas constituintes da franja da árvore, o algoritmo aloca essas subárvores em páginas utilizando empacotamento unidimen- sional. Desta forma, cada página é preenchida visando à otimização dos acessos durante uma pesquisa na árvore binária. O empacotamento unidimensional consiste em alocar um conjunto de subárvores num conjunto de páginas, conhecendo o espaço disponível nas páginas, de modo a minimizar o número de páginas utilizadas.

Uma estrutura de dados alternativa para organização de dados em memória secundária é a árvore B. Mostramos por intermédio de resultados experimentais que a estratégia proposta é equivalente às árvores B em termos do número de páginas acessadas em pesquisas. Por outro lado, a abordagem proposta produz uma taxa de preenchimento de páginas 30% superior às árvores B. Dessa forma, a quantidade de espaço necessário para armazenar e o número de bytes necessário para transferir uma árvore de um local remoto é 30% superior quando utilizamos nossa abordagem em comparação às árvores B.

O presente trabalho está dividido em seis seções, incluindo esta introdução. A seção 2 contém as definições preliminares. Na seção 3 é descrita a funcionalidade do algoritmo, bem como sua especificação formal e análise de complexidade. Na seção 4 são descritas as métricas utilizadas para mensurar o desempenho do algoritmo e apresentados resultados experimentais obtidos com a versão implementada do algoritmo. Na seção 5 são apresentados trabalhos relacionados. A seção 6 conclui o trabalho.

1. Definições Preliminares

As árvores binárias podem ser definidas recursivamente da seguinte maneira l1J:

1. A árvore binária T0 de zero nodos é uma árvore binária.
2. Uma árvore binária Tn de n >= 1 nodos é ordenada em uma tripla (Tesq, R, Tdir), onde R é o nodo simples dito raiz de Tn. Tesq e Tdir são as árvores binárias de esq e dir nodos, respectivamente ditas subárvores esquerda e direita da raiz (esq >= 0, dir >= 0 e esq + dir = n − 1).

Quando não é possível ou desejável manter todo o conjunto de nodos de uma árvore binária de pesquisa na memória principal, os nodos devem ser agrupados em páginas. Cada página é composta de células, cada nodo da árvore é armazenado em uma célula. Como o tempo necessário para acessar ou visitar uma página é predominantemente o tempo de transferência da página, o desempenho do algoritmo de manipulação da árvore é estritamente relacionado ao número de páginas transferidas.

Considere uma árvore binária com n elementos; uma página é definida como a unidade de armazena- mento de nodos da árvore, podendo conter um máximo de p nodos. Os nodos da árvore são transferidos em páginas da memória secundária para a memória primária, ou entre duas máquinas ligadas em rede. Na pesquisa, os nodos são examinados da raiz até uma folha. O número de páginas visitadas que devem ser utilizadas para completar uma pesquisa deve ser o menor possível.