2026-09-20T12:23:41Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/18363 2023-07-10 col_2142_10761 col_2142_5131 com_2142_10755 com_2142_234 com_2142_5130

Adve, Sarita V. Komuravelli, Rakesh 2011-01-14T22:47:45Z 2011-01-14T22:47:45Z 2011-01-14T22:47:45Z 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. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-12-08T15:25:33Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Komuravelli_Rakesh.pdf: 331335 bytes, checksum: fe62075a7e7b9ea3581b8735bd16761a (MD5) Komuravelli_Rakesh.pdf: 327701 bytes, checksum: b1666afc43f7077ef8de9bde38bfb933 (MD5) Made available in DSpace on 2011-01-14T22:47:45Z (GMT). No. of bitstreams: 2 Komuravelli_Rakesh.pdf: 327736 bytes, checksum: 46a4a6b6bc12b30fa0866d882fd460a9 (MD5) license.txt: 4068 bytes, checksum: 2e6e513e925a804c57795abef7074c1c (MD5) http://hdl.handle.net/2142/18363 en Copyright 2010 Rakesh Komuravelli Cache Coherence protocol software-hardware co-design multicores shared memory system compilers, hardware Verification and Performance of the DeNovo cache coherence protocol 2010-12 Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Thesis M.S. PHD:Computer Science -UIUC 10KS0112PHD