ARM_VPT_IPR_00000488
`
`ARM Ex. 1012
`IPR Petition - USP 5,463,750
`
`

`

`
`
`US. Patent
`
`Nhuth 30,1976
`
`Sheet] ofS
`
`3,947,823
`
`
`
`
`S
`P
`IPL
`
`'
`
`I
`
`
`-—-
`
`-——-
`
`ON
`
`- “L
`
`INSTRUCTION
`
`UNIT
`CIRCUITS
`
`EXEC UNIT
`
`I
`I
`I
`
`3
`
`RECIII
`
`.__.
`.
`
`
`I0
`
`(SEE FIC2)
`
`HANDLING
`|
`I
`I
`I
`I
`:
`I
`I
`I
`400
`I
`CPU A_I
`
`|
`I
`| ”MO
`I
`CIRCUITS
`m
`I
`I—
`:
`“a 6”
`12+
`‘
`.CUNTRDL
`I
`I = m CONTROL
`I
`| L
`CIRCUITS
`1
`I
`I05
`I0?
`109
`I
`W =
`READDH
`I
`L_ -n IIO
`40
`
`
`_.‘
`
`_\
`
`30
`
`{BIA
`
`_
`
`“J“
`
`E
`RUS
`
`
`CONTROL
`c
`
`v
`D
`E
`R
`
`I
`:
`
`*——|
`[—
`I
`I
`(STII
`I _ I
`I = |
`I
`|
`I
`PACEIARLEzIPer
`I = I
`I
`I
`I
`PAGETABLEIIPTI) I—
`I
`I‘-2II
`'iHARED MAIN STORE
`
`__
`
`I
`
`
`
`—
`
`ARM_VPT_IPR_00000489
`ARM_VPT_IPR_OOOOO489
`
`CPUB
`
`l
`I
`I
`I
`L——r——'
`I
`.
`I
`'
`II
`“L“7
`I
`I
`I
`.
`"1______I
`
`
`
`I
`
`

`

`
`
`US. Patent March 30, 1976
`
`Sheet 2 of5
`
`3,947,823
`
`(AAB comm CIRCUITS)
`
`
`.18
`
`
`
`
`
`{SIDDD
`S VALID“)
`
`22
`
`QPIII‘I VA.
`REE].
`5*
`
`_
`
`' f ‘1
`23
`
`1517000 SEL.
`
`52"
`n S
`R
`
`2NDEUEN
`VALID
`
`H)
`TGR c
`l}
`
`52
`
`OPDZVA
`
`34
`
`34
`II
`
`82
`
`55
`
`72
`4?
`
`'1' I
`
`70
`
`42
`
`Ill
`
`
`
`ARM_VPT_IPR_00000490
`ARM_VPT_IPR_OOOOO490
`
`
`
`
`
`
`
`
`
`
`
`
`ENBEVEN BEL
`
`zunonn
`SVAHD{H
`
`In
`45
`
`
`
`3
`9
`103
`
`w
`
`MODE mm
`STORE
`
`5
`
`G
`
`I!
`a film
`n M
`41
`
`44
`an
`‘13/ Izuoonn SEL.
`74
`' 75
`prmm)
`II n
`
`73
`TRANSLATION REG.)
`75
`(xwmm.
`
`52
`'
`MWLL
`1047
`__
`
`
`PL
`50’7‘éfi‘ifléfilmm ' mm mm H
`
`ADDRESS OUT)
`LINE'
`
`
`
`~ Mflfiffis
`DAT" 393-
`
`____..(IHCLUDES TLB GIRLS}
`
`pL
`,PTLUDKUPCTRLS)
`MAINSTURE
`
`lstAcE BUS
`ADDHINVAR {
`
`L
`._____.__..
`'
`.__
`_A_
`
`SARHU
`(Tam-15mm: EXCF m cwm CANCEL INST & TAKE ENTR'PJ
`‘01
`
`

`

`US. Patent March 30, 1976
`
`Sheet 3 of5
`
`3,947,823
`
`FIG.3 (summon or PAGE FRAME mvnunmou BY ANY CPU)
`
`THS CPU
`MVAUDATES ENTRY
`
`
`
`PUHGE TLB FOR
`THIS CPU
`
`
`
`
`INHYALIZE CCUHDIHATTON
`COUNT FIELDLCCF)
`
`
`
`
`
`30L
`
`302
`
`
`
`ISSUE SIGNAL PROCESSOR
`INSTRUCTION TO EACH
`OTHER CPU
`
`
`
`
`
`305
`
`THIS CPU RETURNS T0
`INTERRUPTED PROGRAM
`
`34 ——————— ?,.,,a-~----232930 31
`me ////ll
`
`ST ENTRY
`
`PT INVAUD FLAG
`
`0 ----------- H, 42,13, 44,15
`FIG-7 _I%I PFUNASSIGNEDFLRG
`PT EMT
`P_F
`INVALID FLAG
`
`
`
`F|G,3
`
`s
`
`P
`
`PFADDR
`
`TLB ENTRY
`
`INVAUD FLAG
`
`ARM_VPT_IPR_00000491
`ARM_VPT_IPR_OOOOO491
`
`

`

