Particionamento e escalonamento de matrizes densas para processamento em hardware reconfigurável

Abstract

A solução de problemas complexos em várias áreas do conhecimento humano, tais como: análise de investimento no setor bancário, análise e visualização de imagens médicas em tempo real, indústria de óleo e gás, etc. que utilizam muitas vezes algoritmos complexos e/ou uma grande massa de dados, têm requerido cada vez mais sistemas computacionais de alto desempenho para seu processamento. Estes aplicativos, em sua maioria, devido a sua grande massa de dados, grandes laços de processamento em seus procedimentos, podem consumir dias ou até meses de trabalho, em computadores de processamento seqüencial, para apresentar o resultado final. Existem casos em que este tempo excessivo pode inviabilizar um projeto em questão, por perder o time to market de um produto. Diferentes tecnologias e estruturas de dados têm sido sugeridas para lidar com tais problemas, visando uma melhor customização, tentando retirar o melhor da arquitetura e do sistema, seja em termos de software como de hardware. Dentre estas arquiteturas hw/sw, optamos neste trabalho ao estudo de uma solução baseada em FPGAs (Field Programmable Gate Arrays) como um co-processador. O uso deste dispositivo permite uma nova abordagem do problema. Agora, um determinado aplicativo poderia ser particionado em duas partes: a primeira, aquela com características de controle, processo seqüencial, continuaria sendo executado no host com processadores genéricos, enquanto que a parte com os grandes laços de processamento seriam processados, com maior desempenho por explorar o paralelismo, nos co-processadores com FPGAs. Porém, a movimentação dos dados entre a memória principal do host e a memória externa do FPGA é considerada um grande gargalo para o processamento em hardware. Vários autores em seus trabalhos demonstram o desempenho alcançado com o uso de processamento em hardware, mas consideram que os dados já estão na memória externa do FPGA. Poucos comentam sobre a perda de desempenho quando se considera a movimentação de dados. Neste trabalho foram estudadas técnicas de particionamento de grandes matrizes densas, reuso de dados e as estratégias que melhor se adéquam para algumas arquiteturas estudadas neste trabalho. As latências desta movimentação de dados entre o host e o co-processador em FPGA foram o foco deste trabalho também. Concluímos com um estudo de caso onde propomos uma estratégia para particionamento e multiplicação de matrizes por blocos no FPGA virtex 5 (XC5VLX50T -1 FF1136), montado em uma placa (ML 555 Board) da Xilinx