Extension of ACETONE C code generator for multi-core architectures

Este artigo propõe a extensão do gerador de código C ACETONE, originalmente limitado a sequências, para arquiteturas multicore, definindo formalmente o problema de alocação de processadores e planejando a implementação de heurísticas de agendamento, mecanismos de sincronização e avaliação de tempo de execução no pior caso.

O essencial

Imagine que você tem uma equipe de chefs muito talentosos trabalhando em uma cozinha de alta pressão (um sistema de aviação seguro). O objetivo é preparar um prato complexo (uma Rede Neural) que precisa ser feito com perfeição absoluta e dentro de um tempo exato, pois se demorar, o avião pode ter problemas.

Até agora, o sistema ACETONE era como um "super chef solitário". Ele pegava a receita, escrevia as instruções passo a passo para que um único cozinheiro fizesse tudo, do início ao fim. Isso era seguro e previsível, mas se a receita fosse grande, o cozinheiro demoraria muito, e o avião poderia ficar esperando.

Este artigo apresenta uma evolução: transformar essa cozinha de um único chef em uma equipe de vários chefs trabalhando juntos (multi-core), mas mantendo a segurança e a precisão necessárias para voar.

Aqui está a explicação do trabalho, usando analogias do dia a dia:

1. O Problema: Um Chef Só vs. Uma Equipe

No mundo dos aviões, usar Inteligência Artificial é difícil porque os sistemas precisam ser certificados (aprovação oficial de segurança). O sistema antigo (ACETONE) gerava código para um único processador.

• A Analogia: Imagine tentar carregar 100 caixas pesadas sozinho. Você consegue, mas demora. Se você tiver 4 amigos (4 núcleos de processador), você poderia carregar tudo em um quarto do tempo.
• O Desafio: Coordenar 4 pessoas é mais difícil do que fazer sozinho. Se um amigo entregar uma caixa para o outro no meio do caminho, eles precisam combinar quando e como fazer isso, senão as caixas caem ou o tempo de espera aumenta.

2. A Solução: O "Maestro" de Agendamento (DAG)

Os autores transformaram a rede neural em um mapa de tarefas chamado DAG (Grafo Acíclico Direcionado).

• A Analogia: Pense em uma linha de montagem de carros. O motor não pode ser instalado antes da estrutura do carro estar pronta. O DAG é o mapa que diz: "O Passo A deve terminar antes do Passo B começar".
• O Truque: O sistema agora divide esse mapa entre os vários "chefs" (núcleos). O objetivo é que nenhum chef fique parado esperando o outro, e que todos terminem o trabalho o mais rápido possível.

3. Como eles decidem quem faz o quê? (Scheduling)

Para organizar essa equipe, eles usaram duas abordagens principais, como se fossem dois tipos de gerentes:

• O Gerente Rápido (Heurística ISH): Ele olha para a lista de tarefas e diz: "Quem está livre? Vamos colocar a próxima tarefa nele!". É rápido de decidir, mas às vezes deixa um chef esperando um pouco mais do que o necessário.
• O Gerente Perfeccionista (Heurística DSH): Ele pensa mais a fundo. Se um chef vai ficar esperando uma peça chegar de outro, ele pergunta: "E se o chef que está fazendo a peça anterior copiar a tarefa para cá também?". Isso evita o tempo de espera, mas exige mais tempo de planejamento (cálculo).
• O Matemático (Programação Linear - ILP): É como tentar calcular a solução perfeita usando uma calculadora superpotente. É a melhor solução possível, mas pode demorar horas para calcular. Os autores criaram uma versão "mais leve" dessa calculadora para que ela não trave o sistema.

4. A Comunicação: O Sistema de "Bandeirinhas"

Como os chefs (núcleos) não podem falar entre si diretamente, eles usam uma memória compartilhada (uma prateleira central).

