CS61C Spring Homework 6

TA: Shreyas Chand

Due Sunday, May 3rd, 2015 @ 23:59:59

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:

Problem 1: Warming Up

  1. What is the minimum (Update 2) bit width of the Page Table Base Address Register?
  2. How many rows are there in the page table?
  3. (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.

If update_hist is called with num_scores = N and in points to an array containing uniformly randomly distributed values from 0 to 9 0 to 15 (inclusive) (Update 2) ,
  1. 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 that in has mostly 0's. There is an approximately equal amount of each number in the input array in. The order of values will not be such that something bad will happen as a consequence.
  2. 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 the update_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:

  1. In the best-case scenario, how many total bytes of memory can be made available for reference accessed with at most one memory access? Assume there are no data caches ($L1, $L2, $L3 etc. do not exist.) (Update 2)
  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:

  1. 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.


  2. 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