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

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.