Verificação de consistência de memória para sistemas integrados multiprocessados

Abstract

O multiprocessamento em chip (CMP) mudou o panorama arquitetural dos servidores e computadores pessoais e agora está mudando o modo como os dispositivos pessoais móveis são projetados. CMP requer acesso a variáveis compartilhadas em hierarquias multiníveis sofisticadas onde caches privadas e compartilhadas coexistem. Ele se baseia no suporte em hardware para implicitamente gerenciar o relaxamento da ordem de programa e a atomicidade de escrita de modo a fornecer, na interface software-hardware, uma semântica de memória compartilhada bem definida, que é capturada pelos axiomas de um modelo de consistência de memória (MCM). Este trabalho aborda o problema de verificar se uma representação executável do subsistema de memória implementa um MCM especificado. Técnicas convencionais de verificação codificam os axiomas como arestas de um único grafo orientado, inferem arestas extras a partir de traces de memória e indicam um erro quando um ciclo é detectado. Usando uma abordagem diferente, esta dissertação propõe uma nova técnica que decompõe o problema de verificação em múltiplas instâncias de um problema (estendido) de emparelhamento de vértices em grafos bipartidos. Como a decomposição foi judiciosamente projetada para induzir instâncias independentes, o problema-alvo pode ser resolvido por um algoritmo paralelo de verificação. Também é proposto um gerador de sequências de instruções aleatórias distribuídas em múltiplas threads para estimular o sistema de memória sob verificação. Por ser independente do MCM sob verificação, o gerador proposto pode ser utilizado pela maioria dos verificadores. A técnica proposta, que é comprovadamente completa para diversos MCMs, superou um verificador convencional para um conjunto de 2400 casos de uso gerados aleatoriamente. Em média, o verificador proposto encontrou um maior percentual de faltas (90%) comparado ao convencional (69%) e foi, em média, 272 vezes mais rápido.

Chip multiprocessing (CMP) changed the architectural landscape of servers and personal computers and is now changing the way personal mobile devices are designed. CMP requires access to shared variables in sophisticated multilevel hierarchies where private and shared caches coexist. It relies on hardware support to implicitly manage relaxed program order and write atomicity so as to provide, at the hardware-software interface, a well-defined sharedmemory semantics, which is captured by the axioms of a memory consistency model (MCM). This dissertation addresses the problem of checking if an executable representation of the memory system complies with a specified consistency model. Conventional verification techniques encode the axioms as edges of a single directed graph, infer extra edges from memory traces, and indicate an error when a cycle is detected. Unlike them, this dissertation proposes a novel technique that decomposes the verification problem into multiple instances of an extended bipartite graph matching problem. Since the decomposition was judiciously designed to induce independent instances, the target problem can be solved by a parallel verification algorithm. To stimulate the memory system under verification, the dissertation also proposes a generator of multi-threading random-instruction sequences. It complies with an arbitrary MCM and can be used by most checkers. Our technique, which is proven to be complete for several MCMs, outperformed a conventional checker for a suite of 2400 randomly-generated use cases. On average, it found a higher percentage of faults (90%) as compared to that checker (69%) and did it, on average, 272 times faster.