Automatic generation of highly concurrent, hierarchical and heterogeneous cache coherence protocols from atomic specifications
View/ Open
Date
24/05/2023Author
Oswald, Nicolai Alexander
Metadata
Abstract
Cache coherence protocols are often specified using only stable states and atomic transactions
for a single cache hierarchy level. Designing highly-concurrent, hierarchical and heterogeneous directory cache coherence protocols from these atomic specifications for modern
multicore architectures is a complicated task. To overcome these design challenges we have
developed the novel *Gen algorithms (ProtoGen, HieraGen and HeteroGen).
Using the *Gen
algorithms highly-concurrent, hierarchical and heterogeneous cache coherence protocols can
be automatically generated for a wide range of atomic input stable state protocol (SSP) speci fications - including the MOESI variants, as well as for protocols that are targeted towards
Total Store Order and Release Consistency. In addition, for each *Gen algorithm we have
developed and published an eponymous tool.
The ProtoGen tool takes as input a single SSP (i.e., no concurrency) generating the corresponding protocol for a multicore architecture with non-atomic transactions. The ProtoGen
algorithm automatically enforces the correct interleaving of conflicting coherence transactions
for a given atomic coherence protocol specification.
HieraGen is a tool for automatically generating hierarchical cache coherence protocols.
Its inputs are SSPs for each level of the hierarchy and its output is a highly concurrent
hierarchical protocol. HieraGen thus reduces the complexity that architects face by offloading
the challenging task of composing protocols and managing concurrency.
HeteroGen is a tool for automatically generating heterogeneous protocols that adhere to
precise consistency models. As input, HeteroGen takes SSPs of the per-cluster coherence
protocols, each of which satisfies its own per-cluster consistency model. The output is a
concurrent (i.e., with transient states) heterogeneous protocol that satisfies a precisely defined
consistency model that we refer to as a compound consistency model.
To validate the correctness of the *Gen algorithms, the generated output protocols were
verified for safety and deadlock freedom using a model checker. To verify the correctness
of protocols that need to adhere to a specific compound consistency model generated by
HeteroGen, novel litmus tests for multiple compound consistency models were developed.
The protocols automatically generated using the *Gen tools have a comparable or better
performance than manually generated cache coherence protocols, often discovering opportunities to reduce stalls. Thus, the *Gen tools reduce the complexity that architects face by
offloading the challenging tasks of composing protocols and managing concurrency.