Copyright (C) 1982, 1999 by Alastair J.W. Mayer
This paper first appeared in the ACM's Computer Architecture News in 1982, while I was on staff at the Concordia University Computer Centre in Montreal, Quebec.
(As the original text file is on a 2400' 9-track tape that I can no longer easily read, this copy was scanned and OCR'd. There may yet be some minor OCR errors in the text. Sorry. All time references here (e.g. "twenty years ago") should be taken as relative to when this was first published, i.e. 1982.)
Abstract: The Burroughs
B5000 was introduced over twenty years ago. The architectural features
it introduced, and refined when it was upgraded to the B5500 and B6500,
are only now appearing in new computer designs. This paper briefly describes
some of these features, as they relate to high-level language and operating
system support, and as interesting features in their own right. References
are given for more detailed information.
Introduction
The basic premise of this paper is that the architecture of the Burroughs
B5000, as introduced twenty-one years ago and as refined some eighteen
years ago, still stands as an example of a modern high-level language computer.
I will briefly describe some of the features, both in the overall design
and in the instruction set, that make it so. Readers in search of further
architectural details are referred to [Org731 for a general description
and details of the high level language support, to [Bur72] for specific
details of the instruction set and organization of the hardware, and to
(All8l] for notes on the latest refinements of this system. Where known,
the existence of similar features in other machines is noted(l) . There
are some differences in design details between the original B5000 and later
machines, as described below. Documents available to me are unclear as
to whether the B5500, the next model introduced, is more like the B5000
or the later B6500 and subsequent models. This paper will refer to the
'B5000 design' for concepts appearing in this and subsequent machines,
and 'B6000' for details known to be in the B6500 and later machines but
not in the B5000. Other numbers used refer to specific models.
History
The Burroughs B5000 was introduced about twenty years ago, at the beginning
of the nineteen-sixties(2). This system can be considered the first of
the "third generation" of computer systems. It had all of the
features which, according to Denning [Den7l], characterize a computer of
the third generation.
The B5000 was designed with the support of high level languages (ALGOL
and COBOL) in mind. The most remarked-upon aspects are its use of a hardware-managed
stack for calculation, and the extensive use of descriptors for data access.
It included virtual memory -- perhaps the first commercial computer to
do so -- as well as support for multiprogramming and multiprocessing. For
additional security, code and data were distinguished in memory by the
use of a "flag bit", and the hardware would not execute data
or alter code without first having explicitly changed the flag (something
reserved for privileged processes).
The essence of the B5000 design has changed little in the last twenty years,
consisting of the hardware stack, the use of descriptors, and special bits
to differentiate code and data. It has been refined since then. The most
significant changes took place soon after the B5000 was introduced. The
next machine, known as the B5500, appeared in 1964, and an improved version
appearing in 1966 became known as the B6500. The use of descriptors was
extended, the flag bit was extended to a three-bit "tag field"
and made external to the 48-bit data word, and the instruction set altered
to take advantage of these changes.
The instruction set introduced with this change has remained the same through
successive models of the series. This set is now known as "E-mode"
[All8l]. The next model series involved no real design changes, but the
technology was improved. These were known as the B5700 and B6700. A larger
and faster model was also introduced about this time, the B7700. The principal
differences in these series are in the number and arrangement of processors
possible in a given configuration. For example, a B6700 can have up to
three central processors and up to three I/O processors, while a B7700
can have any combination of up to eight central and I/O processors (as
long as there is at least one of each).
At some point in B6700/B7700 production an option known as vector mode
hardware became available. This enhanced the ability of the processor to
do repetitive arithmetic operations on arrays or vectors, improving the
performance of typical FORTRAN and APL programs.
The next upgrade was announced in 1976, with the introduction of the B6800
[Sur76]. Again, this was primarily a technology upgrade, but one new feature
was Global(3) memory. Despite the name, this feature allows each processor
in a multiple processor configuration to have its own local memory as well
as shared memory. The real difference is in the degree of coupling of the
processors. In a tightly coupled mode, all memory is shared and only one
copy of the MCP (the operating system or Master Control Program) exists.
This was the only multiple processor mode available up to this time. Global
memory permitted too (or more) logically discrete computer systems (each
with its own resources and own MCP) to communicate directly through the
shared Global memory [Bur8O]. Other features of the B6800 and B7800 included
the change to semiconductor memory (the B6700 used thin-film), faster cycle
time, lookahead, and the ability to configure more processors into a single
system.
The 900-level systems were introduced in late 1979/early 1980. As opposed
to earlier implementations using discrete logic, the B5900 (and presumably
the B6900) heavily exploit high density parts and bit-slice processor chips
[All8l]. Other features include a redesign of the I/O Data Communications
Subsystem, making extensive use of specialized microprocessors.
An interesting sidelight in the development of this series is the development
of the Attached Fortran Processor (AFP) and the Burroughs Scientific Processor
(BSP). Since the original B5000 design was to support dynamic block structured
languages such as ALGOL, it was not quite as efficient as conventional
machines at executing FORTRAN programs. The addition of vector hardware
to the B6700 and B7700 helped alleviate this somewhat, but not entirely.
For really powerful number-crunching, the Burroughs Scientific Processor
was developed, and announced in the spring of 1977 [jen78]. The BSP is
a 16 processor, single instruction-multiple data stream design, and has
several unique design features (see [jen78] for more on this). Perhaps
the BSP should not be considered in the same context as the B5000/B6000/B7000
machines, except that the BSP incorporates a B7700 or B7800 as a "system
manager" and front-end. Also during 1977 was the development of the
Attached Fortran Processor, designed for users with scientific processing
needs that did not require a BSP. The AFP can connect to any of the B6000
or B7000 machines [Bur78, pg.15].
High Level Language Support
The Burroughs B5000 was designed from the start to support high level
languages (HLLs), specifically ALGOL and COBOL. The initial features supporting
this were the hardware-managed stack, the descriptor, and segmentation.
A redesign of this system, the B6000, extended the concept by moving the
tag bits to their own field, external to the 48-bit data word. The instruction
set was also revised and extended, and has remained essentially unchanged
ever since. HLLs are supported by hardware that allows virtual memory,
multiprocessing, fast context switching and procedure invocation, memory
protection, and code sharing.
Operating System Support
The B5000 was conceived as a system. The hardware and operating software
were designed in concert. Since the operating system (the core of which
is the Master Control Program, or MCP) is written in a HLL, ESPOL (an ALGOL
variant), those features designed for HLL support obviously assist in the
execution of the MCP. Other features specifically implemented for MCP use
include special instructions, such as the LLLU (linked-list lookup) instruction
to assist memory management, processor control instructions for multiprocessing,
and unique interrupt handling mechanisms (on interrupt, the hardware automatically
saves the current execution context and does a procedure call (supplying
any necessary parameters) to the appropriate routine).
Stack Architecture
All calculations performed on B5000 series machines(4) take place using
the operand(s) at the top of the stack. To improve performance, the top
two stack locations exist as the A and B registers (each of which may be
extended sideways by the X and Y registers for double-precision operands)
. Pushing and popping the stack is done automatically by the hardware,
depending upon the specific operations being done. This makes for rapid
expression evaluation, and greatly simplifies a compilers task of code
generation, a fact recognized in other designs. (English Electric KDF-9,
Hewlett-Packard HP3000, the Pascal P-machine ensiliconed as the Western
Digital Pascal microEngine). Since the operands are always implied (the
stack top), instructions do not need an operand field, reducing code size.
Tagged Words
In the original B5000, the tag was a bit within the data word, called
the flag. It was moved outside and expanded to three bits with the B6000,
where it remains. The tag serves to identify the meaning or type of the
word. As a memory protection feature, it differentiates data (operands)
from code and control words. Thus, it is physically impossible to execute
data, or to use code as operands (thus it is impossible for programs to
be self modifying(5)). The tags also differentiate between different types
of data (for example, single and double precision) and different types
of control words (array descriptors, segment descriptors, stack control
words, etc). The use of tags, in combination with the stack, allows the
instruction set to be very compact. Multiple instructions with similar
meanings are not needed: the single ADD instruction can determine from
the tag what operation to perform.
An old argument against the use of tags was that the amount of additional
memory hardware required (about 6% for the B6000) is not warranted by their
usefulness. This argument was dubious even in the days when memory was
expensive: the four parity bits of a four-byte IBM 360 word amount to an
extra 12.5%, so one might as well argue against byte addressability. Furthermore,
this extra 6% is not needed on secondary storage. Here only the 48 data
bits are used, the tag information existing in the disk segment descriptor
[Cam75].
Descriptors
The descriptor was one of the most novel features of the B5000 when
it was introduced twenty years ago. Indeed, Burroughs published a description
of the B5000 system and titled it "The Descriptor", (subtitled
"a definition of the B5000 Information Processing System"). The
descriptor, used simply as an array access mechanism, allows bounds checking
(done automatically by the hardware) as well as simplifying dynamic array
allocation (essential in an ALGOL machine). It also allows for differentiating
between word arrays and character strings, and can indicate the size (in
bits) of the characters. However, it is more powerful than this.
A single bit in the descriptor can be used to specify whether the array
(or other segment) is actually in core or not (the 'presence bit").
Bingo! Virtual memory. Indeed, the B5000 was perhaps the first commercial
computer to provide virtual memory. (How many computers today still don't?
How many can't because of their architecture?)
A variation of the descriptor, the "capability", appeared in
the design of the Plessey 250 [Lis75, pp.120-123] and more recent machines.
Perhaps the most modern of these is the Intel iAPX-432, which again uses
the term "descriptor" [Pol821. It is interesting to note that
this machine too was designed (or perhaps re-designed, see [Pos8l]) with
high level languages in mind, in this case languages like Ada, if not Ada
specifically [Rat8l], [Pol82].
The Instruction Set
The instruction set changed with the refinement of the B5000 design,
but subtly. To be sure, the instructions shrank from 12 bits to 8 bits,
but the concept of the operation set was similar. As mentioned above, this
instruction set, consistent across the B5000/B6000/B7000 series, is now
known as E-mode. As the op-codes can be packed six to a word (reducing
fetch overhead) , they are referred to in Burroughs terminology as syllables.
Some aspects of the instruction set have been discussed above; some brief
comments, by category, are given here.
Arithmetic Instructions. The B6000 has few of these, since 'redundant'
instructions are not needed (due to the tag bits and data word conventions(6))
hence only one ADD instruction exists. The B5000 had two ADD instructions,
one each for single and double precision, since the flag bit could not
distinguish the operands this way. (Compare this with ten on the VAX-11,
not counting the decimal-add and add-compare-and-branch instruction groups!
[DEC79, pp.140-1411)
String Instructions. The B5000/B6000, while being word address machines,
provide for easy access to bits and bit fields within words. Further, the
descriptors used for array access include a field which indicates whether
the array should be treated as an array of words or as a string of four-,
six-, or eight-bit characters. Operations on strings include the fairly
conventional block move and scan instructions, as well as translate instructions
and editing instructions. the latter are generally used for formatting
in conjunction with I/O.
Multitasking Support. This series supports multitasking in its high
level languages (yes, the compilers are extended to allow concurrent ALGOL
and COBOL!) One particularly useful instruction is the RDLK (read-lock).
It is an indivisible operation which reads from and writes into a memory
location (a similar instruction was available on the Plessey 250 [Lis75,
pg.37]).This can be used for task synchronizing flags. (Burroughs software
provide appropriate high level language interfaces to these features, using
the data type 'event' and software interrupts). Another instruction, useful
on multiprocessor configurations, is the HEYU, which interrupts the other
processors). An instruction such as this would be extremely useful when
designing multiple microprocessor systems.
Data Structure Support. The only real hardware data structure on
the B5000/B6000 is the vector, described and pointed to by a descriptor.
But one can do many useful things with vectors: the code segments and operand
stacks of the machine are vectors, and multidimensional arrays are implemented
using vectors of descriptors (dope vectors). Since the hardware also provides
easy access to different bit fields within the words (via a unit known
as the "mask-and-steering logic"), lists can be easily implemented
and managed. A standard format for the link words of a list (breaking the
word down into an address and a value field) is used by the LLLU (linked
list lookup) operator. This operator follows the links until the value
field matches or exceeds the operand of the LLLU, (or until the end of
the list is reached or a timeout interrupt occurs). Those familiar with
dynamic memory allocation techniques will recognize this as a hardware
implementation of the 'first fit' algorithm for segmented memory. Since
the MCP maintains the lists of free and allocated memory in precisely this
form (link words at the front of each segment, beginning at the bottom
of memory), it is obvious that memory allocation is quite fast on this
series of computers.
User Definable Instructions. The definition of the B6000 instruction
set leaves considerable room for future expansion, in that many possible
op codes are undefined. One unusual feature, however, is that sixteen opcodes
are defined as "programmed operators". If these are encountered
by the processor, a "Programmed Operator Interrupt" is generated,
and the last four bits of the instruction (these are sixteen-bit instructions)
is passed to the interrupt handler, which may be defined either within
the MCP or the user program. Thus, the operation set can be extended by
a sort of threaded-code technique(7).
This feature -- the programmed operator -- was used to implement the "do
vectormode" instruction to support vector hardware. The compilers
could safely generate code to take advantage of it, and if the resulting
code was then run on a machine lacking vector hardware, the equivalent
function could be provided in software, without any need to recompile the
original program.
Design Problems
If there were any faults with the original B5000 design, they were
quickly corrected with the B6000. As Organick says [Org73, pg.92], "there
appear to be no blunders" in the system's design. Indeed, it is quite
elegant. The only real problem in the history of this system is that the
design really was ahead of the time.
Since the hardware was required to perform many functions traditionally
left to software, it was necessarily complex. As the early models in this
series were implemented using discrete logic and SSI and MSI chips, the
parts count was bound to be high. This could lead to reliability problems.
To the credit of the Burroughs designers, considerable redundancy and flexibility
was built in (hardware modules could be off-lined and on-lined 'on the
fly') . The fault-tolerance of the design, and such innovations as the
Maintenance Diagnostic Logic processor, meant that the service record was
probably no worse than other, less complex systems of the same period.
Later models in the series -- the last of the 700s, and the 800 and 900s
-- took advantage of the rapid improvements in semiconductor technology,
and have proved the soundness of the original concept.
Conclusions
Twenty years later -- or some sixteen years after the B6500 -- time
and technology may be finally catching up with the B5000 system.
I have attempted to show that the B5000 included many features still considered
new, and which only now are appearing in other systems, The operator set
level of the B5500 design has, of commercial necessity, remained essentially
unchanged. Yet the architecture of this system could be refined further.
Some of Organick's suggestions [Org73, pp. 90-921 have been realized with
the introduction of vector hardware. others, such as extending the tag
field still further, modifying the interrupt hardware, and implementing
instruction set support for queue data structures would be useful, but
incompatible with the existing systems. (The VAX-11 is one recent computer
that provides support for queue data structures.)
Where will computer architecture go in the next twenty years? Anywhere?
Machines worth keeping an eye on are the iAPX-432 and the IBM System/38
[IBM78]. Both of these contain unique features and either could be the
B5000 of the eighties and nineties. But the concepts of this design are
not exhausted yet. They were combined simply and elegantly, while the System/38
and iAPX-432 may be overly complex (but no doubt the same was said of the
B5000 in the 1960s). Still ahead of the times? Perhaps not quite, but very
nearly. Whether this is taken as praise for the B5000's designers or criticism
of a generation of computer architects is left to the reader.
Footnotes
[Bur72] Burroughs Corp., Burroughs B6700 Information Processing
Systems
Reference Manual. Form 1058633, Burroughs Corp., Detroit, 1972.
Detroit, 1978.
[Cam75] Camelford, i.R., The Structure of the Burroughs B6700 Code File.
Technical Report, Queen's University Computer Centre, Kingston, December
1975.
[Jen781 Jensen, Carl,, "Taking Another Approach to Supercmputing",
Datamation,
February 1978, pp. 159-172.