An MLIR-Based Compilation Framework for Control Flow Management on Coarse Grained Reconfigurable Arrays

Resumo Técnico: Um Framework de Compilação Baseado em MLIR para Gerenciamento de Fluxo de Controle em Arrays Reconfiguráveis de Grão Grosso

Declaração do Problema
Os Arrays Reconfiguráveis de Grão Grosso (CGRAs) oferecem alta flexibilidade e eficiência para acelerar cargas de trabalho intensivas, mas enfrentam uma barreira significativa para a adoção generalizada: a complexidade da compilação. Os compiladores atuais de estado da arte (SoA) são limitados em escopo, lidando principalmente com Grafos de Fluxo de Dados (DFGs) para loops únicos, enquanto fornecem pouco ou nenhum suporte para Grafos de Fluxo de Controle (CFGs). Consequentemente, eles frequentemente delegam o gerenciamento do fluxo de controle ao processador host ou dependem de unidades de hardware ad-hoc para lidar com divergências de fluxo de controle. Essa abordagem incorre em um overhead de tempo de execução substancial devido às frequentes trocas de dados entre o CGRA e o host, bem como custos de reconfiguração de instrução e dados ao alternar entre blocos básicos. Além disso, as abordagens baseadas em Contador de Programa (PC) existentes, que evitam a reconfiguração, muitas vezes falham em explorar o paralelismo ao nível de loop porque não conseguem sobrepor a execução de blocos básicos.

Metodologia
Os autores propõem um framework de compilação modular de ponta a ponta construído sobre a infraestrutura Multi-Level Intermediate Representation (MLIR). O framework visa CGRAs homogêneos baseados em PC, onde um contador de programa global controla a execução de todos os Elementos de Processamento (PEs), permitindo a execução multiplexada no tempo (multi-contexto) sem reconfiguração em tempo de execução.

A metodologia procede através de várias etapas principais:

