Chapter 22

1
Design of the B 5000 system

William Lonergan / Paul King

Computing systems have conventionally been designed via the should be made for the generalized handling of indexing and
'hardware' route. Subsequent to design, these systems have been subroutines; a full complement of logical, relational and control
handed over to programming systems people for the development operators should be provided to enable efficient translation of
of a programming package to facilitate the use of the hardware. higher-level source languages such as ALGOL and COBOL; pro-
In contrast to this, the B 5000 system was designed from the start gram syntax should permit an almost mechanical translation from
as a total hardware-software system. The assumption was made source languages into efficient machine code; facilities should be
that higher level programming languages, such as ALGOL, should provided to permit the system to largely control its own operation;
be used to the machine language programming,
virtual exclusion of input-output operations should be divorced from processing and
and that the system should largely be used to control its own should be handled by an operating system; multi-programming and

operation. A hardware-free notation was utilized to design a proc- true parallel processing (requires multiple processors) should be
essor with the desired word and symbol manipulative capabilities. facilitated,and changes in system configuration (within certain
Subsequently this model was translated into hardware specifica- broad limitations) should not require reprogramming.
tions at which time cost constraints were considered.

System organization
Design objectives
The B 5000 system achieves its
unique physical and operational
The fundamental design objective of the B 5000 system was the
modularity through the use of electronic switches which function
reduction of total problem through-put time. A second major
logically like telephone crossbar switches. Figure 1 depicts the
objective was facilitation of changes both in programs and system basic organization of the system as well as
showing a maximum
configurations.Toward these objectives the following aspects of
system.
the total computer utilization problem were considered:
Statement of problems in higher-level machine-independent
languages; efficiency of compilation of machine language; speed of Master control program
compilation of machine language; program debugging in higher-
A master control program will be provided with the B 5000 system.
level languages; problem set-up and load time; efficiency of It be stored on a portion of the magnetic drum. During normal
will
system operation; ease of maintaining and making changes in
operations, a small portion of the MCP will be contained in core
existing programs, and ease of reprogramming when changes are
made in a
memory. This portion will handle a large percentage of recurrent
system configuration.
system operations. Other segments of the MCP will be called in
from the magnetic drum, from time to time, as they are required

criteria to handle less frequently-occurring events, or system situations.

Design
Whenever the system is executing the master control program,
Early in the design phase of the B 5000 system the following
it is said to be in the Control State. All entries to the Control
principles were established and adopted:
State are made via 'interrupts.' A special operation is
provided,
Program should be independent of its location and unmodified which can only be executed when the system is in the Control
as stored at object time; data should be independent of its location;
State, to permit control to return to the object program it was
addressing of memory within a program should take advantage
executing at the time the 'interrupt' occurred.
of contextual addressing schemes to reduce
redundancy; provisions The following are a few typical occurrences which cause an
^Datamation, vol. 7, no. 5,
pp. 28-32, May, 1961. automatic 'interrupt' in the system: An input-output channel is

267
268 Part 3 The instruction-set processor level: variations in the processor Section 5 Processors with stack memories (zero addresses per instruction)

1 or 2

1 to 16

1or2

1or2

1
 Chapter 22 |
Design of the B 5000 system 269

F
270 Part 3
|
The instruction-set processor level: variations in the processor Section 5 Processors with stack memories (zero addresses per instruction)

way around machine still must

design, but they
provide object the / operator is of higher precedence than the + operator. The
coding to
accomplish the storage and recall functions. In brief, right-hand Polish notation used in the B 5000 is based on placing
conventionally designed computers, with or without automatic the operators to the right of their operands: A + B becomes AB +

programming aids, require the wasteful expenditure of program- in Polish notation. A + B + C can be written either as AB + C-I-,

ming effort, memory capacity, and running time to overcome the or as ABC + + . In the expression ABC + + ,
the first + operator
limitations of their internal organization. says to add the operands B and C. The second + operator says
The problem is attacked directly in the B 5000 by incorporation to add A to the sum of B and C. Beturning to the first examples

of a "pushdown" stack, which completely eliminates the need for above, A(B + C) can be written as BC + Ax or ABC+ X in Polish.
instructions (coded or compiled) to store or recall intermediate The second example is written as BC/A + or ABC/ + The . exten-
results. sion of Polish notation to handle equations is shown in the follow-

