Algorithm-Structured Computer Arrays and Networks

PrefaceAcknowledgmentsPart 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 DiscussionPart 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 MessagesPart 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 Discussion 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 PascalPL0Part 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 Lattices 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 FuturesPart 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 PossibilitySuggestions for Further ReadingReferencesGlossaryAuthor IndexSubject Index