• A Analogia: Imagine que cada par de chefs tem uma bandeirinha vermelha e uma verde na prateleira.
  • O Chef 1 termina sua tarefa, coloca o resultado na prateleira e levanta a bandeira verde.
  • O Chef 2 olha para a bandeira. Se estiver vermelha, ele espera. Assim que vê a verde, ele pega o resultado e levanta a bandeira vermelha para avisar que já pegou.
• Isso garante que ninguém use dados que ainda não estão prontos ou que sejam sobrescritos por outro.

5. O Resultado na Prática

Eles testaram isso em um computador real (um chip com 4 núcleos) usando uma rede neural famosa (GoogLeNet).

• O Ganho: A versão paralela ficou 8% mais rápida no total.
• A Surpresa: Parece pouco? É porque a parte mais pesada da receita (as camadas iniciais) ainda tinha que ser feita por um único chef. Mas, na parte onde eles conseguiam dividir o trabalho, a velocidade aumentou em 31%.
• Segurança: O tempo máximo que o sistema poderia levar (WCET) foi calculado com precisão, garantindo que o avião nunca fique esperando indefinidamente.

Conclusão

Este trabalho é como transformar uma cozinha de um único chef em uma equipe coordenada e segura. Eles criaram um "maestro" que divide o trabalho, um sistema de "bandeirinhas" para garantir que ninguém se atrapalhe, e provaram que isso funciona rápido e com segurança em hardware real.

O objetivo final é permitir que aviões usem inteligência artificial mais complexa e rápida, sem violar as regras de segurança rigorosas da aviação. No futuro, eles querem adaptar isso para chips com núcleos diferentes (alguns mais fortes que outros) e até aceleradores dedicados.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Extension of ACETONE C code generator for multi-core architectures", apresentado em português:

Título: Extensão do Gerador de Código C ACETONE para Arquiteturas Multi-core

1. Problema e Contexto

A integração de Redes Neurais Profundas (DNNs) em sistemas aeronáuticos de segurança crítica enfrenta desafios significativos relacionados à previsibilidade e à certificação. O framework existente ACETONE gera código C sequencial e certificável para sistemas mono-core, garantindo que os valores numéricos e o Tempo de Execução no Pior Caso (WCET) sejam previsíveis.

No entanto, o setor aeronáutico está migrando de arquiteturas de núcleo único para multi-core, mas ainda não está pronto para incorporar aceleradores dedicados (como GPUs ou TPUs). O uso de múltiplos núcleos de CPU sem aceleradores exige a paralelização do código de inferência. O problema central abordado neste trabalho é como estender o ACETONE para gerar código C paralelo e previsível em arquiteturas multi-core, mantendo as garantias de segurança e certificação, sem introduzir complexidades de sincronização que comprometam a previsibilidade temporal.

2. Metodologia

A abordagem proposta divide-se em três pilares principais: modelagem, otimização de agendamento e implementação de código.

• Modelagem do Problema:

  • A inferência da DNN é modelada como um Problema de Agendamento de DAG (Grafo Acíclico Direcionado).
  • Cada camada da rede neural é um nó no grafo, com um tempo de execução (WCET) associado.
  • As arestas representam dependências de dados e latências de comunicação entre núcleos.
  • O objetivo é encontrar um agendamento válido que minimize o makespan (tempo total de execução), permitindo a duplicação de tarefas (cálculos redundantes) para evitar latências de comunicação, se benéfico.

• Otimização e Agendamento (Scheduling):

  • Abordagem Exata (ILP): Os autores propõem uma codificação aprimorada de Programação por Restrições (Constraint Programming) baseada em Programação Linear Inteira (ILP). Eles simplificaram a formulação anterior (Tang et al.), reduzindo o número de variáveis de decisão e eliminando tensores 4D complexos, o que permite resolver problemas de agendamento para redes maiores em tempo viável.
  • Heurísticas: Para casos onde a solução exata é computacionalmente proibitiva, são avaliadas duas heurísticas de agendamento:
    1. ISH (Insertion Scheduling Heuristic): Atribui tarefas ao núcleo que minimiza o tempo de início, preenchendo intervalos ociosos.
    2. DSH (Duplication Scheduling Heuristic): Tenta duplicar tarefas predecessores em núcleos específicos para eliminar atrasos de comunicação, buscando soluções mais próximas do ótimo, embora com maior custo computacional.