`
`
`US. Patent March 30,1976
`
`Sheet4 ot'S
`
`3,947,823
`
`FIG.4 (RESPONSE BY EACH OTHER CPU IN STSTEN)
`
`{NTERRUPTION CAUSED B'I’ SICP
`INSTRUCTION FROM INITIATINC CPU
`
` COMPARE
`
`Rl & CCF
`
`
`
`PLACE PACE FRAME ADDR.
`1N ALLOCATION TABLE
`
`
`
`
`COHPARE & SNAP
`INSTRUCTION
`(DETAILED VIEW}
`
`
`
` RETURN TO
`INTERRUPTED
`PROGRAM
`
`ARM_VPT_IPR_00000492
`ARM_VPT_IPR_OOOOO492
`
`

`

`US. Patent March 30. 1976
`
`Sheets of5
`
`3,947,823
`
`
`mo2253525
`
`8.5.23.20-2%.32:
`
`zEEEEEE:8
`
`
`
`EMEES:3sz
`
`
`3.2952153
`
`
`
`35.0.5.2m-=n_o:5:
`
`zofinsmxfizfiE:
`
`
`
`Emacsmid—zoo
`
`fizm
`
`33:3;
`
`2.2on
`
`8:223z_E555;.a“soEmzwmomo3P5Sq.—82._
`
`
`«a:z“m:3E:3sz
`
`:25
`
`mew
`
`EzmmEE
`
`“:5memmumoS:35.3,mgpmwm=m
`
`3%2+5ES:
`
`omEzmmEEEzmamm+0.2198newa.m5%E.53+é32:2.
`
`2.;on
`
`
`
`:35E53.2%azfihw—mfim—fim
`
`
`
`*Z:5m:35;SE::25.
`
`0.2%
`
`m-=n_o
`
`£7210
`
`I..I_l
`
`I-—
`
`
`
`$5258.8.235292:2:
`
`0.0.“.
`
`ARM_VPT_IPR_00000493
`ARM VPT IPR 00000493
`
`

`

