Parallel depth first search. I: Implementation (Q1116343)

The depth-first search (DFS) is one of the most common techniques used in artificial intelligence or for solving various combinatorial problems and constraint satisfaction problems. Since many of the problems solved by DFS are highly computation intensive, there is a great interest in developing parallel versions of this algorithm. The paper presents performance results of a parallel formulation of DFS run on various parallel computers (Sequent Balance 21000, Intel Hypercube and BBN Butterfly). These results clearly show that while retaining the storage efficiency, the DFS can be speeded up by several orders of magnitude. Moreover, if parallel DFS expands fewer nodes than DFS, a speedup of greater than N using N processors can be observed (speedup anomaly). The authors' experiments also show that hypercube and shared- memory architectures are significantly better than the ring architecture. The main conclusion of the research is that the effectiveness of the parallel formulation is strongly influenced by the work distribution scheme and architectural features of the parallel computer system. As general remarks, the paper is self-contained, clear and of high quality. It is intended for specialists or students in final years in the field of artificial intelligence and parallel computers. [For part II see ibid. 16, No.6, 501-519 (1987; Zbl 0665.68049)].