taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Untitled Approved:

D a t e :
E.C. HALL, DIR. DIGITAL DEVEL
GUIDANCE AND NAVIGATION PROGRAM
Approved:
Date:
E
NAVIGATION PROGRAM
Approved:




DIRECTOR
INSTRUMENTATION LABORATORY
E-2097
A MULTIPROCESSING STRUCTURE
R.L.
A.L. Hopkins Jr., H.A.
March 1967
CAMBRIDGE 39, MASSACHUSETTS ACKNOWLEDGMENT
This report was prepared under
Project
sponsored by the
Manned Spacecraft Center of the
National
Aeronaut.1 and Space Administration
through Contract NAS
The publication of this report does no constitute approval by the National
Aeronautics and Space Administration of the findings or the conclusions therein,
It is published only for the exchange and stimulation of ideas. Extrapolation of Apollo experience to spacecraft computers of the next
generation indicates a need for digitai systems of greater computing and interface
activity, and of greater reliability, than has been realized to date.
An
collaborative multiprocessor structure in which a number
of processing elements are tied together by means of a single multiplexed data
bus is explored. At least one
assignment procedure is possible for which no
one processor has to act as master, and which can survive processor mal-
functions or the deletion or addition of processors to
bus, thus accomplishing
graceful degradation and reconfiguration of sorts. The single bus structure
as used here implies things about compilers for it, and also certain bandwidth
relationships between processors, bus and common memory.
Rough estimates
based on short extrapolations of circuit technology show that the structure is
probably realistic.

L. Alonso
A. L. Hopkins, Jr.
H. A. Thaler
March 1967
3
CONTENTS

Page
1.
. . . . . . . . . . . . . . . .
a.
Design Trends
. . . . . . . . . . . . . . . . . . . . .
7
2 Multiprocessors . . . . . . . . . . . . . . . . . . . . .
7
1 . 3 H a r d w a r e . . . . . . . . . . . . . . . . . . . . . . . .
9
Idealized Multiprocessor
. . . . . . . . . . . . . . .
11
2. 1 System Structure
. . . . . . . . . . . . . . . . . . . .
11
2.2 Processing Element Properties . . . . . . . . . . . . . .
13
2.2. 1
Storage . . . . . . . . . . . . . . . . .
13
2.2.2 Message Transmitter and Receiver . . . . . . . . .
13
2.2. 3 Self Error Detection
. . . . . . . . . . . . . . .
13
3.
Operation
. . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.1 Job Assignment . . . . . . . . . . . . . . . . . . . . .
15
3 . 2
. . . . . . . . . . . . . . . . . . . . . . . .
17
3.3 Degradation . . . . . . . . . . . . . . . . . . . . . . .
18
4.
Implications
. . . . . . . . . . . . . . . . . . . . . . . . .
19
4.1
Considerations . . . . . . . . . . . . . . . . .
19
4.2 Estimates of Performance . . . . . . . . . . . . . . . .
19
4.3 Example of Job Assignments . . . . . . . . . . . . . . .
20
4.4 Failure Processing . . . . . . . . . . . . . . . . . . .
22
5.
Common Erasable Memory Organization . . . . . . . . . . . .
23 1 .
This report is based on a paper by
Hopkins and Thaler with
some minor modifications and addition.;, mostly in the way of examples. I t
represents an approach (from among many) to computer organization which
seems to hold promise for both reliability and flexibility.
Many obvious areas
of great importance have not been
with, however, and this note is offered
more as a stimulant than as a serious, completed proposal.
1.1
Design Trends
In manned spacecarft to date, more uses have been identified for on-board
data processing than could be provided by the computers therein.
Computer
designers are
to anticipate this sort of problem by their natural tendency
to supply greater performance than the application seems to require, but have
been inhibited in the spacecraft area by apparently inelastic size, power and
reliability constraints. These constraints are relaxed when it is discovered that
mission success is imperiled by lack of adequate computer performance.
This
very likely arises at a time too late to reconfigure the computer within the mission
schedule.
Instead, mission objectives are apt to be restricted and a large soft-
ware effort is mounted to prepare and verify programs which squeeze out maxi-
mum performance. A lesson for the next spacecraft generation is that graceful
should be a fundamental requirement for the data processor and
other systems. This can result in the ability to profit from lessons learned in
the development phases of a mission by reconfiguring the on-board systems with
a minimum of impact upon the spacecraft.
In this paper, we review some general requirements for the next space-
craft computer generation and the forecast for hardware available in the coming
years.
In the absence of the development of a suitable self-organizing automaton,
the multiprocessor structure appears to be best suited to both the requirements
and the hardware available. We describe an idealized multiprocessor organiza-
tion and examine its performance in terms of the performance of its components.
1.2
Multiprocessors
Extrapolating the Apollo mission to a planetary mission has many pitfalls,
1. Alonso, R. L. , A. L. Hopkins, Jr. and H. A. Thaler, Design Criteria for a
Spacecraft Computer, NASA Electronics Research Center, Spaceborne
Multiprocessing Seminar, Cambridge, Massachusetts, October 1966.
n e w
a n d


