`
`1, Rachel J. Watters, am a librarian, and the Director of Wisconsin TechSearch
`
`(“WTS”), located at 728 State Street, Madison, Wisconsin, 53706. WTS is an
`
`interlibrary loan department at the University of Wisconsin—Madison.
`
`I have worked as
`
`a librarian at the University of Wisconsin library system since 1998.
`
`I have been
`
`employed at WTS since 2002, first as a librarian and, beginning in 201 1,1as the Director.
`
`Through the course of my employment, I have become well informed about the
`
`operations of the University of Wisconsin library system, which follows standard library
`
`practices.
`
`This Declaration relates to the dates of receipt and availability of the following:
`
`Multiprocessors and Parallel Processing. (1974). Enslow Jr.,
`Philip H. (Ed.) New York, NY: John Wiley & Sons.
`
`Standard 0 eratin
`
`rocea’ures or materials at the Universi
`
`0 Wisconsin-
`
`Madison Libraries. When a volume was received by the Library, it would be checked
`
`in, added to library holdings records, and made available to readers as soon after its
`
`arrival as possible. The procedure normally took a few days or at most 2 to 3 weeks.
`
`Exhibit A to this Declaration is true and accurate copy of the front matter of
`
`Multiprocessors and Parallel Processing (1974), from the University of Wisconsin—
`
`Madison Library collection. Exhibit A also includes a true and accurate copy of a page
`
`from this volume showing that this book was part of the collection of the Engineering
`
`Library at the University of Wisconsin-Madison. Exhibit A also includes a true and
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`Declaration of Rachel J. Watters on Authentication of Publication
`
`accurate copy of a back page of the volume, showing several date stamps, beginning
`
`with the date “JA 19 75.” These stamps are records of when the book was physically
`
`checked out by a library patron. The designation of “JA 19 75” indicates that this book
`
`was checked out some time before January 19, 1975 to a library patron and due back to
`
`the library by January 19, 1975. Based on this information, the date stamp on the back
`
`cover page indicates Multiprocessors and Parallel Processing (1974) was received by
`
`the Engineering Library at University of Wisconsin—Madison on or before January 19,
`
`1975, and made available to library patrons on or before January 19, 1975.
`
`I declare that all statements made herein of my own knowledge are true and that
`
`all statements made on information and belief are believed to be true; and further that
`
`these statements were made with the knowledge that willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 of Title 18
`
`of the United States Code.
`
`Date: February 3, 2020
`
`j : §% [2 E ;
`
`Rac e1 J. Watters
`
`Wisconsin TechSearch
`
`Director
`
`Memorial Library
`728 State Street
`
`Madison, Wisconsin 53706
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`INTEL - 1015
`
`
`
`Multiprocessors
`
`and Parallel
`
`Processing
`
`COMTRE CORPORATION
`
`Philip H. Enslow. Jr.. Editor
`
`A WILEY-INTERSCIENCE PUBLICATION
`
`JOHN WILEY & SONS, New You'k
`
`0 London 0 Sydney 0 Totonto
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`Copyright © 1974, by John Wiley & Sons, Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`No part of this book may be reproduced by any means, nor
`transmitted, nor translated into a machine language with—
`out the written permission of the publisher.
`
`Library of Congress Cataloging in Publication Data:
`Comtre Corporation.
`Multiprocessors and parallel processing.
`
`“A Wiley-lnterscience publication.”
`1. Parallel processing (Electronic computers)
`I. Enslow, Philip H., 1933—
`ed.
`11. Title.
`
`1974
`QA76.6.C64
`ISBN 0-471-16735-5
`
`001 .6'4
`
`73-18147
`
`Printed in the United States of America
`
`10987654321
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`CONTENTS
`
`CHAPTER 1
`
`MOTIVATION FOR MULTIPROCESSOR
`AND PARALLEL PROCESSING SYSTEMS
`
`Improving System Performance, 1
`Performance Trends, 2
`Concurrency, 3
`Improving Reliability and Availability, 4
`Single-Computer Systems, 6
`
`_
`
`The Basic Five-Unit Computer— The Von Neumann
`Machine, 7 Direct Memory Access, 8 The Input/ Output
`Channel, 8 The Processor Unit, 11
`
`Multicomputer Systems, 11
`
`Satellite Computers, 12 Peripheral Stand-Alone Computer
`Systems, 13 Coupled Systems—General, l4 Coupled Sys-
`tems—Indirectly or Loosely Coupled, 15 Coupled Systems—
`Directly Coupled, l6 Coupled Systems—A ttached Support
`Processor, 17
`
`Basic Multiprocessors, 19
`
`Definition of a Multiprocessor System, 19 Multiprocessor
`Development and Its Objectives, 21
`
`Historical Evolution of Concurrent Processors, 22
`
`1
`
`ix
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`x
`
`CONTENTS
`
`CHAPTER 2
`
`SYSTEMS HARDWARE
`
`26
`
`Basic Requirements, 26
`System Organizations, 27
`
`Time-Shared or Common-Bus Systems, 28 Crossbar Switch
`Systems, 32 Multibus/Multiport Memory Systems. 36 Asym-
`metrical or Nonhomogeneous Systems, 39 Pipeline Sys-
`tems, 41 Examples of Pipeline Systems, 44 Parallel Systems—
`Array or Vector Processor Organizations, 44 System Organiza-
`tions Emphasizing Fault- Tolerance. 49
`Interconnection
`Paths, 53 Virtual Processors, 55 Multiple Arithmetic Units, 55
`
`Main Memory for Multiprocessor Systems, 58
`
`Overlapped Memory Access, 58 Memory Access Conflicts,
`59 Physical and Logical Memory Address Assignments, 62
`
`Input/Output Organization and Interfaces, 67
`Hardware System Reliability and Availability, 72
`
`Fail-Safe and Fail-Soft, 72 Reconfiguration, 74
`Summary, 75
`
`Multiprocessor Hardware, 75
`
`A Functional View of Organization, 77
`
`CHAPTER 3
`
`OPERATING SYSTEMS AND OTHER SYSTEM
`SOFTWARE FOR MULTIPROCESSORS
`
`81
`
`Introduction, 81
`Organization of Multiprocessor Operating Systems, 82
`
`Master Slave, 84 Separate Executive for Each
`Processor, 85 Symmetric orAnonymous Processors, 86
`
`Basic Functional Capabilities Required, 87
`
`Resource Allocation and Management, 88 Processor Inter-
`communication, 92 Abnormal Termination, 92 Processor
`
`Load Balancing, 92 Table and Data Set Protection, 93
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`CONTENTS
`
`xi
`
`Input/ Output Load Balancing, 93 Reconfiguration, 94
`System Deadlock, 94
`‘
`
`Special Problems for Multiprocessor Software, 96
`
`Memory Sharing and Accessing, 96 Table or Data Set Access
`and Protection, 98 Error Recovery, 100 Recognition and
`Exploitation of Parallelism, 102 Development and Test of
`System Software, 104
`
`Summary, 106
`
`CHAPTER 4
`
`TODAY AND THE FUTURE
`
`108
`
`Comparative Characteristics of Current Multiprocessor and
`Parallel Processing Systems, 108
`Attaining Multiprocessor System Design Objectives, 109
`
`Objectives/Advantages, 109 Availability, 109 Flexibility, 118
`Performance, 118 Witt's Comparative Evaluation, 120
`Disadvantages of Multiprocessors, 123
`
`Some Other Thoughts on Concurrency
`and Parallel Processing, 123
`
`Other Taxonomies, 123 Degree of Parallel Operation, 126
`
`The Future of Multiprocessors, 127
`
`REFERENCES
`
`G LOSSARY
`
`APPENDICES
`
`129
`
`132
`
`A.
`B.
`C.
`
`Parallel Element Processing Ensemble (PEPE), 139
`Burroughs Corporation Multiprocessor System D 825, 150
`Burroughs Corporation B 6700 Information Processing
`Systems, 169
`
`D. Control Data Corporation CDC 6500, CYBER-70/ Models 72-2X,
`73-2X, and 74-2X, 191
`
`7”!“
`
`Digital Equipment Corporation DEC System 1055 and 1077, 204
`Goodyear Aerospace Systems STARAN Computer System, 210
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`m
`
`QTUQFZZF‘F*”‘F9
`
`INDEX
`
`Honeywell Information Systems 6180 MULTICS System and 6000
`Series, 219
`
`Hughes AirCraft Company H4400 Computer System, 229
`IBM System/360 Model 65 Multiprocessor, 238
`IBM System/370 Models 158 and 168 Multip’rocessors, 250
`RCA Corporation Model 215 Military Computer, 257
`Sanders Associates OM EN-60 Orthogonal Computers, 264
`Texas Instruments Advanced Scientific Computer System, 274
`Sperry Rand Corporation UNIVAC 1108 Computer System, 290
`Sperry Rand Corporation UNIVAC 1110 System, 305
`Sperry Rand Corporation UNIVAC AN/UYK-7, 315
`Xerox Data Systems SIGMA 9 Computer System, 328
`
`336
`
`INTEL-1015
`
`INTEL - 1015
`
`
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`59037555q5u
`
`b89037555984:
`
`Illlllllllllll
`
`INTEL - 1015
`
`
`
`SYSTEM ORGANIZATIONS
`
`29
`
`All modules are connected in parallel to the bus which may be a full
`word wide or only one byte wide, or may be able to handle only a single bit
`at a time. As the bus becomes narrower, the control functions become
`more complex.
`The processor and peripheral units may be connected to a single bidirec-
`tional bus as shown in Figure 2—1 or unidirectional buses may be used as
`shown in Figure 2—2. In the latter case the transfer path is completed
`through the unit on the far left, the bus modifier. The trade-offs here are
`primarily in the implementation of a single bidirectional interface as op-
`posed to two unidirectional ones. The control logic of the latter is simpler;
`however, the former has the advantage of utilizing a single buffer register in
`the interface and less cabling.
`[t is also possible to have more than one time-shared bus as shown in
`Figure 2—3. This is approaching the topology of the next system con~
`figuration to be discussed, the crossbar system. The distinguishing feature
`of the time-shared bus is that even if there were an equal number of proces-
`sors and memories, they could not all be active at the same time because of
`the time—sharing property of the transfer path(s).
`Each packet that is placed on a bus must contain the data that are to be
`transferred and the address of the unit to which they are directed. There is
`no problem with conflicts between multiple packets arriving at a unit si-
`multaneously, since only one packet is on the bus at a time and a transmit-
`ter has to wait until the bus is free to place its packet on the line. Even
`though conflict resolution is automatic and not a severe problem, the con-
`flicts still exist and slow the operation of the ensemble considerably. Each
`unit on the bus must contain the circuitry necessary to recognize its address
`in a packet and respond accordingly.
`As a “simple” example of a single bus system, consider the Digital Equip-
`ment Corporation PDP-ll which exploits fully the flexibility of
`its
`
`‘
`
`l/O
`
`channel
` Processor
`
`Figure 2-1 Time-shared/common-bus system organization—single bus.
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`SYSTEM ORGANIZATIONS
`
`33
`
`established between the two units for the complete duration of the transfer.
`In contrast to the time-division switching done on the common-bus system,
`the technique used here is often referred to as space-division switching. It is
`very similar to the technique utilized by most telephone central offices.
`Although not quite as flexible as the single bus system, it is still relatively
`easy to add modules to a crossbar system if the switch matrix is large
`enough. The size of the system is not limited by the access capabilities of
`the individual functional units, since they all are connected by a single port.
`Conflicts in requests for the same memory module are resolved within
`the switch matrix utilizing one of several techniques possible. Since a full-
`time connection does exist, the effective transfer rates can be higher that on
`a single time-shared bus. Also several paths can be established si-
`multaneously.
`The crossbar matrix is totally seperate from the functional units and can
`also be designed in a modular manner to facilitate expansion. However, be-
`cause of the complexity of the functions that the switch may have to per-
`form, it can become quite large and complex. The switch matrix and its con-
`trol circuitry for the maximum configuration of the Hughes H4400 (eight
`CPU’s or lOC’s and 16 memory modules) contains as many components as
`
`
`
`Switch
`points
`
`Figure 2-5 Crossbar switch system organization.
`
`0
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`3B
`
`SYSTEMS HARDWARE
`
`
`
`Figure 2-11 MuItipon system with private memory.
`
`associated with the connecting point. These priorities can be utilized as the
`basis for settling conflicts for simultaneous access with each [/0 unit and
`processor being given preference in the access to its “primary" memory
`module as shown in Figure 2—10.
`Just as in the previous organizations, the width of the data transfer path
`can be any convenient and economical size. If the basic storage unit is a
`word and the data transfer path is less than one word wide, then special
`assemble and disassembly registers will have to be included in the interface
`points as well as special control circuitry so that the transfer path is not
`preempted and broken when the transfer of a word is only partially com-
`plete.
`It is not necessary that every memory module be connected to every
`processor. In fact in some systems it is essential that each processor have
`some “private memory” in which to store private tables for control func-
`tions, recovery, allocation of private resources, and so on (see Figure 2—11).
`There are reliability and recovery drawbacks, however, to the use of private
`memory. If a processor fails and the interrupted task must be completed on
`another processor, it may not be possible for the new processor to access
`the control information that it requires in order to do so.
`Considerable generality is lost
`if every processor cannot access any
`memory. Flexibility in relocatability of object programs, as well as in the
`operating, is lost. The advantages of a single copy of the operating system
`are obvious. Failure of a memory module as well as of a processor (dis-
`cussed above) represents a drawback to this organization if it has restric-
`tions on processor to memory access.
`In all systems of this configuration, the memory module must recognize
`and handle requests for access to the specific memory locations that it
`
`INTEL - 1015
`
`INTEL - 1015
`
`