PARALLEL PROCESSING OF COMBINATORIAL SEARCH PROBLEMS (DIVIDE-AND-CONQUER, BRANCH-AND-BOUND, LOGIC PROGRAMMING, DYNAMIC)

The search for solutions in a combinatorially large problem space is a major problem in artificial intelligence and operations research. Parallel processing of combinatorial searches has become a key issue in designing new generation computer systems. The research gives a theoretical foundation of parallel processing of various combinatorial searches upon which the architectures are based. In this thesis parallel processing of searching AND trees (graphs), OR trees (graphs), and AND/OR trees (graphs) are investigated, and different functional requirements of the architecture are identified. Some of the difficulties in building parallel computers for searching arise from the inability to predict the performance of the resulting systems. One important issue in implementing AND-tree searches is to determine the granularity of parallelism. In this thesis, the optimal granularity of AND-tree searches is found and analyzed. Another important result of this research is in finding the bounds of performance of parallel OR-trees searches and a variety of conditions to cope with anomalies of parallel OR-tree searches that involve approximations and dominance tests. In contrast to previous results, our theoretical analysis and simulations show that a near-linear speedup can be achieved with respect to a large number of processors. Logic programming, one of the foundations of new generation computers, can be represented as searching AND/OR trees. In this research, an optimal search strategy that minimizes the expected overhead of searching AND/OR trees is found. An efficient heuristic search strategy for evaluating logic programs, which can be implemented on a multiprocessor architecture (MANIP-2), is proposed. Dynamic programming problems, a class of problems that can be formulated in multiple ways and solved by different architectures, are used to illustrate the results obtained on graph and tree searches. Dynamic programming formulations are classified into four types and various parallel processing schemes for implementing different formulations of dynamic programming problems are presented. In particular, efficient systolic arrays for solving monadic-serial dynamic programming problems are developed