This project was given as an assignment on multi-threaded programming. A code base, written by Ian D. Romanick, was given which, using a single-threaded algorithm, attempts to calculate the best possible move for a player in the board game Othello. From that base, I was instructed to make the algorithm run using multiple threads. The entire design process was handled with the knowledge that the program would likely be run on a dual-core system.
The program structure as a whole uses a master/worker solution. Upon the first running of the algorithm, all threads to be used are generated. These threads are kept idle between calls to the algorithm. When the algorithm is called, the initial work is added to the queue. This item is then pulled off the queue by a worker, which processes that item and pushes additional work on to the queue. As additional items are added, the other workers then wake up and pull items off the queue. During this time, the master thread will idle, periodically checking for the specified time limit, when it then adds poison pills to the queue to tell the workers to stop and idle again. The workers also track to watch for if all workers are idling, and if such a condition is found, the workers will poison the queue themselves, which will cause the master thread to wake and finish the algorithm prior to the time limit.
Each of the tasks is nearly entirely independent, with no dependencies to the completion of other tasks being required to complete another task, once generated. However, there is a preference that each level of the black/white tree be solved prior to starting on the next level, imposing a weak dependency. In addition, there is a dependency in the fact that the most tasks generate additional tasks. The above requirements then add in some shared data in the form of a shared queue from which tasks are taken and tasks are added. The ultimate solution also requires some shared data which stores the best move calculated so far.
The completed algorithm has moderate overhead required. The threads are generated the first time the algorithm is run, thus nearly eliminating the thread creation overhead. There is, however, signification synchronization overhead, with the requirement of loose ordering. All threads share a multi-level queue and one set of results. Adding and removing work from the queues likely has significant overhead, while updating the results likely holds minimal overhead, typically being a fairly quick compare, and sometimes a memory set.
Tasks, while having effectively no forced ordering due to data dependencies, are ordered to complete each level of the tree prior to beginning the next level. This is solved by using a shared queue, which in itself contains three sub-queues. The items are removed in a priority order, with the lowest level having the highest priority. All items from a lower priority must be removed before an item from a higher priority may be removed. Poison pills always have the highest priority, merely by always adding them to the front of every queue. Attempts to remove an item from an empty queue will cause the calling thread to sleep until new items are added (using a condition variable). The queues automatically grow in size, so it is impossible to add an item to a full queue; if the application cannot get enough memory, the program may crash, however. The queue generally has fairly high contention, with every work item typically adding a number of additional items to the queue; this design would likely need to be revised if it were to be used on a machine with a large number of processors.
