10.6 THE BURROUGHS B5500

The B5000, announced by Burroughs in 1961, is a radical departure from the architecture of most computers. Most computers are register-oriented, from the programmer's point of view, while the Burroughs' computers are stack-oriented (see Section 4.5). The B5000 was the first of this line of computers. The B5500 (1965) was a second edition which solved some of the problems of the B5000. More recent computer systems, including the B2700, B3700 and B4700, and the B2800, B3800, and B4800, have followed the same general architectural design, although with new technology. We describe here the B5500, as the classic model of a stack machine.

<IMG>
FIGURE 10.21 A Burroughs B5500 computer system. The B5500 was a very successful computer system based on a stack architecture. (Photo courtesy of Burroughs Corporation.)

One point should be kept in mind during the discussion of the architecture of the B5500: there is virtually no assembly language programming for the B5500. In fact, there is no assembly language. This remarkable fact is a result of a conscious decision on the part of the designers of the Burroughs' computers. The designers saw the computer hardware as only a part of the overall computing system, composed of hardware and software. Thus, the B5500 was designed to efficiently execute higher-level languages, particularly Algol-like languages. Since it does this so well, there is no need for assembly language, and all code for Burroughs' computers is written in a higher-level language. This includes even the operating system, MCP.

With this in mind, we present a description of the Burroughs B5500.

Memory

The B5500 is a 48-bit machine with 15-bit addresses, allowing up to 32K words of memory. Each word can be either data or instructions. Data words can be interpreted in two ways. A 48-bit word can be interpreted as eight 6-bit characters; the character code is a variant of BCD.

<IMG>
FIGURE 10.22 Representation of numbers on the B5500. All numbers, both floating point and integer, are represented in this floating point format.

Alternatively, the data word can be interpreted as a number. Numbers are represented in floating point notation, with a 6-bit exponent and a 39-bit fraction. Each portion of the number, exponent and fraction, has a separate sign bit, using sign and magnitude notation. "Fraction" is a misleading term for the 39-bit part, since the decimal point is assumed to be at the far right of the "fraction," making the 39-bit portion an integer, not a fraction. This integer portion is in the range 0 to 549,755,813,887. The exponent base is 8, so the range of representation is approximately 8-51 to 8+76 with about 12 places of accuracy. There is no integer number representation; integers are simply floating point numbers with a zero exponent.

Instruction set

The instruction set for the B5500 is composed of two separate sets: word mode instructions and character mode instructions. The computer operates in one of two modes; word mode or character mode, with separate instruction sets for both modes. One of the instructions in word mode switches the B5500 to character mode; one of the instructions in character mode switches to word mode. A one-bit flag register remembers the current mode. We consider word mode operation first.

Word mode

In word mode, the B5500 is completely stack-oriented. Each instruction which needs an operand or generates a result uses the stack for the source of its operands and the destination of its results. For example, the ADD instruction takes the two words at the top of the stack, removes them from the stack, adds them, and places their sum back on the top of the stack. The stack is stored in memory and pointed at by a special register, the S register.

This approach to designing the instruction set has several advantages. No operand address need be specified in the instruction. A stack machine is thus called a 0-address machine. This makes the instruction very short, since it need only specify an opcode. Thus, programs are very short, saving memory. No registers are needed to act as accumulators or counters; all functions are performed on the top of the stack.

<IMG>
FIGURE 10.23 Instruction format for word-mode instructions. The two-bit type field selects either a literal (00), operand (01), descriptor (11), or operation (10); this determines the interpretation of the remaining 10 bits.

The B5500 has 12-bit instructions, allowing 4 instructions to be packed into each word. There are four types of instructions, selected by two bits of the instructions. These four types of instructions are,

  1. Literals (00). This instruction type is composed of a 10-bit literal. This literal is a small integer in the range 0 to 1023 and is copied to top of the stack. This allows small constants and addresses to be put on the stack directly.
  2. Operand (01). This instruction type consists of a 10-bit address. The contents of the addressed location is copied onto the top of the stack. This is similar to a load instruction.
  3. Descriptor (11). This instruction type includes a 10-bit address which is copied to the top of the stack.
  4. Operation (10). The remaining 10 bits of the instruction specify an operation to be performed, generally on the top of the stack.

The operand and descriptor instructions are more complex than the above description indicates. Notice for example that the descriptor function would appear to be the same as the literal function. Also both descriptor and operand instructions specify addresses, but only a 10-bit address, despite the fact that addresses are 15 bits. The reason for this is that the 10-bit "addresses" are not addresses into memory but rather indices into an area of memory called the Program Reference Table (PRT).

The PRT contains constants and simple variables for the program as well as pointers to more complex structures, such as subprograms and arrays. All references to subprograms and arrays are made indirectly through the PRT. The PRT acts like a symbol table (but without the symbols), allowing each symbol in a program to be represented by its index into the PRT rather than a complete 15-bit address. The descriptor function places the absolute 15-bit address of its PRT index on the stack.

Operations

The operations which can be performed on the B5500 are typical of most computers. The top two elements of the stack can be added, subtracted, multiplied, or divided, with the result placed on the top of the stack. These operations can be either single or double precision. All of these operations are floating point operations, but since integers are represented as unnormalized floating point numbers, these same operations can also be used on integers or mixed integer and floating point numbers. A special integer divide instruction allows an integer quotient and remainder to be generated from two numbers.

<IMG>
FIGURE 10.24 Stack operation on the B5500. All operations are done on the top elements of the stack, with the result being placed back on the stack. The S register points to the top of the stack.

Logical operations of AND, OR, equivalence (1 bit for each pair of identical bits, 0 bit for each pair of different bits), and negate operate on the top of the stack, placing the result on the top of the stack. Each word is treated as a string of 48 bits. These logical operations are useful in conjunction with the compare operators and for masking.

The compare operators compare the top two elements of the stack for equal, not equal, less, less or equal, greater, or greater or equal, whichever is selected, and places the result of the comparison (zero for false, nonzero for true) on the top of the stack. A special field compare instruction allows any two arbitrary fields of the top two elements of the stack to be compared.

Conditional jumps use the top of the stack to control jumping: jumping if true, not jumping if false. Unconditional jumps always jump. The address to which to jump is given on the top of the stack. Separate instructions exist for forward jumps and for backward jumps. The address on the stack is the offset (from the current instruction) of the instruction to which to jump. Since a jump will normally not be too far away, only the lower 12 bits of the stack address are used. This allows a jump to any instruction within 1023 words forward or backwards. In all cases the jump offset and logical value (for conditional jumps) are removed after the jump instruction is completed.

Storing operations require the value to be stored and the address of the location to be on the top of the stack. The value is stored in the memory location addressed, and normally both are removed from the stack. A special store operation allows the value to remain on the stack for further use, removing only the address from the stack.

A special set of instructions allows the top two elements on the stack to be interchanged, the top element to be duplicated, or the top element to be deleted.

An example of using the stack

To see how the stack structure of the B5500 affects its programming, consider the program to evaluate a simple arithmetic expression like,

((B+W)  *  Y)  +  2  + ((M-L) * K)/Z 
For the B5500, our program could look like
*
* OPCODE OPERAND STACK CONTENTS
*
OPERAND W W
OPERAND B W B
ADD W+B
OPERAND Y W+B Y
MUL (W+B)*Y
LITERAL 2 (W+B)*Y 2
ADD ((W+B)*Y)+2
OPERAND M ((W+B)*Y)+2 M
OPERAND L ((W+B)*Y)+2 M L
SUB ((W+B)*Y)+2 M-L
OPERAND K ((W+B)*Y)+2 M-L K
MUL ((W+B)*Y)+2 (M-L)*K
OPERAND Z ((W+B)*Y)+2 (M-L)*K Z
DIV ((W+B)*Y)+2 ((M-L)*K)/Z
ADD (((W+B)*Y)+2) + (((M-L)*K)/Z)

This expression was programmed in Chapter 4 with 10 MIX instructions, while the above B5500 program takes 15 instructions. However, remember that MIX instructions are 31 bits in length, while B5500 instructions are only 12 bits. Thus, the MIX program took 310 bits compared to the 180 bits for the B5500 program. Also the MIX program required a temporary storage location, while the B5500 program needs no temporary storage, storing all intermediate results on the stack.

Character mode

One special control instruction for the B5500 changes the mode of execution to character mode. In character mode, the entire instruction is interpreted in a different manner. There is no stack. Two special registers point to two areas of memory called the source and the destination. Operations transfer from the source to the destination, compare the source to the destination, add or subtract the source to the destination (as decimal integers), and perform editing operations (like suppressing leading zeros). Two instructions are almost exactly like NUM and CHAR in MIX. The length of the character strings is included in each 12-bit instruction. Each instruction has a 6-bit repeat field and a 6-bit opcode field. This allows character strings to be any length from 0 to 63.

<IMG>
FIGURE 10.25 Instruction format in character mode. Each instruction has a 6-bit repeat count and a 6-bit opcode. All operations are between two memory areas, the source character string and the destination character string.

An interesting pair of special instructions is the BEGIN-LOOP/END-LOOP pair. When a BEGIN-LOOP opcode is encountered, a counter is initialized to the 6-bit repeat field in the instruction and the address of the BEGIN-LOOP instruction is remembered. When an END-LOOP instruction is executed, the counter is decremented. If it is still positive, the loop is repeated from the address following the BEGIN-LOOP instruction, if the counter is zero, the computer continues to the next instruction, following the END-LOOP instruction. These instructions allow loops on character strings without the need for an explicit counter, decrement, and conditional jump.

I/O and interrupts

The input and output of information is handled by channels executing a channel program. The I/O start instruction starts the channel executing a channel program which starts at memory location 8. An interrupt system is used to signal completion of I/O and also to handle exceptional conditions such as overflow or underflow (of numbers or of the stack), divide by zero, memory parity errors, and so on. A 7-bit interrupt code is used to indicate the type of interrupt occurring. Interrupts are vectored through locations in low memory. Registers are stacked when the interrupt occurs, allowing the interrupted program to be restarted after the interrupt is serviced.

EXERCISES

  1. Describe the memory of the B5500.

  2. What would be the advantage of building a machine which does not need assembly language programs?

  3. Can all programming for a computer be done in a higher-level language, or must at least some program be written in machine language at least once? (Hint: consider loaders),

  4. Why are there two modes of operation on the B5500?

  5. Why are there no integer numbers on the B5500?

  6. Write a program for the B5500 to calculate the expression, Y + 2 * (W + V) / 4 - 6 * (10 - W - V).

  7. A stack machine allows instructions to be much shorter, since no address need be specified for arithmetic operations. Does this mean all programs are always shorter on a stack machine?