Mapping Search Graphs Onto Arbitrary Processor Networks (or Making PROLOG Parallel)

: Logic programming and particularly PROLOG have long been considered good candidates for parallel execution. The absence of any formal control structures have prompted such claims. There are, however, some practical concerns when actually implementing a parallel version of standard PROLOG. Specifically, an economical balance between identifying parallel tasks and solving parallel tasks must be obtained. Furthermore, the balancing mechanism should operate at run time and have a low overhead. Paralogic, Inc. has implemented a parallel version of PROLOG on the INMOS transputer. The current release supports the "standard" Edinburgh syntax and will run PROLOG programs on one to "n" transputers without modification. 1. PROLOG as a Parallel Language If implemented properly, parallel PROLOG would have several advantages over conventional languages. First, parallel PROLOG will be independent of the number and connection of parallel processors. Programs would be expected to run on one to "n" p..