the computers
point of view,
the
can be expressed independently of many
of
attributes
of
the
total
Size and power constraints should not
be expected to be much different than they are today.
However, reliability over
a period of several years adds a new dimension to the problem; for in a system of
perhaps millions of
electronic elements, it must be assumed that
perhaps many, will become inoperative either due to poor quality or to
severity of environment,
A hat is needed i system whose performance will not
be reduced
the minimum required
survival of the spacecraft, unless
failures of calamitous proportions occur.
new concept has arisen to supplement
the old notion of redundancy in which elements may fail, but the circuits which
contain them continue to function with no degradation.
If more elements fail than
the redundancy can cope with, the circuit will fail, and with it, the system.
The new concept, graceful degradation, implies an organization in which circuit
failure reduces, but does not suppress, the machines throughput. The brain has
this characteristic, but neuron-based automata have not yet exhibited promise
for miniature control computer applications.
In a multiprocessor organization, graceful degradation and graceful ex-
pansion are related properties, both made possible by the independence of the
constituent functional units: processors and memories. A multiprocessor is
more complex and expensive than a like-sized array of independent computers.
Its value is greater, for its performance depends on the number of units
functioning at any time. To increase the power of the machine, processors and
memories can be added without affecting parts previously present and, at least
equally important, without affecting existing programs. Each processor may be
made as powerful as the technology allows, but in the face of the reliability
problem,
it appears more desirable to build simple, reliable processors in
greater quantity so as to minimize the impact of a single processors loss.
The multiprocessor structure is compatible with several of the require-
ments of the spacecraft application besides that of reliability.
For one thing,
communication between the multiprocessor and all other spacecraft systems can
be handled in the same fashion as communication among the processors, thus
affording a unified treatment of the problem of input-output involving perhaps
hundreds of external functions. In a time-multiplexed serial transmission
structure, for example, a new system can be added to the multiprocessors
interface with virtually no changes other than the addition of access lines for the
new system to the coaxial cable (or waveguide) run.
Today, multiwire cable and
connector problems probably constitute nalf the battle in making spacecraft systems
work.
8 Another example ot the
well-suitedness is the natural
division of many spacecraft data processing tasks into short Jobs of fractional
second duration.
This is a result of the multiplicity of independent programs
serving the many systems involved, and also of the sampled nature of control
computations. Each program typically has a low duty cycle, requiring brief
service several times per second. Each instance of service can be treated as a

to be handled by any available and competent processor.
In the
spacecraft, repetition rates for jobs vary from a few tens per second
down, with no more than eight
running at a time.
In the future we can expect
on the order of a hundred programs running at once and tons or hundreds of
samples per second per program,
1