CSC 469F / CSC 2208F | Assignment 0 | Fall 2007

Due: 4 p.m., October 3, 2007.

1. Introduction
2. Assignment Requirements
3. Submission Instructions

GOAL: You will develop a tool to measure the performance of several basic operations on x86 systems. You will use this tool to explore the timer interrupt, context switch, and IPC performance of a Linux 2.6 system.

This assignment has more in common with a Chemistry Lab than with the assignments you typically find in Computer Science. You will be collecting data on real systems, analyzing that data, and developing reasonable explanations for the behavior that you observe. Remember that the real world is messy, and the data you collect is likely to be messy as well. Part of your task is to figure out how to control the experimental environment as much as possible, and to identify sources of noise that you cannot control.

The first step in developing our benchmarking tool will be to explore the sources of interference when a process (or function) of interest is running. You will be using the Pentium cycle counter register (TSC, or time stamp counter) for this; we provide simple functions to start timing and read the cycle counter (see /u/csc469h/fall/pub/A0 on CDF).

1. Tracking process activity

A trace of active and inactive periods for a process running on an Intel Linux system can be created using the provided start_counter() and get_counter() functions. Write a function:

   u_int64_t inactive_periods(int num, u_int64_t threshold, u_int64_t *samples);

This function continually checks the cycle counter and detects when two successive readings differ by more than threshold cycles, which indicates that the process has been inactive. You should determine a reasonable value to use for threshold (tip: you don't want to record an inactive period for something like a cache or TLB miss, nor should it be smaller than the time to collect two successive timer samples). The start and end of the inactive period should be recorded in samples, which is an array of 64-bit unsigned ints allocated by the caller of the function. A total of num inactive periods should be recorded. The function should return the initial reading - that is, the start of the first active period.

Write a program that calls this function, with the number of inactive periods to collect as a command-line argument. Your program should use the collected data to produce a trace of the activity, similar to the one below (collected on my 1.2 GHz laptop running Linux 2.6.8):

Active 0: start at 38, duration 627514 cycles (0.523649 ms)
Inactive 0: start at 627552, duration 11444 cycles (0.009550 ms)
Active 1: start at 638996, duration 1184480 cycles (0.988427 ms)
Inactive 1: start at 1823476, duration 8456 cycles (0.007056 ms)
Active 2: start at 1831932, duration 1187491 cycles (0.990939 ms)
Inactive 2: start at 3019423, duration 18233 cycles (0.015215 ms)
Active 3: start at 3037656, duration 1177747 cycles (0.982808 ms)
Inactive 3: start at 4215403, duration 8171 cycles (0.006819 ms)
Active 4: start at 4223574, duration 1187779 cycles (0.991180 ms)
...

To do this, your program will also need to determine experimentally the clock speed on the system being measured, so that a cycle counter measurement can be converted to milliseconds.

Your program should also produce output suitable for input to a graph program like gnuplot, so that you can generate a graph of the results, similar to the ones below:

The first plot was generated by dropping the first measured active and inactive period, since the first active period really started before we started measuring. Blue represents periods of activity, red represents periods of inactivity.Your plots should include a key with this type of information! The second plot shows the full data for a smaller number of intervals. You will be measuring different systems, so don't be surprised if your results don't look like this.

Wrap your experiment in a script that invokes the data gathering program, then invokes gnuplot (or your favorite scriptable graphing program) and displays the resulting graph.

Questions:

1. With what frequency do timer interrupts occur?
2. How long does it take to handle a timer interrupt?
3. If it appears that there are other, non-timer interrupts (that is, other short periods of inactivity that don't fit the pattern of the periodic timer interrupt), explain what these are likely to be, based on what you can determine about other activity on the system you are measuring.
4. Over the period of time that the process is running (that is, without lengthy interruptions corresponding to a switch to another process), what percentage of time is lost to servicing interrupts (of any kind)?

2. Context switches

Now design an experiment to measure the context switch time. The lmbench paper describes a way to do this using pipes, however the measured context switch time using their method will include other overheads. Your goal here is to measure the time to switch between two ready processes. Hint: You will need a lightly-loaded system to increase the likelihood that the scheduler switches between two processes that you are measuring.

Once again, create a script that can be used to run the full experiment, including collecting, plotting, and displaying the data. Plot the activity of the processes that you are switching between, and output the best estimate of the context switch overhead.

How long is a time slice? That is, how long does one process get to run before it is forced to switch to another process? Are you surprised by your measurements? How does it compare to what you were told about time slices in your previous OS course?

3. Testing multiprocessor support

Linux 2.4 was not designed for multiprocessors, and although it could run with more than 1 CPU, it did not provide many of the features needed to allow programmers to write parallel programs that ran efficiently. As one example, the POSIX sched_setaffinity() system call is used to specify what CPU(s) a process is allowed to run on. Under Linux 2.4, this system call returns EUNIMP. Linux 2.6 claims to have vastly superior multiprocessor support, and sched_setaffinity() no longer reports that it is not supported.

Your job is to design an experiment to test whether sched_setaffinity() actually does what it says. Your code for tracking activity of a process should come in handy here, and you should be able to produce a plot that shows clearly whether processes are competing for the same CPU, or running on separate CPUs. Actually collecting the data you need to show this may be difficult - the new CDF servers (redwolf, greywolf) are nice 8-core machines, but you will need to try and find times when they are relatively idle.

4. IPC Performance

Design an experiment to measure IPC performance using pipes. Try to measure just the cost of the IPC, without including the cost of a context switch. Try this (a) with both processes running on the same CPU, and (b) with each process running on a different CPU. How do the two setups compare? Do the results make sense?

What

Write a technical report containing the results of your experiments and your discussions. Your report should be well-organized and easy to read -- you should have an introduction, a description of what you are trying to do and why (preferably other than "for the marks!"), a description of your experimental methodology (for each part of the assignment), your results (for each part of the assignment), and a discussion. Make sure you address all the questions posed above in your report. Include a table describing your hardware platform (include all relevant details - CPU family and speed, cache size, memory size, disk parameters, etc.). Present your benchmark results in both tabular and graphical form (for those who want to see the detailed results, and those who want to spot trends in the data). Do not include a raw dump of all the data you collected - present the relevant details gained from your analysis of the data. Include an appendix that describes how to use your benchmark tools so that someone else could reproduce your experiments.

Create a compressed tar file (tar -czf a0.tgz ) of the benchmark tools you created (that is, the programs that collect the data for each part, and the script that automatically runs the program(s) and plots the results).

How

Submit hardcopy of your report using the assignment drop box in BA 2220

Submit your tar file using 'submit -c csc469h -a A0 a0.tgz' on CDF.