10.9 Threaded Problem-Solving Strategies

There are many techniques that reduce the time taken to solve intensive problems by using multiple threads to farm out parts of the problem. Here are a few strategies:

• Start multiple threads running to solve the whole of a particular problem, each starting from a different point in the solution space. The first to finish is the winner. This technique has, for instance, been used to speed up a graph-coloring problem. The specific strategy followed^[10] was to run several problem solvers at the same time, one at a higher priority than the others (the main thread). Normally the main thread would win, but on occasion, one of the background threads was lucky due to its starting point and finished quickly. By stopping the main thread if it looked to be far behind in the solution, the problem was solved in one-tenth of the time, on average, compared to the time taken when the main thread was not terminated. This improvement occurred in spite of the fact that this was a single-processor machine. The improvement comes about because the problem can be solved much quicker from some starting points than from others. There would be similar improvements if you also used several different problem-solving strategies in the various threads, where some of the strategies are sometimes quicker than others.

  ^[10] Charles Seife, "A Snail's Pace," New Scientist, 21 February 1998. This article reports on the technique used by Bernardo Huberman of Xerox Parc.

• In the same article, a variation of this strategy was applied to network connections for bypassing congestion. By opening multiple connections to download the same large data source on a highly congested network (the Internet), some connections were less likely than others to be slowed significantly or broken. This resulted in the data being downloaded faster. Of course, if everyone on the network used this technique, downloads would be slower for everyone.

• Break up the search space into logically parallelized search spaces. This does not work too well if the problem is entirely CPU-bound, but if there is any significant I/O or if multiple processors are available, this technique works nicely. An example would be searching a disk-based database for items. If the database is partitioned into multiple segments, then having one thread searching per segment makes the search faster (both on average and in the worst case).

• The classic blackboard architecture approach, in which multiple different solvers work on the parts of a problem in which they have expertise, independently of other solver threads. The threads use a "blackboard" (a sort of globally accessible hash table with published keys) to communicate. The blackboard posts both intermediate and full results. This allows a thread to pick up any (intermediate or full) results other threads may publish that help that particular thread with its own problem-solving routines. JavaSpaces is an implementation of blackboards.