Browse Prior Art Database

Search and Storage Technique for Content Addressable Memories

IP.com Disclosure Number: IPCOM000080100D
Original Publication Date: 1973-Oct-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Clapson, PJ: AUTHOR

Abstract

This technique, which can be most profitably applied to secondary storage, is applicable irrespective of the content related key set or the size of a desired file.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Search and Storage Technique for Content Addressable Memories

This technique, which can be most profitably applied to secondary storage, is applicable irrespective of the content related key set or the size of a desired file.

A file address key in EBCDIC code is first divided by a number chosen to minimize clustering and to constrain synonym generation. The remainder from this division is then divided by the number of addressable locations in the file to provide a further remainder, which is the required home address. The basic rule for selecting the divisor (D) is that it satisfies the following conditions: a) No |2/i/| is equal to |2/j/| (D) b) No |2/i/| is equal to D - |2/j/| (D) c) No |2/i/| is equal to |2/j/+ 2/k/| (D) d) No |2/i/| is equal to |2/j/ + 2/k/+ 2/l/| (D) e) No |2/i/| is equal to |2/j/+ 2/k/ + 2/l/+ 2/m/| (D) where ij, ijk, ijkl, ijklm are each, respectively, all combinations of different numbers in the range 0 to 31.

If these conditions are satisfied, then the same conditions are satisfied for any consecutive range of 32 bits. As, in the EBCDIC code, the important changes of bit structure are for the lower four bits. The above conditions rule out the use of divisors which, over the range of 32 bits, generate synonyms up to a level of 4 against 1.

The number 54601 satisfies the above conditions and also the following conditions: f) No |2/i/ + 2/j/|(D) is equal to 0 g) No |2/i/ + 2/j/ + 2/k/| (D) is equal to 0 h) No |2/i/ + 2/j/ + 2/k/ + 2/l/(D) is equal to 0 where ij, ijk, ijkl are each, respectively, all combinations of different numbers in the ranges 0 to 31, 32 to 63, and so on up to 224 to 255. Conditions f) to h) limit, over the same range as
a) to e), the possibility of combinations of residues which produce no effect for a key of up to 32-bytes length.

In the file, as shown in the figure, each eighth locat...