Obtaining first solution faster in parallel problem solving
Laxmikant V. Kalé, S. Vikram · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1988
This paper reports on a prioritizing scheme for parallel problem solving that concentrates the system resources on finding the first solution faster while keeping the storage requirement small. It uses bit-vectors to represent priorities. An efficient data structure for the concommitant priority queue is described. The data structure also ensures that at the two extremes, when the AND-OR tree reduces to a pure AND tree (or to a pure OR tree), the scheme approximates the behavior of the best schemes designed for pure AND (OR) trees. The authors present extended schemes to handle situations when there are dependences accross the subproblems of AND nodes. The scheme has been implemented within an interpreter for parallel logic programs, which can be used for problem-solving. The authors compare the performance of the schemes with the default and other simple schemes. One of the proposed schemes is shown to be quite effective in meeting the dual objective.