CS Examining the Effects of Cache Parameters and Program Factors on Cache Hit Rate Solution

Purpose: In this lab you will study the effect of various cache design parameters. The first part includes problem solving and writing a program. The second part, the lab part, involves execution of the program with possible extensions etc. if suggested by your TA and preparing a report.

In your solutions and report make sure that you have proper tables, numbering etc. All tables must have subtitle and table number furthermore columns must have column names, etc. In your report make sure that you have a nice presentation. Make sure that you number the pages. Try to do everything before coming to the lab but make sure that you demonstrate your work to your TA.

Summary

Preliminary Work: 50 points

Problem solving and writing a matrix addition program with a simple user interface.

Lab Work: 50 points

Experimental observations using a program that finds the summation of the elements of a matrix with different cache conditions.



1
Important Notes for All Labs

    1. Try to complete the lab part at home before coming to the lab. Make sure that you show your work to your TA and answer his questions to show that you know what you are doing before uploading your lab work and follow the instructions of your TAs. In all labs if you are not told you may assume that inputs are corrects. For all works when needed please provide a simple user interface for inputs and outputs.

    2. You are obliged to read this document word by word and are responsible for the mistakes you make by not following the rules. Your programs should be reasonably documented (purpose etc.) and must have a neat presentation in terms of variable names, subprogram names. indentation, comments, blank lines etc.

    3. If we suspect that there is cheating we will send the work with the names of the students to the university disciplinary committee.

DUE DATE OF PRELIMINARY WORK: SAME FOR ALL SECTIONS

No late submission will be accepted.

    a. Please upload your problem solutions and programs of preliminary work to Moodle by 9:30 am on Wednesday December 15 for similarity testing by MOSS. We plan to use MOSS both for problems solutions and program.

    b. Problems: Use the filename

StudentID_FirstName_LastName_SecNo_PRELIMproblem_LabNo.pdf [A pdf fıle as its extension suggests, which contains your solutions to the Preliminary Part]. Only a pdf fıle is accepted. Any other form of submission receives 0 (zero).

Code: For the program part use the filename

StudentID_FirstName_LastName_SecNo_PRELIMcode_LabNo.txt [A NOTEPAD FILE as its extension suggests, which contains only the program part Only a NOTEPAD FILE (txt file) is accepted. Any other form of submission receives 0 (zero).

    c. Note that the Moodle submission closes sharp at 9:30 am and no late submissions will be accepted. You can make resubmissions before the system closes, so do not wait for the last moment. Submit your work earlier and change your submitted work if necessary. Note that only the last submission will be graded.

    d. Do not send your work by email attachment, they will not be processed. They have to be in the Moodle system to be processed.

    e. At the beginning of your submission files include the following make sure that each of them is in a separate line: Course No.: CS224, Lab No., Section No., Your Full Name, and your Bilkent ID.

DUE DATE OF LAB WORK): (different for each section) YOUR LAB DAY

    a. You have to demonstrate your lab work to your TA for grading. Do this by 12:00 in the morning lab and by 17:00 in the afternoon lab. Your TAs may give further instructions on this and they may make changes. If you wait idly and show your work last minute, your work may not be graded. Make sure that you follow your TA's instructions.

2

    b. At the conclusion of the demo for getting your grade, you will upload your Lab Work to the Moodle Assignment, for similarity testing by MOSS. See lab part submission details below.

    c. Aim to finish all of your lab work before coming to the lab, but make sure that you upload your work after making sure that your work is analyzed by your TA and/or you are given the permission by your TA to upload.

    d. At the beginning of your submission files include the following make sure that each of them is in a separate line: Course No.: CS224, Lab No., Section No., Your Full Name, and your Bilkent ID.


Part 1. Preliminary Work / Preliminary Design Report (50 points)

You have to provide a neat presentation prepared by Word or a word processor with similar output quality. Handwritten answers will not be accepted.

    1. ( 5 points: With 2 or more errors you get 0 points. Otherwise full point.) Fill in the empty cells of the following table. Assume that main memory size is 4GB. Index Size: No. of bits needed to express the set number in an address, Block Offset: No. of bits needed to indicate the word offset in a block, Byte Offset: No. of bits needed to indicate the byte offset in a word. Block Replacement Policy Needed: Indicate if a block replacement policy such as FIFO, LRU etc. is needed (yes) or not (no). If some combinations are not possible mark them.





Word
Block
No.
Tag
Index
Word
Byte
Block

Cache
N


of
Size
Size
Block
Offset
Replacement



Size
size






No.
Size
way


