With your earlier program, you were able to thwart the plans of the evil Gamemaster of Bademjan, but you have not yet escaped from his clutches. He was infuriated by the fact that you successfully solved all of his puzzles, but some lingering sense of honor keeps him from killing you on the spot. Instead, he has given you yet another set of puzzles to solve. These puzzles are all as long or longer than the earlier ones, and he has also promised to come back and check on you much earlier than before.
Now, you need to solve (virtually) the same problem as before, but you need to do it faster. What on earth are you going to do? Oh, that's right, you have a multicore laptop.
The problem is the same as the problem given in Project 2 with 3 major differences. The first is that you must design your code to use threads, the second is that you can no longer assume that all words will appear in the puzzle, and the third is that you must use Java API calls to time the amount of time it takes for you to actually solve the puzzle. You will also be expected to make trial runs of your program, time them, and interpret the results.
The input to your program will be a file redirected to stdin, formatted exactly as in Project 2.
To help you testing, we are providing you with another puzzle, puzzle2.txt. Many of the words in the list of words cannot be found in the puzzle. Be sure to test with puzzles from Project 2 as well as your own test cases. In addition, here is yet another puzzle, puzzle100.txt.
In the following section, implementation details about this project will be given.
You are required to divide the list of words you are looking for among a set of threads. Divide the list as efficiently as possible. The job of each thread is simply to find the location of each word. After all the words have been found (or shown not to be present), the main() method should print them all out.
You must create a new class called ThreadedPuzzleSolver. You are free to completely redesign your project or extend your existing PuzzleSolver class in order to solve this problem. If you implement this project in a reasonable manner, you should not need the synchronized keyword, the wait() method, or either of the notify() methods.
The number of threads you use to run the program should be determined by a command line argument passed into the main() method. As you know, the main() method takes an array of String variables passed in by the JVM. This array contains the white-space delimited arguments typed when your program was invoked. For example:
java ThreadedPuzzleSolver 4
In this example, the String "4" will be the argument in the 0-indexed position of the args array passed into main(). You would then be required to parse this String into an int so that you can set the number of threads created to be 4. You will only need to worry about the first (0-indexed) element in this array. You do not need to worry about error checking the arguments passed in. Your code should support any reasonable positive number of threads.
For this project, not all words on the list are guaranteed to exist in the puzzle. This change should be an easy addition to your existing code (assuming that it doesn't already handle this case).
When you print out a word that was not found, it should look very much like any other word, with its starting point at (0,0) and its orientation still set to UNKNOWN. For example, the output for the word "aardvark" if it wasn't found in the puzzle would be:
aardvark (0,0) UNKNOWN
You are required to time the execution of your program. For this project, you will time only the portion of your code that actually solves the puzzle. Reading the puzzle in and printing the list of found words will not be counted in the time taken. Print the time in seconds before list of found words. For example, sample output for puzzle500.txt run with 8 threads can be found here. Because you only need the time in seconds, the System.currentTimeMillis() will be sufficient.
You must do all your timing on the multicore cluster. To access these machines, log into Lore or one of your lab computers. To log into Lore from home, download PuTTY here or go through the more complicated process of downloading SecureCRT from IT@P here. With either program, connect to lore.cs.purdue.edu. Then, ssh into mc01 through mc16. To compare apples to apples, you really should try to run all your time trials on the same machine all at once. To be sure that someone else isn't interfering with your CPU-usage, use the who command to see who else is logged into the machine you pick. It may be impossible to get a machine all to yourself. However, it is unwise to run code on a machine when you recognize that 10 of your fellow classmates are doing the same thing.
You must run your program with 1, 2, 4, and 8 threads using input puzzle100.txt, puzzle500.txt, and puzzle1000.txt. For each number of threads, you should run each puzzle 5-10 times and average the time taken.
Record this information in a text file called analysis.txt. Explain how much speedup or slowdown you got overall. Try to explain the results you observe.
It is easy to get incorrect results when using threads. You may want to compare the output from your previous program with the output from the threaded version. To do so, you might need to collect the output from your programs in a file, instead of just looking on screen. Although you should now be familiar with redirecting input, you can redirect output as well, using the > operator. For example, to run both your programs on puzzle100.txt and save their output to two files called, respectively, output1.txt and output2.txt, you could run commands as follows:
java PuzzleSolver < puzzle100.txt > output1.txt java ThreadedPuzzleSolver 2 < puzzle100.txt > output2.txt
Then, to compare the two, Unix and Linux provide a tool called diff which simply tries to find all the differences between two similar files. To run diff on the output from above, you would type:
diff output1.txt output2.txt
The line-by-line differences will be enumerated.
This problem is a hard one to get impressive speedup on. Do not be discouraged if you cannot get much speedup. Your grade will not be affected by speedup.
When you have tested your code and are satisfied with the results, you will need to turn in all of your Java source files and your analysis.txt file. Make sure you run and test your code from the command line. DrJava does not easily support input redirection.
To turn in your project, navigate to the directory containing your source files. Then type the following command:
turnin -v -c cs190m -p project2b *.java *.txt
You can submit your code as many times as you want. Submit early and often.
Points listed here are out of 100, but, because this is a one week project, the weight of this project will be lower than usual.
30 points will be awarded based on the correct functioning of your code.
You can earn up to 30 points if you correctly use threads to search for words and divide the list evenly among the threads.
You can earn up to 10 points for correct output and formatting, including the proper handling of words that could not be found.
Another 20 points will be awarded based on the quality of your written analysis and the thoroughness of your timing data.
As always, you should use good programming style and commenting in order to receive full credit. Every Java file should have a comment header at the top giving your name, the course, the project, the date, and a short explanation of the class(es) in the file.
Note: Submissions which do not compile will automatically score 0 points.
As always, be sure to uphold the high standards of academic honesty required by this course. Failure to do so can lead to consequences as dire as failing the course and expulsion from the school. If you have any questions about whether or not a given action is allowed, please ask your instructor or TA.