`
`
`1
`
`3,947,823
`
`MEANS FOR COORDINATING ASYNCHRONOUS
`MAIN STORE ACCESSES IN A
`MULTIPROCESSING SYSTEM USING VIRTUAL
`STORAGE
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to apparatus and-methodology
`which facilitates interaction among central processing
`units [CPUs) in a multiprocessing system in the control
`of page frames. The invention enables each CPU to
`complete its current use of operands in a page frame
`even though the page frame has been marked by an-
`other CPU in the multiprocessing system as not avail-
`able for subsequent use. The invention does this by
`maintaining the addressability to each required page
`frame for the duration of each instruction regardless of
`any changes in the translation tables in storage and
`regardless of any changes in the translation lookaside
`buffer during that instruction.
`The invention can be applied where plural CPUs
`independently contend for main store resources in a
`multiprocessing system using demand-paging and vir-
`tual storage operations. A page frame is a hardware
`component of main store in which a page can be copied
`from an U0 device. The number of page frame compo-
`nents in a main store are limited. Whenever an Operand
`is required by the current instruction in any CPU, and
`the operand is not in main store, a page-demand inter-
`rupt is generated by the CPU so that the system can
`transfer the page containing the operand from an [[0
`device into a page frame component in main store. lfall
`page frame components are then in use, the system can
`deallocate one of the page frames and reallocate it for
`the new page having the required operand. The deal-
`located page may also have been used by one or more
`other CPUs. If the deallocation occurs in the middle of
`execution of a current instruction in another CPU hav-
`ing incomplete results obtained thus far, a cessation of
`execution for that instruction may leave incorrect re-
`sults. In this manner. incorrect data may be provided in
`a CPU output, clue to the asynchronous interference of
`CPUs in the multiprocessing system. Furthermore if the
`system should recognize the incomplete execution. and
`later
`retry the instruction alter the page is again
`brought back into main store. a reduction in efficiency
`occurs for
`the multiprocessing system due to the
`thrashing of this page in regard to the instruction sup-
`pressed at some intermediate point in its execution.
`OBJECTS AND BRIEF SUMMARY OF THE
`INVENTION
`
`It is therefore a general object of this invention to
`prevent incorrect results in the execution of instruc-
`tions due to asynchronous operations among the CPUs
`in a multiprocessing system.
`It is another object of this invention to improve the
`efficiency of multiprocessor Operations by eliminating
`the necessity for reexecution of an instruction as a
`result of asynchronous operations of CPUs in a multi—
`processing system.
`It is a further object of this invention to eliminate one
`of the causes of interference among plural CPUs in a
`multiprocessing system.
`It is a more specific object of this invention to force
`a multiprocessing system to continue the addressability
`to and the availability ofa page frame until completion
`of execution of current instructions in all of its CPUs.
`
`l0
`
`[5
`
`20
`
`25
`
`30
`
`35
`
`4o
`
`45
`
`SD
`
`55
`
`60
`
`65
`
`ARM_VPT_IPR_00000494
`ARM_VPT_IPR_OOOOO494
`
`2
`even though the page frame may be invalidated for
`deallocation so that it can be allocated to another CPU
`which has an asynchronous requirement for a page
`frame.
`
`This invention provides a unique control circuit with
`Special buffer hardware to assure the addressability of
`operands needed for completing the execution of cur-
`rent instructions in the reSpective CPUs of a multiprov
`cessing system which found the operands accessible at
`the beginning of execution of the current instructions,
`even though the addressability to the operands is lost
`elsewhere in the system. such as by asynchronous inval-
`idation of the add ressability in a translation table entry
`for these operands. As a result. the invention avoids the
`practice of simultaneously suSpending processing on all
`CPU whenever a page demand interrupt occurs, and
`thus permits the invalidation and subsequent rollout of
`a deallocated page to be handled as a coordinated
`activity in the system after the current instruction activ-
`ity is completed in all CPUs.
`The “current instruction" of any CPU is defined
`herein as the instructioa having its operandts) ad
`dressed by the use of an AAB register(s).
`DESCRIPTION OF THE DRAWINGS
`
`The foregoing and other objects, features and advan-
`tages of the invention will be more apparent from the
`following more particular description of the preferred
`embodiment of the invention illustrated in the accom-
`panying drawings of which:
`FIG. 1 illustrates a conventional virtual address type
`of multiprocessing system including novel address
`availability buffer (AAB) control circuits in each of the
`CPUs.
`
`FIG. 2 is a circuit draWing of AAB control circuits.
`FIG. 3 is a flow diagram of operations by any CPU
`initiating a page frame invalidation in a multiprocessing
`system containing this invention.
`FIG. 4 is a flow diagram of operations by other C PUs
`in a multiprocessing system responding to a page frame
`invalidation initiated by a CPU executing the opera-
`tions shewn in FIG. 3.
`
`FIG. Sis a timing diagram showing a particular exam—
`ple of CPU coordination when using the invention in a
`multiprocessing system.
`FIG. 6 shows a format for a segment table (ST) entry.
`FIG. 7 shows a format for a page table ( PT} entry and
`a table Iookaside buffer (TLB) entry.
`THE PRIOR SYSTEM USED BY THE PREFERRED
`EMBODIMENT
`
`FIG. I shows how the subject invention generally fits
`into otherwise commercially available multiprocessing
`systems, such as IBM Systemf3‘70 and OSIVS2 Release
`2. FIG. 1 includes a plurality of CPUs A. B .
`.
`. N con—
`nected to a shared main store 2] 1. Each CPU includes
`
`conventional components, such as an instruction han-
`dling unit, an execution unit, a virtual address register
`(VAR) 100, a storage address register {SAR} 110, a
`control register I II, and a dynamic address translation
`mechanism (DATM) which includes a translation
`lookaside buffer (TLB). The Operation of each of these
`units is well known. and they combine to provide what
`is commonly known in the digital computer arts as a
`virtual address demand —paging system.
`The invention incorporates address availability buf-
`fer (AAB) control circuits 400 into this combination of
`well known circuits comprising each CPU. That is. the
`
`

`

