Chess Problem SolverProblem CharacteristicsParallel ArchitectureImplementation StrategyBasic Data Unit: “Problem”Basic Software FunctionSearch RoutineSlide 8Master Process RequirementsSlave Process RequirementsSlide 11Possible EnhancementsSlide 13Slide 14Chess Problem Solver•Solves a given chess position for checkmate•Problem input in text formatProblem Characteristics•Search tree solving method•Very large computation•Low communication requirementParallel Architecture•Message passing using PVM•Master/Slave processes•Distributed task queues•Coarse grain tasks•Designed for future flexibilityImplementation Strategy•Basic data unit•Basic software function•Tree search routineBasic Data Unit: “Problem”•Contains all necessary information about the state of a position–Status of pieces on board–Whose turn to move–What player to solve the problem for–Maximum levels to search–The move that was made to get thereBasic Software Function•Breaks down a given problem using all possible moves.•Generates a new list of problems.•Is used to create the branches in the search tree.Search Routine•Examines a problem and determines the necessary action.•There are two possibilities:–the problem represents an end node•the node represents a possible solution•the node does not represent a possible solution•the problem is incomplete and the search levels have been exhausted–further investigation is necessary•break down the problemMaster Process Requirements•Input initial problem and break down into list of tasks•Determine the necessary number of slaves•Spawn the slave processes•Send tasks to slaves•Compile results obtained from slaves•Terminate the slaves when completeSlave Process Requirements•Wait for command from master (solve problem, transfer work, or terminate)•On solve problem command, solve the problem and return results to the master•On transfer work message, send work to another slave process•Terminate message kills the slave process.Possible Enhancements•Assign processors to a number of groups•Each group will have its own master (determined by lowest TID for example)•Assign a task to each group•Will cut down on communication to/from the master which cuts down stalled tasks•Only necessary for a large number of processors when using coarse grain
View Full Document
Unlocking...