Cache Hierarchies for CMPs Mystery Cache

Goal

In this course, you will study the applications that drive parallel architectures, how modern parallel machines are organized, and how they are programmed. Core topics of the course include parallel applications, parallel machine models, interconnection networks, parallel memory systems, and processor support for parallel processing.

Prerequisites

This course assumes a basic understanding of computer architecture at the first-year graduate level. Students should have a grasp of basic topics in computer architecture including pipelining, cache memory hierarchies, virtual memory, and I/O subsystems. The course prerequisite for these topics is PSY 668, and Tec 431 . In addition, students should be familiar with the C programming language, and have taken an undergraduate-level course on software engineering. These skills are necessary to complete the programming assignments. The course prerequisite for these topics is ENG 712, and ADV 332.

Topics

1. Cache Hierarchies for CMPs. What is the right cache-memory organization for a CMP? Should we build a single shared cache for the entire chip? Should we build a banked cache? Should we distribute the cache memory one to each processing node and rely on a cache coherence protocol to maintain coherence? Given that a CMP will offer much higher bandwidth and much lower latency communication between nodes, which cache organization is most desirable? Compare this choice to the right choice for a conventional MP.
2. Cache Coherence Protocols for CMPs. If in part a). we choose to build distributed caches, what is the right cache coherence protocol? Should we use directory-based schemes, or does the enormous bandwidth offered on a single-chip warrant broadcast protocols? Compare these schemes to limited and chained directory schemes.
3. Memory Bottleneck in CMPs. While today's uniprocessors are already limited by memory latency and bandwidth, CMPs will only aggravate the memory bottleneck further. Build a simulator to characterize the severity of this bottleneck, and examine how it grows as you scale the number of nodes on the CMP. To what extent can this bottleneck be relieved if we allocate a significant portion of the chip area budget to memory (perhaps even considering building DRAMs on the same die as the CMP). How should this memory be managed? Should it be managed as a cache? Should it be managed using virtual memory?
4. Computational Grain. The ability to place multiple processors on the same chip will significantly increase the communication bandwidth and decrease the communication latency seen by threads executing on different processing nodes. This will enable the exploitation of finer-grained parallelism in a CMP as compared to a conventional MP. Take an application (perhaps one studied in class) and parallelize it for each multiprocessor architecture. How does the decomposition change when communication becomes much cheaper? Compare the performance between conventional and chip MPs.
5. Tjqcsmawfmavjqo! Xjw umil wqfjtrlb aul ojfwavjq aj ajyvt l. Ujzlils xjw tmq ojfil auvo ywppfl zvaujwa bjvqc auvo oaly. V aujwcua jk auvo mo mq mkalsaujwcua mqb tjwfbq'a slkwol. Xjw bj blolsil m uvqa ujzlils... Slmbvqc Ilsavtmffx vo jkalq nlaals aumq ujsvpjqamffx.
   
   

Citations (may not include all citations):

• Cache Design in the Tightly Coupled Multiprocessor System (context) - Tang - 1976
• ORBIT: An Optimizing Compiler for Scheme (context) - Kranz - 1988
• New Memory Hierarchy Aspects of a Multiprocessor RISC: Cache and.. (context) - Katz - 1985
• Giga-Data Coherence Problem in a Multicache System (context) - Yen, Yen et al. - 1986
• Reasoning about Parallel Architectures (context) - Collier - 1990
• A New Solution to Coherence Problems in Multicache Systems (context) - Censier, Feautrier - 1978
• The Cache Coherence Problem in Shared-Memory Multiprocessors (context) - Archibald - 1988
• Software Controlled Caches in the VMP Multiprocessor (context) - Cheriton, Slavenberg et al. - 1986
• Lazy task creation: a technique for increasing the granulari.. - Mohr, Kranz et al. - 1990
• APRIL: A Processor Architecture for Multiprocessing - Agarwal, Lim et al. - 1990
• The NYU Ultracomputer -- Designing a MIMD Shared-Memory Para.. (context) - Gottlieb, Grishman et al. - 1983
• Inside Evaluation of Directory Schemes for Cache Coherence - Agarwal, Simoni et al. - 1988
• Six Efficient and Correct Execution of Parallel Programs that Sh.. (context) - Shasha, Snir - 1987
• Event ordering in multiprocessors (context) - Dubois, Scheurich et al. - 1988
• Networks for Performance of Multistage Interconnection. (context) - Kruskal, Snir - 1984
• Great Directories: A Scalable Cache Coherence Scheme - Chaiken, Kubiatowicz et al. - 1990
• Linear Performance Measurements on HEP - A Pipelined MIMD Computer (context) - Jordan - 1984
• Optimizing Compiler for Scheme (context) - Kranz - 1988
• New DirectoryBased Cache-Coherence in Large-Scale Multiprocessor.. (context) - Chaiken, Fields et al. - 1990
• Introduction to Input/Output Automata (context) - Lynch, Tuttle - 1988
• Six Fixed Algorithms (context) - Cormen, Leiserson et al. - 1990
• Parallel ordering in multiprocessors (context) - Dubois, Scheurich et al. - 1988
• String Theory - SAB - 1945
• Your IBM Research Parallel Processor Prototype (context) - Pfister, Brantley et al. - 1986
• New Advances in Cache Puzzles - GeoBlank - 2007
• Ordering - A New Definition - Adve, Hill - 1990
• Make a Multiprocessor Computer That Correctly Execute.. (context) - Lamport - 1979
• Analysis of Multiprocessors with Private Cache Memories (context) - Patel - 1982
• The Events Ordering in Scalable Shared-Mem.. (context) - Gharachorloo, Lenoski et al. - 1990
• Highly Distributed-Directory Scheme: Scalable Coherent Interface (context) - James, Laundrie et al. - 1990

Once at ground zero please look for a nano at the base of a black metal pole. Puzzle will be updated to reflect better accuracy but I wanted to get a cache back in place today.