`3,947,823
`
`3
`invention integrates the AAB control circuits with the
`DATM. which is the demand-paging mechanism nor-
`mally found with virtual addressable computer systems.
`Because of the dependency of this invention on the
`prior system. a substantial effort is made herein to
`describe the related features and characteristics of the
`
`prior system which are used by this invention. In de-
`mand-paging systems, a unit of data measure, called a
`page.
`is read from an ”0 device into a page frame
`hardware component of a main store: (I) in response
`to a demand for a next instruction by the CPU when the
`instruction is not in main store, or {2) in response to a
`demand for an operand by a current instruction begin-
`ning its execution in a CPU when the operand is not
`then available in main store. A brief description of
`demand-paging is next provided in order to aid a better
`understanding of the background to this invention.
`In commercial CPUs which can be virtual addressing,
`the addresses of storage operands in machine instruc-
`tions are provided as virtual addresses. sometimes
`called logical addresses. when the CPU is in virtual
`address mode. Virtual address demand—paging mecha-
`nisms are currently in public use in commercial IBM
`computer systems. such as in the Si370 M [58 or M I68
`for example. See the “IBM Systemf370 Principles of
`Operation," form number GA22-7000-3 published
`February l973. which supports 8,1370 CPUs such as the
`IBM 3158 and 3168. Before the machine can access an
`
`operand with a virtual address. the machine must trans-
`late the virtual address into a main store address, some—
`times called a real address. Commercial machines can
`usually operate in either virtual address mode or real
`address mode. which is determined by the setting ofa
`mode bit in the current program status word (PSW) of
`the CPU.
`
`As previously mentioned. a demand-paging opera—
`tion is used to bring a required Operand or instruction
`into main store from an Iz‘O device when demanded by
`a CPU. To do this. the system locates the page on an
`IIO device and uses entries in a segment table (ST) and
`a page table (PT) to store addressability to the page
`after it is put in main store. This involves the assign-
`ment of a page frame address in main store, putting the
`page frame address into a PT entry, and transferring
`the page from the Iz'O device into the assigned page
`frame. The address of the assigned page frame is also
`transferred from the PT entry into a TLB entry in
`DATM which is used for subsequently addressing that
`page frame. If there is no free page frame available
`when one is needed. the system deallocates a least—fre-
`quently used page frame. and assigns it to receive the
`page.
`In more detail, whenever an operand is required that
`cannot be accessed through any valid page frame ad—
`dress in a current TLB or PT entry, 3 page-demand
`interrupt signal is generated to initiate a demand-pag-
`ing operation. This interrupt signal initiates the page
`frame allocation program to assign a page frame in the
`main store. moves the page into that page frame. and
`sets up a PT entry with the assigned page frame address
`and sets its flag bits to valid and assigned; see FIG. 7.
`That is. the PT entry selected to contain the new PF
`address has its unassigned flag bit and its invalidity flag
`bit both set off to indicate the PT entry is assigned and
`contains a valid pagc frame address. At a time thereaf-
`ter. DATM hardware copies the PT entry into a TLB
`entry in the respective CPU.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`ARM_VPT_IPR_00000495
`ARM_VPT_IPR_OOOOO495
`
`||||l
`
`4
`In order to speed the allocation of page frames to
`pages.
`the memory allocation program attempts to
`keep a list of free page frames. However. there are far
`fewer page frames in main store than there are pages
`located on [3'0 devices, and there are times when there
`are no free page frames. i.e.. all have been alloeated to
`the different CPUs. As a result of this continuing CPU
`contention for page frames.
`the allocation of page
`frames to pages must be offset by deallocation of the
`lesser-used page frames to best satisfy the contention
`conflicts. The deallocation of a page frame requires
`making the page that occupies the page frame inacces-
`sible for further translation; and then the contained
`page. if changed. must be stored on an IfO device for
`future use.
`
`Upon deallocation, the PT entry for a page is flagged
`as invalid and unassigned by setting on its invalidity and
`unassigned flag bits; see FIG. 7. A demand-paging re-
`quest occurs for any operand or instruction using a PT
`entry that has its invalidity flag bit set on.
`In commercial multiprocessing systems. the invalida—
`tion indication ofa page frame (i.e. by setting on its PT
`entry invalidity bit) is communicated to all CPUs using
`that page. To do this. four things are done (1) each
`CPU in the system must be signalled to temporarily
`discontinue using any page frame which may be sub-
`jected to invalidation. and each CPU must wait until all
`others have signalled back that they have complied
`with the request; (2} the invalid flag bit for the page
`frame is set in such a way that any subsequent instruc—
`tion using the page frame is cancelled; {3) each CPU
`purges its TLB of all entries; and (4) if the page is
`changed, it is read out onto an IfO device.
`The overall operation of the conventional DATM is
`next described briefly in order to better understand its
`relationship to the invention. In response to a virtual
`address from its CPU. DATM substitutes the assigned
`page frame address in main store for the corresponding
`segment and page virtual address components. In FIG.
`1, the virtual address is supplied to a virtual address
`register (VAR) 100 from the execution unit. which
`generates the virtual address in the well known manner
`from the operand address components in the current
`instruction supplied by the instruction handling unit.
`The DATM apparatus uses the segment tables and page
`tables which reside in the shared main store 2“.
`In each CPU. the content of control register lll
`addresses the location of the segment table currently
`being used by that CPU. Each entry in the segment
`table (ST) has the form shown in FIG. 6, which in-
`cludes a field containing an address of a page table
`(PT). The PT address in a ST entry is valid only if the
`PT invalid flag bit is set to O to indicte a PT is assigned
`to that ST entry. If the PT invalid flag is set to l; the PT
`address is invalid. and a segment exception is generated
`to signal that no page table exists for the 81‘ entry. The
`PT entry and TLB entry format are shown in FIGS. 7
`and 8; they include an address of a page frame. The
`page frame (PF) address in the PT entry is valid if the
`PF invalid bit is set to 0. If this PF bit is set to l. the
`contained page frame address is not valid. which means
`that the related page frame cannot be used.
`Each DATM also includes the translation lookaside
`buffer (TLB) which is used by DATM to maintain the
`main store addresses corresponding to virtual addresses
`that have been most recently referenced. which en-
`hances the speed of obtaining the most frequently used
`main store addresses. Hence the TLB hardware entity
`
`

`

