| This report explores several topics concerning the parallel implementation of logic programming. In the introductory chapter we define logic programs and describe a logic programming language that is suitable for parallel implementation. In the second chapter we treat the semantics of our language with particular attention to the role of negation as failure. The third chapter is an investigation of the parallel complexity of a class of logic programs that we call logical query programs, using the theoretical and abstract PRAM model of computation. In this chapter we show that certain logical query programs are in the complexity class NC, meaning that they have very fast execution times given enough processors. However, "enough processors" for inputs of size n turns out to be a polynomial in n of degree 6 (or more), an unrealistic resource requirement. Consequently, in the fourth and fifth chapters, we investigate more realistic approaches to implementation, based on transforming the logic program into a rule/goal graph, and embedding that graph into a general purpose processor interconnection network in the form of a rectangular grid. |
