Arquiteturas de aceleradores em hardware para o problema de posicionamento de grafos em CGRAs, FPGAs e QCAs

Abstract

O posicionamento de grafos é uma etapa fundamental no fluxo de projeto de diversas arquiteturas reconfiguráveis, como Field Programmable Gate Arrays (FPGAs), Coarse-Grained Reconfigurable Architectures (CGRAs) e arquiteturas emergentes baseadas em Quantum-dot Cellular Automata (QCA). Nesses sistemas, o posicionamento consiste em determinar a localização de operações, células lógicas ou elementos computacionais em uma matriz de processamento, de modo a reduzir o custo de comunicação entre os elementos e respeitar as restrições estruturais da arquitetura. Entretanto, trata-se de um problema computacionalmente complexo, classificado como NP-difícil, o que torna inviável a obtenção de soluções ótimas para grafos de grande porte por meio de busca exaustiva. Esta tese investiga a possibilidade de acelerar o processo de posicionamento por meio da implementação dedicada de algoritmos em hardware reconfigurável. Para isso, são estudados três algoritmos de posicionamento presentes na literatura: Simulated Annealing (SA) e os algoritmos baseados em travessia de grafos You Only Traverse Once (YOTO) e You Only Traverse Twice (YOTT). A partir desses algoritmos, propõe-se um modelo de aceleradores baseado em arquiteturas em pipeline, capaz de explorar paralelismo temporal e espacial em dispositivos FPGA para acelerar a busca por soluções de posicionamento. A abordagem proposta foi estruturada em três etapas principais. Na primeira, são investigadas as características do problema de posicionamento em diferentes arquiteturas reconfiguráveis, com destaque para as particularidades estruturais de CGRAs, FPGAs e circuitos baseados em QCA. Nessa etapa, são analisadas as restrições impostas por cada arquitetura e sua influência no processo de posicionamento. Na segunda etapa, são desenvolvidas arquiteturas de aceleradores para os algoritmos SA, YOTO e YOTT utilizando estruturas em pipeline. Essas arquiteturas exploram o paralelismo interno e o uso de múltiplos fluxos de execução para permitir a avaliação simultânea de diferentes soluções candidatas. Na terceira etapa, são realizados experimentos com conjuntos de benchmarks utilizados na literatura, incluindo MCNC, EPFL, MNIST e JSC. Os resultados obtidos permitem avaliar tanto a qualidade das soluções geradas quanto o desempenho das arquiteturas propostas. Os experimentos demonstram que a implementação dos algoritmos em hardware possibilitou uma redução significativa no tempo de execução, mantendo qualidade de solução compatível com aquela obtida por implementações tradicionais em software o que representa uma abordagem promissora para reduzir o tempo de compilação de aplicações voltadas a arquiteturas reconfiguráveis. Como principal contribuição, esta tese apresenta um modelo genérico de aceleradores para algoritmos de posicionamento de grafos baseado em arquiteturas pipeline. Palavras-chave: posicionamento de grafos; FPGA; arquiteturas reconfiguráveis; aceleração em hardware; arquiteturas em pipelineGraph placement is a fundamental step in the design flow of several reconfigurable architectures, such as Field-Programmable Gate Arrays (FPGAs), Coarse-Grained Reconfigurable Architectures (CGRAs), and emerging architectures based on Quantum-dot Cellular Automata (QCA). In these systems, placement consists of determining the location of operations, logic cells, or computational elements in a processing array, in order to reduce the communication cost between elements while respecting the structural constraints of the architecture. However, this is a computationally complex problem, classified as NP-hard, which makes it infeasible to obtain optimal solutions for large graphs through exhaustive search. This thesis investigates the possibility of accelerating the placement process through dedicated implementations of algorithms in reconfigurable hardware. To this end, three placement algorithms found in the literature are studied: Simulated Annealing (SA) and the graph traversal-based algorithms You Only Traverse Once (YOTO) and You Only Traverse Twice (YOTT). Based on these algorithms, this work proposes an accelerator model based on pipeline architectures, capable of exploiting temporal and spatial parallelism in FPGA devices to accelerate the search for placement solutions. The proposed approach was structured into three main stages. In the first stage, the characteristics of the placement problem are investigated in different reconfigurable architectures, with emphasis on the structural particularities of CGRAs, FPGAs, and QCA-based circuits. In this stage, the constraints imposed by each architecture and their influence on the placement process are analyzed. In the second stage, accelerator architectures are developed for the SA, YOTO, and YOTT algorithms using pipeline structures. These architectures exploit internal parallelism and multiple execution flows to allow the simultaneous evaluation of different candidate solutions. In the third stage, experiments are carried out using benchmark sets commonly used in the literature, including MCNC, EPFL, MNIST, and JSC. The results obtained allow the evaluation of both the quality of the generated solutions and the performance of the proposed architectures. The experiments show that implementing the algorithms in hardware enabled a significant reduction in execution time while maintaining solution quality compatible with that obtained by traditional software implementations. This represents a promising approach to reducing the compilation time of applications targeting reconfigurable architectures. As its main contribution, this thesis presents a generic accelerator model for graph placement algorithms based on pipeline architectures. Keywords: graph placement; FPGA; reconfigurable architectures; hardware accelerationp; ipeline architectures