`
`
`3,947,823
`
`5
`speeds up the storage accessing operations. The TLB is
`used in the referencing of all types of virtual addresses,
`including both operand and non-operand types of ad—
`dresses. As a result of the general use of the TLB and
`the overlapped nature of the CPU, the operation of
`replacing entries in the TLB is such that a particular
`entry may be replaced at any time during the execution
`of an instruction within IBM Systeml370 CPUs.
`As shown in FIG. 1, VAR 100 contains the virtual
`address fur an operand, or for a non-operand such as
`the next instruction to be fetched from main store. To
`do this the virtual address is first translated into a main
`
`store address. A virtual address (VA) is comprised of a
`segment address component 8, a virtual page address
`component P. and a byte displacement D in the page.
`The VA translation begins with the segment table (ST)
`located by the main store address in control register
`11]. First the segment address component S is used as
`an index in the ST to locate the required ST entry. The
`ST entry contains the main store address which locates
`the required page table (PT). The virtual page address
`component P is used as an index in the PT to locate the
`required PT entry; and the PT entry. if marked valid
`and assigned, contains the address of the page frame
`(PF) in main memory containing the operand or in-
`struction. The PT entry contains the high order 12 bits
`of the main store address, and the low order bits of the
`address are all zeros. The displacement D is a byte
`index in both the virtual page and the page frame to the
`location of the required operand or instruction.
`The assigned flag bit in the PT entry in FIG. 7, if set
`to 1, indicates that the addressed page frame is allo-
`cated to a CPU. If the assigned flag bit is set to 0, the
`PT entry is not assigned and it therefore can be as-
`signed to any CPU. Further detail on the DATM opera—
`tion may be found in the published literature for the
`commercially available IBM 8,870 virtual storage sys-
`tems.
`
`FIG. 8 shows the TLB entry format. which include
`the S and P components needed to perform the search
`of the TLB to find any existing associated TLB.
`GENERAL DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`In FIG. 1, the illustrated embodiment of this inven-
`tion contains address availability bufl‘er (AAB) control
`circuits in each CPU of the multiprocessing system.
`The AAB control circuits contain four AAB registers
`10, 20, 30 and 40 which receive and maintain the main
`store addresses corresponding to the virtual addresses
`required for the current instruction in execution. The
`AAB registers are updated synchronously with the
`instruction stream executed by the respective CPU
`during the pretest portion of the instruction execution.
`The AAB control circuits can improve the efficiency
`of the multiprocessing system whenever a page frame is
`invalidated at a time unexpected by the execution state
`of any CPU.
`AAB registers 10, 20, 30 and 40 are used to hold the
`page frame addresst’esljoif operand{s) needed by the
`instruction currently being executed.
`An instruction access does not require any AAB
`register, since execution of an instruction is easily can-
`celled if all, or a portion of the instruction. lies in an
`unavailable page. Thus the page frame address for an
`instruction is only put into SAR [10 in the conven—
`tional manner.
`
`5
`
`IO
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`ARM_VPT_IPR_00000496
`ARM_VPT_IPR_OOOOO496
`
`6
`However, each operand has a pair of AAB registers
`available, i.e. registers 10 and 20 comprise a pair for
`use by one operand, and registers 30 and 40 comprise
`a pair for use by another operand.
`the instruction
`Depending on the instruction type.
`may have zero. one. or two Operands, which may use
`zeroI one. two, three or four of the AAB registers.
`The illustrated two pairs of AAB registers support
`instructions having up to two Operands in the main
`store, in which each operand can cross a page bound-
`ary. That is. each pair of registers support one operand
`which may be located, for example. in two page frames
`in main store. This arrangement can support any oper-
`and starting at any location, provided it does not ex-
`ceed one page in length. This is sufficient since the
`operands of most instructions are limited to lengths less
`than this, and those instructions which have longer
`operands are designed to be resumahle at any point in
`the execution after an interruption. The two AAB reg-
`isters in a pair may be designated an even register and
`an odd register, in relation to the parts of an operand
`found in sequential virtual pages having even and odd
`page addresses, or odd and even page addresses.
`The loading of AAB registers with an operand PF
`address is done by the CPU at the time it transfers the
`PF address from a required PT entry to a TLB entry;
`which is also the time during which the addressed oper-
`and is initially accessed using the PF address in the
`required PT and TLB entries. Thereafter the ope—
`rand(s) is accessed with the PF address in the AAB
`register{s).
`The crossing of a page frame boundary is indicated
`by the changing of the low-order bit PL in the page
`virtual address component P in VAR 100. The crossing
`occurs when the VA for the next page is placed into
`VAR 100 while the CPU continues to signal the same
`Operand request. Then the main store address for the
`second page frame is placed into the other AAB regis—
`ter of the pair. If the operand‘s PF address cannot be
`obtained because an exception signal is encountered
`during the operation of DATM, the instruction execu—
`tion is cancelled and none of its results is permitted to
`be stored.
`
`As previously mentioned, after the AAB registers are
`loaded, only the valid PF addresses contained in the
`AAB are used in the execution of the current instruc—
`tion, and no references are then made through the ST,
`PT or TLB as long as the same content validly remains
`in VAR 100.
`
`The loading of the operand PF address(es) into the
`AAB assures the availability of the main store operand
`address(es) for the using CPU for the duration of the
`current instruction ‘s execution, even though during the
`execution another CPU may make the corresponding
`PT entry invalid.
`It is noted that the TLB entry is not marked invalid at
`the instant that the corresponding PT entry is marked
`invalid, because the marking of the TLB entry awaits
`the actuation of CPU hardware to perform the opera-
`tion. Hence the addressability in the TLB might appear
`valid for a period after the corresponding addressability
`in the PT is lost. But the TLB entry's addressability can
`not be relied upon. because it may be made invalid at
`any time during the execution of the current instruc-
`tion. However, the AAB addressability can be relied
`upon to be maintained throughout the current instruc-
`tion‘s execution period. Hence the AAB avoids any
`unpredicatability in the results of the instruction's exe—
`
`

`

