Assignment 1

In this assignment you will create one or more programs to answer the following questions. Your code should be accompanied by a write-up in the (digital) format of your choice. Your programs should be accompanied by a build script (if necessary) and unit tests, along with instructions on how to run those tests. Your write-up should contain the result of running each of your programs on the requested input, along with timing information where relevant.

Git

I strongly encourage you to start using Git to manage your projects, including your work for this course. (If you have strong opinions about competing version control programs such as Mercurial, Darcs, or SVN, feel free to use those instead). To this end, you will at the very least do the following for this assignment.

  1. Create a new Git repository for this course. If you have already done this then use your existing repository.
  2. Choose what directory you want your work for homework 1 to live in. Create it.
  3. Finish the other questions in this assignment. Add your changes to Git. Commit them. You might make many commits over the course of the assignment – that is fine.
  4. Answer questions 5–8 below once you have a stable commit for all other questions.
  5. Using the helpful command git cat-file -p, find all the blob files corresponding to any files you created for this assignment. For example, if you created the files homework-1.tex and cache_timing.py, then you need to find the SHA-1 values associated with those two files for the most recent commit.
  6. What is the SHA-1 of the current commit? Of the branch you are currently on?
  7. Hypothetically, what is the SHA-1 commit you would share with me if I wanted to clone your repository and check out your work after step 4?
  8. Create a shell script that, if run, answers questions 5–7 for the most recently committed copy of the relevant files. (Hint: this script should contain almost exactly what you typed to answer 5–7 in the first place.).

Note that once you add the answers to 5–8 to your writeup and commit, the SHA-1 of your writeup will change. This is fine – the old SHA-1 values still point to the old copy.

Floating-point arithmetic (preview)

  1. What is the largest integer that can be represented as a 64-bit IEEE 754 floating-point value? That is, find the largest value of z such that

    >>> z == int(float(z))

    Although you should submit code verifying this value, you should also argue why this must be the case.

  2. Give an example of a subnormal number.

  3. Write a function that returns true if its argument is a subnormal floating point number and false otherwise.

Cache efficiency

Credit to Daniel Fleischman for designing this problem.

Suppose we have a machine with a 12-way associative, 6MiB L3 cache with a 64-byte cache line, and we run the following C++ code on it.

int f(int array[], int size, int npasses)
{
  int result = 0;
  for (int pass = 0; pass < npasses; pass++) {
    for (int i = pass; i < size; i += npasses) {
      result += array[i] * pass;
    }
  }
  return result;
}

Knowing that an int takes up 4 bytes, we are interested in computing the worst-case value of npasses for a sufficiently large array array.

  1. What is the worst-case value of npasses for our hypothetical machine with a 6MiB L3 cache and a 64-byte cache line?

  2. What is the worst-case value of npasses on your machine?

    It will be helpful to look into the architecture of your computer to answer this question. If you are on Linux, the following files may be useful:

    /proc/cpuinfo
/sys/devices/system/cpu/cpu0/cache/index3/size
/sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size
/sys/devices/system/cpu/cpu0/cache/index3/number_of_sets
/sys/devices/system/cpu/cpu0/cache/index3/ways_of_associativity

    Note that there are additional files you might find interesting. There are (likely) several other directories you can replace cpu0 with (e.g. cpu1, cpu2, cpu3, cpu4, cpu5, cpu6, cpu7 on my machine), while replacing index3 with index0, index1, or index2 will yield information on different caches.

    Although the code sample is written in C++ (or C) you can in principle write this in any language, although your assumption about the size of an int might change.

  3. Create a plot of the running time of the function for a variety of npasses values, including the worst-case value. State the size of the array you are using.

def f(arr, passes):
    result = 0
    for p in range(passes):
        for x in arr[p::passes]:
            result += x * p

Sample submission

You might write a program that accepts as a first argument the question number from above, and then optionally additional arguments to answer the question for. For example, the following usage of your program homework-1 would answer problems 1 and 2 by simply printing an answer, while it answers problem 3 by printing true or false based on whether the second argument is subnormal or not.

$ homework-1 1      >  answers
$ homework-1 2      >> answers
$ homework-1 3 3.14 >> answers
$ homework-1 3 0.5  >> answers
$ homework-1 3 -14  >> answers

The file answers would then contain one solution per line.

You can, of course, write as many programs as you like, and write them in the language of your choice.