B 5000 processor, the stack is composed of a pair of regis-

In a ing example:
ters, A and B registers, and a memory area. As operands are
the Conventional notation Z = A(B - C)/(D + E)

picked up by the programs, they are placed in the A register. If Polish notation ABC- xDE + /Z=
the A register already contains a word of information, that word
is transferred to the B register prior to loading the operand into
the A B The stack in use
register. If the register is alsooccupied by information,
then the word in B is stored in a memory area defined by an To illustrate the functioning of the stack, two simple examples
address register S. Then the word in A can be transferred to B are shown in Figs. 4 and 5. In the examples, the letters P,Q and
and the operand brought into the A register. The new word coming R represent syllables in the program that cause the operands P,
into the stack has pushed down
the information previously held Q, and R to be picked up and placed in the stack. The symbols
in the registers. As each pushdown occurs, the address in the S + and X represent syllables that cause the add and multiply
register automatically increased by one. The information con-
is operations to occur. The two examples represent different ways
tained in the registers is the last information entered into the stack; of writing P(Q + The first example in Fig.
R) in Polish notation.
the stack operates on a "last in-first out" principle. As information 4 does not require pushdowns or pushups. The second example,
is
operated on in the stack, operands are eliminated from the stack shown in Fig. 5, requires a pushdown in the execution of the
and results of operations are returned to the stack. As information syllable R, and a pushup in the execution of the syllable X The
in the stack used up by operations being performed, it is possible
is columns in the table represent the contents of the various registers

to cause "pushups," i.e., a word is brought from the memory area after execution of the syllable listed in the first column.
addressed by the S register, and the address in the S register is

decreased by one.
To eliminate unnecessary pushdowns and pushups, the A and Independence of addressing
B registers both have indicators used for remembering whether One of the goals set in the design of the B 5000 was to make the
the registers contain information or are empty. When an operand programs independent of the actual memory locations of both the
is to be
placed in the stack and either of the registers is empty, program itself and the data, in order to provide really automatic
no pushdown into memory occurs. Also, when an operation leaves
one or both of the registers empty, no automatic pushup occurs.
Polish Notation QR + Px

Polish notation

The Polish logician, J. Lukasiewicz, developed a notation which

allows the writing of algebraic or logical expressions which do not

require grouping symbols and operator precedence conventions.

For example, parentheses are necessary as grouping symbols in
the expression A(B + C) to convey the desired interpretation of the

expression. In the expression A + B/C, the normal interpretation

is A + (B/C), rather than (A + B)/C, because of the convention that
 Chapter 22 Design of the B 5000 system 271

Polish Notation PQR +

272 Part 3 The instruction-set processor level: variations in the processor Section 5 Processors with stack memories (zero addresses per instruction)

Word mode program For (3), indexing of the descriptor by the item that is now the

The word mode of the B 5000 processor has four types of syllables. second item in the stack occurs. For an operand call syllable, the

The syllable type is distinguished by the two high-order bits of operand is obtained from the indexed address; for the descriptor
call syllable, action is
complete after the indexing.
each 12-bit syllable. The types of syllable and the identification
In the case of subroutine entry occurs to the subroutine
(4),
bits are:
addressed. A word of the three previous types may be left in the

00— Operator Syllable registers upon return from the subroutine, in which instance the
actions described above will take place, depending upon the type
01— Literal Syllable
of syllable which initiated the subroutine.
10— Operand Call Syllable
11 — Descriptor Call Syllable Essentially, the four types of action that occur for an operand
call syllable are obtaining an operand directly, indirectly, from
an array, or by computation. Sometimes in the use of the call
The first of these, the
operator syllable, causes operations to be
syllables, it is not known which type of action will occur for a
performed. The remaining ten bits of the operator syllable are the
particular syllable when the program is created. This is
particu-
operation codes. There are approximately sixty different operations
in the word mode. For those larly true for call syllables in subroutines.
operations requiring an operand or
Programs in the word mode consist of strings of syllables which
operands, the processor checks for sufficient operands in the regis-
follow the rules of Polish notation. Variable length strings of call
ters; if they are not there, pushups from the stack in memory occur
syllables and literal syllables, which place items of information
automatically.
by operator syllables which perform their
in the stack, are followed
The literal syllable is used for placing constants in the stack

