![]() Some Java classes you may find useful are: Thread, Callable, FutureTask. (Hint: you do not necessarily need to create a parallel thread at each level of the call to findSolution().) Make your best effort to create a parallel version with the smallest execution time for puzzle1. ![]() ![]() Discuss the possible trade-offs as to why the parallel version may not be much faster than the sequential version, or may even be slower in some cases. It may be as small as 10% rather than a factor of 2. If you run your code on a processor with more than 1 core, you should see some improvement in execution time compared to 1). Then record the execution time output for solving puzzle1 in Sudoku.java using this parallel version. Each Callable task will now be executed in a separate thread, as discussed in Lecture 34. Part 2: Convert the sequential task decomposition from Part (1) into a parallel task decomposition. Then record the execution time output for solving puzzle1 in Sudoku.java using this sequential version. Test your code by running findSolution() on the given tests, and devise at least 5 more tests for findSolution(). Part 1: Perform a sequential task decomposition on a solution to Assignment 11, creating a separate Callable task (as discussed in Lecture 31) for each possible value for the square located at (initialI,initialJ). In this assignment, you will build a parallel Sudoku puzzle solver by performing the enumeration of possible values for a square in parallel and combining the results of these parallel computations to return the set of all possible solutions to the initial puzzle. When all squares in a partial solution have exactly one value, it is a final solution. If the set of possible values for a square becomes empty, then the partial solution with that square is a dead end it cannot be extended (by binding the unexplored squares to values) to a final solution. It does so by binding the value of this square to each possible value and recurring on an unexplored square until no square has more than one possible value. Note that method findSolution() in PartialSolution.java has the task of enumerating different solutions starting from the square located at (initialI,initialJ). It is an honor code violation to see the materials for Homework 12 before you have submitted Homework 11. If you have not submitted Homework 11 as yet, please stop reading now. We are providing a complete sequential solution to Homework 11 as a starting point, but you are welcome to use your solution if you prefer. The goal of Homework 12 is to write a parallel Java program to solve Sudoku puzzles. Due: Friday 23 April 2010 at 9:59:59 am The assignment
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |