CS 3340 Computer Architecture – Fall 2019 – Mazidi
Homework: Cache Comparisons
Objective: Compare two sorting algorithms in terms of number of instructions and cache utilization.
Turn in, zipped together: Bubble sort program, Selection sort program, Document containing counts and commentary
Instructions:
• Modify the Bubble sort demonstrated in class (https://github.com/kjmazidi/CS3340/blob/master/Code%20Samples/zybook_4/bubble_sort.asm) to sort 500 data items which are defined in the .data section. Remove any functionality in the program that is not sorting, such as printing the array before and after.
• Use the same data as you use in the Bubble sort but copy your Selection sort from Homework 5 into a program and modify it to run the same data. The two sorts should be in two different programs and should do nothing but sort the 500 integers in memory.
• Using the Instruction Counter tool, fill in the instruction comparison table below.
• Using the Data cache Simulator tool, fill in the cache comparison table below.
• Answer questions 1-5 below.
Reminder:
To get to the tools:
• Assemble the program
• Use the Tools menu to find the tool
• Hit the ‘Connect to MIPS’ button on the tool
• Hit the green run arrow at the top of MIPS
Instruction Comparison Table:
Number Instr.
R-type
I-type
J-type
Avg I/item
Bubble Sort
Selection Sort
Cache Comparison Table:
Memory Access Count
Cache Hit Count
Cache Miss Count
Cache Hit Rate
Bub Sort
Sel Sort
Questions:
• How similar are the two algorithms in terms of average instructions executed per item sorted? Did this surprise you?
• How similar is the distribution of R, I, and J instructions for the two algorithms? Comment on why this might be the case.
• Compare the hit rates of the two algorithms using default settings. Given your understanding of the patterns in which these two algorithms access memory, how do you explain this difference?
• Try modifying the placement or replacement schemes? Did you get a different result?
• Try modifying block size or number of blocks. Do not change the total cache size. Did you get different results?