Patent GB-1224961-A (GB)
Title: Binary associative memory
IPC: G11C15/04
Filed: 1969-10-01
Abstract: 1,224,961. Associative stores; calculators. INTERNATIONAL BUSINESS MACHINES CORP. 1 Oct., 1969 [16 Oct., 1968], No. 48211/69. Headings G4A and G4C. A binary associative memory comprises a data storage array 3, a data entry register 11, a binary mask register 13, and a binary back-up register 15 so connected to the mask register that the back-up register is operative in response to a control signal to change the contents of the mask register in accordance with the contents of the mask register. The back-up register can also change the entry register in accordance with the contents of the entry register. Each word of the storage array 3 includes a bit SP, as do the entry and mask registers (though not the back-up register). The unmasked entry register bits can be applied in true or complemented form by T/C gates 5 for interrogation of or writing in the storage array 3. Subtracting one.-The SP bit is set to one in each word of array 3 from which one is to be subtracted. The entry, mask and back-up registers are initially set to all ones, then a series of cycles is performed. In each cycle, the SP bit and lowest-order (excluding SP) bit of the mask register are set to zero (unmask), each zero (if any) in the back-up register is set into the corresponding position of the entry register and the next-higher-order position of the mask register, a true interrogation of array 3 is performed, then a complemented write in the matching words, then each zero in the mask register (except the SPbit), which there are no ones to low order of, is set into the corresponding position of the back-up register. The series of cycles ends when the back-up register is all zeroes. In this way the system interrogates for a one, in progressively-higher orders, followed by all-zeroes (except the SP bit which must be one), and whenever it finds it replaces the one and the following zeroes and the SP bit by their complements. Adding one.-As " subtracting one " (see above) except that the SP bit of the entry register is initially set to zero, and a complemented interrogation . and a true write are used, so that (to replace the last sentence above) the system interrogates for a zero, in progressively-higher orders, followed by allones (including the SP bit) arid whenever it finds it replaces the zero and the following ones including the SP bit by their complements. Overflow.-With the operation above, the addition or subtraction will not occur in a word already at all ones or all zeroes respectively (ignoring the SP bit). These words can be detected by interrogating with only the SP bit unmasked, the interrogation being true for subtraction and complemented for addition since the entry register SP bit is still at one or zero respectively. Adding and subtracting higher values.-Powers of two can be added or subtracted simply by starting at the appropriate bit position, instead of the lowest-order position. Other constants can be added or subtracted by two or more successive additions and/or subtractions starting at different orders. Time-sharing system.-Blocks in the TSS memory shown, which may relate to different users, have respective associated words in the array 3 which store sequence numbers for the blocks from a counter 114 indicating the order in which the blocks were stored, to enable the older data to be selected for transfer to auxiliary storage if room has to be made in the TSS memory for new data. If a block from the TSS memory is read out non-destructively, the corresponding sequence number is read from array 3 to the entry register (via a register 9). A range retrieval operation sets to one the SP bit of each word of array 3 containing a higher sequence number. The count from 114 is set into the word corresponding to the read-out block, and all the sequence numbers with SP bit set to one have one subtracted from them as above. With destructive read-out of a block, the procedure differs by decrementing the counter 114 and not writing the count into array 3. In the range retrieval operation, the entry register zeroes are changed to one successively, with associative interrogation after each change, a match indicating that the stored word is greater than the entry register contents, as follows. The back-up register is set to all zeroes. The following cycle is repeated until the back-up register is all ones: (a) the lowestorder entry register bit (excluding the SP bit) is set to one (it may already be at one) and each one (if any) in the back-up register, which there are no zeroes to low-order of, sets the corresponding bit in the mask register and the nexthigher-order bit in the entry register to one (the latter may already be at one), (b) interrogation, (c) each one in the entry register (ignoring the SP bit) is set into the corresponding position of the back-up register.