1. Homepage
  2. Programming
  3. CS 433 / CSE 422: Computer System Organization HW 06: MSI and MESI cache

CS 433 / CSE 422: Computer System Organization HW 06: MSI and MESI cache

Engage in a Conversation
CS 433CSE 422IllinoisComputer System Organization

CS 433 / CSE 422: Computer System Organization HW 06 [5 problems, 100 points] CourseNana.COM

Covers Classes 22–25 Due: December 6, 2023 CourseNana.COM

Instructions CourseNana.COM

Homework sets are due at 12:00 PM on the due date. Upload your answers, as described below, to Gradescope by then. CourseNana.COM

To hand in your homework, create a PDF either by scanning your paper work, or by generating it in a software tool to start with (e.g., a word processor, LaTeX). Ensure your PDF is readable, your work legible and rotated correctly. Upload your work to Gradescope and follow the Gradescope instructions carefully to ensure your work is graded properly. Points will be deducted if you do not follow directions, for instance, by not assigning problems to pages. CourseNana.COM

This homework has coding questions that must be uploaded to a separate assignment on Gradescope. Please upload any source code files that you have edited to Gradescope. Be careful to edit only the files mentioned in the problem, and make sure to comment your code so we can understand your thought process. CourseNana.COM

Remember: all files need to be generated and uploaded before the deadline, so leave ample time for submission! CourseNana.COM

Discussions about homework with a single partner are encouraged — think of this as giving hints, not solutions, to each other. However, homework must be written up individually (no copying is allowed), and all code must be written by you alone. If you discussed your homework solutions with someone else, either as the giver or receiver of information, your write-up must explicitly identify the partner. CourseNana.COM

You must show details of your work. There is no credit for just writing down an answer. CourseNana.COM

Homework Problems CourseNana.COM

1. [20 points] Let’s look at the MSI and MESI cache coherence protocols. For each part, list a series of state transitions for a single cache block, for a single cache.Assume your cache block starts in the invalid state. List and label the transitions under MSI, and under MESI. CourseNana.COM

As an example, here’s a transition that is equivalent in both MSI and MESI: CourseNana.COM

MSI: I M I MESI: I M I CourseNana.COM

Page 1 of 5 CourseNana.COM

Thread A writes to the cache block, and then the block is evicted. CourseNana.COM

Thread B does not access the cache block. CourseNana.COM

  1. [8 points] List a series of state transitions that will generate fewer coherence messages on the bus for MESI than for MSI (i.e., MESI is more efficient). CourseNana.COM

    Explain both (1) how two threads could make this sequence happen, and (2) why one has fewer messages than the other. CourseNana.COM

  2. [8 points] List a series of state transitions that will generate fewer coherence messages on the bus for MSI than for MESI (i.e., MSI is more efficient). CourseNana.COM

    Explain both (1) how two threads could make this sequence happen, and (2) why one has fewer messages than the other. CourseNana.COM

  3. [4 points] What is the minimum amount of metadata that you need to implement MESI? Can you reuse any cache metadata bits, and if so, how? CourseNana.COM

