In many early systems and languages, programmers were often told not to make their routines too small. Procedure calls and returns were expensive, because a number of operations had to be performed to maintain the stack. The B5000 was designed as a stack machine – all program data except for arrays (which include strings and objects) was kept on the stack. This meant that stack operations were optimized for efficiency. As a stack-oriented machine, there are no programmer addressable registers.
Multitasking is also very efficient on the B5000 and B6500 lines. There are specific instruction to perform process switches: ;B5000, B5500, B5700 :Initiate P1 (IP1) and Initiate P2 (IP2) Each stack and associated One way to increase system speed is to keep data as close to the processor as possible. In the B5000 stack, this was done by assigning the top two positions of the stack to two registers A and B. Most operations are performed on those two top of stack positions. On faster machines past the B5000, more of the stack may be kept in registers or cache near the processor. Thus the designers of the current successors to the B5000 systems can optimize in whatever is the latest technique, and programmers do not have to adjust their code for it to run faster – they do not even need to recompile, thus protecting software investment. Some programs have been known to run for years over many processor upgrades. Such speed up is limited on register-based machines. Another point for speed as promoted by the RISC designers was that processor speed is considerably faster if everything is on a single chip. It was a valid point in the 1970s when more complex architectures such as the B5000 required too many transistors to fit on a single chip. However, this is not the case today and every B5000 successor machine now fits on a single chip as well as the performance support techniques such as caches and instruction pipelines. In fact, the A Series line of B5000 successors included the first single chip mainframe, the Micro-A of the late 1980s. This "mainframe" chip (named SCAMP for Single-Chip A-series Mainframe Processor) sat on an Intel-based plug-in PC board.
How programs map to the stack Here is an example of how programs map to the stack structure
begin — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — This is lexical level 2 (level zero is reserved for the operating system and level 1 for code segments). — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — At level 2 we place global variables for our program.
integer i,
j,
k;
real f,
g;
array a [0:9];
procedure p (
real p1,
p2);
value p1; — p1 passed by value, p2 implicitly passed by reference.
begin — — — — — — — — — — — — — — — — — — — This block is at lexical level 3 — — — — — — — — — — — — — — — — — —
real r1,
r2;
r2 :=
p1 *
5;
p2 :=
r2; — This sets
g to the value of
r2 p1 :=
r2; — This sets
p1 to
r2, but not
f — Since this overwrites the original value of
f in
p1 it
might be a — coding mistake. Some few of ALGOL's successors therefore insist that — value parameters be read only – but most do not.
if r2 >
10 then begin — — — — — — — — — — — — — — — — — — — — — — — — — — — — — A variable declared here makes this lexical level 4 — — — — — — — — — — — — — — — — — — — — — — — — — — — —
integer n; — The declaration of a variable makes this a block, which will invoke some — stack building code. Normally you won't declare variables here, in which — case this would be a compound statement, not a block. ... 3 |
MSCW | (4, 0) The Mark Stack Control Word containing the link to D[3]. |=======================| | 0 |
r2 | (3, 5) The real
r2 |-----------------------| | 0 |
r1 | (3, 4) The real
r1 |-----------------------| | 1 |
p2 | (3, 3) A SIRW reference to
g at (2,6) |-----------------------| | 0 |
p1 | (3, 2) The parameter
p1 from value of
f |-----------------------| | 3 |
RCW | (3, 1) A return control word |-----------------------| | D[3]==>3 |
MSCW | (3, 0) The Mark Stack Control Word containing the link to D[2]. |=======================| | 1 |
a | (2, 7) The array
a ======>[ten word memory block] |-----------------------| | 0 |
g | (2, 6) The real
g |-----------------------| | 0 |
f | (2, 5) The real
f |-----------------------| | 0 |
k | (2, 4) The integer
k |-----------------------| | 0 |
j | (2, 3) The integer
j |-----------------------| | 0 |
i | (2, 2) The integer
i |-----------------------| | 3 |
RCW | (2, 1) A return control word |-----------------------| | D[2]==>3 |
MSCW | (2, 0) The Mark Stack Control Word containing the link to the previous stack frame. |=======================| — Stack bottom If we had invoked the procedure p as a coroutine, or a process instruction, the D[3] environment would have become a separate D[3]-based stack. This means that asynchronous processes still have access to the D[2] environment as implied in ALGOL program code. Taking this one step further, a totally different program could call another program's code, creating a D[3] stack frame pointing to another process' D[2] environment on top of its own process stack. At an instant the whole address space from the code's execution environment changes, making the D[2] environment on the own process stack not directly addressable and instead make the D[2] environment in another process stack directly addressable. This is how library calls are implemented. At such a cross-stack call, the calling code and called code could even originate from programs written in different source languages and be compiled by different compilers. The D[1] and D[0] environments do not occur in the current process's stack. The D[1] environment is the code segment dictionary, which is shared by all processes running the same code. The D[0] environment represents entities exported by the operating system. Stack frames actually don't even have to exist in a process stack. This feature was used early on for file I/O optimization, the FIB (file information block) was linked into the display registers at D[1] during I/O operations. In the early nineties, this ability was implemented as a language feature as STRUCTURE BLOCKs and – combined with library technology - as CONNECTION BLOCKs. The ability to link a data structure into the display register address scope implemented object orientation. Thus, the B6500 actually used a form of object orientation long before the term was ever used. On other systems, the compiler might build its symbol table in a similar manner, but eventually the storage requirements would be collated and the machine code would be written to use flat memory addresses of 16-bits or 32-bits or even 64-bits. These addresses might contain anything so that a write to the wrong address could damage anything. Instead, the two-part address scheme was implemented by the hardware. At each lexical level, variables were placed at displacements up from the base of the level's stack, typically occupying one word - double precision or complex variables would occupy two. Arrays were
not stored in this area, only a one word descriptor for the array was. Thus, at each lexical level the total storage requirement was not great: dozens, hundreds or a few thousand in extreme cases, certainly not a count requiring 32-bits or more. And indeed, this was reflected in the form of the VALC instruction (value call) that loaded an operand onto the stack. This op-code was two bits long and the rest of the byte's bits were concatenated with the following byte to give a fourteen-bit addressing field. The code being executed would be at some lexical level, say six: this meant that only lexical levels zero to six were valid, and so just three bits were needed to specify the lexical level desired. The address part of the VALC operation thus reserved just three bits for that purpose, with the remainder being available for referring to entities at that and lower levels. A deeply nested procedure (thus at a high lexical level) would have fewer bits available to identify entities: for level sixteen upwards five bits would be needed to specify the choice of levels 0–31 thus leaving nine bits to identify no more than the first 512 entities of any lexical level. This is much more compact than addressing entities by their literal memory address in a 32-bit addressing space. Further, only the VALC opcode loaded data: opcodes for ADD, MULT and so forth did no addressing, working entirely on the top elements of the stack. Much more important is that this method meant that many errors possible on systems employing flat addressing could not occur because they were simply unspeakable even at the machine code level. A task had no way to corrupt memory in use by another task, because it had no way to develop its address. Offsets from a specified D-register would be checked by the hardware against the stack frame bound: rogue values would be trapped. Similarly, within a task, an array descriptor contained information on the array's bounds, and so any indexing operation was checked by the hardware: put another way, each array formed its own address space. In any case, the tagging of all memory words provided a second level of protection: a misdirected assignment of a value could only go to a data-holding location, not to one holding a pointer or an array descriptor, etc. and certainly not to a location holding machine code.
Array storage Arrays were not stored contiguous in memory with other variables, they were each granted their own address space, which was located via the descriptor. The access mechanism was to calculate on the stack the index variable (which therefore had the full integer range potential, not just fourteen bits) and use it as the offset into the array's address space, with bound checking provided by the hardware. By default, should an array's length exceed 1,024 words, the array would be segmented, and the index be converted into a segment index and an offset into the indexed segment. There was, however, the option to prevent segmentation by specifying the array as LONG in the declaration. In ALGOL's case, a multidimensional array would employ multiple levels of such addressing. For a reference to A[i,j], the first index would be into an array of descriptors, one descriptor for each of the rows of A, which row would then be indexed with j as for a single-dimensional array, and so on for higher dimensions. Hardware checking against the known bounds of all the array's indices would prevent erroneous indexing. FORTRAN however regards all multidimensional arrays as being equivalent to a single-dimensional array of the same size, and for a multidimensional array simple integer arithmetic is used to calculate the offset where element A[i,j,k] would be found in that single sequence. The single-dimensional equivalent array, possibly segmented if large enough, would then be accessed in the same manner as a single-dimensional array in ALGOL. Although accessing outside this array would be prevented, a wrong value for one index combined with a suitably wrong value for another index might not result in a bounds violation of the single sequence array; in other words, the indices were not checked individually. Because an array's storage was not bounded on each side by storage for other items, it was easy for the system to "resize" an array - though changing the number of dimensions was precluded because compilers required all references to have the same number of dimensions. In ALGOL's case, this enabled the development of "ragged" arrays, rather than the usual fixed rectangular (or higher dimension) arrays. Thus in two dimensions, a ragged array would have rows that were of different sizes. For instance, given a large array A[100,100] of mostly-zero values, a sparse array representation that was declared as SA[100,0] could have each row resized to have exactly enough elements to hold only the non-zero values of A along that row. Because arrays larger than 1024 words were generally segmented but smaller arrays were not, on a system that was short of real memory, increasing the declared size of a collection of scratchpad arrays from 1,000 to say 1,050 could mean that the program would run with far less "thrashing" as only the smaller individual segments in use were needed in memory. Actual storage for an array segment would be allocated at run time only if an element in that segment were accessed, and all elements of a created segment would be initialised to zero. Not initialising an array to zero at the start therefore was encouraged by this, normally an unwise omission. Array equivalencing is also supported. The ARRAY declaration requested allocation of 48-bit data words which could be used to store any bit pattern but the general operational practice was that each allocated word was considered to be a REAL operand. The declaration of: ARRAY A [0:99] requested the allocation of 100 words of type REAL data space in memory. The programmer could also specify that the memory might be referred to as character oriented data by the following equivalence declaration: EBCDIC ARRAY EA [0] = A [*]; or as hexadecimal data via the equivalence declaration: HEX ARRAY HA [0] = A [*]; or as ASCII data via the equivalence declaration: ASCII ARRAY AA [0] = A[*]; The capability to request data type specific arrays without equivalencing is also supported, e.g. EBCDIC ARRAY MY_EA [0:99] requested that the system allocated a 100 character array. Given that the architecture is word based, the actual space allocated is the requested number of characters rounded up to the next whole word boundary. The Data Descriptor generated at compilation time indicated the data type usage for which the array was intended. If an array equivalence declaration was made a copy descriptor indicating that particular usage type was generated but pointed back to the original, or MOM, descriptor. Thus, indexing the correct location in memory was always guaranteed. BOOLEAN arrays are also supported and may be used as a bit vector. INTEGER arrays may also be requested. The immediately preceding discussion uses the ALGOL syntax implementation to describe ARRAY declarations, but the same functionality is supported in COBOL and FORTRAN.
Stack structure advantages One nice thing about the stack structure is that if a program does happen to fail, a stack dump is taken and it is very easy for a programmer to find out exactly what the state of a running program was. Compare that to core dumps and exchange packages of other systems. Another thing about the stack structure is that programs are implicitly recursive. FORTRAN was not expected to support recursion and perhaps one stumbling block to people's understanding of how ALGOL was to be implemented was how to implement recursion. On the B5000, this was not a problem – in fact, they had the reverse problem, how to stop programs from being recursive. In the end they didn't bother. The Burroughs FORTRAN compiler allowed recursive calls (just as every other FORTRAN compiler does), but unlike many other computers, on a stack-based system the returns from such calls succeeded as well. This could have odd effects, as with a system for the formal manipulation of mathematical expressions whose central subroutines repeatedly invoked each other without ever returning: large jobs were ended by stack overflow! Thus Burroughs FORTRAN had better error checking than other contemporary implementation of FORTRAN. For instance, for subroutines and functions it checked that they were invoked with the correct number of parameters, as is normal for ALGOL-style compilers. On other computers, such mismatches were common causes of crashes. Similarly with the array-bound checking: programs that had been used for years on other systems embarrassingly often would fail when run on a Burroughs system. In fact, Burroughs became known for its superior compilers and implementation of languages, including the object-oriented
Simula (a superset of ALGOL), and
Iverson, the designer of
APL declared that the Burroughs implementation of APL was the best he'd seen.
John McCarthy, the language designer of
LISP disagreed, since LISP was based on modifiable code, he did not like the unmodifiable code of the B5000, but most LISP implementations would run in an interpretive environment anyway. The storage required for the multiple processes came from the system's memory pool as needed. There was no need to do SYSGENs on Burroughs systems as with competing systems in order to preconfigure
memory partitions in which to run tasks. ==Tagged architecture==