Systolic parallel processing

목차 (Table of Contents)

• CONTENTS
• Ch. 1 The Systolic Mode of Parallel Processing = 1
• 1.1 Introduction to the Underlying Concept = 1
• 1.1.1 The Term 'Systolic Array' = 1
• 1.1.2 A Representative Example : A Hexagonal Systolic Array for Matrix Multiplication = 4
• 1.1.3 A List of Typical Features = 16
• 1.2 The Original Motivation :VLSI Design and Advantages of Systolic Arrays = 19
• 1.2.1 Problems of VLSI Design and Advantages of Systolic Arrays = 19
• 1.2.2 Systolic Arrays and the Limits of VLSI Technology = 23
• 1.3 The Present Trend :Efficient Algorithms for Massively Parallel Computers = 28
• 1.3.1 Systolic Algorithms and Parallel Computing = 28
• 1.3.2 Performance and Communication = 33
• 1.3.3 Global Interconnection Schemes in Parallel Computers = 36
• 1.3.4 Distributed-Memory Multiprocessors with Static Direct Local Interconnection - Natural Medium for Systolic Algorithms = 44
• 1.3.5 Pipelining, Granularity, SIMD／MIMD／SPMD, Communicating Sequential Processes, Wavefront Arrays, etc. = 56
• 1.3.6 Multiprocessing Systems Built to Support Systolic Algorithms = 74
• 1.3.7 A Speculation :Systolic Algorithms Even for Dataflow Computers? = 88
• 1.4 A List of Known Applications = 100
• 1.4.1 Linear Algebra Operations and Numerical Methods = 100
• 1.4.2 Operations with Polynomials and Integer Numbers = 102
• 1.4.3 Signal and Image Processing, Pattern Recognition and Image Analysis = 103
• 1.4.4 Non-Numerical Applications and Miscellaneous = 105
• Ch. 2 Defining and Expressing Systolic Arrays and Algorithms = 106
• 2.1 Using Automata Notions = 106
• 2.1.1 A Mixed Representation Form - Automata part = 106
• 2.1.2 Automata Models = 108
• 2.1.3 Cellular Automata = 114
• 2.1.4 Some Historical Remarks on Cellular Automata = 115
• 2.2 Defining Systolic Automata, Arrays, and Algorithms = 116
• 2.2.1 Structural Counterparts of Rippling, Broadcasting and Pipelining = 116
• 2.2.2 Systolic Automata and Systolic Arrays = 121
• 2.2.3 Examples of Systolic Structures = 125
• 2.2.4 Systolic Parallel Algorithms = 136
• 2.3 Expressing Systolic Algorithms = 139
• 2.3.1 A Mixed Representation From - Program Part :Specification of Cell Functions = 139
• 2.3.2 The Structure of a Systolic Array = 143
• 2.3.3 Input／Output Operations. Instruction and Data Flows = 144
• 2.4 Analysis and Comparison of Systolic Algorithms = 151
• 2.4.1 Simple Quantitative Measures for Performance Evaluation = 151
• 2.4.2 Comparison with Other Parallel and Sequential Algorithms = 157
• Ch. 3 Matrix - Vector and Matrix Multiplication = 160
• 3.1 Introduction to Vectors and Matrices = 160
• 3.2 Metrix - Vector Multiplication = 164
• 3.2.1 Multiplication with Dense Matrices = 165
• 3.2.2 Multiplication with Band Matrices = 174
• 3.2.3 The Concept of a c-Slow Algorithm and a c-Slow Array An Efficiency Improvement Technique = 178
• 3.2.4 Interleaving of Data Flows :Another Way to Improve the Efficiency of 2-Slow Systolic Algorithms = 185
• 3.3 Systolic Simulation of Feedforward Artificial Neural = 191
• 3.3.1 Multilayer Feedforward Artificial Neural Networks = 191
• 3.3.2 Systolic Simulation of the Network = 196
• 3.3.3 Learning by Error Backpropagation = 200
• 3.3.4 Implementing the Learning Procedure in a Systolic Array = 204
• 3.4 Matrix Multiplication = 209
• 3.4.1 Orthogonal Arrays - One Stationary Matrix = 210
• 3.4.2 Orthogonal Arrays - All Matrices Moving = 218
• 3.4.3 Hexagonal Systolic Arrays for Band Matrices = 228
• Ch. 4 Solving Systems of Linear Algebraic Equations = 236
• 4.1 Introduction to Linear Systems = 236
• 4.2 Gaussian Elimination = 238
• 4.2.1 Forward Elimination = 238
• 4.2.2 Back Substitution = 242
• 4.3 Systolic Arrays for Triangularization and LU／QR Decomposition = 243
• 4.3.1 Triangularization and LU Decomposition of Dense Matrices = 243
• 4.3.2 LU Decomposition of Band Matrices = 252
• 4.3.3 Triangularization by Neighbour Row Pivoting = 260
• 4.3.4 Orthogonal Triangularization and QR Decomposition by Givens Rotations = 264
• 4.4 Systolic Algorithms for Back Substitution = 272
• 4.4.1 Dense Triangular Systems = 272
• 4.4.2 Band Triangular Systems = 278
• 4.5 Systolic Implementation of Iterative Methods = 283
• 4.5.1 Iterative Methods for Linear Systems = 283
• 4.5.2 The Method of Successive Approximation = 284
• 4.5.3 Systolic Algorithms for Successive Approximation = 284
• Ch. 5 Further Problems of Linear Algebra = 191
• 5.1 Computing the Inverse of a Matrix = 291
• 5.1.1 The Inverse and Its Relation to Systems of Linear Equations = 288
• 5.1.2 Computing Systolically the Inverse of a Triangular Matrix = 293
• 5.1.3 Systolic Implementation of Greville's Algorithm = 303
• 5.2 Generalized Elimination = 311
• 5.2.1 Faddeevs Method = 311
• 5.2.2 Systolic Array Implementation of Faddeevs Method = 317
• 5.2.3 Gauβ-Jordan Elimination = 320
• 5.3 Computing the Characteristic Polynomial = 323
• 5.3.1 Eigenvalues and Eigenvectors = 323
• 5.3.2 Characteristic Polynomial and Characteristic Equation = 323
• 5.3.3 Computing the Characteristic Polynomial of Lower Hessenberg Matrix = 324
• 5.3.4 Implementing the Method in a Systolic Array = 328
• 5.4 Matrix Transposition and Related Operations = 334
• 5.4.1 Matrix Transposition on a 2-D Torus and 2-D Mesh = 334
• 5.4.2 Transposition on the Perfect Shuffle = 337
• 5.4.3 Transposition on a Binary Hypercube = 341
• 5.4.4 Comments on the Optimality of Parallel Algorithms = 351
• 5.4.5 Row-to-Diagonal and Column-to-Diagonal I／O Format Conversion = 354
• Ch. 6 Convolution and Linear Filters = 360
• 6.1 Convolution, Correlation, FIR and IIR Filters = 360
• 6.1.1 Definitions = 360
• 6.1.2 Filter Realizations and the Z-Transform = 365
• 6.1.3 Relation between Convolution and 1-D Pattern Matching = 370
• 6.2 Semi-Systolic Realizations = 371
• 6.2.1 Design with Rippling of the Output Sample = 371
• 6.2.2 Design with Brocdcasting of the Input Samples = 372
• 6.3 Unidirectional Full-Systolic Arrays = 375
• 6.3.1 Output Signal Moving Faster = 375
• 6.3.2 Input Signal Moving Faster = 376
• 6.4 Systolic Arrays with Bidirectional Data Flow = 378
• 6.4.1 2-Slow Algorithms and Their 1-Slow Derivatives = 378
• 6.4.2 A Completely Pipelined Bidirectional Algorithm with 100% Utilization = 384
• 6.4.3 Two-Phase Clock :Another Way to Achieve 100% Utilization = 386
• 6.4.4 Two-Phase-Clock Design for Correlation = 389
• 6.4.5 IIR Filter Realizations = 395
• 6.5 Bit-Level Systolic Convolver = 397
• 6.5.1 Bit-Level Systolic Arrays = 397
• 6.5.2 Bit-Level Cells for a Systolic Convolver = 398
• 6.5.3 Semi-Systolic Array for Bit-Product Computation = 400
• 6.5.4 Completing the Structure = 408
• Ch. 7 Operations with Polynomials = 410
• 7.1 Introduction = 410
• 7.2 Multiplication of Polynomials and Integers = 411
• 7.2.1 Relation to Convolution = 411
• 7.2.2 Systolic Realization of Polynomials Multiplication = 413
• 7.2.3 Systolic Multiplication of Binary-Coded Integers = 147
• 7.3 Division of Polynomials = 421
• 7.3.1 Underlying Algorithm = 421
• 7.3.2 Systolic Implementation of the Algorithm = 423
• 7.4 Computing the Greatest Common Divisor = 430
• 7.4.1 Definitions and Notation = 430
• 7.4.2 The Euclidean Algorithm = 431
• 7.4.3 Embedding the Euclidean Algorithm in a Systolic Array = 433
• 7.5 Polynomials Interpolation = 439
• 7.5.1 Iterated Interpolation = 439
• 7.5.2 Systolic Array Interpolation = 443
• 7.6 Evaluation of Polynomials = 448
• 7.6.1 Evaluation of Polynomials in Newton Form = 448
• 7.6.2 Horner's Scheme for the Evaluation of Polynomials = 451
• 7.6.3 Relation to the Division of Polynomials = 454
• Ch. 8 Comparison Problems = 458
• 8.1 Sorting = 458
• 8.1.1 A Systolic Bubble Sorter = 459
• 8.1.2 Systolic Implementation of the Odd-Even Transposition = 467
• 8.1.3 Further Algorithms and Complexity Remarks = 470
• 8.1.4 A Bit-Level Bubble Sorter = 473
• 8.2 Selection and Running Order Statistics = 478
• 8.2.1 The Problem and Its Applications = 478
• 8.2.2 Systolic Algorithm for Full Running Order Statistics = 480
• 8.2.3 Bit-Level Realization = 486
• 8.3 Sorting and Order Statistics for Rank Filtering = 491
• 8.3.1 Rank Filtering Using Window Overlapping = 491
• 8.3.2 Sorting-Based Approach(with an Example of Retiming) = 493
• 8.3.3 Rank Correction Scheme = 499
• 8.4 A Data Structure :Priority Queue = 504
• 8.4.1 The Problem = 504
• 8.4.2 Constructing Recursively a Systolic Priority Queue = 505
• 8.4.3 A Bit-Level Systolic Priority Queue Array = 509
• Ch. 9 Dynamic Programming and its Applications = 513
• 9.1 Introduction = 513
• 9.1.1 Application Examples = 514
• 9.1.2 Template Matching. Treating Linear Distortions = 516
• 9.1.3 Non-Linear Distortions. An Optimization Problem = 516
• 9.1.4 Dynamic Programming and Dynamic Time Warping = 520
• 9.2 Implementing the Dynamic Programming Recurrence in a Two-Dimensional Systolic Array = 523
• 9.2.1 Dynamic Programming Dependence Graph = 523
• 9.2.2 Two-Dimensional Systolic Array = 526
• 9.3 Implementation in One-Dimensional Arrays = 530
• 9.3.1 Array-Resident Test Pattern = 530
• 9.3.2 Bidirectional Data Flow = 535
• 9.4 Further Dynamic Programming Recurrences = 542
• 9.4.1 The Optimal Parenthesization Problem = 542
• 9.4.2 Dynamic Programming Approach to Optimal Parenthesization = 544
• 9.4.3 Implementing the Recurrence in a Systolic Array = 547
• Ch. 10 Computational Geometry = 561
• 10.1 Convex Hull = 563
• 10.1.1 A Simple Approximation Method = 564
• 10.1.2 Parallel Implementations = 568
• 10.1.3 Diameter and Farthest Pair = 573
• 10.1.4 Further Extensions and Concluding Remarks = 576
• 10.2 Nearest-Neighbours Problems = 579
• 10.2.1 Collection of Nearest-Neighbours Problems = 579
• 10.2.2 Cell Function Definition = 583
• 10.2.3 Systolic ANN Algorithms for One-dimensional Arrays = 585
• 10.2.4 Systolic ANN Algorithms for Two-dimensional Arrays = 594
• 10.2.5 An Example of Problem-Specific Partitioning = 597
• 10.2.6 Comparison between the 1-D and 2-D Arrays = 603
• Ch. 11 Systematic Design of Systolic Algorithms = 606
• 11.1 Dependence Graphs = 608
• 11.2 Systolic Array Dependence Graphs = 611
• 11.3 Extracting Systolic Algorithms from Dependence Graphs = 613
• 11.3.1 Interpretation of the Coordinates of the Vertices = 613
• 11.3.2 Obtaining a Systolic Array = 615
• 11.3.3 Cell Function(s), Program, Input／Output Operations = 617
• 11.4 Modifying the Properties of Systolic Algorithms = 620
• 11.4.1 Introduction = 620
• 11.4.2 Relation between the Structure of a Dependence Graph and the Properties of the Respective Systolic Algorithm = 621
• 11.4.3 Linear Transforms Retaining the Topology = 624
• 11.4.4 Obtaining Algorithms with Desired Properties = 629
• 11.4.5 Changing the Topology of a Dependence Graph = 634
• Ch. 12 Partitioning of Systolic Algorithms = 644
• 12.1 Partitioning, Algorithms Mapping, Design of Flexible Systolic Structures, Time Sharing = 644
• 12.1.1 Partitioning of Problem-Size Dependent Algorithms by Mapping onto Fixed-Size Processor Arrays = 640
• 12.1.2 Design of Flexible Systolic Structures = 647
• 12.1.3 Partitioning by Time Sharing = 648
• 12.2 Application of c-Slow Automata to the Realization of Parallel Structures = 650
• 12.2.1 Realizing Independent Processes by a c-Slow Automaton = 650
• 12.2.2 Realizing Parallel Array Structures = 654
• 12.3 Examples : Mapping Different Filter Banks onto the Same Fixed-Size Processor Array = 659
• 12.4 A Summary of the Technique and Alternative Approaches = 674
• 12.4.1 A Summary of the Partitioning Technique = 674
• 12.4.2 Alternative Relocation and Rescheduling Schemes = 676
• 12.4.3 Another Approach :Partitioning of Dependence Graphs = 679
• References and Additional Literature = 684
• Subject Index = 708