CSC252 Assignment 2
Sun Jan 28 17:59:09 EST 1996
In the previous assignment you wrote a program that could sort an arbitrary number of integers. In this assignment you will modify this program to account for a limited amount of main memory. Assume that your data is in a file but you can not read all the data in main memory due to limited memory space. In your case assume that you only have two megabytes of main memory space. In order to sort files which contain more than two megabytes of data you will need to use external sort.
External sort splits the input file in chunks that can fit in memory, sorts these in memory, writes the sorted results in temporary files, and then merges these sorted files into the final result. You can find an algorithm for external sort in Nicklaus Wirth's book ``Algorithms and Data Structures = Programs'' which is on reserve in the Carlson library.
After you have written an external sort I want you to run three versions of the program in as many different types of machines as possible. The undergraduate lab contains sparc1, sparc2, and sparc4 workstations so you should run on all those. The three versions of the program are the following:
Obviously the first two runs do not require external sorting since the data fits in the amount of memory available in your program. Measure the run time of all versions on all machines. What is the relative performance of each version of the program across machines? Why? How does the performance of your program compare with the performance of other standard benchmarks for this same set of machines? Standard benchmarks include SPEC, Whetstone, Dhrystone, the Livermore Loops and others. The URL for the SPEC benchmarks is http://performance.netlib.org/performance/html/spec.html.
Homework is due February 7th. Turn in a report with the measured run time of your programs and how it compares with the reported performance of these machines on other commercial benchmarks. Homework is due February 7th. Start early since this homework is much harder than the previous one!