Snyder / Jamieson / Gannon Algorithmically Specialized Parallel Computers

1. Auflage 2014
ISBN: 978-1-4832-6081-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 266 Seiten, Web PDF

Algorithmically Specialized Parallel Computers focuses on the concept and characteristics of an algorithmically specialized computer. This book discusses the algorithmically specialized computers, algorithmic specialization using VLSI, and innovative architectures. The architectures and algorithms for digital signal, speech, and image processing and specialized architectures for numerical computations are also elaborated. Other topics include the model for analyzing generalized inter-processor, pipelined architecture for search tree maintenance, and specialized computer organization for raster graphics display. The data base applications of the FETCH-AND-ADD instruction, distributed parallel architecture for speech understanding, and two parallel formulations of particle-in-cell models are likewise covered in this text. This publication is suitable for students, researchers and professionals concerned with algorithmically specialized computers.

Autoren/Hrsg.

Snyder, Lawrence

Jamieson, Leah H.

Gannon, Dennis B.

Inhaltsverzeichnis

1;Front Cover;1
2;Algorithmically Specialized Parallel Computers;4
3;Copyright Page;5
4;Table of Contents;6
5;CONTRIBUTORS;10
6;PREFACE;14
7;CHAPTER 1. ALGORITHMICALLY SPECIALIZED COMPUTERS;16
8;CHAPTER 2. ALGORITHMIC SPECIALIZATION USING VLSI;20
8.1;A MODEL FOR ANALYZING GENERALIZED INTERPROCESSOR COMMUNICATION SYSTEMS;22
8.1.1;A MODEL OF PARALLEL PROGRAMS;23
8.1.2;PRELIMINARY RESULTS;29
8.1.3;REFERENCES;30
8.2;Three VLSI Compilation Techniques: PLA's, Weinberger Arrays, and SLAP, A New Silicon Layout Program;32
8.2.1;1. Introduction;32
8.2.2;2. A Description of SLAP;32
8.2.3;3. PLA's Versus SLAP;33
8.2.4;4. Weinberger Arrays Versus SLAP;38
8.2.5;5. Conclusions;40
8.2.6;6. References;40
8.3;Sorting Records in VLSI;42
8.3.1;1. Introduction;42
8.3.2;2. High-Level Design Description;43
8.3.3;3. Low-level Design Description;46
8.3.4;4. Performance Estimates;49
8.3.5;5. Other Enhancements;50
8.3.6;6. Conclusions;51
8.3.7;References;51
8.4;A Pipelined Architecture for Search Tree Maintenance;52
8.4.1;1. Introduction;52
8.4.2;2. Architecture;52
8.4.3;3. Some Observations;53
8.4.4;4. Operations for Tree Maintenance;54
8.4.5;5. Some Implementation and Performance Issues;58
8.4.6;6. Summary and Future Research;60
8.4.7;References;60
8.4.8;Addendum;61
8.5;The Programmable Systolic Chip: Project Overview;62
8.5.1;I. INTRODUCTION;62
8.5.2;II. RATIONALE;63
8.5.3;III. ARCHITECTURE;65
8.5.4;IV. IMPLEMENTATION;65
8.5.5;V. PERFORMANCE EXAMPLES;66
8.5.6;ACKNOWLEDGMENTS;67
8.5.7;REFERENCES;67
9;CHAPTER 3. INNOVATIVE ARCHITECTURES;70
9.1;MPP: A HIGH-SPEED IMAGE PROCESSOR;74
9.1.1;I. INTRODUCTION;74
9.1.2;II. SYSTEM DESCRIPTION;74
9.1.3;III. ARRAY UNIT;76
9.1.4;IV. STAGING MEMORY;81
9.1.5;V. CONCLUSIONS;83
9.1.6;REFERENCES;83
9.2;PASM: A PARTITIONABLE SIMD/MIMD SYSTEM FOR PARALLEL IMAGE PROCESSING RESEARCH;84
9.2.1;I. INTRODUCTION;84
9.2.2;II. PASM ARCHITECTURE OVERVIEW;85
9.2.3;III. PASMOS OVERVIEW;90
9.2.4;IV. PASM PROTOTYPE;90
9.2.5;V. CONCLUSIONS;91
9.2.6;REFERENCES;92
9.3;SPECIALIZED COMPUTER ORGANIZATION FOR RASTER GRAPHICS DISPLAY;94
9.3.1;I. INTRODUCTION;94
9.3.2;II. POLYGON-BASED IMAGE GENERATION;96
9.3.3;III. LINE-GENERATING SYSTEMS;99
9.3.4;IV. CONCLUSIONS AND SUMMARY;101
9.3.5;References;102
9.4;Data Base Applications of the FETCH-AND-ADD Instruction;104
9.4.1;I. INTRODUCTION;104
9.4.2;II. WOUND/WAIT AND WAIT/DIE PROTOCOLS;105
9.4.3;III. Reservation Systems;106
9.4.4;IV. CONCLUSIONS;107
9.4.5;REFERENCES;108
9.5;RECURSIVE MACHINES;110
9.5.1;I. INTRODUCTION;110
9.5.2;II. RECURSIVE INSTRUCTION EXECUTION;111
9.5.3;III. RECURSIVE STORAGE;114
9.5.4;IV. RECURSIVE CONTROL;116
9.5.5;References;118
9.6;Algorithms + Alchemy = Architectures;120
9.6.1;I. INTRODUCTION;120
9.6.2;II. A CASE STUDY IN PARALLEL PERFORMANCE: VM VS AM;124
9.6.3;III. ONE SOLUTION TO THE VM TO AM MAPPING PROBLEM;127
9.6.4;IV. CONCLUSIONS;128
9.6.5;ACKNOWLEDGMENTS;129
9.6.6;REFERENCES;129
10;CHAPTER 4. ARCHITECTURES AND ALGORITHMS FOR DIGITAL SIGNAL, SPEECH, AND IMAGE PROCESSING;130
10.1;Optimal Implementation of DSP Algorithms on Synchronous Multiprocessors;134
10.1.1;I. INTRODUCTION;134
10.1.2;II. THE QUESTION OF OPTIMALLITY;137
10.1.3;III. THE MULTIPROCESSOR COMPILATION PROCEDURE;138
10.1.4;IV. DISCUSSION;142
10.2;ONE ARCHITECTURAL APPROACH FOR SPEECH RECOGNITION PROCESSORS;144
10.2.1;1. INTRODUCTION;144
10.2.2;2. PARTICULAR ALGORITHMS FOR DUR;145
10.2.3;3. APS;147
10.2.4;4. APS-II;149
10.2.5;5. A COMPARISON OF PROCESSORS;151
10.2.6;6. CONCLUSIONS;152
10.2.7;REFERENCES;153
10.3;A DISTRIBUTED PARALLEL ARCHITECTURE FOR SPEECH UNDERSTANDING;154
10.3.1;I. INTRODUCTION;154
10.3.2;II. THE SPEECH UNDERSTANDING TASK;155
10.3.3;III. PARALLEL PROCESSING AND SPEECH UNDERSTANDING;156
10.3.4;IV. THE DISTRIBUTED PARALLEL ARCHITECTURE;157
10.3.5;V. CONCLUSIONS;161
10.3.6;REFERENCES;161
10.4;ALGORITHMS AND ARCHITECTURES FOR SPEECH UNDERSTANDING;164
10.4.1;1 INTRODUCTION;164
10.4.2;2 A COMPUTATIONAL MODEL FOR THE INTERACTION BETWEEN AUDITORY, SYLLABIC AND LEXICAL KNOWLEDGE;165
10.4.3;3 ORGANIZATION OF THE LEXICAL KNOWLEDGE;167
10.4.4;4 CONCLUSIONS;173
10.4.5;ACKNOWLEDGEMENTS;173
10.4.6;REFERENCES;173
10.5;A VLSI ARRAY PROCESSOR FOR IMAGE PROCESSING;174
10.5.1;I. INTRODUCTION;174
10.5.2;II. IMAGE REPRESENTATION;176
10.5.3;III. SCAPE CHIP ARCHITECTURE;176
10.5.4;IV. SCAPE CHAIN CONTROLLER;179
10.5.5;V. DATA FIELD CONTROL;179
10.5.6;VI. DATA CHANNELS;180
10.5.7;VII. SCAPE SOFTWARE;180
10.5.8;VIII. SCAPE OPERATIONS;181
10.5.9;IX. COMPLEXITY AND PERFORMANCE FORECASTS;182
10.5.10;ACKNOWLEDGEMENTS;183
10.5.11;REFERENCES;183
10.6;COMPUTER ARCHITECTURES SPECIALIZED FOR MATHEMATICAL MORPHOLOGY;184
10.6.1;I. INTRODUCTION;184
10.6.2;II. MATHEMATICAL MORPHOLOGY;185
10.6.3;III. SPECIALIZED ARCHITECTURES;187
10.6.4;IV. CONCLUSIONS;191
10.6.5;REFERENCES;191
10.7;PYRAMID MULTI-COMPUTERS, AND EXTENSIONS AND AUGMENTATIONS;192
10.7.1;PARALLEL-PIPE PYRAMIDS; ARRAYS; SERIAL COMPUTERS;192
10.7.2;PYRAMIDS, ARRAYS, PIPELINES AND SERIAL COMPUTERS;193
10.7.3;A VARIETY OF TECHNIQUES FOR AUGMENTING A PYRAMID;194
10.7.4;SUMMARY DISCUSSION;199
10.7.5;REFERENCES;200
11;CHAPTER 5. SPECIALIZED ARCHITECTURES FOR NUMERICAL COMPUTATIONS;202
11.1;SOLVING THE LINEAR LEAST SQUARES PROBLEM ON A LINEAR ARRAY OF PROCESSORS;206
11.1.1;I. INTRODUCTION;206
11.1.2;II. CASE 1: ORTHOGONAL FACTORIZATION;208
11.1.3;II. CASE 2: THE SINGULAR VALUE DECOMPOSITION;212
11.1.4;REFERENCES;214
11.2;EIGENVALUE, SINGULAR VALUE AND LEAST SQUARE SOLVERS VIA THE WAVEFRONT ARRAY PROCESSOR;216
11.2.1;I. INTRODUCTION;216
11.2.2;II. LINEAR ARRAY TRIDIAGONALIZATION OF A SYMMETRIC MATRIX;218
11.2.3;III. DETERMINING THE EIGENVALUES OF A SYMMETRIC TRIDIAGONAL MATRIX;223
11.2.4;IV. COMPUTATION OF THE SVD BY MEANS OF A SQUARE ARRAY;224
11.2.5;V. CONCLUSION;226
11.2.6;REFERENCES;226
11.3;Development and Use of an Asynchronous MIMD Computer for Finite Element Analysis;228
11.3.1;I. INTRODUCTION;228
11.3.2;II. BACKGROUND;229
11.3.3;III. OVERVIEW OF THE FINITE ELEMENT MACHINE;229
11.3.4;IV. PROTOTYPE FEM;232
11.3.5;V. SOFTWARE MODELS;235
11.3.6;VI. OTHER FEM SOLUTION ALGORITHMS;236
11.3.7;VII. REFERENCES;237
11.4;TWO PARALLEL FORMULATIONS OF PARTICLE-IN-CELL MODELS;238
11.4.1;PARTICLE-IN-CELL MODELS;239
11.4.2;PIC ON A MASTER/SLAVE CONFIGURATION;240
11.4.3;PARALLEL PROCESSING PIC ON A RING CONFIGURATION;241
11.4.4;ESTIMATING PERFORMANCE OF THE MASTER/SLAVE IMPLEMENTATION;242
11.4.5;COMPUTATIONAL EXPERIMENTS;244
11.4.6;CONCLUSION;245
11.4.7;ACKNOWLEDGEMENTS;246
11.4.8;REFERENCES;246
11.5;MATHEMATICAL HARDWARE -DESIGN ISSUES AND RESPONSIBILITIES;248
11.5.1;INTRODUCTION;248
11.5.2;ALGORITHM SELECTION;250
11.5.3;PORTABILITY;250
11.5.4;PARAMETERS;252
11.5.5;ARITHMETIC;253
11.5.6;ROBUSTNESS;254
11.5.7;REFERENCES;255
12;CHAPTER 6. DOES GENERAL PURPOSE MEAN GOOD FOR NOTHING (IN PARTICULAR)?;258
12.1;SYNERGISM: THE KEY TO PARALLEL COMPUTING;262
12.2;DOES GENERAL PURPOSE MEAN GOOD FOR NOTHING?;264
12.3;Special-Purpose vs. General-Purpose Systems: A Position Paper;266