Concurrent LogLISP
Himanshu Nayak · 1989
The subject of this dissertation is the implementation of OR parallelism in the execution of Loglisp programs and the various issues arising in the exploitation of OR parallelism. The design of this parallel Loglisp uses concurrent searches, the existing sequential Loglisp developed at Syracuse University by Robinson and Sibert, and the Scheme based concurrent Lisp called Multilisp developed at MIT by Halstead. The implementation exploits lexical scope rules and closures. The hardware computing context is a fixed number of processors with shared memory architecture. The basic mode of execution is an invocation of a concurrent Logic call, and recursive invocations of Logic, but a capability for invoking concurrent calls of Logic with user's concurrent Lisp programs has also been provided. In addition, low level parallelism is exploited to make the new system more effective for the problems with little or no OR parallelism. The concurrent implementation is somewhat transparent to Loglisp users, that is, no special syntax or commands are needed to use this new system. However, when all the results of a query are requested, the order of results in the list returned is not predictable. Also there is no defined rule for selecting a subset of all instances when less than all are requested. The present implementation does not yield very useful performance. Nonetheless, it provides a reasonable framework for investigating concurrent logic implementations, and offers a useful degree of concurrency. We present empirical evidence that the present implementation, if run on a high-performance, concurrent Lisp system, can yield desired performance improvements. Indeed our system sometimes shows super linear speedup when a parallel search finds a solution early on.