Algorithm-Structured Computer Arrays and Networks - 1st Edition - ISBN: 9780127069609, 9781483267050

Algorithm-Structured Computer Arrays and Networks

1st Edition

Architectures and Processes for Images, Percepts, Models, Information

Authors: Leonard Uhr
Editors: Werner Rheinboldt
eBook ISBN: 9781483267050
Imprint: Academic Press
Published Date: 1st February 1984
Page Count: 438
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.


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



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


No. of pages:
© Academic Press 1984
Academic Press
eBook ISBN:

About the Author

Leonard Uhr

About the Editor

Werner Rheinboldt

Ratings and Reviews