Speculation For Simulation. Innovation In Verification

Republicado por Platão

seguidores: 0

Esta é uma ideia interessante, usando o paralelismo especulativo suportado por hardware para acelerar a simulação, com uma reviravolta que requer hardware personalizado. Paul Cunningham (VP/GM Sênior, Verificação na Cadence), Raúl Camposano (Silicon Catalyst, empresário, ex-CTO da Synopsys e agora CTO da Silvaco) e eu continuamos nossa série sobre ideias de pesquisa. Como sempre, comentários são bem-vindos.

Especulação para Simulação

A Inovação

A escolha deste mês é Chronos: paralelismo especulativo eficiente para aceleradores. Os autores apresentaram o artigo na Conferência de 2020 sobre suporte arquitetônico para linguagens de programação e sistemas operacionais e são do MIT.

Explorar o paralelismo usando processadores multicore é uma opção para aplicativos em que o paralelismo é evidente. Outros algoritmos podem não ser tão facilmente particionados, mas podem se beneficiar da execução especulativa explorando o paralelismo intrínseco. Normalmente, a execução especulativa depende da coerência do cache, uma sobrecarga alta especialmente para simulação. Esse método ignora a necessidade de coerência, localizando fisicamente a execução da tarefa para calcular blocos por objeto de leitura/gravação de destino, garantindo que a detecção de conflitos possa ser detectada localmente, sem a necessidade de gerenciamento de coerência global. As tarefas podem ser executadas especulativamente em paralelo; qualquer conflito detectado pode ser desenrolado de uma tarefa por meio de suas tarefas filhas e, em seguida, reexecutado sem a necessidade de interromper outros encadeamentos.

Um outro ponto de nota aqui. Este método suporta simulação baseada em atraso, ao contrário da maioria das técnicas de aceleração de hardware.

Visão de Paul

Uau, que papel maravilhoso de alta octanagem do MIT! Quando questionado sobre computação paralela, penso imediatamente em threads, mutexes e coerência de memória. É claro que é assim que as modernas CPUs multi-core são projetadas. Mas não é a única maneira de oferecer suporte à paralelização em hardware.

Este artigo propõe uma arquitetura alternativa para paralelização chamada Chronos que é baseada em uma fila ordenada de tarefas. No tempo de execução, as tarefas são executadas na ordem do carimbo de data/hora e cada tarefa pode criar novas subtarefas que são adicionadas dinamicamente à fila. A execução começa colocando algumas tarefas iniciais na fila e termina quando não há mais tarefas na fila.

As tarefas na fila são distribuídas para vários elementos de processamento (PEs) em paralelo - o que significa que o Chronos está executando especulativamente tarefas futuras antes que a tarefa atual seja concluída. Se a tarefa atual invalidar quaisquer tarefas futuras executadas especulativamente, as ações dessas tarefas futuras serão “desfeitas” e colocadas novamente na fila. Implementar esse conceito corretamente em hardware não é fácil, mas para o usuário externo é lindo: você apenas codifica seu algoritmo como se a fila de tarefas estivesse sendo executada serialmente em um único PE. Não há necessidade de codificar mutexes ou se preocupar com impasses.

Os autores implementam o Chronos no SystemVerilog e o compilam para um FPGA. Grande parte do documento é dedicado a explicar como eles implementaram a fila de tarefas e qualquer desdobramento necessário no hardware para máxima eficiência. Chronos é comparado em quatro algoritmos adequados para uma arquitetura baseada em fila de tarefas. Cada algoritmo é implementado de duas maneiras: primeiro usando um PE específico de algoritmo dedicado e, em segundo lugar, usando uma CPU RISC-V incorporada de 32 bits de código aberto pronta para uso como o PE. O desempenho do Chronos é então comparado com as implementações de software multi-threaded dos algoritmos rodando em um servidor Intel Xeon com um preço similar ao FPGA sendo usado para o Chronos. Os resultados são impressionantes – Chronos escala de 3x a 15x melhor do que usar o servidor Xeon. No entanto, comparar a Tabela 3 com a Figura 14 me deixa um pouco preocupado com o fato de que a maioria desses ganhos veio dos PEs específicos do algoritmo, e não da própria arquitetura do Chronos.

