A distributed implementation of flat concurrent prolog on message passing multiprocessor systems

Inhaltsverzeichnis1 Introduction and Overview.1.1 General Introduction.1.2 Significance of the Work.1.3 Overall Organization.1.4 Syntax of Logic Programs.1.5 Data Manipulation by Unification.2 Concurrent Logic Programming.2.1 Process Interpretation of Logic Programs.2.1.1 The Process Model.2.1.2 Computational Behaviour.2.1.3 General Language Classification.2.2 Data-Flow Synchronization Techniques.2.2.1 Process Synchronization.2.2.2 Atomicity of Unification.2.2.3 Specification of Synchronization.2.2.4 Overall Comparison.2.3 Operational Semantics of FCP.2.3.1 FCP Data-Flow Synchronization.2.3.2 An Abstract FCP Interpreter.2.3.3 Formal Description of Computations.2.3.4 An Example for an FCP Program.3 Design of an Abstract FCP Machine.3.1 The Process Reduction Mechanism.3.1.1 Complexity Issues.3.1.2 The Process Reduction-Cycle.3.2 The Abstract Machine Model.3.2.1 A Sequential FCP Machine.3.2.2 Functional Machine Architecture.3.2.3 Process Scheduling.4 Concepts for a Distributed Implementation.4.1 Abstract System Architecture.4.1.1 Parallelization.4.1.2 Scalability.4.1.3 Communication and Synchronization.4.2 Distributed Data Representation.4.2.1 Data Representation at the Application Layer.4.2.2 Data Representation at the Machine Layer.4.2.3 Representation of Non-Variable Terms.4.2.4 Representation of Logical Variables.4.2.5 Representation of Process Structures.4.2.6 Distribution of Process Strucures.4.3 The Distributed Reduction Algorithm.4.3.1 Variable Migration.4.3.2 Synchronizing Reduction Operations.4.3.3 Distributed Process Suspension.4.3.4 Observations on Complexity.4.4 Distributed Termination Detection.4.5 Multiprogramming Facilities.4.6 Deadlock and Livelock Prevention.4.6.1 Prevention of Livelocks.4.6.2 Prevention of Deadlocks.4.6.3 Detection of Livelocks.4.6.4 A Combined Approach.4.7 Dynamic Work Load Balancing.4.7.1 The Process Selection Policy.4.7.2 The Load Balancing Policy.4.8 Distributed Garbage Collection.4.9 Related Work.5 Implementing FCP on Large Transputer Networks.5.1 Parallel Machine Architecture.5.2 Reduction Unit Architecture.5.2.1 The Reducer Subunit.5.2.2 The Distributor Subunit.5.2.3 The Router Subunit.5.3 Host Unit Architecture.6 Performance Measurements and Optimizations.6.1 Performance Measures.6.2 Possible Optimizations.7 Conclusions.