Due Sunday, May 3rd, 2015 @ 23:59:59
- Update 1 (4/27 10:35 PM): Add short description of code and driver code to try it out. (
hw6.s
) Clarify Problem 3 question to ask about *number* of accesses. - Update 2 (4/30 3:30 PM): Add several clarifications for Problems 1, 2, and 4. TAKE NOTE OF PROBLEM 2 CHANGES. SOME VALUES HAVE CHANGED. These changes should simplify the answer expression and result in fewer assumptions needing to be made about the data.
- Update 2.5 (4/30 5:10 PM): Add another clarification for Problem 2 for what can be assumed in the worst case.
Goals
This assignment is intended to check and exercise your knowledge of Virtual Memory with exam-style questions.
Setup
You should write up your solutions in hw6.txt. Please use the provided format in hw6.txt. File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified. Detailed submission instructions are given at the bottom of this page. Failure to follow these will result in loss of credit.
Exercises
For exercises 1-3, consider the following system parameters:
- Virtual Address Length: 64-bits
- Physical Memory Size: 4 GiB
- Page size: 32 B
- TLB:
- Fully associative
- 8 entries
- LRU replacement policy
Problem 1: Warming Up
- What is the minimum (Update 2) bit width of the Page Table Base Address Register?
- How many rows are there in the page table?
- (Update 2) At most, how many entries can be valid across all Page Tables at one time?
Problem 2: Analyzing Code
Now suppose we run the following code (the MIPS code, the C is provided for reference to aid in understanding):
# $a0 = int* in, $a1 = int* hist, $a2 = num_scores update_hist: addu $t0 $a0 $0 addu $t1 $a1 $0 addu $t2 $0 $0 sll $a2 $a2 2 hist_loop: beq $t2 $a2 hist_done addu $t3 $t0 $t2 lw $t3 0($t3) sll $t3 $t3 2 addu $t3 $t1 $t3 lw $t4 0($t3) addiu $t4 $t4 1 sw $t4 0($t3) addu $t2 $t2 4 j hist_loop hist_done: jr $ra |
void update_hist(int* in, int* hist, int num_scores) { for (int i = 0; i < num_scores; i++) { hist[in[i]] += 1; } } |
Update 1: The above code creates a histogram out of some set of input data. If you would like to see it in action, download hw6.s and run it in MARS.
For the following questions you may assume: 1) Both in
and hist
point to page-aligned arrays. 2) The update_hist
procedure is page aligned. 3) This is the only process currently running on the machine.
update_hist
is called with num_scores = N
and in
points to an array containing uniformly randomly distributed values from - in the worst-case scenario, how many page faults can occur? (Update 2.5) Do not assume anything insidious about the distribution of values in
in
. For example, do not assume a distribution such thatin
has mostly 0's. There is an approximately equal amount of each number in the input arrayin
. The order of values will not be such that something bad will happen as a consequence. - in the best-case scenario, how many elements in
in
can be processed before a TLB-miss is incurred?
Problem 3: Optimization Effects
(Update 1) Consider theupdate_hist
procedure once again. In order to handle super large arrays efficiently, we decide to try to optimize the code using loop unrolling, by simply duplicating the loop body 16 times (You can assume all input arrays have a length that is a multiple of 16). What effect does this have on performance just in terms of memory/disk accesses? Could the total number of memory/disk accesses (and thus the overall time spent on IO) increase, decrease or stay the same?
Problem 4: Cool Down
Now consider the following system parameters:
- Virtual Address Length: 16-bits
- Physical Memory Size: 4 GiB
- Offset length: 13-bits
- TLB:
- Fully associative
- 8 entries
- LRU replacement policy
- In the best-case scenario, how many total bytes of memory can be
made available for referenceaccessed with at most one memory access? Assume there are no data caches ($L1, $L2, $L3 etc. do not exist.) (Update 2) - If every process requires a minimum of 4 pages (1 each for Stack, Heap, Static and Code), in the best-case scenario, how many processes can be guaranteed to run simultaneously without causing any page faults?
Submission
There are two steps required to submit hw6.txt. Failure to perform both steps will result in loss of credit:
First, you must submit using the standard unix submit program on the instructional servers. To do so, follow these instructions after logging into your cs61c-XX class account:
$ mkdir ~/files_for_submit $ cd ~/files_for_submit $ mkdir hw6 $ cd hw6 $ cp [Your hw6 text file location] hw6.txt # replace the braces with the location of your hw6.txt file $ submit hw6
Once you type submit hw6, follow the prompts generated by the submission system. It will tell you when your submission has been successful and you can confirm this by looking at the output of glookup -t.
Additionally, you must submit hw6.txt to your GitHub repository. To do so, follow these instructions after logging into your cs61c-XX class account:
$ cd ~/work # this is the location of your git repo on your class account $ mkdir hw6 $ cd hw6 $ cp [Your hw6 text file location] hw6.txt # replace the braces with the location of your hw6.txt file $ cd .. $ git add hw6/hw6.txt $ git commit -m "Homework 6 submission" $ git tag "hw6" # The tag MUST be "hw6". Failure to do so will result in loss of credit. $ git push origin master --tags # Note the "--tags" at the end. This pushes tags to github