perm filename FL9.OLL[1,PMP] blob sn#008025 filedate 1971-08-13 generic text, type T, neo UTF8
     The M-Box contains the cache memory and its control, including the connections to main
memory. The paging device (Map) may be considered part of the M-Box. Also a part of the M-Box,    
is the I/O control section which allows data channels to have a connection to the cache and  
elliminates the logical problems associated with such devices when there are two versions of the
contents of a given address. The Map and I/O controller are described seperately.               
     The cache memory is divided into three parts, the Data Part, the Address Part, and the 
the Use-bit Part.
     The first is the Data Part. It consists (see diagram) of four logical memories -- each 
containing 256 words of 74 bits. Each memory takes an 8-bit address from the               
Cache-Address-Latches (CAL) bits 27-34 and produces two (37 bit) words.                    
     The second part is the Address Part which consists of four logical memories, each split 
for writing into 5 logical units. Each memory takes a 7-bit address from the CAL bits 27-33  
and produces an 11-bit address, 4 NEEDWRITE bits, and 4 INVALID bits. These are associated
with the four words in the data part memory with the same number -- at the two addresses (in
the data part) with bits 27-33 the same as those used to address the Addrs Part. The address is
the main memory real (absolute) address (high order 11 bits) of the four data words (the low
order 9 bits of this real address are the address used to address the cache -- except for bits
34 and 35, which choose one of the 4 words). One of the NEEDWRITE and one of the INVALID bits
is associatd with each of the 4 words. If one of the INVALID bits is on, it indicates that that
word does not have correct data in the cache and must be gotten from main memory. If one of the
NEEDWRITE bits is on it indicates that that word may have different data in the cache from what
is in main memory, and the cache version is correct. This means that word will have to be
re-written into main memory when it is flushed from the cache. It also means that the parity may
not be correct for that word in the cache.
     The third part is the Use-Bit part which is only one logical memory (split into 5 seperately
writeable parts). It contains 128 entries -- each associated with the same entry in all four Addrs
Part memories. (And hence with 2 entries in each of the Data Part memories). The memory takes a 
7-bit address from the CAL 27-33 and produces 8 USE-BITS and 4 INVALID bits. Two of the use-bits
are associated with each of the Address Part and Data Part memories and tell the relative
recentcy of use of the entries at that address in each of the memories. If, for example, the
most recent access with a given address (bits 27-33) fetched the data in memory 2, the use-bits for
memory 2 would be 0. The use bits for the second-most-recently-used memory would be 1, and so-on,
with 3 indicating the least-recently-used (oldest) entry. The use bits are updated on some cycles   
and not on others. They are updated by making the use bits 0 for the memory whose data you use, and 
adding one to the use bits for some or all of the other memories. The 4 INVALID bits are associated with the
4 memories. If one of them is on, it indicates that the whole entry at that address and in that
memory is invalid and should be ignored.
     The M-Box does one thing per cycle -- fetching or storing one bunch of data.  There are nine