Sets
in
(Set
Offset
Size in
Policy Needed



in
(no. of







KB
cache



bits
No.)  in
Size in
bits2
(Yes/No)



bits
words)


bits
bits1


1
128
1
32
4

















2
128
2
32
4

















3
128
4
32
8

















4
128
Full
32
8

















9
256
1
16
4

















10
256
2
16
4

















11
256
4
16
16

















12
256
Full
16
16







    1 Word Block Offset Size in bits: Log2(No. of words in a block)

    2 Byte Offset Size in bits: Log2(No. of bytes in a word)


2. (5 points: With 2 or more errors you get 0 points. Otherwise full point.) Consider the following memory configuration: Assume that main memory size is 4GB. N= 1 (direct mapped), Block size= 8 bytes, No. of sets= 4.

3

Consider the following memory accesses and indicate which set is selected and indicate if it is a hit or miss.

Memory
Set
Hit
Address Accessed (hex)
No.
(yes/no)
00 00 00 24


00 00 00 42


00 00 00 68


00 00 00 04


00 00 00 0C


00 00 00 4C



3. (5 points: With 2 or more errors you get 0 points. Otherwise full point.) Consider the following memory configuration: The same as Section 2 above only difference is N= 2. Block replacement policy is FIFO.

Consider the following memory accesses and indicate which set is selected and indicate if it is a hit or miss. (With 2 or more errors you get 0 points. Otherwise full point.)

Memory
Set
Hit
Address Accessed (hex)
No.
(yes/no)
00 00 00 2C


00 00 00 48


00 00 00 44


00 00 00 0C


00 00 00 04


00 00 00 0C



4. (5 points, With 1 or more errors you get 0 points. Otherwise full point.) Consider a three level memory: L1 and L2 are for cache memory and the third level is for the main memory. Access time for L1 is 1 clock cycle, the access time for L2 is 2 clock cycles and main memory access time is 20 clock cycles. The miss rate for L1 is 20% and the miss rate for L2 is 5%. What is the effective clock cycle for memory access (AMAT in number of clock cycles)?

With 4 GHz clock rate how much time is needed for a program with 1012 instructions to execute?


5. (30 points) Write a program to find the summation of the elements of a square matrix. Provide a user interface for user interaction to demonstrate that your program is working properly. Assume that in the main memory matrix elements are placed row by row. Create an array for the matrix elements and initialize them row by row with consecutive values. For example a 3 by 3 (N= 3) matrix would have the following values.

1
2
3
4
5
6
7
8
9

4


The row by row placement means that you will have the values of the above 3 x 3 matrix are stored as follows in the memory.

Matrix Index
(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)
(Row No., Col. No.)



















Displacement









With respect the beginning
0
4
8
12
16
20
24
28
32
of the array containing the matrix









Value stored
1
2
3
4
5
6
7
8
9











In this configuration accessing the matrix element (i, j) simply involves computation of its displacement from the beginning of the array that stores the matrix elements. For example, the displacement of the matrix element with the index (i, j) with respect to the beginning of the array is (i - 1) x N x 4 + (j - 1) x 4, for a matrix of size N x N.

Your user interface/program must provide at least the following functionalities,
    1. Ask the user the matrix size in terms of its dimensions (N),
    2. Allocate an array with proper size using syscall code 9,
    3. Display desired elements of the matrix by specifying its row and column member,
    4. Ask user the matrix element to be accessed and display the content,
    5. Obtain summation of matrix elements row-major (row by row) summation,
    6. Obtain summation of matrix elements column-major (column by column) summation,

When appropriate; such as items no. 4, 5, 6 above; use a subprogram and make sure that you follow the MIPS assembly language programming rules.



2. [50 pts] Experiments with Data Cache Parameters

Run your program with two reasonably large different matrix sizes that would provide meaningful observations.

Report for Matrix Size 1: 25 Points

Report for Matrix Size 2: 25 Points

As described above make sure that you have a easy to follow presentation with numbered tables having proper heading etc.

Make sure that you find the summation of matrix elements by performing row-major and column-major addition. Note that the row-major addition is a simple array addition from the beginning to the end; however, the column-major addition is somewhat tricky.

    a) Direct Mapped Caches: For the matrix sizes you have chosen, conduct tests with various cache sizes and block sizes, to determine the hit rate, miss rate and number of misses. Use at least 5 different

5

cache sizes and 5 different block sizes (make sure your values are reasonable) in order to obtain curves like those of Figure 8.18 in the textbook (see below). Make a 5 x 5 table with your values, with miss rate and # of misses as the data at each row-column location. Make a graph of miss rate versus block size, parameterized by cache size, like Figure 8.18.

