`
`I, RachelJ. Watters, am a librarian, and the Director of Wisconsin TechSearch
`
`(“WTS”), located at 728 State Street, Madison, Wisconsin, 53706. WTSis an
`
`interlibrary loan departmentat 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 WTSsince 2002,first as a librarian and, beginning in 201 L, as the Director.
`
`Through the course of my employment, I have become well informed aboutthe
`operations ofthe 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 operating
`
`procedures for materials at the University
`
`of Wisconsin-
`
`Madison Libraries. When a volume wasreceived by the Library, it would be checked
`
`in, added to library holdings records, and made available to readers as soonafterits
`
`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-
`
`MadisonLibrary collection. Exhibit A also includes a true and accurate copy of a page
`
`from this volume showing that this book waspart 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 stampsare records of when the book wasphysically
`
`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 backto
`the library by January 19, 1975. Based on this information, the date stamp on the back
`
`cover page indicates Multiprocessors and Parallel Processing (1974) wasreceived by
`
`the Engineering Library at University of Wisconsin-Madison on or before January 19,
`
`1975, and madeavailable to library patrons on or before January 19, 1975.
`
`I declare that all statements made herein of my own knowledgeare true andthat
`
`all statements made on information andbelief are believed to be true; and further that
`
`these statements were made with the knowledgethat willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 ofTitle 18
`
`of the United States Code.
`
`Date: February3, 2020
`
`Wisconsin TechSearch
`Memorial Library
`728 State Street
`Madison, Wisconsin 53706
`
`: ) y b ~——
`
`Rachel J. Watters
`Director
`
`=
`
`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 York @® London ¢ Sydney ¢* Toronto
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`Copyright © 1974, by John Wiley & Sons,Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`Nopart 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-Interscience publication.”
`1. Parallel processing (Electronic computers)
`I. Enslow, Philip H., 1933-
`ed.
`Il. Title.
`
`1974
`QA76.6.C64
`ISBN 0-47 1-16735-5
`
`001.6’4
`
`73-18147
`
`Printed in the United States of America
`
`100987654321
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`CONTENTS
`
`CHAPTER 1
`
`MOTIVATION FOR MULTIPROCESSOR
`AND PARALLEL PROCESSING SYSTEMS
`
`1
`
`Improving System Performance, |
`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,
`
`Multicomputer Systems, 11
`Satellite Computers, 12. Peripheral Stand-Alone Computer
`Systems, 13 Coupled Systems—General, 14 Coupled Sys-
`tems—Indirectly or Loosely Coupled, 15 Coupled Systems—
`Directly Coupled, 16 Coupled Systems—Attached Support
`Processor,
`\7
`
`Basic Multiprocessors, 19
`
`Definition of a Multiprocessor System, 19 Multiprocessor
`Developmentand Its Objectives, 21
`
`Historical Evolution of Concurrent Processors, 22
`
`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 Executivefor Each
`Processor, 85 Symmetric or Anonymous 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, = 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
`
`GLOSSARY
`
`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
`Digital Equipment Corporation DEC System 1055 and 1077, 204
`Goodyear Aerospace Systems STARAN Computer System, 210
`
`a7fs
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`xii
`
`QOmOozeraArxra
`
`INDEX
`
`Honeywell Information Systems 6180 MULTICSSystem 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 Multiprocessors, 250
`RCA Corporation Model 215 Military Computer, 257
`Sanders Associates OMEN-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
`
`iyiversti 63706
`jneesing ©
`asin
`Madison
`
`wtNehy
`Arie
`
`brary
`
`INTEL - 1015
`
`
`
`JA197S
`
`my
`
`3°75
`
`wy 11°79
`
`MY 5%
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`89037555964
`
`b89037555984a
`
`UNM
`
`INTEL - 1015
`
`
`
`SYSTEM ORGANIZATIONS
`
`29
`
`All modules are connected in parallel to the bus which may beafull
`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 advantageofutilizing a single buffer register in
`the interface and less cabling.
`It 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 busis that even if there were an equal numberof proces-
`sors and memories, they could notall 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” exampleof a single bus system, consider the Digital Equip-
`ment Corporation PDP-11 which exploits fully the flexibility of
`its
`
`V0
`channel
`
`i
`
`
`
`
`/0
`
`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 hereis often referred to as space-division switching.It is
`very similar to the technique utilized by most telephonecentraloffices.
`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 mannerto facilitate expansion. However, be-
`cause of the complexity of the functions that the switch may haveto per-
`form,it can become quite large and complex. The switch matrix andits con-
`trol circuitry for the maximum configuration of the Hughes H4400 (eight
`CPU’s or [OC’s and 16 memory modules) contains as many components as
`
`
`
`Figure 2-5 Crossbar switch system organization.
`
`INTEL - 1015
`
`INTEL - 1015
`
`
`
`38
`
`SYSTEMS HARDWARE
`
`
`
`Figure 2-11 Multiport 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 I/O unit and
`processor being given preference in the access to its “primary*’ memory
`module as shownin 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 whenthe 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 systemsit 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
`
`