Storage arrangement having a device to determine free storage locations

• US 4,047,160 A
• Filed: 02/02/1976
• Issued: 09/06/1977
• Est. Priority Date: 02/10/1975
• Status: Expired due to Term

• Current Assignee: Siemens Nixdorf Informationssysteme AG (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: Wolf, Gerhard
• Primary Examiner(s): Thomas, James D.
• Application Number:
  US05/654,645
• Time in Patent Office: 582 Days
• Field of Search: 340/172.5, 340/173 AM
• US Class Current: 711/218
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A storage arrangement is used as an associative memory having a main memory serving to accommodate the data composed of an associative component (association word) and a non-associative component. A comparator device serves to compare the associative part of the read-out data with a search word and address converters serve to derive storage addresses from the association word or the search word or from parts of such words (prefix). An extension counter is provided whose count influences the address derivation and is increased by one whenever an initially addressed storage position proves otherwise engaged. The main memory comprises a linearly addressed storage bank which is divided into a plurality of pages each comprising a plurality of rows. Each row contains one storage position for accommodating the data, and the sections for accommodating reference characteristics. Separate address covers are provided for the formation of the page and row addresses and the extension counter co-determines the derivation of the page address in accordance with its relevant count. A book-keeping memory, which is read out row-by-row comprises a plurality of rows each having a plurality of bit positions. Each row of the book-keeping memory is assigned to a page and each bit position is assigned to a row of the main memory. Seizure of the bit positions of the book-keeping memory provides information on seizure of the main memory and the book-keeping memory is assigned a book-keeping control unit which controls the setting and the interrogation of markings in the book-keeping memory for seized storage positions in the main memory and the selection of equivalent storage positions.

Claims

1. A storage arrangement for use as an associative memory, comprising:

a main memory for storing data composed of an associative component and a non-associative component;

a comparator device connected to said main memory to compare the associative part of data therefrom with a search word;

said main memory comprising a linearly addressed storage bank divided into a pages each including b rows, each of said rows including a storage position for the data and a portion for storing reference characteristics;

page and row address converters for providing page and row addresses in response to receipt of a prefix;

an extension counter connected to said page address converter to co-determine page address in accordance with its relavant count and whose count is increased by one when an initially addressed storage position is engaged;

a book-keeping memory connected to said page address converters and operated to be read row-by-row, said book-keeping memory comprising a rows each including b bit positions, where each row corresponds to a page and each bit position corresponds to a row of said main memory, each bit position storing a mark indicating seizure of the corresponding row of said main memory; and

a book-keeping control unit connected to said counter, to said row address converters, to said book-keeping memory and to said main memory, and operable to control the setting and interrogation of the seizure marks and the selection of equivalent storage positions in said main memory.

2. The storage arrangement of claim 1, wherein said book-keeping control unit includes means responsive to an extension counter count EZ, where |EZ|>

φ

, to prevent selection of a storage position in said main memory by a row formed from the prefix and assign a free storage position in said main memory for a new entry as determined by interrogation of said book-keeping memory.

3. The storage arrangement of claim 2, wherein said book-keeping control unit comprises a priority network operable to cause storage of new entries in a free row with the highest particular priority within an addressed page.

4. The storage arrangement of claim 3, wherein said page address converter comprises recoding means for recoding received data in dependence on the lower-value bits of the contents of said extension counter, said row address converter includes means for receiving and translating the number n of lower-value bits of a bit combination, which is equal to the number n of the bits of a row address, for input to said book-keeping control unit, the number m of higher-value bits of a bit combination, equal to the number m of the bits of a page address recoded by said recoding means while preserving the bit number m, and comprising an adder connected to said extension counter and to said page address converter for adding the higher-value bits of the contents of said extension counter to the bits supplied by said page address converter in modulo 2^m fashion to provide a page address.

5. The storage arrangement of claim 4, wherein said recoding means comprises a logic linking network.

6. The storage arrangement of claim 4, wherein said recoding means comprises a read only memory.

7. The storage arrangement of claim 4, comprising a bit mixer to acyclically exchange the positions of k bits of an extended prefix, where k is a whole-number multiple of the bits n + m of a page and row address, and a reduction converter having means for reducing the k bits to n + m bits, said page address converter connected to receive the m bits and said row address converter connected to receive the n bits.

8. The storage arrangement of claim 7, wherein said reduction converter comprises a read only memory.

9. The storage arrangement of claim 7, wherein said reduction converter comprises a logic linking network.

10. The storage arrangement of claim 9, wherein said logic linking network comprises a plurality of exclusive-or gates arranged in the first and second groups with the outputs of two gates of the first group connected to the inputs of a single gate of the second group.

11. The storage arrangement of claim 4, for storing association words having an alpha-numeric coding, comprising a code compressor connected in series with said page and address converters to gate out unused code combinations and eliminate redundant, where the number of the bits fed to said code compressor exceeds the number n + m by the number of redundant bits.