Patent GB-1270483-A (GB)
Title: Data processing system
IPC: G06F12/12
Filed: 1970-09-04
Abstract: 1,270,483. Data storage. INTERNANATIONAL BUSINESS MACHINES CORP. 4 Sept., 1970 [2 Oct., 1969], No. 42416/70. Heading G4C. A data processing system has a working memory into which blocks of information can be loaded from a back-up store replacing existing blocks according to a replacement algorithm, the efficiency of which is measured, utilizing stored indications of which working memory blocks are accessed between successive block replacements from back-up store, and of the numbers of the intervals between replacements in which each block would have been most recently accessed in the working memory according to an " optimal " replacement algorithm. When a CPU attempts to access a word in a working memory (core), an associative memory is used to determine if the block containing the word is in the working memory or only in a back-up store (tape, disc or drum). In the latter case, an interrupt is caused and the block is copied from the back-up store into a block of the working memory selected by a replacement algorithm (see below). If this involves overwriting a block already in working memory and this block was altered since it was itself copied from back-up store, it is rewritten in back-up store first. During the interrupt, counters, registers and tables are updated to obtain a measure of the efficiency of the replacement algorithm (see below). The associative memory has an argument register and a mask register. Each word location in it has a match flip-flop reset in response to mismatch on associative interrogation, and a pointer flip-flop. Only one of the pointer flip-flops is set. The setting of the pointer flip-flop can be moved (via an intermediate flip-flop) to the next pointer flip-flop corresponding to a set match flip-flop. A word can be read/written at the first word location having a set match flip-flop or the location having the pointer flip-flop set. Each word location in the associative memory relates to a respective block in the working memory and has the following fields: (a) an R<SP>1</SP>- bit which is set if the block has been accessed since the last block transfer from back-up store; (b) an L-bit (see below); (c) an SS-bit (serial search) which can be set in all the word locations, then associatively matched on to permit all the word locations to be accessed in turn; (d) an AL-bit which is set if the block has been altered in the working memory; (e) an R-bit which is set when the corresponding block in the working memory is accessed and reset when all the R-bits are in the set state; (f) a field identifying the programme the block relates to; (g) the block address in the back-up store, which is the address specified by the CPU; (h) the actual block address in the working memory, field (h) being read-only. The replacement algorithm loads the block into the block location corresponding to the first word in associative memory having both the R-bit and the AL- bit reset, or if there is none the first having the R-bit reset and the AL-bit set, the pointer flipflop setting being advanced to this word in either case. Using the word " interval " to mean the time between successive transfers of blocks from back-up store, the following quantities are used and updated for the measurement of the efficiency of the replacement algorithm (other replacement algorithms could also have their efficiency measured in this way to permit comparison and improvement on a trial basis): (a) a P-count specifying the interval number i.e. the number of blocks transferred from back-up store; (b) an A-count specifying the interval number under an "optimal" replacement algorithm; (c) an E-count for each addressable block corresponding generally to the number of the interval in which that block would have been most recently accessed under the " optimal " replacement algorithm; (d) a C-count for each interval in the " optimal " sequence, set to N-1 (where N is the number of blocks which can be stored in the working memory) when a block would be first accessed in that interval under the " optimal " algorithm and decremented by 1 at each (" optimal ") reference to a block in that interval (including the first) so that reaching zero indicates a " complete set " of block references corresponding to the capacity of the working memory; (e) a B-pointer which, when it exceeds its starting value of 1, indicates the number of the most recent interval in which the " optimal " algorithm would have defined a " complete set "; (f) a U-count specifying the number of unnecessary block transfers made by the replacement algorithm, equal to P- count minus A-count; (g) a Q-count specifying an uncertainty in the U-count due to doubt about the actual order of accessing represented by the R<SP>1</SP>-bits. When the requested block is not in working memory, the P-count is incremented then if none of the R<SP>1</SP>-bits are set then if the E-count is less than the B-pointer the A-count is incremented and used to select the appropriate C-count which is loaded with N-1 and the E- count selected by the currently requested block address is loaded with the A-count. However if the E-count is not less than the B-pointer, the A-count is loaded into a Y-register used for selecting C-counts. If the Y-register is then not equal to the E-count, the C-count is decremented then the Y-register is decremented this loop of two decrementing operations repeating until the Y-register is equal to the E-count, when the U-count is decremented and the E- count is loaded with the A-count. However the loop is exited from if the C-count is decremented to zero in which case the Y-register is loaded into the B-pointer and the serial search facility of the associative memory is used to obtain in turn all the block addresses therein, which are used to select the corresponding E- counts, the L-bit being set in the associative memory for each case in which the E-count is less than the B-pointer, then when these operations on the associative memory have ended, the U-counter is incremented and the currentlyselected E-count is loaded with the A-count. When the requested block is not in memory (see above) but at least one R<SP>1</SP>-bit is set, then for each such R<SP>1</SP>-bit in turn the corresponding E- count is compared with the A-count. If equal, the R<SP>1</SP>-bit is simply reset. If unequal, and if the E-count is less than the B-pointer, the R<SP>1</SP>-bit is reset, the Q-count and the A-count are incremented, N-1 is loaded into the C-count selected by the A-count, and the A-count is loaded into the E-count. If unequal, and the E-count is not less than the B-pointer, the A-count is loaded into the Y-register (used to select C- counts), then if the Y-register is not equal to the E-count, the C-count selected by the Y- register is decremented then the Y-register is decremented, this loop of two decrementing operations being repeated until the Y-register equals the E-count or the decremented C-count is zero, whichever occurs first, the E-count then being loaded with the A-count in either case (and in the case of "decremented C-count zero," the B-pointer being loaded with the Y-register contents), the next associative memory word with the R<SP>1</SP>-bit set then being taken. When a requested block is in the working memory (whether already or in response to a transfer just completed), the block address and the corresponding L-bit are saved in a hold register, and if the L-bit in the hold register is set, the following extra updating is done: the U-counter is decremented, the L-bit is reset, then a search is done for set R<SP>1</SP>-bits with all the consequential updating as above except that when there are no set R<SP>1</SP>-bits left, the A- count is incremented, the C-count selected by the A-count is loaded with N-1, and the E- count selected by the block address in the hold register is loaded with the A-count. Updating of the contents of the associative memory also occurs as appropriate from the definitions above of the fields. The decrementing of the U-count and the incrementing of the A-count, in response to a set L-bit, give the actual replacement algorithm credit for not performing a block transfer which the " optimal " algorithm would have performed but which would have turned out to be non-optimal. The efficiency measurement procedure only updates back to the previous " complete set " in order to save time, so the "optimal" algorithm which is the algorithm which makes full use of the hindsight provided by this updating, is not truly optimal.