Stored Program Concept for Analog Computers
Prepared for
GEORGE C. MARSHALL SPACE FLIGHT
CENTER, NASA
Huntsville, Alabama
STORED PROGRAM
CONCEPT
FOR
ANALOG COMPUTERS
FINAL REPORT
EAI PROJECT 320009
NASA ORDER NASB8-21228
PRINTED IN U.S.A, JUNE 1968
STORED PROGRAM CONCEPT FOR ANALOG COMPUTERS
Fined: s Report
Prepared for
GEORGE C. MARSHALL SPACE FLIGHT
CENTER, NASA
Huntsville, Alabama
EAI Project #320009
NASA Order #NAS8-21228
Electronic Associates, Inc.
Princeton, N.J.
George Hannauer
Applications Engineer
Digital/Hybrid Programming
Department
5.
TABLE OF CONTENTS
INTRODUCTION
DEFINITION OF TERMS
2.1 Matrix, Inputs, Outputs
2.2 M and N, Expansion Factor E
2.3 Expander, Concentrator, Simple Matrix,
Composite Matrix
4 Rectangular Matrix
5 Programs
6 Abstract and Concrete Programs
COMPARISON WITH THE TELEPHONE SYSTEM
3.1 Size
3,2 Static versus, Dynamic Considerations
3.3 Interchangeability
3.4 Traffic Density
3.5 Fanout
3.6 Blocking Penalty
THREE-STAGE MATRICES (WITHOUT FANOUT)
4.1 Parameters of the Three-Stage Matrix
4.2 Static and Dynamic Accuracy
4.3 Optimizing the Matrix
4.4 Divisibility Considerations
4.5 Comparison with Rectangular Matrix
4.6 Summary
THREE-STAGE MATRIX THEORY WITH FANOUT
1 The Programming Array
2 Implementing a Program
3 Blocking
4 Construction of "Worst Case¥ Programs
5 Construction of Optimal Three-Stage Matrix
With Fanout
6 The Asymptotic Foomnula
7 Adequacy of the Three-Stage Matrix
8 Summary
9 Alternatives
DESIGN OF THE ANALOG CONFIGURATION (GENERAL CONSIDERATIONS )
6.1 The Cost per Input or Output
6.2 Analog Flexibility
6.2 Modular Design
6.4 Determining Module Size
6.5 Design of the External Matrix
6.6 Input Blocks, Output Blocks and Modules
6.7 Assignment of Components
10.
DESIGN OF THE ANALOG CONFIGURATION (SPECIFIC DETAILS)
7.1 Configuration Switching
7.2 Internal and External Access
7.3 Committed Pots
7.4 Description of a Module
7.5 Miscellaneous Components and Features
1 Logic
2 Track/Store Units
3 Hard-Zero Limits
4 Feedback Limiters
7.6 Detailed Component Description
Summers
Integrators
Multipliers
The Multiplier-Squarer (MSQ)
The Dual Function Generator
The Resolver Multipliers
The Comparator
Readout Lines
.
*
ON AUP WHF
e
e
SSI ONION NON ON OS
DDADADAADAA
7e7 The External and Internal Matrices
7.8 The Large System
RESULTS OF NASA SAMPLE PROGRAMS
8.1 Voyager, First-Stage Ascent
8.2 Saturn IV Stage Control, Phase 3
8.3 Summary of Problems Programmed
COMPUTER RESULTS
9.1 The Switch Assignment Algorithm
9.2 The Statistical Studies
' SOFTWARE
10.1 The Switch Assignment Routine
10.2 The Matrix Terminal Assignment Routine
10.3 Interconnection Routine
10.4 A Component Assignment Routine
10.5 Further Software Capabilites
10-1
10-1
10-1
10-1
10-2
10-3
C
1. INTRODUCTION
Eliminating the patchpanel has long been the dream of analog computer users,
for a number of reasons. One of these is psychological; the sight of a large
mass of wires hanging from the front of a computer is ugly and disturbing to
almost anyone except a true ''dyed-in-the-wool analog man'', and even some members
of this select group are more than willing to see the patchpanel give way to a
deck of cards or a punched tape. These aesthetic considerations alone are enough
to discourage many novices and cause them to turn to a digital computer with a
simulation language.
Aesthetics aside, there are sounder reasons for desiring to replace the
patchpanel with a switching matrix. The most obvious among these are the following:
a. Ease of Programming. Patching an analog problem is tedious and time-
consuming, and there is little doubt that an automatic patching system (in con-
junction with appropriate software) would greatly simplify programming. This is
desirable, not because programmers are lazy, but because they are expensive.
The cliche “time is money'' is as applicable to the analog computer (and programmer)
as it is to the digital.
b. Stored-Program Capability. Patchpanels can be stored, of course, but
good ones are expensive, heavy, and space-consuming. Cards and tape provide a
much more desirable storage medium.
c. Reliability. This is something of a question mark, since it is not clear
that a relay matrix, static card reader, or other system would be inherently more
reliable than a patchpanel. However, there is some reason to believe that it
would be, if only because it is stationary. Most of the wires that fall out of
present-day patchpanels do so because the panel must be carried away from the
machine for storage.
In addition to the above considerations, an additional application is con-
ceivable, namely, some form of multi-programming. By this I do not mean allowing
two people to share the same components in alternate 10-millisecond time intervals,
but rather allowing one user to use 75% of the components in a machine for a big
problem while another user uses the remaining 25% for a smaller problem. This is
possible in principle on a patchpanel, and, in fact, has been done at EAL's
Princeton facility, but is not very practical; the users get in each other's way.
It is possible that an automatic programming/patching system would have the
same effect on analog computer utilization that FORTRAN had for the digital
computer. IBM is currently publicizing the fact that before FORTRAN was developed,
a leading business magazine predicted that the total market for digital computers
(not the annual market) would be limited to about fifty consoles, because the”
programming was so involved and expensive! Since then, the total number of install-
ations has exceeded this estimate many times over. If the demand for analogs were
to expand by the same order of magnitude, the market would be a healthy one indeed.
Any automatic patching system will obviously be expensive. Previous attempts
to design such systems for medium-to-large systems (200 to 400 amplifiers and up)
have run into "the N“ problem", that is, the fact that the number of switches
necessary grows faster than linearly with matrix size. Keeping the total size
and cost of such a system within reasonable bounds requires a two-pronged attack
on the problem: -reducing the number of necessary switches to a minimum, and
designing a switch with sufficiently low cost, noise, contact resistance, and
crosstalk.
In 1967, NASA contracted with EAI for a feasibility study for the development
of an automated patching system. This report covers the results of phase 1 of
that study: the reduction of the number of switches.
The last study made of this problem within EAI was done by Joe Marshall and
Bill Hagerbaumer in 1961. Concurrently, Wolfgang Ocker undertook a similar study
for a DDA. The 231-R analog used by Marshall and Hagerbaumer as the basis of
their study was approximately equivalent to the 680 used in this study. Marshali
and Hagerbaumer concluded that between 25,000 and 35,000 switches would be necess-
ary. However, they did not actually test their proposed system on any actual
problems. Examining their proposed system in the light of actual problems, it
appears that the number of switches required would be somewhere between 50, 000
and 100,000.
At the start of this project, I was given a target value of "under 10,000
switches for a 680-size machine’. Thus the task is to effect a reduction by a
factor of five to ten,
This report describes two proposed systems: a "small" system (one 680)
requiring between 8,000 and 9,000 switches, and a "large" system (two 680"'s or
an 8800) requiring between 21,000 and 22,000 switches. Details of the design
are given in Chapters 6 and 7. Furthermore, the switching system appears ade-
quate to handle typical analog programs, including those furnished by NASA as
sample programs to implement (see Chapters 8 and 9). Thus the design goals
have been met.
It should be pointed out that the "typical 680" used in this report is
larger than the fully-expanded standard 680: it contains 30 integrators, 36
summers, 3 resolvers, 39 multipliers (not counting the 12 multipliers within
the resolvers) and 18 variable DFG's, It is possible to get all this equipment
into one system consisting of a 680 console and half of a resolver expansion
rack. Hence the large system (60 integrators, 72 summers, 6 resolvers, 78 multi-
pliers, 36 variable DFG's) would fit into two 680 consoles and one resolver
expansion rack,
This raises the question of whether the system should be implemented on an
existing analog (by hard-wiring the relay matrix to a patehpanel) or whether a
new machine should be developed. The system is obviously "cleaner" aad more
economical if the analog is designed from the ground up to accomodate the switch-
ing matrix, but obviously, any prototype matrix must be evaluated on an existing
machine. Furthermore, the possibility of producing a plug-in matrix for existing
machines as a standard product should not be overlooked.
I have kept the 680 in mind throughout this project as a possibility for
plug-in implementation of the matrix. This is in accord with the wishes of NASA
personnel and also with my own inclinations, since I am more familiar with this
machine than any other. The resulting design appears feasible for implementation
on a 680 (or 8800) with two qualifications. One of these is minor; the other
may be major.
1-3
The minor qualification has to do with configuration switches (that is,
the switches that convert a summer into an integrator or a multiplier into a
divider). Ideally, these switches should be within the analog console itself,
for two reasons: first, because they do not involve component~to-component
connection (and hence do not need to be in the main matrix), and second, be~
cause some of them switch summing junctions, and hence should be kept as close
as possible to the components themselves. There is a third reason: some of
them involve form-C or multi-pole switching and hence might be more economical
with conventional relays. To implement the configuration switching on a 680
or 8800 may require some changes in internal tray wiring, but I do not believe
this problem is insurmountable.
The more serious problem is the handling of pots. To keep the number of
inputs and outputs down (and to avoid the switching of relatively high-impedance
pot outputs) pots are committed to summer inputs, integrator inputs, integrator
Ic's, and comparator biasing. This, of course, increases the necessary pot
complement, since in any given problem, some of the pots will not be used. 1
strongly believe that the number of contacts saved justifies this decision
(further information on this point is given in Chapter 6), and there is no
inherent problem in increasing the pot complement in future machines if this
decision is, in fact, sound. However, it raises the question of what to do with
existing machines. The 680 configuration used in this report requires: over 300
pots, so that implementing the full system on an existing 680 would require a
pot expansion rack. The pots are the only components (except for the configur-
ation relays and the switching matrix itself) that need to be added to the 680
to complete the system.
As far as a prototype is concerned, the pots should be no problem, since a
prototype (for evaluating noise, crosstalk, and packaging problems) need not be
full-size. There should be enough pots on a fully-expanded 680 for implementing
a prototype matrix.
The proposed design divides the 680 into six nearly-identical modules.
Components within a module are interconnected by means of a small matrix, and
the components have limited access to inputs and outputs of other modules through
a large matrix. Hence, for a prototype, it is only necessary to build a matrix
for about one-third of the machine (two modules). This will allow the concept
and the hardware to be evaluated without any additional external analog equipment.
2-1
DEFINITION OF TERMS
This section defines most of the terminology to be used in this
report. It is divided into sub-sections to facilitate reference.
2.1 Matrix, inputs, outputs
A matrix is any collection of switches that allows terminals of one
type (called inputs) to be connected to terminals of another type
(called outputs). The use of the terms ''input' and 'output'' requires
some clarification; the inputs to the switching matrix are the outputs
of computing components and vice-versa. Thus, whether a given
terminal is called an input or an output depends on whether one looks
at it from the viewpoint of the computing components or from the
viewpoint of the switching matrix. Wherever there might be doubt,
the term ''matrix input'', ''component output'', etc. will be used.
When used alone, the terms "input" and 'output'' will be used from the
viewpoint of the matrix; that is, the term "input" will, by convention,
refer to a matrix input (a component output).
2.2 MandwN, Expansion Factor E
The letters N and M will be used to refer to the number of matrix inputs
and outputs respectively. In many cases, it is desirable to describe
the size of the matrix in terms of a single parameter, rather than two.
For this reason, we define the expansion factor of a matrix by E = M/N.
The matrix may then be described by specifying the size by means of
the parameter N and the ''shape'' by the parameter E. Note that when
two or more identical computers (each with N matrix inputs and M
matrix outputs) are slaved together, the result is a larger computer
with the same expansion factor. The expansion factor is thus independent
of size. It depends on the computer configuration. A preliminary
investigation indicates that E will lie in the range from 1.5 to 2.5 for
a practical analog programming matrix.
2.3 Expander, concentrator, simple matrix, composite matrix
A matrix with more outputs than inputs (E>1) will be called an expander.
A matrix for which E€1 will be called a concentrator. If E = 1, the Matrix
is a_ square matrix. The term ''concentrator" is taken from telephone
usage; the term "expander" is a natural extension.
Matrices may be classified according to the number of switching stages;
an n-stage matrix is one in which every path from an input to an output
passes through n switches. If some paths take more switches than
others, the matrix is a composite matrix; if all paths are of the
same length, it is a simple matrix. The telephone company uses
composite matrices (a long-distance call uses more switches than
a local call) and it seems reasonable to consider the same sort d
approach for analog programs.
2.4 Rectangular Matrices
A one-stage matrix is, by definition, a matrix in which each input-
to-output connection passes through a single switch. For N inputs
and M outputs, such a matrix is usually arranged (physically and in
circuit diagrams) in an N x M rectangular array, and hence is often |
called a rectangular matrix. If any input is to be connectable to any
output, then MN switches are required. Such a matrix will be called
a complete rectangular matrix. A rectangular matrix with fewer than
MN switches will be called an incomplete or restricted rectangular matrix.
Some restriction of matricies appears desirable (for example, a pot
output need not be connected to the input of another pot, nor to its
own input, nor to the inputs on a multiplier).
Note, in passing, that if the number of switches is expressed in terms
of the parameters N and E, a complete rectangular matrix requires
N*E switches. This gives the expected result that for rectangular
matricies of different sizes but with the same value of E, the number of
switches is proportional to the square of the matrix size. A straight-
forward rectangular matrix requires far too many switches to be
practical, but it serves as a natural basis of comparison for evaulating
other matrix configurations.
2.5 Programs
The purpose of any GPAC switching matrix is to implement programs,
From the matrix point of view, a program may be defined as a list of
connection statements of the form ''connect input i to outputj'’ where
14i < Nand1S j&M. However, not every such list represents a
valid analog program. We must add an additional restriction that no
two connection statements in a program involve the same matrix output.
Such a pair of connection statements would require that two analog
component outputs be tied to the same input (remember component
outputs are matrix inputs and vice versa). It is, however, perfectly
possible for a single matrix input to connect to many different outputs;
this corresponds to an analog component whose output drives several
other components. A matrix input that is to be conncected ton different
matrix outputs is said to have a fanout of n.
Since a matrix output connects to at most one matrix input, an alternative
mathematical description of a program is as a single-valued function
whose domain is the set of matrix outputs and whose range is the set
of matrix inputs plus one additional symbol which represents "no —
connection’. In other words, one may index the N inputs 1, 2, ...N,
with the symbol 'O'' representing "no connection" and define for
each output j ( 1£j & M) the function
f(j) = i if matrix output j is connected to input i
f(j) =. o if matrix output j is not used.
This approach makes it immediately obvious that the number of possible
programsfor an N by M matrix is (N+1)M If the matrix contains n
Switches, then it has 2" possible states, and hence if it is to be able
to handle all possible programs, we must have n eM logo(Mt1).
In fact, if N is one less than an integral power of 2, say N = 2k -1,
then it is possible to design a switching matrix with M log?(Ntl) = Mk
switches which can handle all programs. The catch is that each "switch"
must be a relay with several sets of contacts. Each matrix output is
wired to the arm of a form- C relay, and each contact of this relay is
wired to one of the arms of a 2 pole relay (2 formC sets of contacts),
and soon. This "binary tree'' design uses k relays per matrix output
(Mk relays total) and allows each matrix output to connect to any one of
the N = 2-1 inputs, or to nothing ( the last matrix input being grounded).
However, since the first input stage must be a relay with 2k-l form C
contacts, the size of the relays makes this scheme impractical. The
technique might prove practical with cascaded stepping switches rather
than relays, but the cost would probably be prohibitive.
Incidentally, if this scheme is implemented with relays, then since each
relay has twice as many contacts as the preceding one, the total number
of sets of form -C contacts per matrix output is 1+2+4+... +2k-1, which
sums to 2K-EN, Hence the total number of form C contacts for the
entire N by M matrix is MN. If each set of form-C contacts is replaced by
two form-A contacts, this binary tree method takes exactly twice as
many form A switches as a simple rectangular matrix.
2.6 Abstract and Concrete Programs
The definition of a program" in the previous section leaves out one
important point; the interchangeability of components. The analog
programmer does not (or, at any rate, should not) care which components
of a given type are used to solve a given problem. If integrator 35 and
integrator 45 are interchanged, the program (in the sense of the connection
statements) is changed, but the same analog problem is being solved.
2-4
To keep this distinction in mind, let us define a concrete program.
as a set of connection statements (or, equivalently a function from
outputs to inputs) in the sense of the last section. Two concrete
programs will be called equivalent if one is obtainable from the other
by permutation of components of similar type (i.e. renumbering the
integrators, the pots, the summers, etc.) An abstract program is
defined as an equivalence class of concrete programs. In other words
we ‘identify'' any two programs which are "abstractly equivalent". An
abstract program is essentially what the analog programmer has
produced after he has drawn the circuit diagram, complete with all
component interconnections, but has not written any nurmibers inside the
component symbols. After assigning all components, he has reduced
the abstract program toa concrete program.
A digital computer routine for implementing a program should probably
consist of two successive algorithms: a component assignment algorithm
for assigning components (thus reducing the abstract program to a concrete
one), followed by a switch assignment algorithm, which chooses appropriate
switch paths to implement the concrete program. Initially, it appeared
desirable to combine the two: that is, at each stage of the algorithm,
choose the "nearest'' component of the desired type and the choose the
best switch path to implement the desired connection. The result would
be a single algorithm assigning components and switch paths alternately.
This line of attack has proved fruitless. The two types of choices (choice
of component and choice of switch path) seem too dissimilar to ''mesh"
well, It now appears that two separate algorithms are preferable
(although if the switch-assignment algorithm experiences blocking, it
may be possible to re-assign a few components to relieve the blocking
and try again.
ee eee
3-1
3. COMPARISON WITH THE TELEPHONE SYSTEM
Any study of the automatic patching problemmust, at some point, make reference
to the experience of the Bell System. This is so for two reasons. The most obvious
reason is the success of the system in getting around "the N2 problem", that is,
the fact that the number of switches in any switching matrix grows faster than
linearly with the matrix size.
A system of over ten million telephones, which allows (with rare exceptions)
anyone to call anyone else must have a large number of switches. If a straight -
forward rectangular array were used, ten million phones would require 1014 switches.
Even at the ridiculously low price of a penny a switch, such a system would cost
1012 dollars, which is more than the entire country's annual Gross National Product.
Even more interesting is the marginal cost of adding one additional subscriber. If
this subscriber is to have direct access to all ten million existing subscribers,
ten million additional switches would be required. Using again the optimistic price
of a penny a switch, the subscriber would have to pay 100,000 dollars for the in-
stallation.
Now, of course, the Bell System does not provide direct access between sub-
scribers, but instead provides indirect access through several levels of switching.
It is the multi-stage nature of the switching system that prevents the number of
switches from growing excessively. In fact, as the number of telephones has in-
creased, the cost per telephone has actually decreased - a remarkable tribute to
the efficiency of the system.
The second reason for interest in the Bell System is that much of the published
literature on switching theory is based upon the particular switching problem faced
by Bell. In fact, the three-Stage matrix theory presented in Chapter 4 is based
on ideas originally published by Charles Clos in the Bell System Technical Journal.
Despite the wealth of published literature on the subject of switching theory,
there is very little that is relevant to the automatic analog patching problem.
This is because our problem differs from Bell's in a number of important respects.
It is worthwhile to list these differences to obtain some perspective on the
nature of the automatic patching problem. There are basically six significant
differences, three of which tend to make our problem easier than Bell's and three
of which tend to make it harder. Taken together, they make the problem not necess-
arily harder or easier than Bell's, but merely different.
3.1 Size
The largest contemplated analog system is much smaller than the Bell System.
This fact not only tends to make our problem easier than Bell's, but changes its
character as well. In Chapters 4 and 5, we will see that a simple rectangular
matrix is the most economical design for small systems, while a large system is
more efficient with multi-stage matrices. Thus differences in size mean differ-
ences in type as well.
3.2 Static Versus Dynamic Considerations
The Bell System must allow dynamic access between callers, that is, a switch path
must be chosen for a given connection without prior knowledge of what other connect-
ions may be made in the future. Confronted with a Chicago-San Francisco call, the
system has to decide whether to route it through Denver or Salt Lake City without
knowing which city is going to have the heaviest traffic a few minutes later. In
contrast, the analog programmer knows all connections before the first connection
3=2
is made, and once made, they do not change. Occasional program changes (the
equivalent of re-patching) are made so seldom that the entire switch assignment
may be re-computed if necessary. Hence our problem is static, while Bell’s is
dynamic, In the static problem, every switch path may be chosen with full know-
ledge of the entire problem. In Chapter 4, we will see that this fact "buys" _
us about a factor of two; that is, the static case takes about half as many
switches as the dynamic case.
3.3 Interchangeability
In analog programming it is not necessary for every component to be able to
communicate with every other component, since component assignment is arbitrary.
If I want to connect a summer to an integrator, I may not care whether the summer
is A21 or A36, but when I want to talk to Joe Green in Chicago, I won't be satisfied
with Jim Black in Cleveland instead. Summers are interchangeable; integrators are
interchangeable; people aren't. In other words, we are interested in abstract,
rather than concrete programs (See Chapter 2). The ability to interchange com-
ponents at will should prove a significant advantage, if we take advantage of it
properly.
The preceding three points are all in our favor. The three disadvantages
are as follows:
3.4 Traffic Density
At any given time, only a small percentage of the country's telephones are
in use. In contrast, a typical analog program may use most of the components in
the machine. Hence, although Bell works with much larger matrices, the traffic
on them is much lighter. One way that Bell takes advantage of this fact is to
use concentrator matrices at the inputs to their large switching systems. This
-keeps the number of inputs and outputs to their large systems within reasonable
bounds, but it also means that only a small fraction of the people in a given
exchange can use the phone at any given time, and a still smaller fraction may
make long-distance calls. Fortunately, traffic is normally light enough that
blocking does not often take place. In the event of a catastrophe, such as a
fire, flood, or earthquake, when many people in a given area want to use the phone
at once, a number of them will find the trunklines all busy. The analog programmer
must operate under such conditions of moderate-to-heavy traffic density most of
the time.
3.5 Fanout
Fanout is quite rare in the Bell System, but quite common in analog pro-
grams. Cases of fanout occuring within the Bell System (e.g. conference calls)
probably require manual intervention; at any rate, I don't know any way to set
up a conference call between three different cities by direct dialing.
The "cost" of fanout in terms of switches is less than I had originally
anticipated; comparison of the results of Chapter 4 and Chapter 5 indicate that
the cost is about /2; that is, about 1.4 times as many switches are needed to
- cover the case of fanout.
3.6 Blocking Penalty
In order to program an analog problem it is necessary to make all connections;
if even one connection is omitted, the entire simulation is affected. A typical
200-amplifier problem may require 500 connections. If one of these is blocked
(and cannot be un-blocked by re<assigning components) then the problem can not be
run. If this happens in the Bell System, it merely means that one person in 500
3-3
can't complete his call because the trunk lines are busy; the other 499 people
are satisfied and the 500th can always try again later. (In this case, the
dynamic nature of the Bell System pointed out in section 2 becomes an advantage).
Thus a level of blocking that Bell might find acceptable may be unacceptable
in an analog switching scheme.
The advantages that the analog programmer enjoys over the Bell System may be
summarized as follows: he is concerned with a relatively small switching matrix
making static connections between interchangeable components, while Bell's System
is large, and makes connections dynamically between unique subscribers. Bell's
advantages may be summed up as follows: they operate under conditions of. low
traffic density (low percentage utilization) and negligible fanout, and they can
tolerate a small percentage of blocked connections at any time. The analog pro-
grammer operates under conditions of high traffic density (over 50% of the com-
ponents are in use in a given problem) and moderate-to-heavy fanout (fanouts of
2 or 3 are quite common, and fanouts of 8 to 10 occur occasionally). Furthermore,
any blocking is not merely undesirable; it is catastrophic.
. 6
4-1
THREE STAGE MATRICES (WITHOUT FANOUT)
The theory of the three-stage matrix is a natural starting point for
any study of automated analog patching. Almost all proposed systems
utilize three-stage matrices (sometimes in combination with other
matrices). If fanout is ignored, the theory assumes an especially
simple form. It is fairly easy to prove that a three-stage matrix can
be found that can handle any non-fanout program with fewer switches
than a straightforward rectangular matrix, if the matrix i rge
enough. Most of the theory in this chapter is due to Clos |1) , but
is summarized here ina slightly different form to facilitate generalization
to the fanout case, which is covered in Chapter 5.
4.1 Parameters of the three-stage Matrix
The type of three-stage matrix considered in this report consists of
three types of rectangular matrices, called input blocks, middle blocks,
and output blocks. The input blocks are connected to the matrix inputs,
the output blocks are connected to the matrix outputs, and the input blocks
are connected to the output blocks through the middle blocks. Each
middle block has one connection to each input block and one connection
to each output block. Figure 4.1 illustrates the configuration. The input
blocks are 2 by 2 rectangular matrices; the middle blocks are 3 by 4 rec-
tangular matrices, md the output blocks are 2 by 3.
An arbitrary matrix of this type is characterized by the following
parameters;
the number of inputs
the number of outputs
the number of inputs per input block
the number of outputs per output block
the number of input blocks
the number of middle blocks
the number of output blocks
NX HB ee
From the definition, it is obvious that N= Xn and M=Zm. Eq. 4.1
The total number of switches in the matrix may be expressed in terms of the
parameters as follows:
The input blocks are n by Y matrices; hence they each contain nY switches.
Hence the total number of switches in all input blocks. is XnY. Since
Xn =N, this can be written as NY. The same reasoning leads to the
conclusion that MY switches are needed inthe output blocks. Finally,
the middle blocks have X inputs and Z outputs each, and hence the total
number of switches required in the middle blocks is XYZ. Thus the
total number of switches is given by
---- a a re 2 ol oe OY
4-2
N=6
NPUTS
| s< M=/2
> ovTPuTs
ovrpur
BLOCH S
(2 by 3)
If we eliminate X and Z in favor of mand n, we get a form that
turns out to be more useful:
M N
S = Y (M+N+ "Br a) Eq. 4.2
In a practical design problem, M and N may be taken as given (that
is, the problem is to find the most efficient matrix for connecting N
inputs to M outputs). Hence m, n, and Y are the design parameters
to optimize. We want the minimum number of switches for an adequate
matrix, where the term ''adequate" meana that the matrix contains
enough switches to implement a particular class of programs. Any
definition of ''adequate" will impose some constraints on m, n, and Y
and the problem becomes one of choosing m n, and Y to minimize S
subject to these constraints. Since S is a monotonic increasing function
of Y and a monotonic decreasing function of m and n, we want to choose
Y as small as possible and m and nas large as possible. Thus one
would expect any definition of "adequacy'! to impose a lower bound on Y
and /or upper bounds on m and n.
In this chapter, two definitions of "adequate" are considered (for the
case of non-fanout programs). In the next chapter, an additional
definition is: considered for the case of fanout. In all cases, the
definitions lead to upper bounds on m and n and lower bounds on Y, as
expected. The problem thus reduces to a problem in constrained
parameter optimization. Solution of these problems yields design
criteria for optimal three-stage matrices and formulas for the optimal
numbers of switches.
4.2 Static and Dynamic Adequacy
A matrix will be called statically adequate # it is capable of handling any
concrete program (that is, any concrete program, as defined in Chapter 2
can be implemented on it). It will be called dynamically adequate if any
transition from one such program to another can be made without breaking
any connections common to both. The dynamic case is not particularly
important. for ananalog programming matrix, since transitions from
one program to another (the equivalent of re-patching) are normally made
between runs, not during runs. Switching during runs will ordinarily
be done with electronic switches for reasons of speed. The dynamic
case is, of course, the one that interests the telephone company, and
hence most of the published theory is based on dynamic considerations.
4a4
The terms "statically adequate without fanout'' and "dynamically
adequate without fanout'" will be used in the obvious sense (one
considers only non-fanout programs). In the non-fanout case, the
adequacy conditions assume very simple forms as follows:
Therorem 4,1 For a three-stage matrix to be dynamically adequate
without fanout, it is necessary and sufficient that Y > m+tn-l.
Proof: At any given time, it must be possible to connect any unused
input to any unused output. There are n-1l other inputs on the same
input block as the input to be connected. If these inputs are all in use,
they tie up n-1 middle blocks. (No middle block can handle more than
one connection from a given input block). Similarly, the m-1l other
outputs on the output block might all be in use, tying up an additional
m-l middle blocks. Thus at most m+n-2 middle blocks are tied up
by existing connections. The actual number of middle blocks tied up
may be less than this, because some of the n-1 middle blocks that are
tied up on the input side may be the same as someaf the m-l middle
blocks tied up on the output side. However, the worst case occurs
when there is no such overlap (and there will be no overlap if there is
no pre-existing connection between the input block and the output block
under discussion). In this case m+n-2 middle blocks are tied up, and
if Y >m-tn-1l, there will be one middle block left to make the necessary
connection. Since this is a ''worst case" the condition is both necessary
and sufficient.
Therorem 4.2 For a three-stage matrix to be statically adequate without
fanout, it is necessary that Ym and Y>n.
Proof: In order to handle the case where all m outputs in a given output
block are in use, we must have Y >m. In order to handle the case where
all n inputs in a given input block are in use, we must have Y= n.
Hence both conditions are necessary.
Furthermore, it appears likely that these two conditions taken together
are also sufficient, that is, that any non-fanout program can be implemented
on a three-stage matrix as long as the number of middle blocks is at
leagt as great as mandn. This is asserted without proof in the literature
2 - Isuspect it could be proved rigorously, but the proof appears
trickier than I had first suspected. At any rate, practical experience
indicates that it is at least approximatelysufficient; that is, that the number
of middle blocks is necessary, at worst, not much greater than m or n.
For the purposes of this report, it will simply be assumed that these
conditions are sufficient. If this asaimption turns out to be false, it
will not really affect the overall conclusions of this report, since the
real practical interest is in programs with fanout. The non-fanout
case is of interest only as a prelude tothe more realistic case
covered in Chapter 5.
With these assumptions, the problem becomes one of minimizing S
(given in Eq. 4.2) subject to the constraints
Y =min-l for the dynamic case 4.3
Y = mand Yn forthe static case 4.4
4.3 Optimizing the Matrix
As expected, the constraints impose upper bounds on m andn and lower
bounds on Y. It is fairly clear that these inequalities must reduce
to equalities for an optimum design. For example, if Y*m+n-l, then
we could reduce Y or increase m or n without violating 4. 3. Reducing
Y or increasing m or n would reduce S according to 4.2. Hence, for
the optimum designs, 4.3. and 4.4 must reduce to equalities..
We can use these equalities to eliminate Y and express S as a function
of mandn. Minimization then becomes a straightforward problem in
elementary calculus. We have
S = (min-1l) | eve mah | in the dynamic case 4.5
MN :
- 4,
S=n [M+ 2 | in the static case 6
Setting 9s/dmandds/gn equal to zero, we get for the dynamic case
2 _ wi
me — (1 * a) 4.7
>_ [MN 1
no = E ay (1 ) 4.8
and for the static case
MN
M+N
4-6
Although 4.7 and 4.8 are difficult to solve for m and n, we observe that
if mand n are much greater than unity, we may make the obvious ——
approximations on the right-hand sides, in which case 4.7 and 4.8
reduce to 4.9. It should be noted that even 4.9 is itself an "approximation"!
in the sense that it usually does not yield integral values for m and n;
so that the calculated values must be rounded off to the nearest integer
anyway. Hence for practical purposes, the static and dynamic cases
yield the same values of rm and n. . . oe
Substituting 4.9 into 4.5 and 4. 6, we get, for the dynamic case
S=4 YMN(M+N) -2 (M+N) 4.10
and for the static case
= 2 YMN (M+N) 4.11
Note that the second term in 4.10 is much smaller than the first; in
fact, dropping this termis equivalent to using Y = m+n instead of
Y = mtn-l, which introduces only a small error if m and n are large.
Hence, to a first approximation, we see that the dynamic case takes
about twice as many switches as the static case. In other words, knowing
all connections beforehand allows a sa-ring of a factor of two.
4.4 Divisibility Considerations
Ali the formulas in the previous section are approximate. For example
equation 4.9 does not usually yield integer values of mandn. Even if
the values turn out to be integers, they may not be divisible into M and N.
To get around this, one does the
obvious things: round off the calculated m and n to the nearest integer, and
then round Mand Nuptothe next larger multiple of this value. This
gives a matrix slightly larger thanrquired, allowing a few more inputs
and outputs to be terminated in the matrix. However, for matricies
sufficiently large to be of interest, the percentage error in 4.10 and
4.1llis small.
4.5 Comparison with Rectangular Matrix
To see how fast the number of switches increases as a function of
matrix size, we may express S in terms of N and E (see Chapter 2)
rather than N and M. This gives
Ss = an?/* V E(1+E) (dynamic case) 4.12
s = 2nN 3/2 V E(1+E) (static case) 4.13
Since S = EN@ for a rectangular matrix (see Chapter 2), it follows
that for sm