Theory of Structured Parallel Programming

1. Introduction


2. Parallelism and Concurrency

2.1 Unstructured Parallelism - True Concurrency

2.2 Structured Parallelism

2.3 From Unstructured Parallelism to Structured Parallelism

2.4 Foundation of Unstructured and Structured Parallelism


3. Truly Concurrent Process Algebra

3.1 Operational Semantics

3.2 Proof Techniques

3.3 Basic Algebra for True Concurrency

3.4 Algebra for Parallelism in True Concurrency

3.5 Recursion

3.6 Abstraction

3.7 Placeholder

3.8 Axiomatization for Hhp-Bisimilarity

3.8.1 APTC with Left Parallel Composition

3.8.2 Recursion

3.8.3 Abstraction

3.9 APTC with Asynchronous Communication

3.10 Applications


4. Guarded APTC

4.1 Operational Semantics

4.2 BATC with Guards

4.3 APTC with Guards

4.4 Recursion

4.5 Abstraction


5. Distributed APTC

5.1 Static Location Bisimulations

5.2 BATC with Static Localities

5.3 APTC with Static Localities

5.4 Recursion

5.5 Abstraction


6. Building Blocks Based Structured Parallel Programming

6.1 Orchestration and Choreography

6.2 The Building Block in Parallel Programming

6.3 Building Blocks Based Parallel Programming


7. Modeling and Verification of Parallel Programming Languages

7.1 Numbers and Arithmetic Expressions

7.2 Truth Values and Boolean Expressions

7.3 Storage Locations and Assign Command

7.4 Commands

7.5 Verification of Parallel Programs


8. Modeling and Verification of Parallel Programming Patterns

8.1 Parallel Control Patterns

8.1.1 Fork-Join

8.1.2 Map

8.1.3 Stencil

8.1.4 Reduction

8.1.5 Scan

8.1.6 Recurrence

8.2 Parallel Data Management Patterns

8.2.1 Pack

8.2.2 Pipeline

8.2.3 Geometric Decomposition

8.2.4 Gather

8.2.5 Scatter

8.3 Other Parallel Patterns

8.3.1 Superscalar Sequences

8.3.2 Speculative Selection

8.3.3 Workpile

8.3.4 Search

8.3.5 Segmentation

8.3.6 Expand

8.3.7 Category Reduction

8.3.8 Term Graph Rewriting

8.4 Verification of Parallel Programming Patterns


9. Modeling and Verification of Distributed Systems

9.1 A Model of Distributed Computations

9.2 Distributed Transactions

9.2.1 Two-Phase Commit Protocol

9.2.2 Three-Phase Commit Protocol

9.3 Authentication in Distributed Systems

9.3.1 Protocols Based on Symmetric Cryptosystems

9.3.2 Protocols Based on Asymmetric Cryptosystems

Appendix A - Parallel Programming Language
A.1 Syntax
A.2 Operational Semantics
A.2.1 Operational Rules of Aexp
A.2.2 Operational Rules of Bexp
A.2.3 Operational Rules for Com
A.3 Denotational Semantics
A.3.1 Denotational Semantics of Aexp
A.3.2 Denotational Semantics of Bexp
A.3.3 Denotational Semantics of Com
A.4 Relations between Operational and Denotational Semantics
A.5 Axiomatic Semantics
A.5.1 Extended Hoare Rules for Parallelism
A.5.2 Soundness of The Extended Hoare Rules
A.5.3 Completeness of The Extended Hoare Rules
A.6 Non-determinism
A.7 Communication
A.8 Confliction
A.9 Structuring Algorithm