to be used as operands. The ten bits of the literal syllable are operations on information in the stack.
The indexing features of the B 5000 allow generalized indexing
transferred to the stack. This allows the program to contain inte-
and at the same time provide complete storage protection. Data
gers less than 1,024 as constants.
areas and program segments of different programs may be inter-
The operand call syllable, and the descriptor call syllable ad-
mingled, but a program is prevented from storing outside of its
dress locations in the program reference table. The purpose of the
data areas. The method of indexing allows any of the 1,024 words
operand call syllable is to
place an operand in the stack; the
of the program reference table to be considered index
registers.
purpose of the descriptor call syllable is to place the address of
Multilevel indexing is
provided, i.e., indices of arrays can them-
an operand, a descriptor, in the stack. There are four situations
selves be elements of arrays.
that arise, depending on the word read from the program reference
table.
The subroutine control provided in the B 5000 allows nesting
of subroutines — even recursive nesting subroutine a subrou-
(a is

1 The word is an operand. tine of itself) — arbitrarily deep. Dynamic allocation of storage for

parameter and temporary working storage simplify the use

lists
2 The word is a descriptor containing the address of the
of subroutines. Storage is automatically allocated and deallocated
operand. as required.
3 The word a descriptor containing the base address of the
is

data area in which the operand resides.

4 The word a program descriptor containing the base ad-

is
Character mode program
dress of a subroutine. In the character mode of the B 5000 Processor, there is
only one
type of syllable, called the operator syllable. Program segments
For the operand call syllable has completed its action by
(1), in the character mode are constructed of strings of these syllables.
placing an operand in the stack. The descriptor call syllable will The character mode is designed to provide editing, formatting,
cause the construction of a descriptor of the operand, replacing comparison, and other forms of data manipulation. In doing so,
the operand by the constructed descriptor. the processor uses two areas of memory the source and desti- —
For (2), the operand call syllable then reads the operand from nation areas. When
a program switches from word mode to char-
the cell addressed. The descriptor call syllable has completed its acter mode, two descriptors containing the base addresses of these
action. areas are supplied. The source area or destination area may be
 Chapter 22 j
Design of the B 5000 system 273

changed at any time during character mode so that the program Conclusion

may act on several areas. The Burroughs B 5000 system has been designed as an integrated
The character mode operator syllable is
split into
two 6-bit
hardware-software package which offers such benefits as savings
parts; the
last part specifies the operation to be performed and in the memory space required to store equivalent object programs;
is to be
the part specifies the number of times the operation
first
multi-processing and parallel processing; and running identical
performed. Operations are provided for the transferring, deletion,
programs on systems with different size memories and different
comparison, and insertion of characters or bits. Also, there are system configurations with no loss in individual system efficiency.
operations which allow the repetition of syllable strings. This is
References
quite useful for complex table look-up operations and for editing
information which contains repeated patterns. LoneW61; BartR61; BockR63; CarlC63; MaheR61
 indexing and subroutines; a full complement of logical, relational
Chapter 9 and control operators should be provided to enable efficient
translation of higher-level source languages such as ALGOL and

Design of the B 5000 System^ COBOL; program syntax should permit an almost mechanical
translation from source languages into efficient machine code;
William Lonergan /Paul King should be provided to jjermit the system to largely
facilities

control own operation; input-output operations should be

its

divorced from processing and should be handled by an

Computing systems have conventionally been designed via the operating
"hardware" route. Subsequent to design, these systems have been system; multi-programming and true parallel processing (requires
handed over to programming systems people for the development multiple processors) should be facilitated, and changes in system
of'a programming package to facilitate the use of the hardware. In configuration (within certain broad limitations) should not require
contrast to this, the B 5000 system was designed from the start as reprogramming.
a total hardware-software system. The
assumption was made that
higher level programming languages, such as ALGOL, should be
used to the virtual exclusion of machine language programming, System Organization
and that the
system should largely be used to control its own
The B 5000 system achieves unique physical and operational
operation. A hardware-free notation was utilized to design a
its

