Placement and routing graph transversal-based algorithms for coarse-grained reconfigurable architectures (CGRA)

A desaceleração da lei de Moore e o fim da escalabilidade de Dennard, criou no- vos desafios para prover desempenho, flexibilidade e eficiência energética na área de arquitetura de computadores. Processadores de propósito geral (CPUs), unidades de processamento gráfico (GPUs) e processadores de sinais digitais (DSPs) oferecem flexibilidade, mas possuem baixa eficiência energética. Circuitos integrados de apli- cação específicas (ASICs) possuem uma alta eficiência energética, mas uma baixa fle- xibilidade. Arranjos de portas programáveis (FPGAs) tem eficiência e flexibilidade, entretanto requerem a necessidade de conhecimento especializado em hardware e em linguagens de descrição e o tempo de compilação leva de minutos a horas. Por outro lado, arquiteturas reconfiguráveis de grão grosso (CGRAs) apresentam flexibilidade próxima a um FPGA e sua eficiência energética é próxima a um ASIC. Entretanto, ainda faltam ferramentas para a popularização dos CGRAs, dentre elas podemos ci- tar os algoritmos de posicionamento e roteamento (P&R). Esta dissertação apresenta dois algoritmos de P&R baseados em travessia de grafos para CGRA. O primeiro algo- ritmo introduz um novo percurso em Zigzag que explora a correlação entre as saídas, uma implementação em GPU e uma exploração sistemática do espaço de soluções. Os resultados mostraram uma aceleração de até 502x sem perda de qualidade em comparação ao estado da arte. O segundo algoritmo propõe uma nova abordagem de travessia capaz de explorar as reconvergências presentes nos grafos. Os resultados mostraram que a solução reduziu o comprimento dos fios em 7%, o tamanho máximo das filas em 2 vezes e melhorou o tempo de execução em até 4 vezes comparado com o primeiro algoritmo. Palavras-chave: Arquiteturas Reconfiguráveis. CGRAs. Posicionamento. Roteamento.The slowdown in Moore’s law and the end of Dennard’s scalability has created new challenges in providing performance, flexibility, and energy efficiency in the area of computer architecture. General-purpose processors (CPUs), graphics processing units (GPUs), and digital signal processors (DSPs) offer flexibility but are low in energy ef- ficiency. Application-specific integrated circuits (ASICs) have high energy efficiency but low flexibility. Field-programmable gate array (FPGAs) are flexible and energy efficient, but they require specialized knowledge in hardware and description lan- guage, not to mention that the compilation time takes from minutes to hours. On the other hand, reconfigurable coarse-grained architectures (CGRAs) have flexibility close to that of a FPGA, and their energy efficiency is comparable to that of an ASIC. However, tools for popularizing CGRAs are still lacking. Among them, we can men- tion the placement and routing algorithms (P&R). This dissertation presents two P&R algorithms based on graph crossing for CGRA. The first algorithm introduces a new path in Zigzag that explores the correlation between outputs, a GPU implementation, and a systematic exploration of the solution space. The results showed an acceleration of up to 502x without loss of quality than the state of the art. The second algorithm proposes a new crossing approach capable of exploring the reconvergences present in the graphs. The results shows that the solution reduced the wire length by 7%, the maximum queue size by 2x, and improved the execution time by up to 4 times compared to the first algorithm. Keywords: Reconfigurable architecture. CGRAs. Placement. Routing