Chess Problem Solver Solves a given chess position for checkmate Problem input in text format Problem Characteristics Search tree solving method Very large computation Low communication requirement Parallel Architecture Message passing using PVM Master Slave processes Distributed task queues Coarse grain tasks Designed for future flexibility Implementation Strategy Basic data unit Basic software function Tree search routine Basic 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 there Basic 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 problem Master 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 complete Slave 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 strategy
View Full Document
Unlocking...