Patent GB-1533326-A (GB)
Title: Storage arrangements
IPC: G06F17/30
Filed: 1976-02-09
Abstract: 1533326 Associative storage system SIEMENS AG 9 Feb 1976 [10 Feb 1975] 04913/76 Heading G4A A storage system includes a store ASP divided into a = 2<SP>m</SP> pages each of which has b = 2<SP>n</SP> rows, each row being arranged to store a tag, and an associated data item, a comparator to compare tags read from the store with a search tag, and means to address the store which includes means SAW, ZAW forming page and row addresses for the store from a tag, the page address being also dependent on the contents of an extension counter EZ which is incremented whenever an addressed row is already occupied, a book-keeping store BSP having a rows, one per page, each of b-bit positions, one per row, each bit indicating whether the corresponding row is occupied, and a control unit BFE which acts in response to page and row addresses to access the book keeping store to determine whether the corresponding row is occupied and if so to form a new row address for the tag to be stored for use in conjunction with a new page address formed by incrementing the extension counter. It is stated that the store may be operated as a conventionally addressed store rather than as an associative store either wholly or over only part of its storage space. Part VS of a tag to be stored, or a group of bits formed by logical operations on the tag (Figs. 7, 8, 9,not shown) is formed and split into page VS2 and row VS1 parts. The page part VS2 together with a group of bits EZ1 from the extension counter EZ, initially zero, form in converter SAW an m-bit page address (e.g. by addressing read only memories) to which the remainder of the extension counter contents EZ2 are added ADD module 2<SP>m</SP> to form an m-bit page address SA for store ASP. The row part VS1 is passed either unchanged or via a row address converter ZAW, which may for example simply exchange certain bits, to the store. The resulting location is used to store the tag and its associated data item. Since the number of addressable locations in the store is lower than the number of possible combinations of all the bit positions in the tags irrespective of the way in which addresses are formed from the tags, several tags will produce the same address. Thus whenever a tag is stored the corresponding bit in the book keeping store, addressed by the page and row addresses, is set. When an addressed formed from a further tag is already occupied, indicated by the book keeping store, the extension counter contents are incremented to form a new page address, which may be the same as the original page address, and a row address is determined by locating the highest priority free row in the newly addressed page using the book keeping store, e.g. by feeding all the bits for the relevant page to a priority network. In order to enable a chain of locations formed by successive incrementings of the extension counter EZ to be searched the first location in the chain, extension counter 0, contains a reference Fl, in the form of the extension counter content and row address to the last item in the chain, this being updated as more tags are stored in the chain, and the remaining locations each contain a similar reference F2 to the preceding location. Thus when searching, and a tag read from the initially addressed location does not match the required tag, the chain may be searched by using the references and extension counter to examine successive locations in the chain until the required tag is located. This is symbolized in Fig. 6 by switch AS which has three positions, one connected to ZAW for the initial item EZ = O, one connected to the book keeping store BFE for use when an address for an item to be stored is occupied, and one connected to the main store to receive the references F1, F2  in the chain for searching. The book keeping store may be a small bipolar semiconductor device or may be part of the main store ASP or another store which is also used for other purposes. Although each chain begins at a location addressed with EZ = O it may be that this location is occupied by an item some way along a different chain, EZ # O. In this case the alien item may be relocated using a different setting for EZ and the references in the relevant chain updated as appropriate. When deleting an item from a chain the last item in the chain is moved to fill the gap and the references updated as necessary.  Large tags which cannot be stored in a single location may be split with each part being treated as a separate tag. An additional reference F3 may be included in each location to indicate this. The way in which the page VS2 and row VS1 parts are formed from the tags determines the distribution of a given set of tags in the store, i.e. whether long chains are formed or whether most tags can be stored at the head (EZ = O) of a new chain. Long chains are useful when sorting operations are to be performed which may be as in Specification number 1,486,214. The Specification also refers to Specification 1,533,325 and 1,475,785.