This is the teaching fellow's page. I will post some supplemental material here from time to time, allowing both students and the professor to keep track of what happened in discussion sessions.
You're welcome to make appointment by e-mail; checking my schedule first.
CS350 Spring 2009 TF
Regarding the programming assignment, I've attached two simplified workloads that should help you test whether you implemented cache replacement correctly. This is what you should get when running 1 process on 1 core for 1,000,000 references with wrap-around.
cache lines used: 4, unused: 65532 pid hits misses eviction trace file 1 999996 4 0 data/simple-cache-addrs cache lines used: 40, unused: 65496 pid hits misses eviction trace file 1 999936 64 24 data/synthetic-l2-cache-addrs
The simple-cache-addrs should be easy enough to see what's going on. The four addresses are mapped to four distinct sets, so there should be no eviction. The synthetic workload is slightly more involved. It is generated using the following for-loop:
for (int msb = 0; msb < 16; msb++) for (int index = 0; index < 4; index++) printf("%#x\n", (msb << 18 | index << 6));
The purpose is that, for each of the index 0 through 3, each of which map to a cache set, we want to populate that cache set 16 times. Since cache replacement is uniform random, eviction can occur quite often.
Some people like to wrap everything into C++ classes, including threads. There is some intricate danger in wrapping a resource around a C++ object because the C++ object gives you the impression that the resource can be aliased (i.e. it is okay to have multiple pointers/references to the same object) when it is not. Also, since you're not allowed to peek inside the internal state of the object, the user may call object methods in an order that violates object consistency and produce undefined result. In the worst case, it may cause leakage of scarce resources like processes, file descriptors, and network sockets. Object-oriented encapsulation takes away your ability to reason about resource usage.
For example, suppose you write a C++ Mutex class to wrap around pthread mutex. What if the destructor is called when the mutex is still locked?
In the code I attach below, the Thread class represents a pthread. It has a start() method that begins execution of some threaded code and a join() method to wait until the thread finishes. What if start() is called twice on the same object? (Answer: the previous thread could be orphaned and we lose a reference to it while it's still running). What if the C++ object is destructed while a thread is still running? (Answer: the operating system wouldn't be able to properly clean-up the thread, such as freeing its run-time stack, which can be as large as 4MB). The example code I attach below tries to deal with these issues by doing lots of run-time checks. The run-time checks is what gives the impression that C++ is bloated.
Having warned you with all that, the code I attach below is tested to work on g++ (The C++ compiler in GCC) with -Wall.
Getting familiar with C programming. Let the class participated in brainstorming ideas for implementing problem 6. Went over some C language constructs that would be required for that problem.
Students are encouraged to do other problems on their own time as well. Unit tests for selected exercises are also included in exercises.tar.gz attached below. When you do problem 2 (strlen.c), problem 4 (assoc.c) and problem 5 (palin.c), you could modify the corresponding source file and do a "make test", which would create a unittest_main executable. Run the executable to see if your implementation works. You are encouraged to come up with a unit testing strategy for problem 3 as well.
To make sure that unit testing works, try to break code in queue.c and see how the test fails. First comment out the lines commented by marker 1, make and run the unit test. You should see that the deq_null test fails. Restore queue.c to its original content. Now, comment out the line commented by marker 2, make and run the unit test. You should see that enq_deq_enq_deq test fails.
A summary of formulas that might be helpful for homework 2 is attached.
Just went over homework 1 today. Also did an M/M/1 example.