Verification and Performance of the DeNovo cache coherence protocol

With the advent of multicores, parallel programming has gained a lot of importance. For parallel programming to be viable for the predicted hundreds of cores per chip, shared memory programming languages and environments must evolve to enforce disciplined practices like ``determinism-by-default semantics'' and ban ``wild shared-memory behaviors'' like arbitrary data races and potential non-determinism everywhere. This evolution can not only benefit software development, but can also greatly reduce the complexity in hardware. DeNovo is a hardware architecture designed from the ground up to exploit the opportunities exposed by such disciplined software models to make the hardware much simpler and efficient at the same time. This thesis describes an effort to formally verify and evaluate the DeNovo cache coherence protocol. By using a model checking tool, we uncovered three bugs in the protocol implementation which had not been found either in the testing phase or in the simulation runs. All of these bugs were caused by errors in translating the high level description into the implementation. Surprisingly, we also found six bugs in a state-of-the-art implementation of the widely used MESI protocol. Most of these bugs were hard to analyze and took several days to fix. We provide quantitative evidence that DeNovo is a much simpler protocol by showing that the DeNovo protocol has about 15X fewer reachable states when compared to MESI when using the Murphi model checking tool for verification. This translates to about 20X difference in the runtime of the tool. Finally, we show that this simplicity of the DeNovo protocol does not compromise performance for the applications we evaluated. On the contrary, for some applications, DeNovo achieves up to 67\% reduction in memory stall time and up to 70\% reduction in network traffic when compared to MESI.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Komuravelli, Rakesh

Contributors dc:contributor

• Adve, Sarita V.

• Cache Coherence protocol
• software-hardware co-design
• multicores
• shared memory system
• compilers, hardware

Statement dc:rights

• Copyright 2010 Rakesh Komuravelli

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/18363

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/18363