• Implementação no ACETONE:

  • O gerador de código foi estendido para produzir múltiplas funções de inferência (uma por núcleo).
  • Mecanismos de Sincronização: Em um ambiente "bare-metal" (sem sistema operacional), a comunicação entre núcleos é gerenciada via memória compartilhada (UMA) usando flags binárias e buffers.
  • São inseridos operadores de "Escrita" (Writing) e "Leitura" (Reading) no código gerado. O operador de escrita espera por uma flag, escreve os dados e atualiza a flag; o leitor espera pela atualização da flag antes de ler. Isso garante a ordem de execução e a integridade dos dados.

3. Contribuições Principais

1. Formalização do Agendamento Offline: Definição formal do problema de agendamento paralelo de DNNs em sistemas embarcados como um problema de DAG com restrições de duplicação e comunicação.
2. Otimização de Algoritmos: Desenvolvimento de uma codificação ILP mais eficiente e a avaliação comparativa de heurísticas (ISH e DSH) para escalabilidade.
3. Extensão do Framework ACETONE: Integração prática da geração de código paralelo, incluindo a inserção automática de mecanismos de sincronização específicos para a plataforma alvo.
4. Validação Experimental: Avaliação rigorosa através de análise estática de WCET (usando a ferramenta OTAWA) e medições experimentais em hardware real.

4. Resultados

• Desempenho do Agendamento:

  • A codificação ILP otimizada consegue encontrar soluções para grafos de até 50 nós, superando as limitações de abordagens anteriores que falhavam antes do tempo limite (timeout).
  • A heurística DSH oferece speedups (aceleração) ligeiramente superiores ou iguais à ISH, mas com um tempo de computação significativamente maior (até 100 vezes mais lento em alguns casos). A ISH mostrou-se mais estável e rápida para a geração de agendamentos.
  • O speedup atinge um platô quando o número de núcleos excede o grau de paralelismo máximo da rede (número de ramificações independentes).

• Validação em Hardware (GoogLeNet em 4 núcleos):

  • O código foi executado em um SoC Texas Instruments Keystone II (4 núcleos ARM Cortex-A15).
  • Ganho Global: Foi alcançado um ganho de 8% no tempo total de execução (redução de $2.90 \times 10^{10}$para$2.68 \times 10^{10}$ ciclos).
  • Ganho em Seções Paralelizáveis: A parte do modelo que pode ser paralelizada (das camadas maxpool_2 até inception_2/concat) apresentou um ganho de 46% na análise teórica e 31% na medição real.
  • Interferência: Observou-se que camadas sequenciais pesadas (como conv_1 e conv_2) limitam o ganho global, e a interferência de memória em núcleos múltiplos pode aumentar o tempo de execução de camadas de entrada.

5. Significado e Conclusão

Este trabalho demonstra a viabilidade de executar inferência de DNNs em arquiteturas multi-core de uso geral (sem aceleradores dedicados) dentro de sistemas críticos de aviação.

• Certificabilidade: A abordagem mantém a previsibilidade necessária para certificação, gerando código C determinístico com WCET estimável.
• Eficiência: Permite o uso de modelos maiores ou com restrições de tempo mais apertadas, explorando o paralelismo disponível em hardware moderno.
• Limitações e Futuro: O trabalho atual assume núcleos homogêneos e memória unificada. Trabalhos futuros visam estender a teoria para núcleos heterogêneos e aceleradores, além de explorar métodos de paralelização mais finos (dentro de camadas individuais).

Em resumo, a extensão do ACETONE oferece uma solução prática para a transição da indústria aeronáutica de sistemas mono-core para multi-core, equilibrando desempenho, previsibilidade temporal e requisitos de segurança.