1997-98

1997-98 CS 284a

Homework Five: Multithreaded Stream Mergesort

Handed out: Friday, 14^th November 1997.
Due in: 9:00am, Monday, 24^th November 1997.

Introduction

There are two parts to this homework, the first worth 5 points and the second worth 15 points. Part 1 is to time the execution overhead of flag operations. Part 2 is to develop an efficient multithreaded mergesort algorithm for streams implemented as linked lists with flags guarding the links. For Part 2, you will be graded entirely on how fast your program can sort a stream of 30 million items, as compared to sequential mergesort of a similar stream. Your results from the Part 1 will help you make the right programming decisions in Part 2.

Part 1

How long does an sthread_flag_set operation take in a sequential program on a single processor? How long does an sthread_flag_check operation take in a sequential program on a single processor (when the flag has previously been set)? It is up to you to decide how to time these operations. Hand in the program that does your timing and the measurements on which you base your final result. Also hand in a brief written description of the experiment that you performed.

Part 2

Starting from the stream_mergesort project that we provide, implement an efficient mergesort of a stream with links synchronized using flags. The project that we provide contains:

streams.h, streams.c:

This unit provides two stream types: unsync_stream and sync_stream. unsync_stream is a stream of blocks without flags guarding the links. sync_stream is a stream of blocks with flags guarding the links. Both these stream types are implemented for you. Look at the implementation, but don't change it in any way.

stream_mergesort.h, stream_mergesort.c:

This unit provides two stream-mergesort functions: seq_unsync_mergesort and multi_sync_mergesort. seq_unsync_mergesort is sequential mergesort of an unsync_stream. This is written for you. multi_sync_mergesort is multithreaded mergesort of a sync_stream. This is what you have to write.

main.c

This unit tests the two stream-mergesort functions.

What to hand in

Hand your results from Part 1 into the homework box in the lab. Write the date and time at the top of the front-page of your Part 1 results. When you are ready to submit your program from Part 2, create a folder called homework_5 at the top level of your user directory. Copy your stream_mergesort.c file into this directory. Send an email to cs284@cs telling us that you have completed the homework. In this email, tell us the value t (the number of threads) that you want us to use when we time your program on a randomly generated stream of 30 million items. Do not change the stream_mergesort.c file after you send us the email.

Part 2 Grading

Sequential mergesort of an unsynchronized stream of 30 million items with block size of 100,000 items takes approximately 60 seconds. First, we will test your program using an expanded test suite. If your program passes the test suite, we will time your program sorting a synchronized stream of 30 million items with block size of 100,000 items on a quad-processor Pentium Pro. We will use the value of t that you specify. We will time 4 trials and take the average of the median two trials to be your program’s time. Your grade for Part 2 (out of 15 points) will be given by the following formula:

points = 300/time

For example, if program runs in 20 seconds (a three-fold speedup over sequential), you will receive 15 points. If your program does not pass the test suite, you will receive up to a maximum of 7 points, depending on our opinion of the quality of your incorrect program

Rules

You must not alter the streams compilation unit in any way.

You must not alter the interface to the stream_mergesort compilation unit in any way.

You must implement the stream mergesort algorithm described in lectures.

Your algorithm must use the block size passed as an argument for all streams that it creates.

You must use the quicksort function provided for sorting blocks. You must not change the behavior of the quicksort function in any way.

You must only use the Sthreads library for multithreading.

The later of the time you turn in Part 1 and the time that we receive your email will determine the time we use for lateness deductions.