Assignment #3 - Request Trace Analysis

Assignment due by 11:59pm, Thursday, March 24.

In the class we discussed tracking requests in server systems. After properly tracking each request's execution, we can attribute system events (e.g., CPU context switches, network sends/recvs, file reads/writes, system calls) to corresponding request contexts. The purpose of this assignment is to analyze collected request event traces in order to understand the per-request behavior in traced server workloads.

Server request traces:
From any machine in the department graduate/research network, you can find request traces for four server workloads at /p/key-search4/kshen/traces/csc258-requesttrace/. The traces are in four sub-directories:

For the purpose of this assignment, you don't have to understand high-level semantics of these application workloads. But knowing them may help understanding the results of the trace analysis.

In each sub-directory, you will find around 4000 files, each of which corresponds to the event trace of one request. The name of each file is in the format of tid0000xxxx.trace, in which xxxx indicates the time order of the request arrival --- for instance, request tid00001000 arrives right before tid00001001, which in turn arrives right before tid00001002.

The format of each request event trace file is described as follows. The first line is always "Request Type: ..." which indicates the type or input of this particular request. There may be a few more lines of overall request description and some empty lines before the traced events. Each event is in the format of "event: etype x, pid y, time z, ...".

Later parts of the event format depends on the event type and they should be mostly self-explanatory. Feel free to ask the instructor if you have any questions. Note that there can be more than one spaces as field delimiters. Do NOT assume there is a single space between adjacent fields.

The traces were collected in Linux operating system version 2.6.10. You might not care about the underlying operating system in your trace analysis and I am providing this information just in case. For instance, if you care to know the semantics of each system call id, you can start looking at the bottom of /u/kshen/downloads/linux-2.6.10/arch/i386/kernel/entry.S. As another example, process id 0 indicates the idle process in Linux.

Task #1: plot CPU time distribution
Your first task is to parse each request trace file to extract the aggregate CPU time of each request. This can be done by aggregating all CPU running spurts, each of which is marked by a pair of adjacent CPU switch-in/out events. Note that there is a chance that some CPU switch in/out events are lost in the trace --- you may find a switch-in event with no matching switch-out. Do some reasonable approximation in such cases.

After extracting the aggregate CPU time of each request for each workload, please plot the distribution of request CPU time for each of the four workloads. In other words, there should be four plots each corresponds to one workload. Each plot shows the distribution of CPU time for all traced requests in this workload.

Task #2: CPU time prediction
In addition to the aggregate CPU time, you can also extract the system call events from each request trace file. In this task, you are asked to explore using request system call events to predict its aggregate CPU time. Specifically, given the knowledge of a request's system call events, the predictor should output a prediction of request CPU time.

For each workload, you divide its traced requests into two groups. You should use the first group to train a predictor that predicts request CPU time from its system call events. You are free to use any (simple or complex) learning techniques that you feel appropriate. Then you apply the predictor on the second group of requests to test its accuracy. Please also comment on the prediction results for the four workloads.

Extra credit work:
If you are interested and have the time, feel free to do any additional analysis on the provided server request traces. Good analysis results are those that help understand these workloads and their differences from the high level. Please contact the instructor if you want to discuss your idea of some possible extra credit work.

Turn-in:
You are asked to electronically turn in a written report (in PDF). The report should describe the results of your trace analysis (in graphical illustration in some cases). Describe important implications of your results and any further thoughts you developed through this process. You do not need to turn in any source code.

Grading:
50% for each of the two tasks. We will evaluate any submitted extra credit work at our discretion.

Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.