1. Frontend MLIR e Dialeto: O framework utiliza um dialeto cgra customizado dentro do MLIR para representar Grafos de Fluxo de Dados de Controle (CDFGs) no nível de Representação Intermediária (IR). Isso separa limpa e elegantemente as otimizações independentes de hardware das transformações específicas de hardware.
2. Transformações do Middle-End:
   • Otimizações Independentes de Arquitetura: O framework emprega técnicas de simplificação de CFG, incluindo a fusão horizontal e vertical de blocos básicos e a fusão de cabeçalho-corpo de loop. Essas transformações reduzem o overhead de controle e aumentam o escopo para paralelismo ao nível de instrução.
   • Compatibilidade de Hardware: Operações de memória são convertidas para se alinharem com endereços físicos, e instruções ilegais são reescritas para corresponder à Arquitetura de Conjunto de Instruções (ISA) do CGRA alvo.
   • Adaptação de Escalonamento Modular (Modulo Scheduling): Para permitir o paralelismo ao nível de loop dentro do modelo baseado em PC (que tipicamente requer blocos básicos não sobrepostos), o framework realiza a adaptação de CFG. Ele remodela o IR para criar novos kernels de loop onde o comprimento do loop ($L'$) é igual ao Intervalo de Iniciação ($II$), permitindo que múltiplas iterações sejam encapsuladas dentro de uma única estrutura de bloco básico.
3. Mapeamento de CDFG via ILP e Análise de Liveness:
   • Decomposição: O CDFG é decomposto em DFGs individuais para cada bloco básico. As dependências entre blocos são gerenciadas usando análise de liveness global para rastrear valores propagados entre blocos.
   • Formulação de ILP: Um modelo de Programação Linear Inteira (ILP) customizado mapeia o DFG de cada bloco básico na malha (mesh) do CGRA. O modelo minimiza o tempo de execução enquanto satisfaz restrições de acessibilidade, dominância, liveness e consistência de memória.
   • Tratamento de Falhas: Se o modelo ILP falhar devido a limitações de roteamento ou estouro de registradores, o framework emprega um mecanismo de reparo pós-mapeamento. Isso envolve a inserção de operações de movimentação ou pares load-store para desalojar valores para a memória. Crucialmente, este processo de reparo é projetado para evitar o reescalonamento de blocos básicos previamente resolvidos, mantendo assim a eficiência da compilação.
4. Back-End: A etapa final envolve alocação de registradores (usando coloração de grafos) e a geração de código assembly binário para o hardware alvo.

Principais Contribuições

• Framework End-to-End: Um framework de compilação modular que suporta fluxos de controle arbitrários em CGRAs homogêneos baseados em PC, eliminando o overhead de reconfiguração durante a troca de blocos básicos.
• Dialeto MLIR Customizado: O design de um dialeto cgra que representa CDFGs diretamente no nível de IR, facilitando otimizações independentes de hardware e uma separação limpa de preocupações.
• Mapeamento ILP Baseado em Liveness: Uma metodologia de mapeamento inovadora que utiliza análise de liveness para formular um modelo ILP para o mapeamento de blocos básicos. Introduz um mecanismo de reparo que resolve a inviabilidade sem reescalonamento, reduzindo significativamente a complexidade do mapeamento.
• Transformações de CFG para Escalonamento Modular: Técnicas para adaptar CFGs (ex: fusão de blocos básicos) para permitir o escalonamento modular dentro de um modelo de controle baseado em PC, thereby explorando o paralelismo ao nível de loop sem reconfiguração.
• Avaliação de Desempenho: Comparação abrangente contra métodos de SoA, demonstrando acelerações através de otimizações puras de compilação.

Resultos
O framework foi avaliado em um template de CGRA OpenEdge de 250MHz, 65nm com vários tamanhos de malha (3x3 e 4x4). Os benchmarks incluíram convolução, álgebra linear (PolyBench) e processamento de sinais (MiBench).

• Aceleração de Tempo de Execução (Runtime Speedup): O framework proposto alcançou um aumento médio de velocidade de 2.12× sobre o EffiMap (um mapeador de DFG baseado em PC), 1.48× sobre o SAT-MapIt (mapeamento de DFG + suporte de CPU) e 1.20× sobre o Marionette (mapeamento de CDFG com hardware reconfigurável).
• Impacto da Otimização: A combinação de simplificação de CFG e escalonamento modular gerou ganhos significativos. Por exemplo, o escalonamento modular alcançou comprimentos de loop ($L$) aproximadamente duas vezes o intervalo de iniciação ($II$), levando a aumentos médios de velocidade de 197% em 3x3 e 223% em 4x4 CGRAs.
• Escopo de Compilação: O framework mapeou com sucesso kernels inteiros, incluindo aqueles com ramos divergentes e loops aninhados, que são frequentemente impossíveis de serem alvo por estratégias de apenas DFG.

Significância e Alegações
O artigo alega que a principal limitação da adoção atual de CGRAs é a falta de suporte de compilação para fluxos de controle complexos. Ao deslocar o gerenciamento do fluxo de controle inteiramente para o nível do compilador usando um modelo baseado em PC, os autores demonstram que é possível:

1. Eliminar o Overhead de Reconfiguração: Evitar as penalidades de reconfiguração de instrução e dados associadas à troca de blocos básicos em abordagens de hardware reconfigurável.
2. Habilitar o Paralelismo ao Nível de Loop: Superar as limitações de execução sequencial dos modelos tradicionais baseados em PC ao remodelar o CFG para suportar o escalonamento modular.
3. Alcançar Independência de Hardware: Visar um amplo conjunto de aplicações sem a necessidade de unidades de hardware dedicadas para gerenciamento de fluxo de controle ou propagação de dados.

Os autores concluem que sua abordagem oferece um caminho robusto para automatizar o deployment de kernels de computação complexos em CGRAs, alcançando alto desempenho através de otimização de software em vez de complexidade de hardware.