Parallel Processing from Applications to Systems - 1st Edition - ISBN: 9781558602540, 9781483297514

Parallel Processing from Applications to Systems

1st Edition

Authors: Dan Moldovan
eBook ISBN: 9781483297514
Imprint: Morgan Kaufmann
Published Date: 1st March 1993
Page Count: 567
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


This text provides one of the broadest presentations of parallel processing available, including the structure of parallel processors and parallel algorithms. The emphasis is on mapping algorithms to highly parallel computers, with extensive coverage of array and multiprocessor architectures. Early chapters provide insightful coverage on the analysis of parallel algorithms and program transformations, effectively integrating a variety of material previously scattered throughout the literature. Theory and practice are well balanced across diverse topics in this concise presentation. For exceptional clarity and comprehension, the author presents complex material in geometric graphs as well as algebraic notation. Each chapter includes well-chosen examples, tables summarizing related key concepts and definitions, and a broad range of worked exercises.

Key Features

* 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

Table of Contents

Parallel Processing: From Applications to Systems
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


No. of pages:
© Morgan Kaufmann 1993
Morgan Kaufmann
eBook ISBN:

About the Author

Dan Moldovan

Ratings and Reviews