聯系方式

您當前位置:首頁 >> 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.

?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-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?


版權所有:編程輔導網 2018 All Rights Reserved 聯系方式:QQ:99515681 電子信箱:[email protected]
免責聲明:本站部分內容從網絡整理而來,只供參考!如有版權問題可聯系本站刪除。

黑龙江体彩22选5