processor with the desired word and s\ mbol manipulative capabil- modularity through the use of electronic switches which function
ities. Subsequently this model was translated into hardware logically like telephone crossbar switches. Figure 1 depicts the

specifications at which time cost constraints were considered.

basic organization of the system as well as
showing a maximum
system.

Design Objectives
lUlaster Control Program
The fundamental design objective of the B 5000 system was the
reduction of total problem through-put time. A second A master control program will be provided with the B 5000
major
will be stored on a portion of the magnetic drum.
It
objective was facilitation of changes both in programs and system system.
configurations. Toward these objectives the following aspects of During normal operations, a small portion of the will be MCP
the total computer utilization problem were considered: contained core memory. This portion will handle a large
in

Statement of problems in higher-level machine-independent percentage of recurrent system operations. Other segments of the
languages; efficiency of compilation of machine language; speed of
MCP will be called in from the magnetic drum, from time to time,
as they are re(juired tohandle less frequently-occurring events, or
compilation of machine language; program debugging in higher-
level languages; problem set-up and load time; efficiency of system situations. Whenever the system is executing the master
control program, it is said to be in the Control State. All entries to
system operation; ease of maintaining and making changes in "
the Control State are made via "interrupts. A special operation is
existing programs, and ease of reprogramming when changes are
made in a system configuration. provided, which can only be executed when the system is in the
Control State, to permit control to return to the object program it
was executing at the time the "interrupt" occurred.
Design Criteria The following are a few typical occurrences which cause an
automatic "interrupt" in the system: An input-output channel is

Farly in the design phase of the B 5000 system the following available, an input-output operation has been completed or an

principleswere established and adopted: indexing operation was attempted which violated the storage
Program should be independent of its location and unmodified protection features built into the system.
as stored at object time; data should be In addition to processing interrupt conditions, the master
independent of its
location; addressing of memory within a program should take control program handles fundamental parts of the total system
advantage of contextual addressing schemes to reduce redundan- operation such as the initiation of all input-output operations,
c\; provisions should be made for the generalized linking of input-output areas when required, file control, alloca-
handling of
tion of memory, scheduling of jobs (priority ratings,
system
requirements of each object program, and the present system
configuration are considered), maintenance of an operations log
'Datamation, vol. 7, no. 3, May 1961, pp. 28-.32. and maintenance of a system description.

1S»
130 Part 1 Fundamentals Section 3 | Computers of Historical Significance

1 or 2

1 to 16

lor 2

lor 2

1
 Chapter 9 Design of the B 5000 System 131

on how the program references the data word. If the data word is a
single sariable and not an element of an array, the flag identifies
the word as being operand, that is, a data word. If the word is an
element of an array, the flag may be used to identify this particular
element as an element of data which is not to be processed by the
normal program (for example, a boundary point in mesh calcula-
tions).

When operating in the character mode, each data word consists

of eight alphanumeric characters as illustrated in Fig. 3. Programs
in the character mode can address any character in a word. Fields

can at any position in a word. A processor in a single

start

operation can operate on fields of any length up to 63 characters

long; operations on fields of greater length can easily be pro-
grammed. For example, two 57 character fields could be com-
pared in a single operation.

There are two instances when the character mode operates with
words of the type used in the word mode. Operations are
provided in the character mode for converting numeric informa-
tion in the alphanumeric representation to the standard word type
of the word mode and vice versa. In both of these instances, the

length of the alphanumeric fields being converted to or from the

word mode type of word can be no greater than eight characters
long. Again, conversion of fields of greater length can easily be
programmed.
The purpose of the word mode is to provide the advantages of
high-speed parallel operations, floating-point abilities and the
inherent information density possible in a binary- machine. In the
first case, it is
economically feasible to provide parallel operations
in a word machine; the cost of parallel operations on variable
length fields would be prohibitive. In the last case, a given size
memor\' can contain over twenty percent more numeric informa-
tion if that information is expressed in binar>' rather than
binary-coded decimal, and over eighty percent more information
than can be expressed in six-bit alphanumeric representation.
The purpose of the character mode is to provide editing,
scanning, comparison and data manipulative abilities (although
addition and subtraction are also provided). The type of editing
facilities provided obviate the need for the artificial "add-shift-

extract-store" type of editing. For example, operations are

provided for generalized insertion of editing symbols (such as

blanks, decimal points, floating dollar signs, etc.) and for the
substitution or suppression of any unwanted characters. For those
interested in the new area of Information Processing Languages,
the character mode is particularly well suited to list structures.

First
Char
acter
132 Part 1 Fundamentals Section 3 Computers of Historical Significance

information is operated on in the stack, operands are eliminated Polish Notation QR + Px

from the stack and results of operations are returned to the stack.
As information in the stack is used up by operations being Syllable
performed, it is possible to cause "pushups," i.e., a word is Executed
brought from the memory area addressed by the S register, and
the address in the S register is decreased by one.
To eliminate unnecessary pushdowns and pushups, the A and B
registers both have indicators used for remembering whether the
registers contain information or are empty. When an operand is to
be placed in the stack and either of the registers isempty, no
pushdown into memory occurs. Also, when an operation leaves
one or both of the registers empty, no automatic pushup occurs.

Polish Notation
 Chapter 9 |
Design of the B 5000 System 133

then possible to load all the segments of a program or programs memory, automatic entry to the Master Control Program
onto the drum at load time and call in the segments to any willoccur and the desired segment will then be brought in
memory as needed during run time. If
available space in core from the drum. Notice that in moving from one segment to
some segment of a program is overlaid by a subsequent segment is not necessary to know whether the
another, it
segment to be
of a program, the segment of the program destroyed in core entered currently in core memory. Branching within a program
is

memory is still available on the drum to be called in again if segment is self-relative, i.e., the distance to jump either forward
needed. or backward is specified, not the address to be jumped to.
Due to the very high program densities in the B 5000, the As a result of keeping all actual addresses of data and program in

availability of high capacity drum storage on every system and the PRT, the program itself does not contain any addresses, but
automatic segmentation, a minimum B 5000 system has the only references to the PRT. To specify one of the 1,024 positions
capacity for a program or programs equivalent to approximately in the PRT requires only 10 bits which contributes greatly to the

40,000 to 60,000 single address instructions. Of course, if an high program density achieved in the B 5000. Since the PRT is
installation normally ran such large programs, the system would relocatable, references to the PRT contained in the program are to
very likely not be a minimum system. However, the installation relative locations, thus completely freeing the program from any
having an occasional need to run very large programs is not dependence whatsoever on actual memory locations.

prevented from doing so by storage capacity.

Processing speed now becomes a function of the size of core
memory. If large programs are run in a system with small core The Word Mode Program
memory, time will be consumed in recalling program segments
from drum to core. If the core memory is expanded, less time will The word mode of the B 5000 processor has four types of syllables.
be spent in such activity and the program or programs will be The syllable type is distinguished by the two high-order bits of
speeded up, and no reprogramming is required. each 12-bit syllable. The types of syllable and the identification
bits are:

Program Reference Table 00—Operator Syllable

01— Literal Syllable
The means of achieving independence of addressing in the B 5000 10—Operand Call Syllable
is called a
Program Reference Table (PRT). The PRT is a 1,024 11 — Descriptor Call Syllable
word relocatable area in memory used primarily for storing
control words that locate data areas or program segments. There The first of these, the operator syllable, causes operations to be

are also control words for describing input-output operations. performed. The remaining ten bits of the operator syllable are the
These control words, called descriptors, contain the base address operation codes. There are approximately sixty different opera-
and size of data areas, program segments and input-output tions in the word mode. For those operations requiring an
operation areas. A descriptor specifying an input-output operation _ operand or operands, the processor checks for sufficient operands
also contains the designation of the unit to be used and the type of in the registers; ifthey are not there, pushups from the stack in
operation to be performed. Operands may also be stored in the memory occur automatically.
PRT, providing direct access to single values such as indices, The literal syllable is used for placing constants in the stack to
counts, control totals, etc. be used as operands. The ten bits of the literal syllable are
In the word mode of the B every item of data is
5000, transferred to the stack. This allows the program to contain
considered to be either a single value or an element of an array of integers less than 1,024 as constants.
data. If it is a single value, it will be obtained directly by The operand call syllable, and the descriptor call syllable
indexing
a descriptor contained in the PRT. address locations in the program reference table. The purpose of
Program segments are described by program descriptors. In the operand call syllable is to place an operand in the stack; the
addition to core base address, the program descriptor contains the purpose of the descriptor place the address of an
call syllable is to
location indrum storage of the program segment and an indication operand, a descriptor, in the stack. There are four situations that
ifthe program segment is currently in core memory starting at the arise, depending on the word read from the program reference
address specified in the descriptor. Entry to a program segment is table.
made viaprogram descriptor contained in the PRT. If the pro-
its
1 The word is an operand.
gram segment is in core memory, entry will be made to the program
segment. However, when entry is attempted to a program seg- 2 The word is a descriptor containing the address of the
ment whose descriptor indicates that the segment is not in core operand.
134 Part 1 Fundamentals Section 3 I
Computers of Historical Significance

3 The word is a descriptor containing the base address of the parameter lists and temporary working storage simplify the use of
data area in which the operand resides. subroutines. Storage is automatically allocated and deallocated as

4 The word is a program descriptor containing the base required.

address of a subroutine.

For (1), the operand call syllable has completed its action by
Character Mode Program
placing an operand in the stack. The descriptor call syllable will
cause the construction of a descriptor of the operand, replacing In the character mode of the B 5000 Processor, there is only one
the operand by the constructed descriptor. type of syllable, called the operator syllable. Program segments in

For (2), the operand call syllable then reads the operand from the character mode are constructed of strings of these syllables.

the cell addressed. The descriptor call syllable has completed its The character mode is designed to provide editing, formatting,

action. comparison, and other forms of data manipulation. In doing so,

For indexing of the descriptor by the item that is now the
(3),
—
the processor uses two areas of memory the source and destina-
second item in the stack occurs. For an operand call syllable, the tion areas. When a program switches from word mode to

obtained from the indexed address; for the descriptor character mode, two descriptors containing the base addresses of
operand is

call s\Ilable, action is complete after the indexing. these areas are supplied. The source area or destination area may
In the case of subroutine entry occurs to the subroutine
(4),
be changed at any time during character mode so that the
addressed. A word of the three previous types may be left in the program may act on several areas.
The character mode operator syllable is split into two 6-bit
registers upon return from the subroutine, in which instance the
actions described above will take place, depending upon the type parts; the last part specifies the operation to be performed and the
of syllable which initiated the subroutine. first part specifies the number of times the operation is to be

Essentially, the four types of action that occur for an operand performed. Operations are provided for the transferring, deletion,
call syllable are obtaining an operand directly, indirectly, from an comparison, and insertion of characters or bits. Also, there are

array, or by computation. Sometimes in the use of the call operations which allow the repetition of syllable strings. This is

syllables, it is not known which type of action will occur for a quite usefiil for complex table look-up operations and for editing
when the program is
created. This is information which contains repeated patterns.
particular syllable particular-
ly true for call syllables in subroutines.

Programs in the word mode consist of strings of syllables which

follow the rules of Polish notation. Variable length strings of call Conclusion
syllables and literal syllables, which place items of information in
the stack, are followed by operator syllables which perform their The Burroughs B 5000 system has been designed as an integrated
operations on information in the stack. hardware-software package which offers such benefits as savings
The indexing features of the B 5000 allow generalized indexing in the memory space required to store equivalent object pro-

and at the same time provide complete storage protection. Data grams; multi-processing and parallel processing; and running
areas and program segments of different programs may be identical programs on systems with different size memories and

intermingled, but a program is prevented from storing outside of different system configurations with no loss in individual system
its data areas. The method of indexing allows any of the 1,024 efficiency.
words of the program reference table to be considered index
registers. Multilevel indexing is provided, i.e., indices of arrays
can themselves be elements of arrays. References
The subroutine control provided in the B 5000 allows nesting of
subroutines — even recursive nesting (a subroutine is a subroutine Lonergan and King [1961]; Barton [1961]; Bock [1963]; Carlson
of itself) arbitrarily deep. Dynamic allocation of storage for [1963]; Maher [1961].