The point of this project is to allow you to refresh your memory on using Eclipse and JUnit testing and a bit of concurrency in Java. You will implement a class which can be used to compute the maximum value in a list of positive integers. Since the list might be relatively large, and you want to make use of all the computing power available (multiple CPUs), you will find the maximum value in a parallel manner, by using threads and intrinsic locks.
For our parallel max we will be passed a reference to a shared linked list that contains all of the values. This is a regular linked list, not a concurrent collect of any sort. Each thread will get a reference to this list. Each thread will maintain its own local max value. As each thread object has its run() method called, it will start a loop that repeatedly tries to remove a group of values from the shared list (the size of the group will be determined by a constant - if fewer than that amount of values remain, it will just remove the available values) and then from the values it obtained (if any) it will see if any of them are larger than the locally maintained max. If it is, that new value will become the new local max. If the shared list is empty, the thread will stop executing its run() method. Once all of the threads have completed, a main driver will collect all of the local max results and determine the maximum of those, which will then be the maximum of the original list.
The first thing to do is think about the above algorithm. Next, use Eclipse to check project0-spring2013-433 out of your CVS repository.
The project will have two packages; cmsc433_1301_P0 and cmsc433_1301_P0_Tests. In the first you will see two classes; ParallelMaxWorker.java and ParallelMaxDriver.java.
This is the driver class that will be told via the constructor how many worker threads will be used by the instance with it is asked to find the maximum value of a list. The constructor creates an array to hold references to the threads that will eventually be created. It has a method parallelMax that is passed a linked list containing the values of which the maximum should be returned. The parallelMax method will create the actual threads, start each thread working, and then wait for each thread to finish and consolidate the partial results. This class is partially written for you, but make sure you read through the provided code to understand what it does so that you know how to complete the class. Note that the list is shared yet in the provided code isn't protected in any way. How could that cause problems?
The run() method should have a loop in which it extracts blockSize values at a time from the shared list, tests to see if any of them are larger than any other values that the current thread has seen before, setting the local max appropriately. The getPartialMax() method returns the maximum of the elements of the shared list that was observed and processed during the run method. The posted ParallelMaxWorker class provides some starter code and a run method that needs to be implemented. Make sure you read the existing code and understand it before working on the run method. It is important that you do NOT lock the shared list for the entire time that you are doing the actual max finding. Also, if there are not blockSize values remaining in the list, then you should just extract what is left in the list.
This is a JUnit test class that you will implement. In order to be able to test your code, and make sure it's working properly, you'll first have to get past our public and release tests. After that, you will need to write several new JUnit tests of your own. The class currently contains two example JUnit test methods. The first is a fairly simple test of things. The second is a more rigorous test that is actually executed several times in a row. Read through these to get a feel for how they are testing your code. You will need to add three tests of your own. The first of these, testBigRandomListMax, is required to generate a list that contains 10,000 random positive integer values, creates a 50-thread version of ParallelMaxDriver, uses it to find the maximum in that list, and then checks that it got the right value. The second and third of these, testCornerCaseOne and testCornerCaseTwo, need to be designed by you to test two "corner case" scenarios that you think should be tested. For each of these you will need to provide (in the comment block) your reasons for selecting the corner case being tested.
NOTE: The public and release tests are preliminary. If you do something like call .run rather than .start and therefore don't have threads running correctly, you will lose all points.