Verification and Performance of the DeNovo cache coherence protocol

Komuravelli, Rakesh

Permalink

https://hdl.handle.net/2142/18363 Copy

Description

Title

Verification and Performance of the DeNovo cache coherence protocol

Author(s)

Komuravelli, Rakesh

Issue Date

2011-01-14T22:47:45Z

Director of Research (if dissertation) or Advisor (if thesis)

Adve, Sarita V.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

Abstract

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.

Graduation Semester

2010-12

Permalink

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

Copyright and License Information

Copyright 2010 Rakesh Komuravelli

Owning Collections