A Distributed Implementation of Flat Concurrent Prolog on Message-Passing Multiprocessor Systems

Inhaltsverzeichnis

• 1 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.