Parallel logic graph reduction system

A language for a parallel, logic graph reduction system is described in this dissertation. The language, descended from the SUPER and LOGLISP programming languages, is intended for massively parallel execution, and has been implemented on the Connection Machine. The language has several important features. First, the language is based on a generalized kind of logic programming incorporating aspects of functional programming. Second, the language is defined in terms of graphs; graph model is described which allows nodes to have arbitrary degrees so that massive parallelism can be achieved. Third, the language possesses a reduction semantics which is suitable for data-parallel implementation. We also describe a parallel implementation model for the language. Graphs are concretely represented by targets and links. Targets represent nodes. Links represent arbitrary edges; they mediate between operators and operands, thereby decreasing communication and making many decisions regarding reductions massively parallel. Parallel algorithms for reduction rules are also described. Two- or three-dimensional rendezvous virtual processor sets are used to assist in implementing complex parallel reductions. Two reduction models, the eager system and the resource-constrained system, are implemented. Some resource-consuming rules have different reduction schemes in the two models. Copying is interleaved with garbage collection and reduction in the resource-constrained system in order to alleviate the limitations of resources and permit computation to proceed in the presence of limited resources. We show the implementation results using a number of examples