Starting with the program provided, use the sthread_block() function to develop a correct and efficient multithreaded quicksort function. The program consists of three files: quicksort.h, quicksort.c, and main.c. Write the multithreaded quicksort function in quicksort.c. Use the main program provided to test and time your multithreaded quicksort function.

1. Hand in your modified quicksort.c file.
2. Time sequential and multithreaded quicksort of 25 million items using 1, 2, 4, 8, 16, 32, 64, 96, and 128 threads. Hand in a table giving the execution time and speedup of multithreaded quicksort over sequential quicksort for increasing number of threads. Hand in a graph showing speedup of multithreaded quicksort over sequential quicksort for increasing number of threads.
3. Using the best number of threads for multithreaded quicksort of 25 million items, time multithreaded quicksort of 25 million items on 1, 2, 3, and 4 processors. Hand in a table giving the execution time and the speedup of multithreaded quicksort over sequential quicksort for increasing number of processors. Hand in a graph showing speedup of multithreaded quicksort over sequential quicksort for increasing number of processors.
4. Using the best number of threads for multithreaded quicksort of 25 million items, time sequential and multithreaded quicksort of 10, 20, 30, 40, and 50 million items. Hand in a table giving the execution time and the speedup of multithreaded quicksort over sequential quicksort for increasing number of items. Hand in a graph showing speedup of multithreaded quicksort over sequential quicksort for increasing number of items.
5. Hand in a short written performance analysis, discussing the issues that limit the speedup of multithreaded quicksort. Quantitatively estimate the overheads of thread management, load imbalance, and memory contention.

• Test your program with the BASE_LENGTH constant defined to be 2. This will help you to catch errors. Time your program with the BASE_LENGTH constant defined to be 64.
• Perform all timing experiments on a quad-processor Pentium Pro. For each experiment, perform 5 timing trials and report the average of the median 3 trials.
• Make sure that the machine is otherwise completely unloaded while you are performing timing experiments. Don’t touch the mouse or keyboard.
• Perform all timing experiments on programs compiled and linked using the standard Visual C++ 5.0 Release settings. Do not use additional compiler optimizations.
• For each experiment, use the value 123 as the seed for random generation of data.
• Make sure that you completely and precisely title and label tables and graphs. For example: (i) tables and graphs must have a descriptive title, (ii) columns and rows of a table must be labeled, (iii) axes of a graph must be labeled, and (iv) units must be given.
• It is an honor code violation to claim execution times that were not achieved. Claimed times must be repeatable.