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 (implementing bubble sort.txt) 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.
Grading Rubric:
20 points: Bubble Sort works (check memory to make sure it sorted)
20 points: Selection Sort works (check memory to make sure it sorted)
20 points: Instruction comparison table (below)
20 points: Cache comparison table (below)
20 points: Answer the questions 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:
1.How similar are the two algorithms in terms of average instructions executed per item sorted? Did this surprise you?
2.How similar is the distribution of R, I, and J instructions for the two algorithms? Comment on why this might be the case.
3.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?
4.Try modifying the placement or replacement schemes? Did you get a different result?
5.Try modifying block size or number of blocks. Do not change the total cache size. Did you get different results?