2. [24 points] Time to think about locks and atomics. CourseNana.COM

  1. [4 points] Look at the following piece of code: CourseNana.COM

    volatile int iters = 6; // shared memory CourseNana.COM

    void myThread(int *iters) { --iters; CourseNana.COM

    If we run four threads of myThread(), what are the possible values of iters after the CourseNana.COM

    threads complete? Why? CourseNana.COM

  2. [4 points] Now let’s change our code up a bit: CourseNana.COM

    volatile int iters = 6; // shared memory CourseNana.COM

    void myThread(int *iters) { while(iters > 0) CourseNana.COM

    --iters; CourseNana.COM

    After we run four threads of myThread(), will iters always be 0? Why or why not? CourseNana.COM

Page 2 of 5 CourseNana.COM

C. [4 points] An atomic read–modify–write (RMW) avoids race conditions for locks. Why don’t we use atomic RMW for all memory operations? CourseNana.COM

  1. [8 points] MESI can reduce coherence traffic compared to MSI for a test and test-and-set lock. Describe in a few sentences why MESI is better for this type of lock. CourseNana.COM

    Make sure your answer is specific to the lock, and not just about general advantages of MESI over MSI. CourseNana.COM

  2. [4 points] Does an atomic RMW solve the false sharing problem? Why or why not? CourseNana.COM

  1. [11 points] Are you consistent or coherent? CourseNana.COM

    1. [2 points] We have a cache block where false sharing occurs. Do we need to use coherence, consistency, or neither to keep the data synchronized? CourseNana.COM

    2. [3 points] Let’s look at a very simple trace of instructions from two threads belonging to the same process: CourseNana.COM

      Thread 0 Thread 1 CourseNana.COM

      a=2 b=a b=3 CourseNana.COM

      Before the threads start, a and b are shared memory integers, each in their own cache block, that are both initialized to 1. CourseNana.COM

      In a machine that implements sequential consistency, what are the different values that b could hold after a valid execution? CourseNana.COM

    3. [6 points] Now, we want you to get rid of exactly one of those possible values of b, by running the threads on a machine that implements weak consistency. Rewrite the traces for each thread, showing where you insert SYNCH operations (if any are needed), and tell us which value of b is no longer possible. You should not introduce a new possible output, and you should not reorder the instructions. CourseNana.COM

  2. [10 points] CourseNana.COM

A. [3 points] In a CPU with big–little cores, how does coherence help when we move a thread from a big core to a little core? CourseNana.COM

Page 3 of 5 CourseNana.COM

  1. [3 points] Describe why a GPU is different from having a very wide version of a SIMD instruction set extension. CourseNana.COM

  2. [4 points] Look up two processors online: (1) the Intel Xeon Platinum 8470 (a server processor), and (2) the Snapdragon 8 Gen 2 (a mobile SoC). See if you can find specification that list the components inside each processor. CourseNana.COM

    List one key difference between the two, and explain why these are different. CourseNana.COM

Coding Problems CourseNana.COM

5. [35 points] You will implement the MESI cache coherence protocol in Python, along with any necessary movement of data, in a cache subsystem. CourseNana.COM

Please read the problem statement completely before starting. CourseNana.COM

Important: We are using Python 3 (available for download at the official Python website, https: // www. python. org/ downloads/ ) with no specific OS or code editor requirements. However, your code must run on the Gradescope Autograder or you will not receive any credit for this problem. CourseNana.COM

Download a ZIP file with starter code at https://courses.engr.illinois.edu/cs433/ fa2023/hw/hw06-q05.zip. CourseNana.COM

System Setup CourseNana.COM

We define a multi-core system with a private cache per core, a shared last-level cache (LLC), and a main memory. The main memory is assumed to be large enough to store all data that we will handle, and the LLC has enough space to prevent any evictions from it. CourseNana.COM

Cache Back End CourseNana.COM

We use a simple model of caching where each cache is a hashmap, which maps a cache block to a MemoryLocation object that contains the data, state, and address of a piece of data. The state of each location should be defined as None in main memory and the LLC. CourseNana.COM

Whenever a private cache is full, it will try and evict the least recently used and Invalid MemoryLocation object. If all of the data in the cache is valid, then it will evict the least recently used data. CourseNana.COM

Each eviction will call the evict_from_private_cache() function in the MESICoherence class. CourseNana.COM

A load instruction to the cache triggers the load_data() method in the MESICoherence class. This method should return the data, which is stored as an int (not as a MemoryLocation object). CourseNana.COM

Page 4 of 5 CourseNana.COM


When a store instruction accesses the cache, the store_data() method in the MESICoherence class is called, and this method should not return anything. CourseNana.COM

You should assume that all data is stored before a load call is made to it. CourseNana.COM

Your assignment is to code the MESICoherence class. This class contains a list of private CPU caches in cpu_cache variables, an LLC in the llc variable, and main memory in the main_memory variable. CourseNana.COM

Assumptions CourseNana.COM

You should assume that the main memory stores the initial state for all addresses passed in the trace. This means that you can load data from the MainMemory object for all addresses used by the tester. CourseNana.COM

Your private caches should be write-back, write-allocate. CourseNana.COM

Trace Description CourseNana.COM

The first line in each provided trace file contains three integers that define the size of the private cache and shared LLC. Main memory is assumed to be infinite. CourseNana.COM

All subsequent lines of the trace define load/store instructions. Each of these instructions is definedasLD/ST, <CPU ID>, <ADDR>, <DATA>,wherethedatatagrepresentstheexpected value for a load. CourseNana.COM

Local Testing CourseNana.COM

coherence.py has an optional output argument that prints a large JSON file containing the internal state of the system. The autograder generates this file to test code, so make sure that the internal state of the system is consistent with what you are implementing. CourseNana.COM

Submission CourseNana.COM

Make sure that you comment your logic in code (you will lose points for code that is not thoroughly commented in English). Please submit the following file (make sure that you do not the complete homework folder): CourseNana.COM

Your code must work on the Autograder to get points and code with syntax errors will get no CourseNana.COM

points. CourseNana.COM

Make sure you check Campuswire for clarifications, and ask questions whenever you are stuck. Remember that this problem is only a part of your homework. Happy coding! CourseNana.COM

Page 5 of 5  CourseNana.COM

Get in Touch with Our Experts

Wechat WeChat
Whatsapp Whatsapp
CS 433代写,CSE 422代写,Illinois代写,Computer System Organization代写,CS 433代编,CSE 422代编,Illinois代编,Computer System Organization代编,CS 433代考,CSE 422代考,Illinois代考,Computer System Organization代考,CS 433help,CSE 422help,Illinoishelp,Computer System Organizationhelp,CS 433作业代写,CSE 422作业代写,Illinois作业代写,Computer System Organization作业代写,CS 433编程代写,CSE 422编程代写,Illinois编程代写,Computer System Organization编程代写,CS 433programming help,CSE 422programming help,Illinoisprogramming help,Computer System Organizationprogramming help,CS 433assignment help,CSE 422assignment help,Illinoisassignment help,Computer System Organizationassignment help,CS 433solution,CSE 422solution,Illinoissolution,Computer System Organizationsolution,