Overview

Assignment

The report should describe and compare the performance of the calendar queue and the binary heap. Four graphs that should be included in your report. These graphs should be presented professionally using plotting tools in common spreadsheets.

1. Time per event vs. bucket width for the calendar queue. Fix the number of events to be 1,000, fix the mean of the jump to be 1,000,000, fix the work to be 0, and fix the number of buckets to be 5,000. Plot the expected time per event for varying sizes of bucket width. Your plot should demonstrate that there is an optimal bucket width.
2. Time per event vs. number of buckets for the calendar queue. Fix the number of events to be 1,000, fix the mean of the jump to be 1,000,000, fix the work to be 0, and fix the bucket width to be approximately optimal for the number buckets equal to 5,000. Plot the expected time per event for varying number of buckets. Your plot should demonstrate that choosing a small number of buckets degrades performance and that as the number of buckets grows performance eventually levels off.
3. Compare the binary heap and the calendar queue for varying priority queue size. Fix the mean of the jump to be 1,000,000, fix and the work to be 0. Plot the expected time per event for each of the binary heap and the calendar queue for varying number of events ranging from 100 events to 10,000 events. Care must be taken to choose the bucket width and number of buckets to achieve good performance for the calendar queue for the various numbers of events.
4. Compare the binary heap and the calendar queue for varying work. Fix the mean of the jump to be 1,000,000 and the number of events to be 10,000. Fix a bucket width and number of bucket for near optimal performance for the calendar queue. Define the speed-up to be the expected time of the calendar queue divided by the expected time for the binary heap. Plot the speed-up for varying amounts of work, starting with work equal to 0.

Care must be taken to make sure that the numbers you generate are valid and reflect the true performance of two priority queues. You should use a function to measure the wall clock time. A good one to use is the standard C library function clock (defined in "time.h") which returns the number of clock ticks that have passed since your program started. There are also some non-standard functions available on our UNIX machines that may be more accurate. You will want to run the simulation for a number of steps before starting to measure the time per event. This is the "warm-up" period. How long should the warm-up period be? You will then want to run the simulation for long enough to get a good measurement of the time per event. How long is long enough? One common test is that if you run the simulation for K steps and 2K steps and there is little change in the time per event, the K steps is probably enough.

You will discover the need to make repeated experiments for each of your data points. If you are running your experiment on a multi-tasking system, then your timing measurement can be affected by other tasks running on the same machine. How many trials should you make in order to get good data? What data should be thrown out? A common experimental approach is to make a small number of trials like 15 and take the median as indicative of the correct value. Taking the average of 15 would include bad data. To minimize interference from other tasks you might consider running your experiments on a single user computer. Even on a single user machine that is also multi-tasking you should be careful to stop any background jobs.

Remember that your project report should contain a description of your experimental methodology.

What to hand in

You are required to hand in your project4 directory with your implementation of the binary heap and calendar queue. You may have implemented a number of different drivers to generate the data for your four plots. We don't need to see them all. You can just include one in your project4 directory. You also need to turn in a written report on Wednesday, June 3rd.

• Source Code:
If you generated your data on a machine other than a Sieg 329 Lab machine then be sure to compile and run your programs on a Lab machine before turning them in.
• README: - This is a text file describing your project implementation. This does not need to duplicate information in your project 4 report.
• Project 4 Report: This is a formal report on what you have learned from the experiments you did in this project. The report must be type written and well organized. It should include the four plots described above. For each plot write a paragraph that explains what the plot demonstrates about the performance of the calendar queue and/or the binary heap. Your report should contain your experimental methodology. Your report should contain a conclusion that gives the pros and cons of using a binary heap or calendar queue as the event queue in a discrete event simulator. The report should be less than 5 pages not including the plots. This report is to be turned in on Wednesday, June 3rd, in class.

% cd ~/326stuff/myproj4dir
% make clean
% cd ../
% turnin -c cse326=AA -p project4 myproj4dir

Warning

Some of your experiments can take a long time. You do not want to wait until the last minute to do this project.