#### 您當前位置：首頁 >> Algorithm 算法作業Algorithm 算法作業

###### 日期：2019-11-20 10:49

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.

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-typeI-typeJ-typeAvg I/item

Bubble Sort

Selection Sort

Cache Comparison Table:

Memory Access  CountCache Hit CountCache 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?