联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> 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?


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp