22C:18, Lecture 28, Summer 1997

Douglas W. Jones
University of Iowa Department of Computer Science

A Bit of History

In the 1960's, people sometimes described the computer industry as consisting of IBM and the BUNCH, where the latter term is an acronym for the other players in the computer industry of the era,

founded in the 1890's as a maker of business calculators, and, by the 1950's, a major force in the banking industry. They made the machines used to post interest to bank accounts, and when computers came along, naturally, they began to make computers for the same purposes. Burroughs eventually merged with Univac to make Unisys.

the very first computer sold commercially in the United States was the UNIVAC I; this company, eventually acquired by Sperry, was a major manufacturer of mainframes in the early 1960's, focusing on selling to the government and academic markets.

another company from the 19th century, originally and still the leading maker of cash registers, they came out with a fairly pedestrian line of business oriented mainframes in the 1960's.

founded in the 1950's, this company went on to build the world's fastest computers in the 1960's and into the 1970's. Seymour Cray designed these computers, and when he left the company, it began its decline.

yet another 19th century company, they have made thermostats since the 1890's, and their product line has grown to include complex industrial control systems. This led to a natural interest in computers applied to this area, and in the 1960's, Honeywell bought a number of computer manufacturers. When GE finally sold off its computer division, Honeywell bought that!

In the late 1960's, the BUNCH grew to include General Electric and Xerox, both of which sold some very interesting mainframes, so instead of talking about IBM and the BUNCH, people talked about Snow White and the Seven Dwarves. IBM, as Snow White, was, of course, untouchable, while the dwarves, while large companies in their own right, were hardly more than bit players in the computer industry.

All of these groupings omitted the most dynamic companies of the 1960's, the minicomputer makers. Companies like Digital Equipment Corporation, Hewlett Packard, Data General, and Motorola all began making small computers in this decade, and these computers, particularly DEC's PDP-11, were the major influence on the birth of microcomputers in the 1970's. From the point of view of the computer industry in the 1960's, however, these minicomputer makers seemed totally irrelevant!

The Burroughs 5000

This bit of history is relevant because it serves to introduce the Burroughs product line. The Burroughs 5000 and its successors were the most innovative new computers of the early 1960's. While no modern microprocessors (with the possible exception of the Rockwell AAMP) follow the design philosophy of these machines, the experience writing compilers for Algol on Burroughs machines shaped the style of memory use and addressing that dominates our thinking about procedure calling and activation records to this day.

The Burroughs architecture was not a low level architecture, but rather, a mid-level one. The machine language was at a high enough level that Burroughs did not use an assembly language; instead, they used dialects of Algol (the common ancestor of C, Pascal and Ada) for all their system programming.

Here is a summary of some aspects of the Burroughs architecture, ommitting all details of instruction coding and oversimplifing many issues:

Word Size:
48 bits.

Byte Size:
6 bits. Burroughs called them syllables!

PC - a byte pointer
Points to the next instruction syllable

SP - a word pointer
Points to the top of stack; this marks the end of the current activation record.

FP - a word pointer
Points to the base of the activation record. The activation record contains all local variables of the current procedure or function.

GP - a word pointer
Points to the base of the record of global variables

The stack:
Most machine instructions used the stack for their operands. The basic stack operations were defined as:
push(x) -- M[SP] = x; SP = SP + 1;
pop() -- SP = SP - 1; return M[SP]

The instruction set:
Most machine instructions were only one syllable, although some had extra syllables added to them
Push Immediate x

Versions of push immediate were available for short (one syllable) and long constants.

Push Local x
push( M[FP + x] )
Push Global x
push( M[GP + x] )

Pop Local x
M[FP + x] = pop()
Pop Global x
M[GP + x] = pop()

The push and pop instructions allowed the contents of local or global variables to be referenced. The displacement x used in these instrucitons was limited to 1 syllable, so no procedure could have more than 64 local variables, and no program could have more than 64 global variables! Arrays and records were referenced using pointers, so this limitation was not too serious.

push( pop() + pop() )
push( pop() - pop() )
push( pop() * pop() )
push( pop() / pop() )

Arithmetic instructions operated exclusively on operands on the stack! This was an RPN machine!

Branch d
PC = PC + d

Unconditional branch; d is a signed 12 bit displacement.

Branch Greater d
if pop() > 0 then PC = PC + d
Branch Less d
if pop() < 0 then PC = PC + d
Branch Equal d
if pop() = 0 then PC = PC + d
Branch Greater or Equal d
if pop() >= 0 then PC = PC + d
Branch Less or Equal d
if pop() <= 0 then PC = PC + d
Branch Not Equal d
if pop() != 0 then PC = PC + d

Conditional branches; d is a signed 12 bit displacement.

Simple Call p
push( PC ); push( FP ); FP = SP; PC = p
Simple Return
SP = FP; FP = pop(); PC = pop()

Simple calls cannot pass parameters. The simple return cannot return a result from a function.

Push Mark
push( 0 ); push( FP )
Parameterized Call p, n
M[SP - n - 2] = PC; FP = SP - n; PC = p

To pass parameters, first push the mark, then push each parameter, and finally use a parameterized call, with n equal to the number of parameters passed. The called procedure or function can address the parameters as local variables.

Function Return
temp = pop();SP = FP; FP = pop(); PC = pop(); push( temp )

To return a result, a function pushes it on the stack and then does a function return. This saves the parameter, pops the activation record off the stack, and then puts the parameter on the stack top.

Activation Record Format
All of the procedure linkage and local variable referencing instructions shown above assume the following activation record format:
		|   Free   |
		|  Space   |
		|          | <---- SP
		|          | \
		|Temporary |  \
		|     Stuff|   |
		|          |   |
		|----------|   |
		|          |   | Current
		|Local     |   | Activation
		| Variables|   | Record
		|          |   |
		|----------|   |
		|          |   |
		|Parameters|  /
		|          | / <-- FP
	     ---+o  Old FP |  A stack 
	    |   |   Old PC |  mark
	    |   |----------|
	    |   |          | \
	    |   |          |  > Previous Activation Record
	     -->|          | /
		|   Old FP |  An older
		|   Old PC |  stack mark

The above summary does not include many details of the Burroughs stack architecture, and it simplifies others. Nonetheless, it is a fair representation of how Burroughs went about designing their system.

Why Study The Burroughs 5000

Why are we interested in the B 5000? First, UNISYS still makes the descendants of this machine, and it is the machine from which much of our standard terminology about activation records is derived. Second, the B 5000 instruction set is at a much higher level than the instruction set on which we have focused up until this point.

Consider the following simple function:

	integer function multiply(x,y)
	  if x = 0
	    return 0
            return multiply(y,x-1)+y
Note first that the B 5000 had no assembly language! A B 5000 programmer would write something very similar to the above in Burroughs Algol, and would never see the actual machine instructions. As a result, there was no official symbolic instruction format for the B 5000 machine language, so we'll be informal here:
	   -- assume the caller the parameters above the mark
	   -- x is therefore local variable 0
	   -- y is therefore local variable 1
	   Push Local 0	-- get x
	   Branch Not Equal else
	   Push Immediate 0
	   Function Return
	   Push Mark -- setup to push parameters to call
	   Push Local 1 -- get y
	   Push Local 0 -- get x
	   Push Immediate 1
	   Subtract     -- we're passing x-1
	   Parameterized Call multiply, 2  -- the call
	   Push Local 1 -- get y again
	   Add		-- we're returning multiply(y,x-1)+y
	   Function Return
Note that the program makes no mention of registers! All you do is mention the variables, parameters, etc! From a programmer's perspective, this seems very civilized compared to the RISC architectures we've been exploring.

On the other hand, implementing such a stack architecture is expensive! Large amounts of hardware must be dedicated to doing things at run-time which we know how to do before run-time, using compilers or hand assembly methods. As a result, for just about any fixed choice of technology, If you fix the dollar cost you're willing to spend on the CPU, the stack CPU will run slower. If, instead, you fix the speed you demand, the stack CPU will cost more.

A Project

It is not hard to compose a set of macros that make a machine like the Hawk look like the B 5000! This will form the basis of the next extended example we will undertake.