types of cycles that the M-Box can do. On most cycles an address is supplied and the low order
bits are sent to the 4 Data Part memories, The 4 Addrs Part memories, and the Use-Bit memory. The
high order bits are sent to the Map. After an appropriate delay, the mapped (absolute) version of
the high order bits comes out of the Map and the high order bits of the 4 addresses come out of the
Addrs Part. These 4 addresses are compared with the address from the Map. If one of the addresses
matches (only one is allowed to -- it is illegal to have the same address in there twice), this
is a HIT condition and the data from the memory that hit is used (assuming it was a data fetching
type of cycle). If none of them hit, it is a MISS, and, if appropriate, the data is fetched from main
memory and put in the cache. Main memory fetches always fetch 4 words and put them in the cache.

     The nine types of cycles are:

          This type of cycle is requested by the I-Box to fetch instructions. The address is
     taken from the APCL, a register in the I-Box. An address is considered to MISS if either    
     of the two words fetched are invalid (i.e. the word addressed and the one with the same 
     address with bit 35 inverted), even if the addresses match. The I-Box, in general, takes both
     words. If no addresses hit, a fetch is started to get the 4 words, and put them in the cache.
     (See READ-AROUND and M-STORE cycles). Additionally, on MISS, the M-Box decides where it      
     is going to put the 4 words when they come from main memory (it must pick one of the 4 
     cache memories). It always chooses the memory with use-bits =3. The number of the memory         
     selected is saved in the "M-STO MEM-SEL" register (in unary form) for use when the data          
     arrives. Also, if the current entry in the place this data will be stored is valid and has one  
     or more NEEDWRITE bits on, the associated words are put into the Memory Store Buffers, and           
     a main memory cycle will be started to store them, as soon as the data fetching memory cycle
     is done. Since the data part of the Cache reads out only 2 of the 4 words associated with    
     an address, it will be necessary to take an extra cycle to get one or more of the other   
     two words into the Memory-Store buffers, if one or more of them has a NEEDWRITE bit on. If     
     this is the case, a DUMP-2 cycle is taken for that purpose. DUMP-2 cycles have highest          
     priority, so the DUMP-2 will be the next cycle. Use bits are updated on I-Fetch except if       
     there is a miss which causes a DUMP-2 cycle.                                                   

     This type of cycle is requested by the I-Box to fetch data. It is identical to the I-FETCH
     except as follows:
       The address is taken from the MA.
       An address is considered to MISS if the addressed word is invalid (but NOT if the other
                    word of the pair is invalid), even if the addresses match.

     This type of cycle is requested internally by the M-Box if the last cycle was a fetch that
     missed and one or more of the words in the unobtained pair to be thrown out needs to be
     written into main memory. The address is taken from the FETCH register (where it was put
     last cycle) and is the same as the address last cycle except that bit 34 is inverted. The
     address will MISS. The two other words come out and are put in the store buffers.  
     The use bits are updated on DUMP-2 cycles.

     This type of cycle is requested internally by the M-Box when the data has come in from
     main memory on a main-memory fetch. It is used to pass the data to the I-Box, which is waiting
     for it. No address is used, the data is merely passed around the cache memory directly into
     the Cache Output Data Latches. The cycle looks like a Fetch that HIT to the I-Box. Use bits      
     are NOT updated on READ-AROUND.
     This type of cycle is requested internally by the M-Box when the data has come in from
     memory and needs to be stored into the cache. Since only 2 words can be stored at a time,
     two of these cycles are needed for each main-memory fetch. The first pair of words to arrive
     from memory is stored first. The address is taken from the                              
     FETCH register where it was put during the fetch cycle that missed, except that bit 34 is made
     either 1 or 0 depending on which 2 words are being stored. The Addrs Part and Data Part memories     
     selected by the "M-STO MEM-SEL" register are made to take a write cycle. The two words are,
     hence, stored in the Data Part. In the Addrs Part, the address (from the FETCH register)
     is stored and the INVALID and NEEDWRITE bits for the words being stored are set to 0. If
     this is the first of the two M-STORE cycles associated with a given fetch, the NEEDWRITE
     bits associated with the other two words are cleared and the invalid bits are set. Use bits are
     NOT updated.

     Before the E-Box can store a word of generated data into the cache, it must first decide where
     to put it. This is done, in general, with a Store-Check cycle. The store-check cycle looks
     very much like a fetch cycle, except that no-one looks at the data from the Data Part, and
     information is saved about where to eventually store the generated data.
          This type of cycle is requested either by the I-Box or by the E-Box (through the I-Box).
     The address is taken either from the MA (I-Box) or the E-STORE ADDRS register (E-Box).
     An address is considered to HIT as long as the addresses match, regardless of the invalidity
     of individual words. The number of the memory that hits is saved in the "E-STO MEM-SEL" register
     (in unary). If there are no hits, the memory with use-bits =3 is used and, if necessary, a
     main-memory store cycle is started to store the words being replaced. This may cause a
     DUMP-2 cycle to be taken. Use bits are updated unless a DUMP-2 is caused by this cycle.

     This type of cycle is requested by the E-Box to store generated data into the cache. It
     is usually preceded by a Store-Check cycle.                                          
     The address is taken from the E-STORE-ADDRS register. The Addrs Part and Data Part            
     memories selected by the "E-STO MEM-SEL" register are made to take write cycles. In the Data
     Part, only the even or odd section takes a write cycle, depending on bit 35 of the address. In
     the Addrs Part, the Address section takes a write cycle only if this is a new address (i.e. the
     Store-Check MISSed). The NEEDWRITE bit is set on and the INVALID bit off for the word
     involved. The other three sets of NEEDWRITE and INVALID bits are left alone (unchanged --
     no write cycle taken in those sections) unless this is a new address, in which case they are
     all set to INVALID and NO NEEDWRITE.
          A variation of the E-Store cycle happens if "STORE-THROUGH" is requested. In this case,
     the cache takes write cycles only if this is NOT a new address. Additionally, the data word
     is passed around the cache to the Memory-Store buffers and a main memory write cycle is
     initiated to write the data into main memory. Use bits are NOT updated.

     This cycle is used (repeatedly) to empty the cache. The E-Box, when it decides to dump the
     cache, first initializes the Cache-Dump register to 0, then requests continuous Cache-Dump
     cycles, until the M-Box decides the whole cache has been dumped. (The Cache-Dump register
     overflows). The address is taken from the Cache-Dump register. (This register has only bits
     27-33, the rest being irrelevant for dumping). The memories cycle and if none of the 16
     NEEDWRITE bits are on, all 4 invalid bits (in the Use-Bit memory) are set on and the Cache-
     Dump register is incremented by 4. (by 1 in bit 33). If one or more NEEDWRITE bits are on,
     the Cache-Dump register is not incremented and additional Cache-Dump (and DUMP-2) cycles are
     used to get the words out of the cache and into the Memory-Store buffers. From there they
     are written into main memory. The INVALID bits are set on (in the Use-Bit memory) one at
     a time as the cache is emptied of words needing to be written. When all of the words in that
     group of 16 are taken care of, the Cache-Dump register is incremented and the next 16 are
     looked at. Note that if some NEEDWRITE bits are on, the normal use-bit update mechanism    
     is used to cycle through the 4 memories looking for specific words to write.               
     Since addresses are forced to miss, the mem with use-bits =3 is the one under consideration.
     Each time the use-bits are updated, a new memory becomes 3.

     This cycle is requested by the I/O controller (for data channels) and is used to see if
     there is a spot in the cache allocated to a word being transfered to or from an I/O channel.
     The address is taken from the I/O address in the I/O controller. The cycle looks like a 
     fetch (or Store-Check) cycle except as follows:
       MISS does not cause a main-memory fetch to be started.
       The I/O controller may request that the INVALID bit be turned on in the use-bit memory
                   associated with the memory (if any) whose address matches.
       No words are forced out of the cache and stored under any circumstances.
     See the description of the I/O controller for further details.
     Use bits are NOT updated during I/O cycles.

                     M-BOX CYCLE-TYPE PRIORITIES:

    The current setting of the relative priorities of the cycle types
    in the M-Box is:

          DUMP-2                  This must be highest priority so that it will
                                  immediately follow the cycle that cuased it.

          I/O FAST                Requested by the I/O controller when it is
                                  getting frantic.

          CACHE-DUMP              I/O can happen during Cache-Dumping
          READ-AROUND                           |
          M-STORE                               |
          E-FETCH                               }  Simulation shows     
                                                }  that a slightly      
          STORE-CHECK                           }  different arrangement
                                                }  of these may improve 
          I-FETCH-2      (2 instrs. needed)     }  speed slightly.      
          E-STORE                               |
          I-FETCH-1      (1 instr. needed)      |
          I/O SLOW                I/O requests this when not in a hurry.

                    CONNECTION TO MAIN MEMORY:

         The M-Box (Cache) connection to main memory consists of 2 busses
    with 1/2 of main memory connected to each. Which bus has a given word
    is determined by bit 34 of the word's address. In general, each bus
    does "double-length" cycles -- meaning that two words of data are
    transfered (serially by word -- parallel by bit), the addressed word
    first. (The two word's addresses differ only in bit 35). Single length
    cycles are possible, but are used only when writing into main memory
    and only if there is only one word to be stored in that memory.  
         On fetches, bit 35 of the address on which the cache missed is sent 
    to memory as bit 35 so that, on the bus which has the word you primarily
    wanted, that word will be the first to come in, and the Read-Around
    cycle can be taken then. Both words of a pair must arrive before the
    associated M-STO cycle can happen.