Description
In this lab, you will be implementing the a cache-oblivious sorting algorithm,
the k-funnel sort. As the primary metric, we will be looking at cache
misses and try to beat the C standard library qsort as implemented on
PACE.
## Getting Started
Begin by obtaining the starter code from the github repository.
<pre><code>
git clone –recursive https://github.gatech.edu/omscse6220/lab5
</code></pre>
Note that this is the [GT github server](https://github.gatech.edu), so you will
need to authenticate with your GT credentials.
Optionally, you may choose use a git hosting service for your code. As always,
please **do not make your repository public** on Github or another git hosting
service. Anyone will be able to see it. If you feel the need to use a hosting
service for your project, please keep your repository private. Your GT account
allows you to create free private repositories on [the GT github server]
(https://github.gatech.edu).
Tasks:<br />
1. Implement the Funnel Sort algorithm in *funnel.c*<br />
2. Answer the questions in the file *short_answers.md* <br />
For more details on the funnel sort algorithm, you can refer to these
resources:<br />
-Slides: Funnel_Sort.pdf, included in the repository.<br />
-[“Cache-Oblivious Algorithms and Data Structures [PDF]”](http://erikdemaine.org/papers/BRICS2002/paper.pdf) [[Video]](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/lecture-24-cache-oblivious-algorithms-searching-sorting/)
## Programming
You need to fill in the implementation of funnel sort in *funnel.c*. You
can use any number of auxiliary functions as long as they are contained in
*funnel.c*. (To further reduce the load, we provide the reference code in the
file *funnel_skeleton.c*, which is a skeleton of one possible implementation.
Although it would be easier to follow the skeleton and comments in this file,
it is not necessary, feel free to develop your own version of implementation.
When using *funnel_skeleton.c* as a reference, please keep in mind your submission is *funnel.c*.)
Some utility functions are provided in *sort_utils.c* with their simple
explanations in *sort_utils.h* and timing functions in *timer.c* and *timer.h*.
## Correctness
You can test your code for correctness by doing the following:
<pre><code>
$ make clean
$ make sort
$ ./sort -c
</code></pre>
## Performance
To check the performance of your implementation against quick sort, you can
run the python script *check_with_perf.py*. You need to pass an argument
*SIZE* to the script to set up different array sizes for sorting. For eg.
“`./check_with_perf.py 8388608 “` to run with an array size of 8388608.
If you are on the cluster, you need to write a submission script like the provided *job.pbs*
(please don’t run directly on the login node).
Funnel sort will probably be slower than quick sort, but should have a lot less
data cache misses if the test case exceeds the cache size. To measure data
cache misses, the provided python script uses the ‘perf’ linux tool, a tutorial of ‘perf’ is [[here]](https://perf.wiki.kernel.org/index.php/Tutorial).
Our reference code has the performance on PACE as follows:
SIZE=2^23<br />
1. Runtime: 6.79 s (funnel / quick sort: 3.39)<br />
2. Data cache misses: 5433535 (funnel / quick sort: 0.594)
SIZE=2^24<br />
1. Runtime: 14.26 s (funnel / quick sort: 3.41)<br />
2. Data cache misses: 14344564 (funnel / quick sort: 0.610)
SIZE=2^25<br />
1. Runtime: 62.71 s (funnel / quick sort: 3.43)<br />
2. Data cache misses: 58022356 (funnel / quick sort: 0.424)
SIZE=50,000,000<br />
1. Runtime: 46.70 s (funnel / quick sort: 3.51)<br />
2. Data cache misses: 42815003 (funnel / quick sort: 0.455)
> Note that you may observe larger cache misses with Funnel Sort when the size is not large enough.
Your score is based only the cache miss ratio of the (funnel / quick sort), *not* the execution time. That’s because we expect funnelsort to run more slowly but nevertheless reduce cache misses. It’s an instance where the theoretically better option does not quite translate into practice! If there is any slight tuning involved, you should optimize for (minimize)
cache misses.
## Analysis
This lab includes a couple questions asking you to analyze various aspects of the Funnel Sort algorithm.
Please be sure to review and respond to them in *short_answers.md*.
## Deliverables
The deliverables for this lab are as follows:
* funnel.c
* short_answers.md
Please do not make any changes to the *Makefile*. If you include any additional headers or libraries, please make sure they compile as-is on the VM, PACE and through Bonnie.
## Submitting Your Code
When you have finished and tested your implementations, please submit using
submit.py as always, which will make a quick test for correctness.
After the deadline, the TAs will pull the code and perform some timing runs to
test your implementation.
These results along with a manual inspection of the code will determine your grade.
