The Architecture of the Burroughs B5000 -
20 Years Later and Still Ahead of the Times?

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

1. I would appreciate hearing of any other designs incorporating any of these features, especially any prior to 1961. I am also interested in hearing from anyone involved with the design of a computer in which features of the B5000 were consciously considered, either to be included or excluded.
   
   
2. The exact dates are not clear. Documents describing the B5000 were available as early as February 1961 [Bur6l], but Hayes (Hay78] says that first delivery was in 1963. Unless otherwise specified, the dates given here are the earliest to which I can find published reference, which are probably the announcement dates.
   
   
3. 'Global' is a Burroughs trademark for this shared memory feature.
   
   
4. Except address calculations, which are performed by a separate address adder within the Memory Control Unit.
   
   
5. Of course, a suitably privileged process may explicitly alter the tag bits and so modify itself, but only the ESPOL compiler will emit such code, and the MCP will refuse to execute as a normal program anything identified as ESPOLCODE. Such programs must be installed as part of the operating system.
   
   
6. For example, the only difference between a 'real' and an 'integer' is that an integer has an empty exponent part. However, the 48-bit word still leaves 39-bit integer precision. Integer subfields of words are extracted using the mask-and-steering logic to form an integer operand in the A register, and replaced in a similar manner.
   
   
7. This will require the cooperation of the site manager, as the compilers do not normally emit such code, nor can users modify code. This is a security feature of the MCP; only designated compilers can create executable code files, and only the MCP can designate a program as a compiler (via a console command).
   

1. [All8l]Allweiss, Jack A., & McClintock, John H., "High Level Language Design", Datamation, April 1981, pp. 186-191.
   

   
   

2. [Bur6l]Burroughs Corp., The Descriptor -- a definition of the B5000 Information Processing System. Bulletin 5000-20002-P, Burroughs Corp., Detroit, 1961.
   

   
   

3. [Bur63]Burroughs Corp., Operational Characteristics of the Processors for the Burroughs B5000. Form 5000-21005 Revision A, Burroughs Corp., Detroit, 1963.
   

   
   [Bur72] Burroughs Corp., Burroughs B6700 Information Processing Systems
   Reference Manual. Form 1058633, Burroughs Corp., Detroit, 1972.
   
   

4. [Bur78] Burroughs Corp.,Burroughs 1977 Annual Report. Burroughs Corp.,
   

   Detroit, 1978.
   

5. [Bur8O] Burroughs Corp."B6900 System Designed for Worldwide Networks", Burroughs International Group Users Report, Vol 2 No 1, April 1980, pp. 4-8.
   

   
   [Cam75] Camelford, i.R., The Structure of the Burroughs B6700 Code File.
   Technical Report, Queen's University Computer Centre, Kingston, December 1975.
   
   

6. [DEC791Digital Equipment Corp., VAX11 Architecture Handbook. Digital Equipment Corp., Maynard, Mass. 1979.
   

   
   

7. [Den7l]Denning, Peter J., "Third Generation Computer Systems" , ACM Computer Surveys, Vol 3 No 4, December 1971, pp. 175-216.
   

   
   

8. (Hay781Hayes, John P., Computer Architecture and organization. McGraw-Hill, New York, 1978.
   

   
   

9. [IBM781 IBM General Systems Div., IBM System/38 Technical Developments. International Business Machines Corp., Dec r 1978.
   

   
   [Jen781 Jensen, Carl,, "Taking Another Approach to Supercmputing", Datamation,
   February 1978, pp. 159-172.
   
   

10. [Lis751Lister, A.M., Fundamentals of Operating Systems. Macmillan Press Ltd., London, 1975.
    

    
    

11. [Org73]Organick, Elliott I., Computer System Organization: The B5700/B6700 Series. Academic Press, Inc., New York, 1973.
    

    
    

12. [Pol82] Pollack, Fred J., Cox, George W., et al., "Supporting Ada Memory Management in the iAPX-432", Proc. Symposium on Architectural Support for Programming Languages and Operating Systems, March 1982, pp. 117-131.
    

    
    

13. [Pos8l] Posa, John G., "A History of the Aloha Project", Electronics, Vol 4 No 54, February 24, 1981, pg. 125.
    

    
    

14. [Rat8l] Rattner, Justin & Lattin, Willian W., "Ada Determines Architecture of 32-bit Microprocessor", Electronics, Vol 4 No 54, February 24 1981, pp. 119-126.
    

    
    

15. [Sur76] Surden, Esther, "Burroughs Doubles Power of B6700s in 800 Models" Computerworld, Vol 10 No 29, July 19, 1976, pp. 1,6.