United States Patent
`Andersen et al.
`
`3,967,247
`in,
`[451 June 29, 1976
`
`[541 STORAGE INTERFACE UNIT
`[75] Inventors: Vernon K. Andersen, New Brighton;
`Michael W. Goddard, Roseville.
`both of Minn.
`[73] Assignee: Sperry Rand Corporation, New
`York, N.Y.
`Nov. ll, 1974
`{22] Filed:
`[2]] Appl. No.: 522,553
`
`[52] U.S. Cl. ........................................... .. 340/1725
`[51] Int. Cl.2 .................... .. G06F 13/00; G1 1C 9/06
`[58] Field of Search ..................... .. 340/1725; 444/1
`
`[56]
`
`References Cited
`UNITED STATES PATENTS
`
`3,394,353
`
`7/1968 Bloom et al. .................. .. 340/1725
`
`3,569,938
`
`3/1971
`
`Eden . . . . . . . . i . . . . . . .
`
`. . . . .. 340/1725
`
`3,588,839
`
`6/1971
`
`Belady cl al. . . . .
`
`. . . . .. 340/1725
`
`3,647,348
`
`3/1972 Smith ct a1 . . . . . . .
`
`. . . . . . . . . . .. 340/1725
`
`3,670,309
`R26,624
`
`......... .. 340/1725
`6/1972 Amdahl et a1. ..
`7/1969 Bloom et a1. .................. .. 340/1725
`
`Primary Examt'ner—Gareth D. Shaw
`Assistant Examiner—-Michael C. Sachs
`Attorney, Agent, or Firm-Thomas J. Nikolai; Kenneth
`T. Grace; Marshall M. Truex
`
`[57]
`
`ABSTRACT
`
`A storage interface unit adapted to serve as a high
`speed buffer between plural requestor units and a rela
`tively low speed main memory in a data processing
`system. The high speed buffer provides temporary
`storage for a limited number of blocks of data stored
`in the main memory. When a particular address is re
`quested by a requestor unit, a check is made to deter
`mine if that address is resident in the high speed buffer
`and if so, it is available to the requestor unit for read‘
`ing or writing. If the desired address is not resident in
`the high speed buffer, a block in the buffer is selected
`for replacement. in accordance with the present in
`vention, when a block is to be displaced from the buf~
`fer and a new block is requested from the main mem
`ory, during the interval that the new block is re
`quested from the main memory, the block to be dis
`placed is checked for modi?cations. If any word of the
`old block has been modi?ed since it was obtained
`originally from main memory the entire block is read
`into a temporary holding register and is restored in the
`main memory while the new block is being entered
`into the buffer storage.
`
`2 Claims, 11 Drawing Figures
`
`one ADDRESS
`SEGMENT
`(SEGMENT o)
`
`'0
`
`REQO
`
`REG. 1
`
`RED. 2
`
`'2
`
`56
`
`f 58
`
`I 60
`
`RED.
`R0. REG.
`i
`
`REO.
`no. REG.
`i
`‘
`
`R50.
`no. REG.
`l
`‘
`
`54
`
`f7:
`WR. DATA
`SLR.
`
`52
`f
`span mm‘ lmnnmwnmm ass.
`
`[J
`
`'
`
`I
`
`:
`
`‘
`
`--"°
`
`36
`
`[
`
`1
`MAIN
`venom
`
`72
`I
`mm ME".
`
`"ET:
`
`SLR.
`
`I
`
`
`
`
`
`I I ._'l_l_l
`
`‘
`
`AOR. REG.
`
`1
`
`'
`
`I
`
`EVEN ADDRESS
`s EGMENT
`(SEGMENT 1)
`
`{7|
`wn. DATA
`suit
`
`"54
`
`11
`
`L1
`
`52
`se
`[
`I
`mu MEMWRDATA REG. mom, mom
`
`
`
`
`
`I I LI_I_.. I
`
`
`
`SLR.
`
`-
`
`--
`
`-
`
`—
`
`-
`
`l -
`
`- -
`
`—
`
`Petitioners' EX1025 Page 1
`
`

`
`U.S. Patent
`
`Mvm
`
`wE%Ilnll
`_...._mumomommom8m9._Mdam.82.8E.w::,_ms_omm.8kzusomm.
`9,Pzmsaumommmmmhzuzomm
`
`2mmmEn_<zm_>um$m8<So
`
`nmN_Ndmm_dmm0.0mmO_uJI0‘
`
`fO
`
`9,
`
`M
`
`8Eozmz
`
`3mmm
`
`29.»mn__,_.m._m.8m.34.m._mH_»m_n__,_
`
`
`
`"W29:E59.5:2:2,.«:3.9.20¢“.
`
`Petitioners‘ EX1025 Page 2
`
`Petitioners' EX1025 Page 2
`
`
`
`

`
`aP
`
`Jm
`
`S
`
`8f0
`
`
`
`
`2mo<mo.6m>:<_uomm<Emmofiemm>_.§oomm<mmm_U.
`,%-mmwmooqzm>m<29mmumoeqSom,wm"~”mm
`
`
`
`
`
`.mm_m8<aim9mmmmmm8<SEtamEtnmUvm$
`
`w¢Nww
`
`31mm.mo<Em.m>>
`
`
`
`.mmnizm
`
`9,
`
`74
`
`2'i2ill7II6E.E_u|
`
`.mmutamdum
`
`mm.8”..m§aux.mo<
`
`H3
`
`
`
`IlIIIII.|§\|.'N_O3..|..\m.dumdumdmm
`
`fllill
`
`mmnrsmcumIo_
`
`.m..mEs.m._m.ma<
`
`Petitioners‘ EX1025 Page 3
`
`Petitioners' EX1025 Page 3
`
`
`

