RESUMO

Tal como referido anteriormente, na realização de tarefas de grande complexidade, a utilização de co-processadores com características mais adequadas tem como objectivo reduzir o tempo da sua realização. No entanto, perante tarefas que implicam grandes quantidades de dados, a largura de banda do canal de transferência pode ser um factor limitativo da taxa de realização das tarefas. Para não comprometer a utilidade do co-processamento, a comunicação pode tornar-se mais rápida através da compressão dos dados, num modelo como o ilustrado na seguinte figura.

Modelo de co-processamento baseado em compressão e descompressão de dados genéricos

Depois de os dados comprimidos se encontrarem no co-processador, existe a possibilidade de operar directamente sobre eles ou de os descomprimir previamente. No presente trabalho, foram realizadas as duas abordagens de forma a as poder comparar.

Primeira Abordagem

A primeira abordagem consistiu na implementação de um modelo, no qual o computador anfitrião começa por comprimir os dados, utilizando um algoritmo de compressão genérico, e enviá-los pela porta paralela ou interface ethernet. Seguidamente, o co-processador efectua a descompressão, opera sobre os dados originais e responde, devolvendo os resultados (de muito menor dimensão) pelo mesmo canal de transmissão.

Procurou-se um algoritmo eficiente (com factores de compressão elevados), simples (para ser rápido) e implementável em hardware de recursos limitados. Assim, foi adoptada a versão adaptativa do algoritmo de Huffman, à qual se integrou:

·        Mecanismo de remoção da redundância em repetições consecutivas;

·        Mecanismo limitador do tamanho da codificação dos símbolos.

Baseando-se em operações sobre dados organizados em árvore, o algoritmo de compressão/descompressão de Huffman levou a implementações de cariz recursivo. Se, por um lado, as linguagens de programação de software permitem utilizar esta técnica trivialmente, nenhuma linguagem de especificação de hardware inclui suporte à recursividade. Para dar resposta a este problema, foi implementado o modelo RHFSM – Recursive Hieraquichal Finite State Machine [V. Sklyarov, 2004]. Este modelo baseia-se na concepção das partes recursivas do algoritmo na forma de máquinas de estados finitos. Para permitir alguma abstracção no que diz respeito à gestão das variáveis de suporte às transições entre estados e módulos, foi criada uma biblioteca simples e reutilizável, denominada RHFSM.

Com o suporte à recursividade em hardware, tornou-se possível implementar o parser para a interpretação da árvore de codificação Huffman que precede os dados comprimidos.

Abordagem Alternativa

Numa segunda abordagem, assente num compromisso relativamente ao tipo de dados a transmitir para o co-processador, a forma de acelerar a transferência consistiu em utilizar um formato comprimido específico e que não implicasse descompressão.

O formato escolhido destinava-se a dados que representam matrizes SAT3, ou seja, matrizes ternárias, tais como as matrizes SAT, com valores '0', '1' e dontcare, mas com um número máximo por linha de valores não dontcare igual a 3. Estas matrizes podem ser obtidas através de uma conversão de ordem de complexidade polinomial a partir de matrizes SAT comuns – tarefa atribuída ao computador anfitrião.

Foi implementado um sistema SAT3-Solver na FPGA do co-processador, que obtém o vector solução (caso exista), acedendo directamente aos dados comprimidos. Porque o formato utilizado permite níveis de compressão muito elevados e por se ter utilizado a interface ethernet, obtiveram-se tempos globais de co-processamento significativamente reduzidos.