`
`
`3,947,823
`
`7
`cution that would be caused by invalidation of the PT
`or TLB entry at a time during execution when use is
`made of the page frame designated by those table
`entries.
`1 and 2
`The entries in the AAB registers in FIGS.
`(like the PT and TLB entries) contain only a page-
`frame address, which is the high—order part of the main
`store address, e.g., on the high-order [2 bits of a 24 bit
`address. The low—order part of the main store address is
`directly transferred to the SAR 110 from the byte dis—
`placement (D) ficld in the VAR 100. The page frame
`address and the D field are combined in the main store
`address register {SAR) 110 in FIGS.
`1 and 2 to gener—
`ate the main store address of the operand or instruc—
`tion, which is provided to the main store address hard-
`ware in order to access the operand.
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`The AAB control circuits are shown in FIG. 2. They
`are organized in such a way that they require a mini-
`mum amount of control lines from the CPU. In present
`commercial systems without any AAB, the CPU con—
`tains, among other things, the lines 3 through 60 shown
`in FIG. 1 provided by the CPU execution unit. The
`AAB - is connected to lines 3 through 60 which are
`shown in detail in FIG. 2 as input control lines 60, 61.
`62, 50 and 3. The end 0]) line 60 is electrically pulsed
`when the execution of the current instruction is ended.
`
`The OPDl VA request line 61 is pulsed when the cur-
`rent instruction makes its first operand (OPDl) request
`while the CPU is operating in virtual address mode, i.e.
`the execution unit is then outputting the first operand‘s
`virtual address to VAR 100. The 0pD2 VA request line
`62 is pulsed when the current instruction makes its
`second operand request while the CPU is operating in
`virtual address mode.
`
`The non—OPD VA request line is pulsed when the
`CPU is requesting a non-Operand store access, such as
`an instruction fetch; it uses DATM but does not use any
`AAB register. The main-store address request line 3 is
`pulsed when the address provided to VAR 100 is a
`main store address; and it therefore can be directly put
`into SAR [00, without using either the DATM or the
`AAB circuits. Whenever a main store access request
`signal is received on line 3 from the CPU. the signal on
`line 3 is applied to a gate 9 which causes the S and P
`fields in VAR 100 to be gated directly into the PF field
`in SAR 100.
`In FIG. 2, a virtual address in register 100 comprises
`the segment address component 8, the page address
`component P, and the page displacement field D, how-
`ever a real address in VAR [00 provides the page
`frame address in the S and P fields.
`The content of register 100 is not affected by address
`translation, and it provides the input to a conventional
`address translation operation. Field D in VAR 100 is
`transferred directly into the D field of main store ad-
`dress register (SAR) 100 with no gating therebetween.
`The segment address S and page address P components
`of the virtual address are inputted to the dynamic ad-
`dress translation mechanism (DATM) 120 which trans-
`lates them into a corresponding main-store page—frame
`address, which is outputted on main store PF address
`out line 12] to AAB register gates 16, 26, 36 and 46.
`The AAB circuits include validity triggers ll, 2]. 31
`and 41 which are respectively associated with the four
`registers 10, 20. 30 and 40. Each trigger is reset by an
`
`8
`end 0p signal on line 60 upon the completion of execu—
`tion of the current instruction. the reset state indicates
`that the associated AAB register does not contain a
`valid PF address.
`The CPU activates required signals on control lines 3
`through 60 at the beginning of the execution of the
`current instruction, so that if any address translation
`exception interrupt signal is generated by the DATM
`on its output line 101, it must occur early enough to
`permit all results of the current instruction to be can-
`celled. The translation exception interrupt signal
`is
`generated by DATM when a particular VA cannot be
`translated because no assigned or available PF address
`is found in the PT or TLB. This early portion of the
`instruction execution is conventionally called “pretest—
`mg."
`During pretesting the CPU translates by means of the
`ST, PT and TLB entries all virtual addresses to be used
`in the instruction execution, and the AAB registers are
`used for operand accessing after pretesting for the
`remainder of the instruction execution.
`
`Therefore the page frame address for an Operand is
`provided by DATM to the AAB in the early portion of
`execution for the current instruction.
`
`The choice of which AAB register in a pair is selected
`to be loaded with a currently provided address on line
`121 is determined by whether the virtual page address
`in VAR 100 is even or odd, which is indicated by the
`signal on PL line '71 provided from the lowest-order bit
`position in the P field of register 100. The line ‘72 out-
`put of inverter 70 is activated by an even P field con-
`tent since the PL bit is then set to the 0 current level;
`but line 7] is activated by an odd P field content which
`sets PL to the 1 current level.
`A non-operand differs from an operand in that the
`non—operand either uses a main store address, e.g. its
`addres does not require translation, or it is an instruc-
`tion which is fetched prior to Operand pretest and
`hence its execution can be terminated at any time dur-
`ing its fetch which is before any results have been
`stored for the instruction.
`
`When an instruction (or other non-operand) is to be
`accessed in VA mode, the CPU pulses a non-operand
`virtual address (NON-OPD VA) request signal on a
`line 50 through an OR circuit 51 to actuate the address
`translation mechanism 120.
`
`Whenever a virtual address is put into VAR 100, the
`DATM 120 outputs on line 12] the main store page
`frame address corresponding to the S and P compo-
`nents of the virtual address in register 100, when a
`corresponding page frame has been assigned. This is
`indicated by a translation available signal being pro—
`vided on a line 102. If no page frame was assigned, a
`translation exception signal is provided on line lfll to
`the CPU, so that the CPU can provide a page demand
`interrupt signal.
`The virtual storage operand access request signals on
`line 61 and 62 are mparately provided by the CPU to
`distinguish whether the address in VAR 100 is for a
`first or a second operand of the current instruction.
`Line 6] is activated for the first operand and enables a
`selection by the PL line 72 or ’71 in the first pair of AAB
`registers l0 and 20. Line 62 is activated for the second
`operand and enables a selection by the PL line 72 or 7]
`in the second pair of AAB registers 30 and 40.
`The following example illustrates the internal Opera-
`tion of the AAB circuits:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`ARM_VPT_IPR_00000497
`ARM_VPT_IPR_OOOOO497
`
`Illli
`
`