Dado que este é um blog de verificação, naturalmente ampliei o benchmark de simulação em nível de portão. A indústria EDA investiu pesadamente para tentar paralelizar a simulação lógica e provou ser difícil ver grandes ganhos além de alguns casos de uso específicos. Isso se deve principalmente ao desempenho da maioria das simulações do mundo real sendo dominado por instruções de carregamento/armazenamento ausentes no cache L3 e enviadas para a DRAM. Há apenas um caso de teste comparado neste artigo e é um pequeno somador de salvamento de transporte de 32 bits. Se você estiver lendo este blog e estiver interessado em fazer um benchmarking mais completo, por favor me avise - se o Chronos puder realmente escalar bem em simulações do mundo real, ele teria um enorme valor comercial!

Visão de Raúl

A principal contribuição deste artigo é a Modelo de execução de Tarefas Ordenadas Espacialmente Localizadas (SLOT) que é eficiente para aceleradores de hardware que exploram paralelismo e especulação e para aplicativos que geram tarefas dinamicamente em tempo de execução. O suporte ao paralelismo dinâmico é inevitável para simulação e a sincronização especulativa é uma opção atraente, mas a sobrecarga de coerência é muito alta.

O SLOT evita a necessidade de coerência, restringindo cada tarefa para operar (gravar) em um único objeto e suporta tarefas ordenadas para permitir a atomicidade de vários objetos. Os aplicativos SLOT são tarefas ordenadas e criadas dinamicamente, caracterizadas por um registro de data e hora e um ID de objeto. Timestamps especificam restrições de ordem; ids de objeto especificam as dependências de dados, ou seja, tarefas são dependentes de dados se e somente se tiverem o mesmo id de objeto. (se houver uma dependência de leitura, a tarefa pode ser executada especulativamente). A detecção de conflitos torna-se local (sem estruturas de rastreamento complexas) mapeando IDs de objeto para núcleos ou blocos e enviando cada tarefa para onde seu ID de objeto é mapeado.

A Chronos O sistema foi implementado na estrutura FPGA da AWS como um sistema com 16 blocos, cada um com 4 elementos de processamento (PE) específicos do aplicativo, rodando a 125MHz. Este sistema é comparado com uma linha de base que consiste em um Intel Xeon E20-40v2.4 de 5 núcleos/2676 threads de 3 GHz, escolhido especificamente porque seu preço é comparável ao do FPGA (aproximadamente US$ 2/hora). Executando uma única tarefa em um PE, o Chronos é 2.45 vezes mais rápido que a linha de base. À medida que o número de tarefas simultâneas aumenta, a implementação do Chronos aumenta para uma aceleração auto-relativa de 44.9x em 8 blocos, correspondendo a uma aceleração de 15.3x em relação à implementação da CPU. Eles também compararam uma implementação baseada em RISC-V de uso geral em vez de PEs específicos de aplicativos; Os PEs foram 5x mais rápidos que o RISC-V.

Achei o paper impressionante porque abrange desde o conceito até a definição do modelo de execução do SLOT até a implementação do hardware e a comparação detalhada com uma CPU Xeon tradicional para 4 aplicações. O esforço é substancial, Chronos tem mais de 20,000 linhas de SystemVerilog. O resultado é uma aceleração média de 5.4x (dos 4 aplicativos) em relação às versões paralelas de software, devido a mais paralelismo e maior uso de execução especulativa. Também vale a pena ler o documento para aplicação em tarefas de não simulação; o artigo inclui três exemplos.

Compartilhe esta postagem via: