Text preview for : 1035441_B6500_B7500_Stack_Mechanism_1968.pdf part of burroughs 1035441 B6500 B7500 Stack Mechanism 1968 burroughs B6500_6700 1035441_B6500_B7500_Stack_Mechanism_1968.pdf
Back to : 1035441_B6500_B7500_Stack | Home
Reprintedfrom
AFIPS
ConferenceProceedings
Volume 32, 1968
by E. A. HAUCK and B. A. DENT
BurroughsCorporation
Pasadena.California
INTRODUCTION and within the Processor in 51 bit words. The first 3
bits of the word are used as tag bits, which serve to
Burroughs' B6500/B7500 system structure and
identify the various word types as illustrated in Fig. 1.
philosophy are an extension of the concepts employed
The remaining 48 bits are data. Tag bits, in addition
in the development of the B5500 system. The unique
to identifying word type, provide the 86500/87500
features, common to both hardware systems, are
Processor with two unique features: (1) data may be
that they have been designed to operate under the
referenced as an operand, with the processor worrying
control of an executive program (MCP) and are to
about whether the operand consists of one or two
be programmed in only higher level languages (e.g.,
words, and (2) system integrity and memory pro-
ALGOL, COBOL, and FORTRAN). Through a
tection are extended to the level of the basic machine
close integration of the software and hardware dis-
data words. If a job attempts to execute data as pro-
ciplines, a machine organization has been developed
gram code, or to modify program code, the system is
which permits the compilation of efficient machine
code and which is addressed to the solution of prob- interrupted.
lems associated with multiprogramming, multiprocess-
ing and time sharing.
Some of the important features provided by the DATA WORDS
86500/B7500 system are dynamic storage allocation, I 000 Ii EXPONENT! MANTISSA I ~~~~{;ftECISION
re-entrant programming, recursive procedure facili-
ties, a tree structured stack organization, memory pro- I 0101
!IO EXPONENT
! EXPONENT!
I
MANTISSAtMSJ DOUBLE PRECISION
OPERAND-II' WORD
tection and an efficient interrupt system. A compre-
hensive stack mechanism is the basic ingredient of the 010
I 0101 EXPONENTIMSII
EJPONENTIMSII MANTISSA (LSI
MANTISSA (LSI II DOUBLE PRECISION
OPERAND-2nd WORD
86500/87500 system for providing these features. .-6 BITS
~I. 39 BITS---~
86500187500 processor
The command structure of the 86500/87500 Pro-
cessor is Polish string, which allows for the separa-
tion of program code and data addresses. The basic
machine instruction is called an operator syllable.
This operator syllable is variable in length, from a
minimum of 8 bits to a maximum of 96 bits. In the
interest of code compactness, more frequently used
operator syllables are encoded in the 8 bit form.
The Processor is provided with a hardware imple-
mented stack in which to manipulate data and store
dynamic program history. Also, data may be located
in arrays outside the stack and may be brought to the
stack temporarily for processing. Program parameters,
local variables, references to program procedures and
data arrays are normally stored within the stack.
The data word of the 86500/87500 Processor is
51 bits long. Data are transferred between memory Figure 1- 86500/87500word formats
245
246 SpringJoint ComputerConference,1968
The stack register, and the Stack Limit (SL) register. The con-
tents (\f the 80S register defines t11ebase of the stack
The stack consists of an area of memory assignedto
area, and the SL register defines the upper limit of the
a job. This stack area serves to provide storage for
stack area. The job is interrupted if the S register is
basic program and data references associated with
set to the value contained in either SL or 80S.
the job. In addition, it provides a facility for the tem-
The contents of the top-of-stack registers are main-
porary storage of data and job history. When the
job is activated, four high speed registers (A, X, 8 tained automatically by the processor hardware in
accordance with the environmental demands of the
and Y) are linked to the job's stack area (Fig. 2). This
current operator syllable. If the current operator
linkage is established by the stack pointer register
(S), which contains the memory address of the last syllable demands that data be brought into the stack,
then the top-of-stack registers are adjusted to accom-
word placed in the stack memory area. The four top-
of-stack registers (A, X, 8 and Y) function to extend modate the incoming data, and the surplus contents
of the top-of-stack registers, if any, are pushed into
the job's stack into a quick access environment for
the job's stack memory area. Words are brought out
data manipulation.
of the job's stack memory area and pushed into the
top-of-stack register for operator syllables which
IN/~TPUT TOP OF STACK REGISTER
" 1 require the presence of data in the top-of-stack regis-
MTM DA~'-
OF I ters, but do not explicitly move data into the stack.
TO STACK-'-I
I
Top-of-stack registers operate in an operand ori-
I ented fashion as opposed to being word oriented. Call-
L_.
Iing a double precision operand into the top-of-stack
-~
registers implies the loading of two memory words into
the top-or-stack registers. The first word is always
~St AREA
ASSIGNED
TO PROGRAM
"t" loaded into the A register where its tag bits are
checked. If the word has a double precision tag, a
second word is loaded into X. The A and X registers
~I are then concatenated to form a double precision
operand image. The 8 and Y registers concatenate
STACK AREA
CURRENTLY when a double precision operand is moved to the 8
IN USE rSr~ UMiT""REGiS"T""ER
f
register. The double precision operand splits back to
single words as it is pushed from the 8 and Y registers
into the stack memory area. The reverse process is
L___~ repeated when the double precision operand is eventu-
STACK
ally popped up from the stack memory area back
MEMORY
AREA into the top-of-stack registers.
Figure 2 -Top of stack and stack bounds registers
Data are brought into the.stack through the top-of- Data addressing
stack registers. The stack's operating characteristic Three mechanisms exist within the 86500/87500
is such that the l~st operand placed into the stack is the Processor for addressing data or program code: (I)
first to be extracted. The top-of-stack registers be- Data Descriptor (DD)/Segment Descriptor (SO),
come saturated after having been filled with two oper- (2) Indirect Reference Word (IRW), and (3) Stuffed
ands. Loading a third operand into the top-of-stack Indirect Reference Word (IRWS). The Data Descrip-
registers causes an operand to be pushed from the tor (DO) and Segment Descriptor (SO) are 85500
top-of-stack registers into the stack memory area. carryovers and provide the basic mechanism for
The stack pointer register (S) is incremented by one as addressing data or program segments which are lo-
each additional word is placed into the stack memory cated outside of the job's stack area. The basic
area; and is, of course, decremented by one as a word addressing component of the descriptor is an absolute
is withdrawn from the stack memory area and placed machine address. The Indirect Reference Word (IRW)
in the top-of-stack registers. As a result, the S register and the Stuffed Indirect Reference Word (IRWS) are
continually points to the last word placed into the 86500/87500 mechanisms for addressingdata located
job's stack memory area. within the job's stack memory area. The addressing
A job's stack memory area is bound, for memory component of both the IRW and IRWS is a relative
protection, by two registers, the Base of Stack (BOS) address. The IRW is used to address within the im-
WORD
Burroughs' B6500/B7500 Stack Mechanism 247
mediate environment of the job's stack, and addresses scriptor is set to ONE to indicate that indexin~ has
relative to a displav register (described later in Non- taken place. The ADDRESS and LENGTH fields
local Addressing). The IRWS is used to address be- are added together to generate an absolute machine
yond the immediate environment of the current pro- address whenever a present, indexed Data Descriptor
cedure, and addresses relative to the base of the job's is used to fetch or store data.
stack. Addressing across stacks is accomplished The Double Precision bit (D) is used to identify the
with an IRWS. referenced data as being either single or double
precision and, as a result, is also associated with the
The descriptor indexing operation. The D bit being equal to ONE
In general, the descriptor functiohsto describe and signifies double precision and implies that the index
locate data or program code associated with 2. given value be multiplied by two before indexing.
job. The Data Descriptor (DD) is used to fetch data The Read-Only bit (R) specifies that the memory
to the stack or store data from the stack into an array area described by the Data Descriptor is a read-only
which resides outside the job's stack area. The format area. An interrupt is incurred uDon referencinl! an
of Data and Segment Descriptors are illustrated in area through a descriptor with the intention to write
Fig. I. The ADDRESS field of both descriptors is if the R bit is equal to ONE.
20 bits in length and contains the absolute address of The Copy bit (C) identifies a descriptor as being a
an array in either main system memory or in the back- copy of a master descriptor and is related to the pres-
up disk store. The Presence bit (P) indicates whether ent bit action. The intent of the copy action is to keep
the referenced data are present in main system mem- multiple copies of an absent descriptor linked back to
ory or in the back-up disk store, and is set equal -to one master descriptor. Copy action is incurred when
ONE when the referenced data are present in main a job attempts to pass by name an absent Data De-
system memory. scriptor. When this occurs, the hardware manufac-
A Presence Bit Interrupt is incurred when the job tures a copy of the master descriptor, forces the C bit
makes reference to data via a descriptor which has a P equal to ONE and inserts into the ADDRESS field
bit equal to ZERO. The Presence Bit Interrupt stimu- the address of the master descriptor. Thus, multiple
lates the operating system (called the Master Control copies of absent descriptors are all linked back to the
Program, or MCP) to move the data from disk to main master descriptor.
memory. The data location on disk is contained in the
ADDRESS field of the DD when the P bit is equal to Non-localaddressing
ZERO. After transferring the data array into the The most important single aspect of the B6500/
main memory, the operating system (MCP) marks the B7500 stack is its facility for storing the dynamic
descriptor present by setting the P bit equal to ONE, history of a program under execution. Two lists of
and places the current memory address into the AD- program information are saved in the B6500/B7500
DRESS field of the descriptor. The interrupted job stack, the stack history list and the addressing environ-
is then reactivated. ment list. The stack history list is dynamic in nature,
A Data Descriptor may describe either an entire varying as the job is driven through different program
array of data words, or a particular element within an paths with changing sets of data. Both lists are gen-
array of data words. If the descriptor describes an erated and maintained by the B6500/B7500 hardware
entire array, the Indexed bit (I-bit) in the descriptor system.
is ZERO, indicating that the descriptor has not yet The stack history list is formed from a list of Mark
been indexed. The LENGTH field of the descriptor Stack Control Words (MSCW) which are linked to-
defines the length of the data array. gether by their DF fields (Fig. 3). A MSCW is inserted
A particular element of an array may be described into the stack as a procedure is entered, and is ex-
by indexing an array descriptor. Memory protection tracted as that procedure is exited. Therefore, the
is insured during indexing operations by performing a stack history list grows and contracts in accordance
comparison between the LENGTH field of the de- with the procedural depth of the program. Mark Stack
scriptor and the index being applied to it. An Invalid Control Words serve to identify the portion of the
Index Interrupt is incurred if the index value exceeds stack related to each procedure. When the procedure
the length of the memory area defined by the de- is entered, its parameters and local variables are en-
scriptor. tered in the stack following the MSCW. When ex-
If the value being used to index the descriptor is ecuting the procedure, its parameters and local vari-
valid, the LENGTH field of the descriptor is replaced ables are referenced by addressing relative to the loca-
by the index value. At this time the I-bit in the de- tion of the related MSCW.
248 SpringJoint ComputerConference,1968
This concept is implemented in the Burroughs'
B5500 system, and it provides a convenient means to
handle subroutine entry and exit. But this mechanism
alone also gives rise to one of the most serious limita-
tions of the ALGOL implementation on the B5500.
In the B5500 stack, local variables are addressedrela-
tive to the first Mark Stack Control Word (which
corresponds to the outer-most block), or relative to
the most recent Mark Stack Control Word (which
corresponds to the current procedure). All intervening
Mark Stack Control Words, however, are invisible to
the current procedure. This means that the variables
declared global to the current procedure, but local to
some other procedure, cannot be addressed at all!
This inability to reference variables declared non-local
to the current procedure but local to some other pro-
cedure is termed the non-local addressing problem.
The manner in which these variables are addressed
in the B6500/B7500 stack can best be understood by.
analyzing the structure of an ALGOL program. The
addressing environment of an ALGOL procedure is
established when the program is structured by the
programmer, and is referred to as the lexicographical
ordering of the procedural blocks (Fig. 6A). At com-
Figure 3 -Stack history and addressing environment list pile time, this lexicographical ordering is used to form
address couples. An address couple consists of two
Each MSCW is linked back to the prior MSCW items: I) the lexicographical level through the contents of its DF field to identify the and 2) an index value (8) used to locate the specific.
pomt in the stack where the prior procedure began. variable within a given lexicographical level. The lexi-
When a procedure is exited, its related portion of cographical ordering of the program remains static as
the stack is discarded. This action is achieved by the program is executed, thereby allowing variables to
setting the stack pointer register (S) to point to the be referenced via address couples as the program is
memory cell preceding the most recent MSCW (Fig.
executed.
4). This top-most MSCW, pointed to by another
register (F), is in effect deleted from the stack history
list by causing F to point back at the prior MSCW,
thereby placing it at the head of the stack history
list.
Figure -' -Display registers indicatin