`

`3,947,823
`
`9
`Assume that an end op signal has just Occurred on
`line 60 indicating completion of the last instruction
`execution. It resets all of the validity triggers ll, 21, 31
`and 41.
`
`Now assume that. the CPU has just pulsed a signal on
`OPDl VA line 61, and that the PL bit in virtual address
`register 100 is 0 indicating an even—numbered content
`in virtual page field P. The 0 signal on line 71 to in-
`verter 70 activates its output line 72. AND circuit 12 is
`therefore enabled by active lines 61 and 72, and its
`output line 13 provides a first even selection signal to
`condition AND circuits 1?, 14 and 15.
`Since trigger 11 is now in a reset state, its comple-
`mentary output (c) enables the AND circuit 14 to
`energize line 73 to provide an operand translation re-
`quest signal through OR circuit 51 to DATM 120. If the
`translation is available, line 102 is activated; but if it is
`not available, the CPU is signalled on line 101 to gener—
`ate a page demand interruption. Assuming that the
`translation is available, line 102 and line 73 activates an
`AND circuit 74; and its output line 75 activates AND
`circuit 15 which then conditions gate 16 to transfer the
`main store PF address provided on bus 121 into the
`first even AAB register 10. The signal from AND cir-
`cuit 74 is also delayed through delay circuit 76 and
`shortly thereafter enables AND circuit 17 to set the
`first even validity trigger 11 to its valid state, indicating
`the content of register 10 is valid. This activates the (t)
`output of trigger 11 (and deactivates its (c) output} to
`enable AND circuit 18 and therefore gate 19 transfers
`the valid content of the AAB register 10 into the PF
`field in SAR register 110.
`When the current instruction completes its execu—
`tion, the execution unit activates the end op line 60,
`which resets trigger 11 to indicate an invalidity state for
`the content of AAB register 10, and AND 18 deacti-
`vates gate 19 to block the connection between register
`10 and SAR 110.
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`10
`ment. Then field P in VAR 100 is changed by the CPU
`to the next page; and DATM 120 provides another
`main store page frame address on line 121 correspond-
`ing to the new S and Pcombination in VAR 100. Hence
`the reversal in the state of the PL bit signal on line 71
`puts the new page frame address