Newsgroups: comp.arch,comp.ai,comp.ai.neural-nets,comp.parallel From: morgan@unix.sri.com (Morgan Kaufmann Publishers) Subject: Publication Announcement for PARALLEL PROCESSING by Moldovan Organization: SRI International, Menlo Park, CA Date: Fri, 8 Oct 1993 12:29:59 GMT Announcing A New Publication from Morgan Kaufmann Publishers PARALLEL PROCESSING FROM APPLICATIONS TO SYSTEMS by Dan I. Moldovan (University of Southern California) ISBN 1-55860-254-2; 567 pages; cloth; $59.95 U.S. / International prices will vary. 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. 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: 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 OTHER TITLES OF INTEREST FROM MORGAN KAUFMANN Computer Architecture: A Quantitative Approach John L. Hennessy (Stanford) and David A. Patterson (UC Berkeley) Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes F. Thomson Leighton (MIT) Parallel Computing Works! Geoffrey C. Fox (Syracuse), Roy D. Williams (Caltech), and Paul C. Messina (Caltech) ORDERING INFORMATION: Orders may be placed by: U.S. Canada Phone: (800) 745-7323 (outside U.S.& Canada (415) 578-9911) Fax: (415) 578-0672 E-mail: morgan@unix.sri.com Mail: 2929 Campus Dr., #260 San Mateo, CA 94403 USA Europe/UK Phone: (0273) 748427 Fax: (0273) 722180 Mail: 27 Church Road, Hove, East Sussex, BN3 2FA, England Australia Phone: (02)566-4400 Fax: (02) 566-4411 Mail: Locked Bag 2, Annandale P.O., NSW 2038, Australia All other countries please contact our U.S. office. American Express, Master Card, VISA and Personal Checks drawn on U.S. banks accepted for payment. Shipping: In the U.S. and Canada, please add $3.50 for the first book and $2.50 for each additional book for surface shipping. For International shipping please add $6.50 for the first book and $3.50 for each additional book.