A reinforcement learning approach to directed test generation for shared memory verification

Abstract

É esperado que multicore chips continuem a utilizar memória compartilhada coerente. Apesar do hardware de coerência escalar elegantemente, o espaço de estados do protocolo de coerência aumenta exponencialmente com o aumento do número de cores. É por isso que verificação de hardware requer geração de testes dirigida (DTG), para o controle dinâmico de cobertura no limite curto de tempo proveniente de lenta simulação e curto tempo disponível para a verificação. É esperado que a próxima geração de ferramentas de Electronic Design Automation utilizem aprendizado de máquina para obter valores mais altos de cobertura em menos tempo. Esta dissertação propõe uma técnica que modela DTG como um processo de decisão e busca encontrar uma política de decisão que maximiza a cobertura acumulada como resultado da execução de ações sucessivas por um agente. A técnica proposta utiliza conhecimento consolidado de geração aleatória de testes (RTG), em vez de somente utilizar aprendizado. Ela modela DTG como RTG dirigida por cobertura e explora mecanismos de RTG distintos, sujeitos a limitações progressivamente mais restritivas. Quatro geradores de aprendizado por reforço foram comparados com dois geradores estado da arte baseados em geração híbrida e programação genética. Os resultados experimentais mostram que a aplicação de restrições apropriadas é mais eficiente para guiar o aprendizado para atingir coberturas maiores, do que somente permitir que o gerador aprenda como selecionar os eventos de memória mais promissores para o aumento de cobertura. Para um projeto com 32 núcleos e o protocolo MOESI com dois níveis, a abordagem proposta obteve a cobertura mais alta (94.06%) observada (p < 0.05), e foi duas vezes mais rápida para alcançar a maior cobertura obtida pelo gerador híbrido, assim como foi sete vezes mais rápida para alcançar a cobertura máxima obtida pelo gerador baseado em programação genética.

Abstract: Multicore chips are expected to continue to rely on coherent shared memory. Albeit the coherence hardware can scale gracefully, the protocol state space grows exponentially with core count. That is why design verification requires directed test generation (DTG) for dynamic coverage control under the tight time constraints resulting from slow simulation and short verification budgets. Next generation Electronic Design Automation tools are expected to exploit Machine Learning for reaching high coverage in less time. This dissertation proposes a technique that addresses DTG as a decision process and tries to find a decision-making policy for maximizing the cumulative coverage, as a result of successive actions taken by an agent. Instead of simply relying on learning, the proposed technique builds upon the legacy from constrained random test generation (RTG). It casts DTG as coverage-driven RTG, and it explores distinct RTG engines subject to progressively tighter constraints. Four Reinforcement Learning generators were compared with two state-of-the-art generators based on hybrid generation and Genetic Programming. The experimental results show that the proper enforcement of constraints is more efficient for guiding learning towards higher coverage than simply letting the generator learn how to select the most promising memory events for increasing coverage. For a 2-level MOESI 32-core design, the proposed approach led to the highest observed (p < 0.05) coverage (94.09%), and it was 2 times faster than the hybrid generation method to reach the latter?s maximal coverage, as well as 7 times faster than the Genetic Programming technique to achieve its maximal coverage.