CS416/CS518 Assignment

Topic: Warmup – Understanding Processor Primitives for Time Measurements

Goal

The purpose of this warmup homework is five-fold:

  1. To help you assess your preparedness in terms of the programming skills required for this course. For those of you that wish to brush up your C and assembly language programming skills from CS211 and CS214, this is your chance.
  2. To help you identify possible partners for this and other homeworks that you will do during the semester. Homeworks can be done alone or in teams of two students.
  3. To expose you to processor features that allow precise measurement of time, which is an important part of performance measurements.
  4. To learn how to concisely summarize and write up your results using tables, graphs and text.
  5. And finally, to familiarize you with the homework submission requirements for this course. For those of you that are new to Rutgers or are from other departments, this is also your chance to become familiar with the UNIX computing environment used for our homeworks. Your homeworks must work on the iLab machines supported by LCSR.

All homework will be submitted via Sakai in the format that we request and by the due date and time. Any questions about the homework must be posted to Sakai forums. Since this is a warmup homework, it is only worth 1% of your overall course grade. But at the same time, do not ignore this homework, since it serves as a good benchmark to assess your preparedness for future homeworks. Homeworks #1, #2 and #3 will be much more demanding that this one, and will use this one for performance measurements.

Deliverables

You will submit two things via Sakai:

  1. A file called c, containing all your code. We should be able to compile your file using 'gcc ­o a.out time.c'. You can feel free to work on any machine of your choosing, but your program must work on the iLab Linux machines.
  2. A short (1 page) writeup containing the results of your experiment. This writeup must be submitted only in PDF format.

Homework Description

In each experiment below, you need to ensure that your measurements do not capture some anomalous behavior; therefore, to increase the confidence of your measurements, you should run each experiment multiple times within a loop and have your code report the average. While there are different ways you can determine the number of times your code must loop, the simplest is experimental. With this approach, you run each experiment manually, increasing the number of iterations each time, stopping when adding more iterations does not change the average.

Your goal is to investigate the use of the processor's time-stamp counters to measure time. Using the time-stamp counter allows you to precisely measure the number of clock cycles that have elapsed between two successive measurements of the counter. Together with the processor's frequency, you can use this feature to measure the time taken to execute a piece of code. We have uploaded a file called rdtsc.pdf to the Resources section of the course page on Sakai to help you get started, but please free to Google and learn about time-stamp counters from other sources on the Web. In particular, you may find that the code examples in rdtsc.pdf do not directly work on your machine, but it contains sufficient information for you to get started on the assembly language instructions that you must use to access the processor's performance counters.

Learn how to use time-stamp counters to measure time elapsed, and use this feature to measure time for the following operations:

  1. Choose three simple kernel calls (e.g., getpid(), gettimeofday()) and measure the elapsed time to perform the call. Be careful that some versions of these simple kernel calls may cache their result in a variable on the first call, making subsequent calls artificially fast. If so, then report both results. Also be sure that the platform actually performs a system call, e.g., by printint its output. In your writeup, present a table that reports the time that it takes to execute each of these system calls on your platform.
  2. Understand how to use the read() system call, and measure the time taken to read a large file using this system call. In your writeup, present a graph showing how the time elapsed varies as a function of the size of the file being read. (Create dummy text files of various sizes and read them). Note that the operating system can often cache files that have previously been read from disk. In your experiment, be sure to consider both files that are cached in RAM as well as those that are read directly from the local disk.
  3. Now learn how the mmap() system call can be used to map the contents of the file into memory. For this experiment, mmap() a file into the process memory, and copy the data from the mapped region into another buffer. In your writeup, present a graph showing the time elapsed when executing the mmap() system call and the time elapsed when copying the mapped file into another buffer in memory. Repeat the experiment for various file sizes.

Your time.c file must contain three methods named simple_time, read_time, and mmap_time, within which you implement the three tasks above. You can create and call other methods, but we must find at least three methods with these names in your submission.

Credits: Based on a similar homework offered by Remzi Arpaci-Dusseau at UW-Madison.