Hint: You can reach the Cache Simulator from MARS/Tools/Data Cache Simulator as shown in the following image:























    b) Fully Associative Caches: Pick 3 of your parameter points obtained in part for column-major addition a), one with good hit rate, one with medium hit rate, and one with poor hit rate. For these 3 results, there were 3 configuration pairs of cache size and block size that resulted in the data. Take the same 3 configuration pairs, but this time run the simulation with a fully associate cache, using LRU replacement policy. Compare the results obtained: the Direct Mapped good result versus the Fully Associative good result, the Direct Mapped medium result versus the Fully Associative medium result, and the Direct Mapped poor result versus the Fully Associative poor result. How much difference did the change to fully associative architecture make? Now change the replacement policy to Random replacement, and run the 3 tests again (using the same 3 configuration pairs). Does replacement policy make a significant difference? Record these 9 values in a new table, with 3 lines: for Direct Mapped, for Fully Associative-LRU and for Fully Associative-Random.


    c) N-way Set Associative Caches: to save on hardware costs, fully set-associative caches are rarely used. Instead, most of the benefit can be obtained with an N-way set associative cache. Pick the medium hit rate configuration that you found in a) and used again in b), and change the architecture to N-way set associative. For several different set sizes (at least 4) and LRU replacement policy, run the program and record the hit rate, miss rate and number of misses. What set size gives the best result? How much improvement is gained as N (the number of blocks in a set) increases each step? Now repeat the tests, but for the good hit rate configuration from a) and b). Record these data and answer the same question again. Finally, repeat for the poor hit rate configuration.


6


Oral Interview with TA and Submission of your Data

Get ready for the interview with your TA, by gathering and analyzing your data, having it ready to submit in a clean understandable format. Be sure that you understand what you have done, and can interpret your data to the TA. Then call him over, and answer the questions he asks you.



























Part 3. Submit Lab Work for MOSS Similarity Testing

    1. Submit your Lab Work MIPS codes for similarity testing to Moodle. See instructions below.

    2. Report: Put your experiment results for Part 2 (including the tables and graphs) in a single PDF file. Use filename StudentID_FirstName_LastName_SecNo_Lab6_lab_report.pdf [pdf FILE as its extension suggests, which contains all the work done for the Lab Experiment Report Part].

Code: Put your MIPS code for Part 1.5 into a .txt file. Use filename . Note that as you do the experiments your program may or may not involve changes. Whichever the case upload. StudentID_FirstName_LastName_SecNo_Lab6_lab_code.txt [A NOTEPAD FILE as its extension suggests, which contains the Program Code Part]

Your program (code) will be compared against all the other programs in the class, by the MOSS program, to determine how similar it is (as an indication of plagiarism). So be sure that the code you submit is code that you actually wrote yourself! The same type of comparison is also planned for the reports.

    3. Even if you didn’t finish, or didn’t get the MIPS codes working, you must submit your code to the

Moodle Assignment for similarity checking.




7

    4. Your codes will be compared against all the other codes in the class, by the MOSS program, to determine how similar it is (as an indication of plagiarism). So be sure that the code you submit is code that you actually wrote yourself!

    5. At the beginning of your submission files include the following make sure that each of them is in a separate line: CS224, Lab No., Section No., Your Full Name, Bilkent ID.

    6. For your preliminary and lab works to be graded you must attend the lab.

Part 4 . Cleanup

    1. After saving any files that you might want to have in the future to your own storage device, erase all the files you created from the computer in the lab.

    2. When applicable put back all the hardware, boards, wires, tools, etc where they came from.

    3. Clean up your lab desk, to leave it completely clean and ready for the next group who will come.

------------------------------------------------------------------------------------------------------------------------------

LAB POLICIES

    1. You can do the lab only in your section. Missing your section time and doing in another day is not allowed.

    2. The questions asked by the TA will have an effect on your lab score.

    3. Lab score will be reduced to 0 if the code is not submitted for similarity testing, or if it is plagiarized. MOSS-testing will be done, to determine similarity rates. Trivial changes to code will not hide plagiarism from MOSS—the algorithm is quite sophisticated and powerful. Please also note that obviously you should not use any program available on the web, or in a book, etc. since MOSS will find it. The use of the ideas we discussed in the classroom is not a problem.

    4. You must be in lab, working on the lab, from the time lab starts until your work is finished and you leave.

    5. No cell phone usage during lab.

    6. Internet usage is permitted only to lab-related technical sites.






















8