Parallel Processing from Applications to Systems
- 1st Edition - March 1, 1993
- Imprint: Morgan Kaufmann
- Author: Dan I. Moldovan
- Language: English
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 9 7 5 1 - 4
This text provides one of the broadest presentations of parallelprocessing available, including the structure of parallelprocessors and parallel algorithms. The emphasis is on ma… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteThis text provides one of the broadest presentations of parallelprocessing available, including the structure of parallelprocessors and parallel algorithms. The emphasis is on mappingalgorithms to highly parallel computers, with extensive coverage ofarray and multiprocessor architectures. Early chapters provideinsightful coverage on the analysis of parallel algorithms andprogram transformations, effectively integrating a variety ofmaterial previously scattered throughout the literature. Theory andpractice are well balanced across diverse topics in this concisepresentation. For exceptional clarity and comprehension, the authorpresents complex material in geometric graphs as well as algebraicnotation. Each chapter includes well-chosen examples, tablessummarizing related key concepts and definitions, and a broad rangeof worked exercises.
* Overview of common hardware and theoretical models, including
algorithm characteristics and impediments to fast performance
* Analysis of data dependencies and inherent parallelism through
program examples, building from simple to complex
* Graphic and explanatory coverage of program transformations
* Easy-to-follow presentation of parallel processor structures
and interconnection networks, including parallelizing and
restructuring compilers
* Parallel synchronization methods and types of parallel
operating systems
* Detailed descriptions of hypercube systems
* Specialized chapters on dataflow and on AI architectures
algorithm characteristics and impediments to fast performance
* Analysis of data dependencies and inherent parallelism through
program examples, building from simple to complex
* Graphic and explanatory coverage of program transformations
* Easy-to-follow presentation of parallel processor structures
and interconnection networks, including parallelizing and
restructuring compilers
* Parallel synchronization methods and types of parallel
operating systems
* Detailed descriptions of hypercube systems
* Specialized chapters on dataflow and on AI architectures
Parallel Processing: From Applications to Systems
by Dan I. Moldovan
by Dan I. Moldovan
- 1. Introduction
- 1.1 Parallelism as a Concept
- 1.1.1 Models of Parallel Computations
1.1.2 Levels of Parallelism
1.2 Applications of Parallel Processing
1.3 Relation between Parallel Algorithms and Architectures
1.4 Performance of Parallel Computations
- 1.4.1 Need for Performance Evaluation
1.4.2 Performance Indices of Parallel Computation
1.4.3 Striving Toward Teraflops Performance
1.4.4 Mathematical Models
1.4.5 Performance Measurement and Analysis
1.5 Main Issues for Future research in Parallel Processing
- 1.5.1 Understand the Influence of Technology on Parallel Computer Designs
1.5.2 Develop Models for Large Parallel Computer Systems
1.5.3 Define the Fundamental Parallel Architectures
1.5.4 Develop a System Level Design Theory
1.5.5 Develop Theory and Practices for Designing Parallel Algorithms
1.5.6 Develop Techniques for Mapping Algorithms and Programs into Architectures
1.5.7 Develop Languages Specific to Parallel Processing
1.5.8 Develop Parallel Compilers for Commonly Used Languages
1.5.9 Develop the Means to Evaluate Performance of Parallel Computer Systems
1.5.10 Develop Taxonomies for Parallel Processing Systems
1.5.11 Develop Techniques for Parallel Knowledge Processing
1.6 Bibliographical Notes and Further Reading
1.7 Problems
2 Analysis of Parallelism in Computer Algorithms
- 2.1 Data and Control Dependencies
2.2 Parallel Numerical Algorithms
- 2.2.1 Algorithms without Loops
2.2.2 Matrix Multiplication
2.2.3 Relaxation
2.2.4 Recurrence Relations
2.2.5 QR Algorithm
2.3 Parallel Non-Numerical Algorithms
- 2.3.1 Transitive Closure
2.3.2 Dynamic Programming
2.3.3 Optimal Binary Search Trees
2.3.4 Subgraph Isomorphism
2.3.5 Parallel Sorting
2.4 Bibliographical Notes and Further Reading
2.5 Problems
3 Program Transformations
- 3.1 Removal of Output Dependencies and Anti-dependencies
3.2 Programs with Loops
- 3.2.1 Forms of Parallel Loops
3.2.2 Loop Transformations
3.3 Transformation of Index sets and Dependencies
- 3.3.1 The Basic Idea
3.3.2 Linear Transformations
3.4 Optimal Time Transformations
- 3.4.1 Parallel Computation Time
3.4.2 Selection of Optimal Time Transformation
3.5 Nonlinear Transformations
3.6 Bibliographical Notes and Further Reading
3.7 Problems
4 Array Processors
- 4.1 Single-Instruction Multiple-Data (SIMD) Computers
- 4.1.1 Local-Memory SIMD Model
4.1.2 Shared-Memory SIMD
4.1.3 Three-Dimensional SIMD Model
4.2 Interconnection Networks for SIMD Computers
- 4.2.1 Permutation Functions
4.2.2 Single-Stage Networks
4.2.3 Multistage Networks
4.3 SIMD Supercomputers
- 4.3.1 The Connection Machine
4.3.2 The Hughes 3-D Computer
4.4 Systolic Array Processors
- 4.4.1 Principles of Systolic Processing
4.4.2 Warp and iWarp
4.5 Associative Processing
- 4.5.1 The Structure of an Associative Memory
4.5.2 Algorithms
4.5.3 Associative Array Processors
4.6 Bibliographical Notes and Further Reading
4.7 Problems
5 Mapping Algorithms into Array Processors
- 5.1 Mapping of Algorithms into Systolic Arrays
- 5.1.1 Systolic Array Model
5.1.2 Space Transformations
5.1.3 Design Parameters
5.2 Algorithms Partitioning for Fixed-Size Systolic Arrays
- 5.2.1 The Partitioning Problem
5.2.2 Examples of Algorithm Partitioning
5.2.3 Partitioning Methodology
5.3 Mapping of Algorithms into SIMD Processors
- 5.3.1 Remapping Transformations
5.3.2 Design Tradeoffs Using Transformations
5.3.3 Relation Between Logical Transfers and Physical Transfers
5.4 Mapping of Algorithms into Mesh-Connected Networks
- 5.4.1 Mapping techniques
5.4.2 Mapping of Algorithms with the Perfect-Shuffle Permutation
5.5 Bibliographical Notes and Further Reading
5.6 Problems
6 Multiprocessor Systems
- 6.1 Multiprocessor Organization and Operating Principle
- 6.1.1 Shared-Memory Systems
6.1.2 Message-Passing Systems
6.1.3 Primary Issues in Multiprocessing Systems
6.2 Multiprocessor Interconnection Networks and Memories
- 6.2.1 Interconnection Organizations
6.2.2 Network Characteristics
6.2.3 NYU Enhanced Omega Network
6.2.4 Multiprocessor Memories
6.3 Mapping Algorithms into Multiprocessors
- 6.3.1 Parallelism Detection
6.3.2 Partitioning
6.3.3 Scheduling
6.4 Operating System for Multiprocessors
- 6.4.1 Operating System Functions
6.4.2 Synchronization
6.4.3 The MACH Operating System
6.4.4 Multiprocessor Operating System Organization
6.5 The Cedar Multiprocessor
- 6.5.1 Architecture
6.5.2 Software
6.6 Hypercube Computers
- 6.6.1 Hypercube Topology
6.6.2 Design Issues
6.6.3 From Hypercubes to Touchstones
6.7 Bibliographical Notes and Further Reading Problems
6.8 Problems
7 Data-Flow Computing
- 7.1 Data and Demand-Driven Models of Computation
- 7.1.1 Basic Models
7.1.2 Data-Flow graphs
7.2 Static Data-Flow Computers
7.3 Dynamic Data-Flow Computers
- 7.3.1 The Tagged-Token Principle
7.3.2 The Manchester Data-Flow Computer
7.3.3 The SIGMA-1 Data-Flow Computer
7.4 Combining Data Flow and Control Flow
- 7.4.1 Hybrid Data-Flow Computers
7.5 Bibliographical Notes and Further Reading
7.6 Problems
8 Parallel Processing of Rule-Based Systems and Semantic Networks
- 8.1 Parallelism Analysis in Rule-Based Systems
- 8.1.1 Rule-Based Systems
8.1.2 Parallelism in the Match Phase
8.1.3 Rule Interdependencies
8.1.4 Search Space Reduction
8.2 Multiple-Rule Firing
- 8.2.1 Compatibility and Convergence
8.2.2 Multiple-Rule Firing Models
8.2.3 Mapping RBS into Multiprocessors
8.3 Knowledge Representation and Reasoning Using Semantic Networks
- 8.3.1 Semantic Networks
8.3.2 Marker/Value Propagation Model
8.3.3 Reasoning on Semantic Networks
8.4 Parallel Natural Language Processing
- 8.4.1 Memory-Based Parsing
8.4.2 Parallel Linguistic Processing
8.5 Semantic Network Array Processor
- 8.5.1 Conceptual SNAP Architecture
8.5.2 Marker Processing on a SNAP
8.5.3 Examples of Knowledge Processing on a SNAP
8.6 Bibliographical Notes and Further Reading
8.7 Problems
Bibliography
Index
- Edition: 1
- Published: March 1, 1993
- No. of pages (eBook): 567
- Imprint: Morgan Kaufmann
- Language: English
- eBook ISBN: 9781483297514
Read Parallel Processing from Applications to Systems on ScienceDirect