`
`U.S. Patent
`
`June 29, 1976
`
`.m3
`
`8
`
`no
`N
`
`
`
`Q0m<50.550.5V608xuo._m
`
`
`
`mmizoo:02:
`
`N¢
`
`Sw._._m
`Wummuo_
`
`769.,
`
`
`
`3v_oo._mIV
`
`21Nok
`
`mowmuaoum
`
`Petitioners‘ EX1025 Page 4
`
`Petitioners' EX1025 Page 4
`
`
`
`

`
`U.S. Patent June 29, 1976
`
`Sheet 4 of 8
`
`3,967,247
`
`BLOCK SELECTOR
`
`"*8
`
`BLOCK A
`
`BLOCK B
`k
`A l
`
`BLOCK 0 BLOCK D
`A
`A
`
`_
`F! g. 3
`
`|
`
`WORD |
`
`WORD 1
`
`f3O
`
`WORD | 5
`
`3
`5
`7
`
`l
`
`3
`5
`7
`
`0
`
`3
`5
`7
`
`3 h
`5
`7
`
`O
`
`0
`
`d-1
`
`A B c D
`MATCH
`COMPARE W
`OUTPUT
`'
`-
`(FIG. 2)
`WORD a
`WORD |
`3
`3
`
`SET
`
`l2?
`
`l
`
`5
`
`7
`
`i 5
`
`7
`
`\ _
`
`°
`WORD I
`3
`
`5
`
`7
`
`°
`WORD |
`3 __
`
`l
`
`5
`
`7
`
`+__+
`_ I
`‘4'
`
`44
`f
`SET
`SLR.
`
`46
`/
`WORD
`SLR.
`
`09-03
`
`OZ-Ol
`V
`
`REQUESTOR
`ADR. REG.
`
`BLOCK A BLOCK B BLOCK 0
`
`BLOCK 0
`
`|8_._
`
`92
`ADD
`a4\ f
`>=<
`COMP.
`A t
`
`[74
`1‘
`BLK.ADR AGE ‘g
`
`96\
`ADD
`as T
`>=<
`COMP
`A
`
`/98
`ADD
`T ,90
`>=<
`COMP.
`A A
`
`,94
`ADD
`Ahas
`>=<
`COMP.
`‘
`A _
`FROM
`I
`82
`MATCH
`\_ COMPARE t
`COMPARE
`SLR.
`(FIG. 2)
`A 1 LA
`{so
`#5 [76
`Fe [78 _? D
`BLK.ADR AGE ‘3'
`IBLKADR. AGE ‘3'
`BLK.ADR. AGE ‘g
`
`Petitioners' EX1025 Page 5
`
`

`
`US. Patent June 29, 1976
`
`Sheet 5 of 8
`
`3,967,247
`
`Fig. 5
`
`C?
`l
`
`GATE WORD
`FROM REQ. TO
`BUFFER STACK
`
`w-l24
`
`SET WB BIT
`IN TAG STACK
`
`l
`
`SEND ACK. TO
`REQUESTOR
`
`g. 50
`
`Petitioners' EX1025 Page 6
`
`

`
`US. Patent
`
`June 29, 1976
`
`Sheet 6 of 8
`
`3,967,247
`
`WAIT FOR
`REQ.
`
`/ I02
`
`I04
`
`IS THERE MORE
`THAN 1 REQ. ?
`
`/ I06
`ESTABLISH
`PRIORITY
`
`UPDATE AGE
`BITS OF
`TAG WORD
`
`LOCK OUT
`OTHER REQ.
`
`l
`
`GATE REQ. ADR.
`BITS |O~O3 TO
`SET SEL. 8 BITS
`02-Ol TO WRD. SEL.
`
`l
`
`READ 4 BLK.
`ADDESSES FROM
`TAG STACK TO
`MATCH CKT.
`
`,-|08
`
`r- | l 0
`
`PIIZ
`
`k-| |4
`
`GATE SELECTED
`WORD FROM BLOCK
`SEL. TO REQ.
`RD. REG.
`
`l
`
`[I32
`
`SEND ACK. TO
`REQ. UNIT
`
`l
`
`READ 4 DATA
`WORDS FROM
`BUFFER STACK
`TO BLOCK SLR.
`
`l
`
`COMPARE 4 BLOCK ,.||6
`ADRS. WITH
`REQ. ADR.
`
`Fig. 50
`
`Petitioners' EX1025 Page 7
`
`

`
`U.S. Patent June 29, 1976
`
`Sheet 7 0f 8
`
`3,967,247
`
`I
`
`SELECT LRU
`ADDRESS FROM
`MISS SEGMENT
`
`I
`
`STORE ADDRESS OF
`NON-RESIDENT
`BLOCK
`
`I
`
`I40“ SEND READ REQ. TO
`BOTH SEGMENTS
`
`I
`
`UNCONDITIONALLY
`UN LOAD LRU DATA
`IB-WORDSI
`INTO HOLDING REG.
`
`I44
`
`15 W5 BIT
`SET ?
`YES
`
`SEND WRITE REQ.
`TO MAIN MEMORY
`
`I
`
`SIU RECEIVES
`WRITE RESUME
`FROM MAIN MEMORY
`
`I
`
`SEND READ REQ. TO
`MAIN MEMORY
`
`I
`
`SEND DESIRED
`8-WORD BLOCK
`FROM MAIN MEMORY
`TO SASU
`
`I
`
`STORE B-WORD BLOCK
`IN SASU BUFFER
`LOCATION PREVIOUSLY
`KNOWN AS LRU
`
`I
`
`UPDATE TAG
`ADDRESS B AGE.
`CLEAR WB BIT
`
`I
`
`SIU RECIEVES READ
`RESUME SIGNAL
`FROM MAIN MEMORY
`
`.T.
`
`REI N ITIATE
`EXTERNAL
`REQUEST
`
`Fig. 5b
`
`Petitioners' EX1025 Page 8
`
`

`
`U.S. Patent
`
`June 29, 1976
`
`Sheet 8 of 8
`
`3,967,247
`
`
`
`
`
`
`
`mz_._><4mo.6528z_<2
`
`.m;>.22mtmz
`
`dmm22o._.mu.._x
`
`.E<._.m
`
`woos.mtm;am
`
`
`
`woos.ofim_.:m
`
`vmm
`
`HSo32mtwtWONN.H-cm2»z_.mo<mkzuzmmm..s_.s_9mmmm8<
`
`
`o:,u___«EamammopmEtnamomom..mo<2:Wwmm
`
`
`
`momfimatomflmmmmomkmwwmwm
`
`ozmm
`
`Fzmzmmomo
`
`E28
`
`
`
`
`
`mz:><._mo.55282.3,.
`
`Fzmzmmomo
`
`._.zDOom:o>odhdo
`
`
`
`zfiwmfi
`
`._v_Noqwm
`
`mmm
`
`Umm<u..o5.
`
`mm&54..‘.>.:mo_Emm.mm.
`
`AEosaz
`
`0%:C0
`
`
`
`3353noozmmes.mm_s_
`
`Sumodmm
`
`I.._.zOo
`
`oom<oom<
`
`Petitioners‘ EX1025 Page 9
`
`Petitioners' EX1025 Page 9
`
`
`
`
`

`
`1
`
`STORAGE INTERFACE UNIT
`
`5
`
`BACKGROUND OF THE INVENTION
`It has long been recognized that the speed of a com
`puter memory system can be increased through the use
`of a relatively high speed. low capacity buffer store.
`That is, if a high speed buffer is implemented properly
`in a computer system, main memory speed will appear
`to approach that of the buffer. For example, in a case |
`where the cycle time of the buffer is one-tenth of that
`of the main memory, the effective access time may be
`eight to nine times less than that of the main memory.
`The underlying reason for this speed-up of operation is
`that experience has shown that data currently being
`processed have a high probability of being used again in
`the near future and that related data is commonly
`stored in contiguous address locations in the main
`memory.
`The manner in which so-called “cache” buffers have
`been implemented in various lBM computer systems
`has been described in a number of published technical
`articles. For example, reference is made to the article
`by J. S. Liptay entitled, “Structural Aspects of the
`System/360 Model 85, [l the Cache", IBM Systems
`Journal, Vol. 7, No. 1, pp 15-21; that by D. H. Gibson
`entitled “Considerations in Block-Oriented Systems
`Design", Spring Joint Computer Conference I967; and
`that by C. .I. Conti et al entitled “Structural Aspects of
`the System/ 360 Model 85,l General Organization”,
`IBM Systems Journal, Vol. 7, No. 1, 1968. In the IBM
`System 360-Model 85, store operations always cause
`the main memory to be directly updated. If the main
`storage sector being changed has a sector in the buffer
`assigned to it, the buffer is also updated; otherwise, no
`activity related to the buffer takes place. Therefore,
`store operations cannot cause a buffer sector to be
`reassigned, a block to be loaded, or the activity list
`controlling the replacement algorithm to be revised.
`The present invention is considered to be a signi?
`cant improvement over the memory hierarchy em
`ployed in the IBM system. In accordance with the
`teachings of the present invention, one or more proces
`sor units and/or Input-Output devices are adapted to
`receive instructions and operands (hereinafter collec
`tively referred to as “data") from a main memory only
`by way of a high speed buffer memory. Also, data from
`the processors and/or [/0 units to be stored in the main
`memory must pass through the high speed buffer mem
`ory. Thus, the buffer of the present invention will here
`inafter be termed a “Storage lnterface Unit" or “S]U".
`The SIU of the present invention is a high-speed (low
`cycle time) storage buffer designed to reduce the over
`all storage delay time of a computing system by auto
`matically allowing the great majority of storage refer
`ences to take place in the SlU proper, rather than in the
`lower speed (higher cycle time) main memory or back
`ing store. In the preferred embodiment of the present
`invention, this is accomplished by providing circuitry
`(hardware) to transfer an 8-w0rd block of data into the
`SIU whenever any word from that block is required by
`a processor or input/output unit. This block becomes
`one of several blocks remaining resident in the SlU
`until it is displaced by a new current block as deter
`mined by a suitable replacement algorithm.
`The SlU of the present invention employs a so-called
`set-associative storage buffer. In an exemplary arrange
`ment, the buffer may comprise 4,096 words of storage
`
`3,967,247
`2
`which may be divided into 128 sets, each set consisting
`of four 8~word blocks of data. The main memory em
`ployed in the system is then also divided into 128 sets,
`each set containing l/l28 of the words in the total main
`memory address range. Alternatively, the buffer may
`be expanded to contain additional words of storage
`divided into a larger number of sets with each set con
`sisting of four 8-word blocks of data. In this alternative
`arrangement, the main memory would also be divided
`0 into an identical number of sets but each set would
`include a lesser number of 8-word blocks. Any one of
`the 8-word blocks in a given main memory set may be
`placed in any one of the four 8-word blocks in the
`corresponding SIU set. When a transfer (either a read
`or a write) is made between the SlU and main storage,
`an 8-word block from contiguous addresses is trans
`ferred during a single main memory cycle.
`When a request for a word from storage is made by a
`processor or an input/output unit, this request is seen
`only by the SlU. Conventional direct address selection
`is used to address the one of 128 sets in which the
`required word is located. This selection causes the SIU
`to simultaneously read the address of each of the four
`blocks currently resident in the set and to compare
`each with the requested address. If one of the four
`block addresses matches the requested address, the
`appropriate word is read from that block and sent to
`the requesting unit. If none of the four block addresses
`matches, an immediate request is made by the SIU to
`the main memory for the entire block which contains
`the desired word. While waiting for this new block of
`data, the SlU determines which of the four current
`blocks is the least recently used and marks it for re
`placement. Next, the SlU checks the block to be re
`placed to determine whether any word in that block has
`been modi?ed while resident in the SIU. if a modi?ca
`tion had occurred, the entire block plus its address is
`read into a temporary holding register in the SlU so
`that it can be restored to the main memory as soon as
`the current main memory cycle is ?nished. When the
`data arrives from the main memory, it is stored into the
`now-vacated block and the appropriate word is ulti
`mately sent by the SlU to the original requestor to
`complete the cycle.
`In prior art computing systems wherein high speed
`bu?'ers are employed to increase the throughput of the
`system, store operations always cause the main mem
`ory to be updated. If the main memory set being
`changed has a corresponding set in the bu?'er assigned
`to it, the buffer is also updated. That is, each time a
`processor or [/0 unit effects a write operation, the main
`memory must be updated immediately. Since the main
`memory operates at a relatively long cycle time, fre
`quent references to main memory slow down the over
`all processing speed of the system.
`The system of the present invention utilizes what is
`termed a “post-store" method to obviate this problem.
`Rather than making a write reference to the main mem
`ory each time a write is effected in the SIU bu?'er mem
`ory, in the system of the present invention the main
`memory is only updated when the address to be modi
`fied is not resident in the buffer and a block containing
`altered data, i.e., data different from what is in its cor
`responding block in main memory is selected for re
`placement. Upon detecting that a desired address is not
`resident in the SIU buffer, the SlU immediately sends a
`“read“ request to the main memory to obtain the entire
`block in which the desired address is located. Simulta
`
`25
`
`30
`
`35
`
`40
`
`50
`
`55
`
`60
`
`65
`
`Petitioners' EX1025 Page 10
`
`

`
`3,967,247
`neously the SIU, through a replacement algorithm,
`determines which of the blocks currently in the buffer
`memory is to be replaced. A check is made to deter
`mine if this selected block had its contents modi?ed
`while resident in the buffer and if so, the entire block
`plus its address is gated into a temporary holding regis
`ter. While the new block is being brought into the buf
`fer from the main memory and stored in the now
`vacated block location, the displaced block contained
`in the holding register is written back into the main
`memory, thereby updating the main memory.
`The economy in time occasioned by this “post-store"
`method is readily apparent. Rather than requiring a
`relatively slow main memory cycle each time a change
`is made in a block stored in the buffer to update the
`main memory as in prior art systems, in the system of
`this invention only one main memory cycle is used to
`update main memory and this only occurs when a block
`is selected for replacement which had its contents mod
`i?ed while it was resident in the buffer. However, while
`resident in the buffer, this block may have undergone
`many, many modi?cations before being selected for
`replacement.
`
`20
`
`4
`invention. This drawing will be used in explaining the
`organization and functional operation of the SIU and
`following this explanation will be a description of the
`construction and mode of operation of the various
`blocks of FIG. 1 which are other than conventional.
`As has been mentioned in the introductory portion of
`this speci?cation, the present invention relates to a
`Storage Interface Unit (SIU) which operates as a high
`speed buffer between plural requestor units and a main
`memory in such a way that the overall memory access
`time for a given operand is substantially decreased.
`This is accomplished by including as an interface be
`tween the requestor units and the main memory a high
`speed buffer memory which contains a subset of the
`information stored in the main memory. The design is
`such that on a statistical basis there is a high probability
`that a given operand being sought by a requestor unit
`for reading or writing will be found in the high speed
`buffer, thereby obviating the necessity of making a
`reference to the lower speed main memory.
`The system illustrated in FIG. 1 includes two seg
`ments denoted “odd segment” and “even segment”
`which are substantially identical in construction, mode
`of operation and which operate in parallel. Hence, in
`the following detailed description reference will be
`made to the various functional elements in the odd
`segment, i.e., those to the left of the section line 10, but
`it is to be understood that what is said about those
`elements also holds true for those to the right of the
`section line 12. Elements which are shared by both
`segments are shown between the section lines 10 and
`12.
`Shown at the bottom of FIG. I are the plurality of
`input lines 13 which originate at the requestor units and
`which are used to present request control signals, ad
`dress representing signals and data to be written to the
`SIU. The requestor units may comprise one or more
`central processing units (CPU‘s) and input/output units
`(lOU’s). While only three such units (Reg. 0, l, 2) are
`indicated, it is to be understood that additional request
`ors may be used. The incoming request signals are
`applied to priority networks 14 in each SIU half which,
`upon receipt of simultaneous requests from two or
`more requestor units, award priority to one and only
`one unit at a time for communication with the SIU.
`Both the CPU’s and IOU’s communicate with the SIU
`on a Request/Acknowledge basis. This mode of com
`munication is fully explained in the Ehrman, et al US.
`Pat. No. 3,243,78l, so that it is felt to be unnecessary
`to explain in further detail the construction or organi
`zation of such requestors. That patent also shows the
`manner in which plural request signals originating at
`different units are applied to a priority network which
`selects one such unit at a time for communication with
`the remainder of the system.
`Presented along with the request signal is an address
`which uniquely selects a desired word for reading or for
`modi?cation in the event that the request signal is a
`read or a write request, respectively. These address
`representing signals are applied as inputs to the re
`questor address selectors I6. The selectors 16 are
`merely gating devices responsive to control signals
`emanating from the priority circuitry 14 which permit
`the address signals from a single requestor selected by
`the priority network to pass through to the requestor
`address registers 18. In a similar fashion the buffer
`write selectors 20 are conventional gating arrange
`
`25
`
`30
`
`35
`
`OBJECTS
`It is accordingly an object of the present invention to
`provide an improved buffer memory system for a digi
`tal computing system.
`Another object is to provide an improved storage
`interface unit between one or more requestors and a
`main memory which unit contains a high speed buffer
`memory which, on a statistical basis, has a high proba
`bility of containing a word address speci?ed by the
`requestor.
`Another object is to provide an improved memory
`architecture for a digital computing system permitting
`repeated modi?cations to a given block of data resident
`in a high speed buffer without the need of effecting a
`corresponding modi?cation to the associated block in
`the main memory each time the block in the buffer is
`modi?ed.
`These and other objects and advantages of the inven
`tion will become apparent to those having skill in the
`art upon a reading of the following detailed description
`taken in conjunction with the accompanying drawings
`in which:
`
`40
`
`45
`
`DESCRIPTION OF THE DRAWINGS
`FIGS. la and lb when arranged as shown in FIG. I
`depict a system block diagram of the SIU in which the
`present invention is used;
`FIG. 2 is a block diagram representation of the tag
`portion of the set associative storage modules;
`FIG. 3 is a block diagram representation of the buffer
`portion of the set associative storage modules;
`FIG. 4 is a logic diagram illustrating the circuits used
`to implement the “least recently used" algorithm.
`FIGS. 50, 5b and 5(- when arranged as indicated in
`FIG. 5, show by means of a ?ow diagram the sequence
`of the various operations performed by the preferred
`embodiment; and
`FIG. 6 illustrates by means of a logic diagram the
`control network used in the system of FIG. 1.
`
`50
`
`55
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`Referring now to FIG. 1, there is shown a system
`block diagram of the preferred embodiment of the
`
`65
`
`Petitioners' EX1025 Page 11
`
`

`
`3,967,247
`
`v
`
`5
`ments which permit write data from the selected re
`questor to be entered into the buffer write registers 22.
`The outputs from the requestor address registers 18
`and the requestor write registers 22 are made available
`to the two Set Associative Storage Units (SASU) iden
`ti?ed generally by the numerals 24 and 26. The SASU
`24 is used to store the odd address of plural blocks
`while SASU 26 stores the even addresses in these same
`blocks. The storage units 24 and 26 may be conven
`tional addressable random access memories, but are
`divided into two parts termed the “tag" and the “buf
`fer". More speci?cally and as will be further explained
`with the aid of FIGS. 2 and 3, the SASU 24 has a ?rst
`stack of addressable registers 28 for storing so-called
`tag words and a second stack of addressable registers
`30 for storing plural sets of four 4-word half blocks of
`data. Similarly, the SASU 26 is divided in two parts, 32
`and 34, part 32 storing tag words and part 34 storing
`plural sets of four 4-word half blocks of data. There is
`one tag word in the sections 28 and 32 for each of the
`4-word half blocks stored in the sections 30 and 34.
`To gain a clearer understanding of the overall organi
`zation of the SIU, it is deemed helpful to consider an
`exemplary embodiment. However, it is to be under
`stood that the storage capacities to be set forth are a
`matter of choice and no limitation to the ?gures pres
`ented should be inferred.
`bet it be assumed that the buffers 30 and 34 have a
`combined capacity of 4,096 words of data and that the
`main memory 36 has a capacity of 262,144 words. In
`this exemplary con?guration, the buffers may be parti
`tioned into I28 sets of four 8~word blocks (I28 X 4 X
`8 = 4,096 words). The main memory may then also be
`considered as being comprised of I28 sets, each set
`containing l / I 28 of the word capacity of the main
`memory. In the example, then, each set would contain
`256 8-word blocks (I28 X 256 X 8 = 262,l44 words).
`Any four of the 256 8-word blocks of a set in main
`memory may be resident in a corresponding one of the
`I28 sets in the combined buffers 30 and 34.
`To speed up the addressing of data stored in the SIU
`buffers, the SIU is divided into an odd address segment
`and an even address segment so that under certain
`conditions to be explained, buffer access can be ac
`complished in an overlapped fashion. The odd/even
`segmentation affects the set/block structure by dividing
`each 8-word block into two 4-word half blocks. Thus,
`buffer 30 may store the 2,048 words having odd ad
`dresses and buffer 34 may store the remaining 2,048
`words having even addresses. This odd/even address
`structure is displayed below in Table I.
`TABLE!
`
`6
`main memory 36 in those instances where the address
`being sought for reading or writing is not resident in the
`SASU‘s. Again, this format is premised on the use of a
`single main memory module 36 having a storage capac
`ity of 262,144 words and a combined buffer having a
`capacity of 4,096 words. If additional memory modules
`are employed, additional address bits would be re
`quired for module selection.
`TABLE II
`
`22 4 I0
`
`9 _ 3
`
`2 _ I
`
`SE'I'
`BLOCK
`SEL.
`SEL.
`l‘- MAIN MEMORY ADDRESS —~>
`
`WD.
`SEL.
`
`20
`
`3
`
`u
`
`O/F.
`SEL.
`
`FIG. 2 illustrates diagrammatically the makeup of the
`tag parts 28 and 32 of the SASU’s 24 and 26 and before
`proceeding with the system description shown in FIGv
`I, consideration will be given to the organization and
`operation of the odd segment SASU 24, it being under
`stood that the even segment SASU 26 operates in an
`identical manner.
`The SASU 24 involves conventional addressing in
`both the tag and buffer portions thereof. The output
`from the requestor address register 18 is applied via
`cable 38 to an address translator 40 in SASU 24 which
`functions to examine bits 3 through 9 of the address to
`uniquely select one out of I28 lines used to access any
`one of the I28 registers comprising the tag memory.
`Stored in each tag memory register is a 64-bit entry,
`each having the format shown at set address 0 0 0 in
`FIG. 2. The part of the tag word labeled “block ad
`dress" includes bits l0—22 of the address of the ?rst
`word in each of the four blocks comprising that set in
`the buffer, a block being eight contiguous words lo
`cated on eight word‘boundaries.
`The entries labeled “age" are each a 2-bit ?eld asso
`ciated with each of the four block addresses in each tag
`location that provide a relative indication If how long it
`has been since each block has been referenced. More
`will be said of this age ?eld when the details of the
`“least recently used" replacement algorithm are ex
`plained.
`The ?eld labeled “W8” is termed the “Writeback
`Bit" and is one bit wide and is used to indicate whether
`modi?ed data exists in the speci?ed block. If this bit is
`a binary “ I” when the block in question is selected for
`replacement, all four words in that block must be writ
`ten back into main storage. When it is a binary “0”
`there is no need to write the displaced block into main
`memory, since no word in that block had been modi
`?ed by a write operation while it was resident in the
`buffer.
`To determine whether a desired block is resident in
`the buffer, the four block addresses of the tag asso
`ciated with the requested set are compared, bit-by-bit,
`with bits 10 through 22 of the address present in the
`requestor address register 18 (FIG. 2). If one of the
`four block addresses match, as determined by a Match
`Compare circuit 42, the requested word is resident in
`the buffer and can be obtained directly from the buffer.
`Because the buffer sections are addressed with the set
`number (bits 3-9) and the bits identifying a word
`within the block (bits I—2), its output is four words
`wide. one word from each of the four blocks in the
`requested set. The output from comparator 42, which
`
`35
`
`40
`
`45
`
`50
`
`4 8~Wurd
`Blocks
`
`44-Word
`Half Blocks
`
`4 4-Word
`Half Blocks
`
`55
`
`ABCD - BLOCK-v ABCD
`EEFF.
`EEEF
`0000
`EFIEE
`EEFE
`EEEF
`0000
`EEEE
`EFEE
`0000
`E F l- E
`0000
`
`BUFFER 34
`
`ABCD
`0000
`0000
`0000
`0000
`
`BUFFER 30
`
`Set forth below in Table II (for exemplary purposes
`only) is the format adopted for the address provided by
`the selected requestor units and employed to access
`information stored in the SASU’s 24 and 26 or in the
`
`65
`
`Petitioners' EX1025 Page 12
`
`

`
`3,967,247
`
`7
`identi?es the block number in which the match oc
`curred, is used to select the appropriate word from the
`buffer to send it to the requestor as will next be ex
`plained.
`Referring to FIG. 3, there is shown the organization
`of the buffer portion 30 of the SASU 24. Buffer 34 is
`identical in construction. The buffers per se each com
`prise a plurality of addressable registers for storing
`data. The individual words are grouped into 128 sets,
`each containing four 4-word half blocks, the even ad
`dresses being stored in buffer 34 and the odd ones in
`buffer 30. To access a given word, bits 09 through 03 of
`the requestor address selects one of the l28 sets stored
`in the buffer. Bit 0 of the requestor address register is
`decoded to specify whether the address is odd or even
`such that buffer 30 or 34 should be accessed, respec
`tively, and bits 02 and 01 of the requestor address
`register are translated by the word selector 46 to
`uniquely select one of the four words in each block
`within a given set in the speci?ed odd or even segment.
`Because the same requestor address is simultaneously
`applied to the tag stack (FIG. 2), if a match occurs
`between the address of a requested block and the ad
`dress of a block resident in the buffer, an output signal
`will be developed on one of the lines A, B, C, D from
`the comparator 42 of the speci?ed odd or even seg
`ment. This output signal, when applied to the inputs of
`the block selector 48 (FIG. 3) will permit only the
`selected word of the selected block of the selected set
`in the selected segment to be read out from the buffer ~
`30 or 34 of the SASU 24 or 26. Of course, if the desired
`block is not resident in the buffer, match compare
`circuit 42 will fail to produce an output signal on either
`output line A, B, C, or D and selector network 48 will
`be precluded from gating any word out from the buffer
`30.
`Words sent out from the SASU buffer segments 30
`and 34 may be passed over the cables 50 (FIG. 1) to
`read data selectors 52 which are controlled by the
`priority network 14. The re ad data selectors function to
`gate these words over cables 54 to the particular one of
`the read registers 56, S8 or 60 of the requestor unit
`which presented the read request to the SIU in the ?rst
`instance.
`In the event that a read or a write request is presented
`to the SIU and a determination is made that the word
`being sought is not resident in the buffer, the desired
`address from the requestor address registers 18 is trans
`ferred via cable 6] to the miss address register 62
`where it is captured and held for later use. Next, the
`least recently used (LRU) algorithm is invoked which
`causes the tag address associated with the block to be
`replaced to be read out from the tag segment 28 or 32
`to the associated tag address register 64 and from
`there, by way of cables 63 and 65, to the buffer tag
`address register 66.
`Following this, during four buffer memory read cy
`cles, the two 4~word half blocks singled out for replace
`ment are read out from the buffer sections 30 and 34 of
`the SASU’s and loaded one-by-one into the four sec
`tions of the main memory write data registers 68 where
`they are held.
`The desired non-resident block of data is read out
`two words at a time from the main memory 36 in four
`cycles on cable 70 and applied through the buffer write
`selectors 20 to the buffer write registers 22. The re
`placement block obtained from the main memory is
`stored at the beginning buffer address designated by
`
`50
`
`55
`
`65
`
`the contents of the buffer tag address register 66 and as
`each word is entered, the bits 1 and 2 are incremented
`to provide the word address for each entry. Also, a new
`tag word is written into the tag sections 28 and 32 of
`the SASU‘s in a manner yet to be described.
`While these operations are in progress, the writeback
`bit of the portion of the tag word presently contained in
`the tag address register 64 is checked and if set, it
`indicates that the block now resident in the main mem
`ory write data registers 68 had undergone modi?cation
`while resident in the buffer. As such, it is necessary to
`write this block back into the main memory.
`During four main memory cycles, words are un
`loaded two at a time from the registers 68 (one from
`the odd segment and one from the even segment) and
`stored in the main memory at the block location speci
`?ed by the address which had been earlier captured in
`the miss address register 62. More speci?cally, the
`contents of the miss address register 62 are applied to
`the main memory address register 72.
`After the last word of read data from the main mem~
`ory unit 36 has been entered into the bu?'er, another
`priority scan is initiated, thereby allowing the original
`requestor to gain access to the now-resident address in
`the buffer. The desired word is therefore made avail
`able to the original requestor for reading or writing.
`To understand the operation of the least recently
`used (LRU) algorithm, which is the means utilized to
`select a block for replacement when a request is pres
`ented for a word which is not resident in the buffer,
`reference will be made to the circuitry of FIG. 4.
`It will be recalled from the explanation of the tag
`portion of the SASU (FIG. 2), that each set has a tag
`word specifying the address of the four blocks currently
`resident in the buffer as well as a pair of “age” bits for
`each block which may have the binary values 00, 0],
`10, or 11. By convention, the bloc