Algorithm-Structured Computer Arrays and Networks

Algorithm-Structured Computer Arrays and Networks

Architectures and Processes for Images, Percepts, Models, Information

1st Edition - February 1, 1984

Write a review

  • Author: Leonard Uhr
  • eBook ISBN: 9781483267050

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


Computer Science and Applied Mathematics: Algorithm-Structured Computer Arrays and Networks: Architectures and Processes for Images, Percepts, Models, Information examines the parallel-array, pipeline, and other network multi-computers. This book describes and explores arrays and networks, those built, being designed, or proposed. The problems of developing higher-level languages for systems and designing algorithm, program, data flow, and computer structure are also discussed. This text likewise describes several sequences of successively more general attempts to combine the power of arrays with the flexibility of networks into structures that reflect and embody the flow of information through their processors. This publication is useful as a textbook or auxiliary textbook for students taking courses on computer architecture, parallel computers, arrays and networks, and image processing and pattern recognition.

Table of Contents

  • Preface


    Part I An Introduction to Computers

    Introduction Toward Algorithm-Structured Architectures

    Arrays and Networks of Large Numbers of Closely Coupled Computers

    Toward Architectures That Mirror Algorithms' Information Flow

    The Traditional Single "Central Processing Unit" Serial Computer

    Problems for Which the One-CPU Serial Computer Is Inadequate

    Toward Developing Powerfully Structured Arrays and Networks

    Very Large-Scale Integration (VLSI) and Very Large Networks

    Steps Toward Efficient, Powerful Algorithm-Structured Architectures

    Chapter 1 Conventional Computers and Loosely Distributed Networks

    General-Purpose Computers and Turing Machines

    The General-Purpose Single-Processor Serial Computer Described

    How Computers Actually Work

    Graphs, Automata, Petri Nets, Information Flow, Network Flow

    Parallel Hardware Additions for Super (Traditional) Computers

    Networks of Loosely Coupled Distributed Computers

    Summary Discussion

    Part II Arrays and Networks Built or Designed

    Chapter 2 First Attempts at Designing and Organizing MultiComputers

    Mapping Process-Information Graph into Processor-Memory Network Flow

    A Survey of Early (Pre-LSI) Multicomputer Arrays and Networks

    Associative, Content-Addressable Memories (CAMs) and Logic-in-Memory

    Super Multicomputers

    Organizing Computers: Clocks, Controllers, Operating Systems

    The Overall Coordination and Operation of a Multicomputer Network

    Summary Discussion

    Chapter 3 Large and Powerful Arrays and Pipelines

    The General Architecture of Parallel Cellular Array Computers

    The Very Large LSI Parallel-Array Computer

    An Examination of Today's Very Large Arrays

    Pipelines of Processors

    Systems That Combine Array, Pipeline, and Specialized Hardware

    Summary Discussion: Arrays, Pipelines, Parallelism, VLSI

    Chapter 4 More or Less Tightly Coupled Networks

    Simple Structures: Buses, Rings, and Cross-Point Switches

    Lattices, TV-Cubes, Trees, and Stars

    Augmenting Trees for Density, Connectivity, and Structure

    Miscellaneous Interconnection Patterns

    Reconfiguring Network Topologies and Component Parts

    Network-Structured Programs and Algorithms

    Summary Discussion and Preliminary Comparisons

    Chapter 5 Parallel Parallel Computers

    The Great Variety of Possible Array, Pipeline, and Network Structures

    The Value of a Parallel Set of Parallel Resources

    Suggested Requirements for Parallel Parallel Systems

    Summary and Conclusions

    Chapter 6 Converging Pyramids of Arrays

    A Pipeline of Converging Stacked Arrays

    An Example of a Potentially Powerful yet Economical Pyramid

    A Combined Array/Network Architecture

    Possible Mixtures of N-Bit Processors

    Summary Discussion

    Chapter 7 Comparisons Among Different Interconnection Strategies

    Comparisons Between Arrays and Networks

    Comparisons Among Networks Using Formal Criteria

    Tests, Simulations, Estimates, Models

    Some Structural Similarities among Different Networks

    X-Trees, Hex-Trees, N-Trees, Arrays, and Lattices

    Moving from an N-Cube to an N-Lattice

    The Need to Build and Evaluate Networks, and to Handle Messages

    Part III Developing Parallel Algorithms, Languages, Data Flow

    Chapter 8 Formulating, Programming, and Executing Efficient Parallel Algorithms

    Programming Languages and Operating Systems for Parallel Programs

    Converting Our Programs and Ways of Thinking from Serial to Parallel

    Functional Applicative, Production, and Data-Flow Languages

    Language Development Systems to Specify Data Flow through Structures

    On Fitting Problem, Algorithm, Program, and Network to One Another

    Chapter 9 Development of Algorithm-Program-Architecture-Data Flow

    Developing Program, Mapping onto Network, and Program Flow

    Parallel versus Serial Versus Appropriately Structured Parallel-Serial

    An Example Formulation of a Program for a Parallel Pyramid Network

    Summarizing Observation

    Chapter 10 Some Short Examples Mapping Algorithms onto Networks

    Breadth-First and Heuristic Searches

    Searches for Question-Answering and Database Access

    Modeling Systems of Muscles and of Neurons

    Modeling the Whole System, in Interaction with Other Systems

    Parallel Algorithms for Processes That May Be Basically Serial

    Chapter 11 A Language for Parallel Processing, Embedded in Pascal

    A Brief Examination of Parallel Programming Languages

    A Description, with Examples, of PascalPL1


    Chapter 12 A Programming Language for a Very Large Array

    An Introductory Description of PascalPL0

    Coding an Array like CLIP in a Language like PascalPL0

    Summary of Experience with PascalPL0

    Part IV Toward General and Powerful Future Network Architectures

    Chapter 13 A Quick Introduction to Future Possibilities

    Very Very Large Networks

    Very Large Networks

    A Small, Powerful Network of Very Powerful Processors

    Very Very Very Large Arrays and 3D Lattices of Stacked Arrays

    Very Powerful Pipelines and Arrays and Trees of Pipelines

    A Summarizing Comment

    Chapter 14 Construction Principles for Efficient Parallel Structures

    The Great Variety of Possible Sources of Parallelism

    Additional Speedups and Efficiencies from Hardware and Software

    From Tightly Coupled to Loosely Coupled and Possibilities in Between

    Promising Construction Methods: General Principles

    Load-Balancing Processor, Input, Output, and Memory Resources

    Chapter 15 Designing VLSI Chip-Embodied Information-Flow Multicomputers

    Embedding Networks on VLSI Chips

    Examples of Related Analogous Design Problems

    Arrays of Processors Surrounding Local Shared Memories

    Designing in Terms of Chip Area

    Summary Discussion

    Chapter 16 Compounding Clusters and Augmenting Trees

    Arrays, Tree/Pyramids, N-Cubes

    Pyramids and Lattices

    Toroidal Lattices and Spheres

    A Summarizing Tentative Choice and Design of Attractive Structures

    Chapter 17 Pyramid, Lattice, Discus, Torus, Sphere

    The Basic Pyramid Structure

    Building Blocks and Modules

    Handling Input-Output, Control, and Fault Tolerance with an IOC Pyramid

    Examples of Attractive Pyramids


    Discus, Torus, Egg, Cone, Sphere

    Chapter 18 Three-Dimensional Array/Network Whorls of Processors

    Spheres within Spheres of Onion-Layered Faceted Arrays

    Dense Three-Dimensional Whorls with Programs Pipeline-Swirling through Them

    Limited Reconfiguring for Multiprogramming and Fault Tolerance

    Array/Networks That Are Sections of a Whorl

    Summary Discussion

    Chapter 19 Toward Very Large, Efficient, Usable Network Structures

    The Great Variety of Potentially Powerful, Efficient Networks

    The Promise, and Problems, in Future VLSI Technologies

    Allocating Gates to Networks of Processors and Memory on Silicon

    Pipe-Network Flow through Combined Array-Network Clusters

    A Final Word: The Immediate and More Distant Futures

    Part V Appendixes: Background Matters and Related Issues

    Appendix A Applied Graphs, to Describe and Construct Computer Networks

    Defining and Describing Connected Graphs

    Representing Successively Lower Levels of the Network as Graphs

    Some Formal Properties That May Be Desirable for Computer Networks

    Using Graph Theory to Help Increase Density

    Evaluating Networks in Terms of Local versus Global Density

    Some Graphs with Maximal Connectivity

    Gaining an Intuitive Understanding from, and Being Misled by, Graphs

    Embedding Data-Flow Graphs in Grids, and in Chip Area and Time

    Appendix B Bits of Logical Design Embodied in Binary Switches

    Some Basics of Logical Design Using Switches

    Realizing Arithmetic and Handling Information Using Two-Valued Logic

    Choosing among Equivalent Logical Expressions and Alternative Technologies

    Concluding Remarks

    Appendix C Component Cost and Chip Packing Estimates for VLSI

    A Quick Look at the Modular Way Computers Are Built

    Cost Estimates for Specific Types of Devices

    Allocating Resources to Different Types and Mixes of Processors

    Summary Discussion: Toward a More Powerful Distribution of Resources

    Appendix D Design of Basic Components and Modules for Very Large Networks

    Basic Components and Representations of a Computer Array or Network

    Constructing Building Blocks from Basic Components

    Some Alternative Possible Types of Linkages Between Components

    A Reconfigurable Processor-Store Group

    Two-Dimensional Building Blocks

    Hexagonal Facets, Hexagonal Solids; Moore Graphs, Dense Clusters

    N-Dimensional Compact Modules

    More Powerful 3×3×3-Modules and IOC Modules

    Building Larger Structures from Basic Modules

    Lattices, Cubes, Spheres, and Other Overall Architectures

    Appendix E Examples of Languages and Code for Arrays and Networks

    Examples of Data Flow and Functional Languages

    Examples of Languages for SIMD Arrays

    Example Fragments of PascalPL0 Code and the CLIP3 Object Code

    Examples of Statements and a Simple Program Coded in PascalPL1

    Appendix F Organizations in Crystal, Cell, Animal, and Human Groups

    Natural Organizations

    Human-Made Organizations: To Produce Goods, to Make Decisions

    The Problems with a Democracy or an Anarchy of Computers

    Groups, and the Operating Systems That Run Them

    Appendix G Messages (Information Passed Between Processors)

    What Is a Message?

    Contending with Messages: More Coordination, Hardware, or Silence

    Summary and Conclusion

    Appendix H What Is "'Real' 'Time'"?—A Metaphysical Aside

    Examples of Word Magic and Word Distortion, to Clarify

    The Limited Meaning within the Computer Context Is the Whole Meaning

    Summary, and an Impossible Possibility

    Suggestions for Further Reading



    Author Index

    Subject Index

Product details

  • No. of pages: 438
  • Language: English
  • Copyright: © Academic Press 1984
  • Published: February 1, 1984
  • Imprint: Academic Press
  • eBook ISBN: 9781483267050

About the Author

Leonard Uhr

About the Editor

Werner Rheinboldt

Ratings and Reviews

Write a review

There are currently no reviews for "Algorithm-Structured Computer Arrays and Networks"