Arquitetura e Organização de Computadores - Atividade Discursiva

...

- A árvore binária T0 de zero nodos é uma árvore binária.

- 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.

O algoritmo para paginação de árvores binárias proposto neste trabalho é dividido em duas fases. Na primeira fase são alocadas subárvores que preenchem completamente uma página. As subárvores remanescentes são ditas constituintes da franja da árvore. Na segunda fase é necessário que as subárvores da franja sejam alocadas utilizando empacotamento unidimensional.

O problema do empacotamento unidimensional pode ser definido como: dados uma constante C e uma lista finita de itens L = p1, p2, ... , pn, onde cada item p, está associado a um valor w(pi) satisfazendo 0 (pi) , deseja-se encontrar o menor inteiro m tal que L possa ser particionada em m listas L1, L2, ... ,Lm onde cada lista Li, satisfaz[pic 2]

Li = pj ∈Li w(pj) ≤ C com i=l..m.

Num típico problema de empacotamento unidimensional deseja-se particionar uma lista de itens em sublistas de maneira a minimizar o número de partições respeitando a capacidade de cada sublista.

Neste trabalho é proposto um algoritmo para alocar um conjunto de subárvores (sem restrição de precedência) em um conjunto de páginas, conhecendo o espaço disponível nas páginas, de modo a mini- mizar o número de páginas utilizadas. As subárvores, com tamanhos s1, s2 ,..., sn devem ser alocadas em páginas de tamanho C. Um algoritmo de empacotamento unidimensional encontra a alocação que minimiza o número de páginas de tamanho C.

Por exemplo, na figura 2 a subárvore s1 formada pelos nodos 3, 5, 7 e 12; a subárvore s2 formada pelos nodos 36, 38 e 41; a subárvore s3 formada pelos nodos 46, 49, 53 e 57; a subárvore s4 formada

---------------------------------------------------------------

[pic 3]

Figura 2: Exemplo de aplicação de empacotamento unidimensional.

[pic 4]

Figura 3: Paginação utilizando empacotamento unidimensional.

pelo nodo 73; a subárvore s5 formada pelos nodos 83, 85 e 87 e a subárvore s6 formada pelos nodos 93, 95, 97 e 98 devem ser alocadas no menor número possível de páginas. Observa-se que estamos diante de subárvores com tamanhos 4, 3, 4, 1, 3 e 4, respectivamente, e que devem ser alocadas em páginas de tamanho 7.

Uma solução ótima, que é obtida pelo algoritmo, produz uma alta taxa de preenchimento das páginas, alocando as subárvores s1 e s2 na página 1, as subárvores s3 e s5 na página 2 e as subárvores s4 e s6 na página 3, conforme se observa na figura 3.

O problema de empacotamento unidimensional encontra-se entre os problemas clássicos de Otimização Combinatória, sendo considerado N P -difícil no sentido forte. Entre as possíveis alternativas para a implementação do empacotamento unidimensional destaca-se a utilização de algoritmos aproximados ou heurísticos, ou seja, onde não existe a garantia de se encontrar a solução ótima, porém o tempo de execução é polinomial. Com isso, busca-se resolver o problema baseado em regras empíricas, cuja aplicação costuma ser dependente do tipo de problema. Diversos algoritmos aproximados são propostos na literatura l4J. Na implementação realizada neste trabalho utilizou-se um algoritmo guloso para solucionar o empacotamento das subárvores existentes na franja.

-

O Algoritmo Proposto

Esta seção apresenta o algoritmo proposto para paginação de árvores binárias de pesquisa. O algoritmo é aplicável quando o conjunto de informações a ser tratado é estático, as freqüências de acesso não são conhecidas e o armazenamento é remoto ou secundário.

---------------------------------------------------------------

- Funcionalidade do Algoritmo

O algoritmo proposto neste trabalho é um paginador de árvores binárias que visa aumentar o grau de parentesco dos nodos que serão armazenados numa mesma página. O algoritmo 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. Além disso, estabelece uma política eficiente de preenchimento de páginas, para a hipótese das árvores degeneradas.

Antes de descrever o algoritmo é necessário definir a noção de nodo patriarca. Um patriarca é um nodo raiz de uma subárvore que deverá ser alocado em uma página específica, bem como seus descendentes, tantos quantos couberem na página.

Considere que uma página armazena até x níveis ou gerações com relação a um nodo de uma árvore binária, onde x é um número natural. O algoritmo inicia pela raiz da árvore a ser paginada, considerando esta raiz o patriarca da primeira página. Em seguida, são armazenadas x 1 gerações do patriarca nesta página. Todos os nodos da geração seguinte não podem ser armazenados aí, pois não há espaço disponível. Estes nodos serão, cada um, o patriarca de uma nova página. Em cada uma destas páginas são alocadas x 1 gerações do patriarca, e assim sucessivamente, até que todos os nodos tenham sido armazenados adequadamente.[pic 5][pic 6]

Quando