Theory of Structured Parallel Programming
- 1st Edition - April 26, 2024
- Author: Yong Wang
- Language: English
- Paperback ISBN:9 7 8 - 0 - 4 4 3 - 2 4 8 1 4 - 6
- eBook ISBN:9 7 8 - 0 - 4 4 3 - 2 4 8 1 5 - 3
Theory of Structured Parallel Programming is a comprehensive guide to structured parallel programming corresponding to traditional structured sequential programming. The book p… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteTheory of Structured Parallel Programming is a comprehensive guide to structured parallel programming corresponding to traditional structured sequential programming. The book provides readers with comprehensive coverage of theoretical foundations of structured parallel programming, including analyses of parallelism and concurrency, truly concurrent process algebras, building block-based structured parallel programming, modelling and verification of parallel programming language, modelling and verification of parallel programming patterns, as well as modeling and verification of distributed systems.
There have been always two ways to approach parallel computing: one is the structured way, and the other is the graph-based (true concurrent) way. The structured way is often based on the interleaving semantics, such as process algebra CCS. Since the parallelism in interleaving semantics is not a fundamental computational pattern (the parallel operator can be replaced by alternative composition and sequential composition), the parallel operator often does not occur as an explicit operator, such as in the mainstream programming languages C, C++, Java, et al.
There have been always two ways to approach parallel computing: one is the structured way, and the other is the graph-based (true concurrent) way. The structured way is often based on the interleaving semantics, such as process algebra CCS. Since the parallelism in interleaving semantics is not a fundamental computational pattern (the parallel operator can be replaced by alternative composition and sequential composition), the parallel operator often does not occur as an explicit operator, such as in the mainstream programming languages C, C++, Java, et al.
- Introduces algebraic properties and laws for structured parallel programming, one of the foundational concepts of Computer Science
- Discusses modeling and verification of parallel programming language, parallel programming patterns, and distributed systems
- Demonstrates parallel programming language with its operational semantics, denotational semantics, axiomatic semantics, and their relations
Software engineers, programmers, and Computer Science researchers in academia and industry working in the field of concurrent and parallel computing
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
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
- No. of pages: 200
- Language: English
- Edition: 1
- Published: April 26, 2024
- Imprint: Morgan Kaufmann
- Paperback ISBN: 9780443248146
- eBook ISBN: 9780443248153
YW
Yong Wang
Dr. Yong Wang is an Associate Professor of Computer Science and Technology, Faculty of Information, at Beijing University of Technology. He holds a PhD in Computer Science from Beihang University, China. He has more than 20 years of research and teaching experience in parallel and distributed computing. Dr. Wang’s research interests include Theory of Parallel Computing, including algebraic theory for true concurrency and its extensions and applications, algebraic theory for reversible computing, and quantum process algebra and its application in quantum communication protocol. Dr. Wang’s other research interests include SOA, grid computing, cloud computing, and big data. Dr. Wang has published more than 120 research papers in leading Computer Science journals, including Wiley-Blackwell International Journal of Communication Systems, Springer International Journal of Theoretical Physics, and IEEE Transactions on Network and Service Management.
Affiliations and expertise
Associate Professor of Computer Science and Technology, Faculty of Information, Beijing University of Technology, ChinaRead Theory of Structured Parallel Programming on ScienceDirect