Storage arrangements

Main memory, a quick overview of the respective occupancy state of the main memory is achieved

The addresses for the pages and lines of the main memory are obtained from the association or search terms or from parts of these terms. The bit parts used for the address formation of the association or Search terms are referred to as prefixes, regardless of whether the prefix covers only the higher-order bit positions of these terms or the entire terms. There are many ways of deriving the page and line addresses of the main memory, which sometimes result in different filing modes for new entries of association terms , All embodiments, which will be discussed in more detail later, is a Seitenadreßwandler in common, which consists of a link network or a small read-only memory He outputs at its output as many bits in parallel, as applied to its input. On a particular Zeilenadreßwandler can be dispensed with in general.

For some applications, it is advantageous to use a prefix with more bits than required for addressing. The prefix is ​​then compressed by link networks or read-only memory

Since ir. Rule, the number of memory locations in the main memory is less than the number of possible combinations of all bit positions of the association terms, regardless of the specific type of address formation always lead multiple association terms to the same addresses. It will therefore frequently happen that a memory location selected in the main memory by the original page and line address already proves occupied if a new association term is to be stored. Due to the mapping of the occupancy state of the main memory in the accounting memory but the allocation of an equivalent storage space for the upcoming new entry is easily and quickly possible. For this purpose, an extension counter is provided, the respective counter reading for the formation of the page addresses is co-determining and is always increased from 0 by one counting unit, if the previously addressed memory space is already occupied. In this way, a chain of similar association terms is constructed, all of which initially lead to the same addresses of the main memory

would. ,

In forming such links, it is advantageous to control the translation function of the page address converter by a few (e.g., 3 or 4) least significant bits of the respective state of the extension counter. The higher order bits from the expansion counter are added to the bits at the output of the page address converter without increasing the number of digits. The addition result represents the page address.

Memory content often consists of several independent data groups, with the data within each group being in an organizational context. Such data sets may be, for example, translation tables, decision tables, programs and program parts, and many others. They will be referred to as independent tables. Manipulating such tables in large associative memories having a plurality of independent IIs will in many cases be greatly simplified if separate associative memory areas are assigned to the individual tables become. It should be noted here only on the sorting of table contents, in which otherwise the entire memory would have to be searched systematically.

However, partitioning the memory into fixed physical areas carries the risk that areas will not be exploited or prove too tight. It is therefore the object of the invention to provide measures which allow the subdivision of the associative memory in separately associable areas whose capacity can be adapted to the respective requirements at any time. It goes without saying that this can only apply to the extent that the total capacity of the memory is not exceeded.

According to the invention, this object is achieved in an associative memory of the type mentioned by the features listed in the characterizing part of the main claim

It should be noted here that the subdivision of the memory into separately associatable areas created by the invention only exists in an organizational respect. Nothing can be said in general form about the actual spatial position of these areas in the physical memory. Rather, the areas can penetrate each other. The invention will be explained in more detail by means of embodiments with the aid of the drawing. It shows in it

F i g. 1 shows an overview of an associative memory with a main memory with a memory bank and with additional devices.

F i g. 2 shows the course of chain lines depending on the state of the extension counter,

F i g. 3 fields associated with the entry of reference identifiers in the memory locations,

F i g. 4 shows an arrangement for deriving addresses for the main memory from the association or search terms, F i g. 5 shows an exemplary embodiment of an address wall

F i g. 6 shows an arrangement for supplementing the arrangement according to FIG. 4 (code compressor),

F i g. 7 shows a block of the arrangement according to FIG. 6 and

F i g. 8 shows an overview of an associative memory with a main memory with a plurality of memory banks and with additional devices.

The fi g. 1 indicates the main memory ASP1, which is subdivided into a pages of b lines each. Each memory line consists of the actual memory space for recording the association term to be stored and, if appropriate, a non-associative data part and two additional fields Fl unc FI for the entry of markings, which will be discussed in more detail later. The comparison necessary for the associative comparison of the read-out data with the respective present search term is shown in FIG. 1 not shown. Also not shown are a mask register, whose variable content makes it possible to expand the area taken into account in the associative comparison, or narrow down the address decoder necessary for selecting the memory location.

The main memory ASP 1 is associated with the wordwise readable bookkeeping memory BSP. The book store BSP has as many words as the main memory ASPi has pages, every word ir

Accounting memory BSP consists of as many bit locations as each page of the main memory has lines. In a bit position of the bookkeeping memory ASP, a mark bit is set (indicated by a dot in the drawing) when the relevant line of the main memory is occupied by an entry.

As bookkeeping memory BSP, a fast bipolar semiconductor memory is advantageously used. It can be a reserved area of ​​a shared memory for other purposes. If appropriate, however, a section of the memory serving as main memory can also be used for this purpose.

The bookkeeping memory BSP is an accounting control unit BFE added that performs auxiliary functions. For example, it reads the word selected by the page address SA of the main memory ASP \ in the accounting memory BSP, and selects the highest priority free space within the selected page of the main memory ASP by a priority network if a memory selected by the original line address ZAo already exists is occupied. The accounting control unit BFE also sets the flags in the fields Fl and F2 of the main memory ASPi and evaluates the flags read from these fields. It also controls the extension counter EZ.

It has already been pointed out that the extension counter EZaIs is provided for the allocation of equivalent storage locations for new entries. Its respective counter reading is decisive for the formation of the page addresses and is always increased by one counting unit from 0, if the previously addressed memory space is already occupied. The chain of similar association terms constructed in this way, which would all initially lead to identical addresses, is in the F i g. 2 depending on the level \ EZ \ of the extension counter ΕΖΥΕΖ-Stand). The irregular line drawn by the arrows connecting the individual links is called a chain line. One and only one such chain line can begin in each line of main memory. However, it is not necessary for the chaining line to change to a different page of the main memory every time the state \ EZ \ of the extension counter EZ changes. Furthermore, it may happen that single £ Z levels are skipped because the main memory pages addressed with the aid of the skipped £ Z levels are already fully occupied

It is advantageous that the address ZAo derived from the association address by the row address converter only at the first respective term d h. For the entry of further chaining items (| EZ |> 0), free memory locations within the selected pages are determined with the help of the bookkeeping memory

For the systematic construction of a chaining line and for retrieving the association terms stored along the chaining line, it is necessary to enter reference labels in the fields assigned to each memory location. All reference labels consist of specifying a specific state of the extension counter EZ and a row address (within a main memory page). It is advantageous to provide two fields F1 and F2 and proceed in the following way:

The field F1 of the start link of a chain (start line) contains a reference to the respective end of the chain. The fields F2 of all other links contain the information concerning the respective preceding link. 3 shows the reference numbers of a four-membered chain from the terms Bi to B 4. The chain is constructed from left to right and - starting from the field Fl on the left side - read from right to left or

aufgebautο built.

The previously not mentioned devices of the arrangement according to F i g. 1 serve to derive the memory addresses from the association or search terms in the register REG. The role of the extension counter in connection with the address formation has already been pointed out. The various possibilities for deriving the memory addresses can be divided into three main groups, which result in different storage modes. It is expedient, as in FIG. 1 shown to provide the three groups corresponding versions simultaneously, which can then be used according to the respective requirements either. To select between the different types of address derivation is a multi-pole switching device symbolized by the switch MOD Depending on its position and the MASK mask is changed.

In all positions of the switch MOD is a

Bit combination with constant number of bits, the fragment FRAG, switched through The number of bits corresponds to the sum of the bits in the page and row address. In the middle position m2 of the switch MOD, the fragment FRAG is identical to the prefix VS. which is hidden by corresponding setting of the mask MASK from the association term (or search term).

The further processing of the fragment, in particular with the aim of achieving a subdivision of the memory into separately associable regions, is as shown in FIG. 1 only hinted at. It will be described in detail below with reference to FIG. A register ÄS provides on-demand (per program) control information BGR for area delineation and an area address BAD.

The control information BGR is used to control an oblique operator, which is shown in FIG. 4 is represented by a displaceable mask MSAB with a constant aperture and by a field SAB (cf. DT-AS 19 16 377). The opening of the mask MSAB is shifted under the influence of the control information BGR so that more or less of the more significant bit of the fragment FRAG is tapped and transferred into the field SAB. At most, the entire fragment FRAG m is transferred to the field SAB. Incidentally, as many low-order Bh of the area address BAD, detected as low-order bits of the fragment FRAG are excluded. The π least significant bits of the bit combination present in field SAB are used directly as the row address for the main switch. The remaining m more significant bits of the bit combination are fed to a page address converter consisting of a link network or a read-only memory. three or four) bits of lower value \ EZ \\ of the content of the expansion counter EZ controls the translation function of the page address converter SA W. The portion \ EZ2 \ containing the high-order bits of the content of the expansion

Counter is modulo 2 in an adder ADD to the bit supplied by the page address converter SAW^m added. The addition result represents the page address SA for the main memory.

An embodiment of the Seitenadreßwandler SA W for processing 16 bits of commercially available memory modules, the Fig.5. Each read-only memory ROM accepts a group of 4 bits from the skew provider SAB υηά the 4 least significant bits of the extension counter £ Zals address, the latter are all equally supplied to all four read memory blocks ROM. The accessed memory contents of the read memory blocks ROM are removed via 4 output lines.

It has already been noted that the line address ZAo derived from the fragment FRAG or from the association term is only used for addressing the start line of a prefix line, ie only at the state 0 of the extension counter. In order to make this clear, a symbolic switch 45 with three positions is shown in FIG. The drawn (right) position of the switch AS applies to the case | £ Z | = 0. The two other positions, the switch AS always takes. if the state of the extension counter is different from 0 (| £ Z |> 0). Under this condition, the middle position is valid for a write cycle in which the line address is determined by the accounting control unit BFE using the accounting memory BSP. In the right-hand position, the switch AS is located during a search operation in which reading the terms along a chain line also reads the line addresses of the links belonging to the chain contained in the reference marks.

The separately associative regions generated by the function of the oblique operator are defined only for primary entries ("EZ = 0") by the fragment FRAG, the area address BAD and the control information BGR, otherwise behaving like elastic bubbles whose size is independent of this entrance opening Of course, the total available memory space can not be exceeded. If the area available for primary storage is insufficient, an unlimited number of secondary storage spaces are available as an extension. In this case are on the after F i g. Thanks to the possibility of allocating free memory locations with the aid of the bookkeeping memory BSP, the storage is effected without significant inhibition. Overlapping of chain lines does not occur.

The type of address derivation resulting in the middle position m 2 of the switch MOD (FIG. 4) results in a sortable storage mode of the stored association terms. It is particularly suitable for sorting the terms according to a dual numerical order. For this purpose, a sorting counter can be used, which retrieves all chaining lines in this order one after the other. The individual, not yet sorted content stored along a chaining line are transferred into an associative register set and output by the latter in the final sorting order.

In the above storage mode, however, must occasionally mn the formation of longer chains can be expected. There are hardly any disadvantages for the sorting, whereas time losses occur in the associative search for individual terms. It is therefore expedient to use this filing mode only if in particular a dual-numeric sorted output of terms is desired.

The last-mentioned disadvantage is avoided by a »diffuse« storage of the terms in the main memory. However, the immediate sorting capability of the memory contents is practically lost because the sorting of diffused words would require too much time. If you still want to sort, then a previous shift to a sortable storage mode is recommended. The diffuse filing is achieved in that the prefix VS used for the address formation is extended to substantially more bit positions by appropriate control of the MASK mask than are actually required for addressing the main memory. The necessary reduction of the many-digit prefix to the fragment FRAG having a smaller number of bits is achieved by a reduction converter REW, which functions in the position m 1 of the switch MODm. The reduction converter REW preferably consists of a read memory which is addressed by the prefix VS and outputs at its output the various bit combinations of the fragment FRAG. Naturally, different prefixes VS also deliver identical fragments FRAG.

The extension of the prefix area improves the statistical distribution of terms on different chainlines so as to drastically reduce the number of longer chains. Links with more than four links are extremely rare.

Accordingly, associative searches can be handled quickly because there are hardly any more serial searches.

In the third position m3 of the switch MOD an address formation is performed, which also leads to a sortable storage mode. It is suitable for the later sorting of the terms in alpha-numeric order

In the position m3 of the switch MOD, the fragment FRAG is obtained by means of a code compressor CV from the prefix VS (see Fig. 1). Since the conventional codes for letters and numbers occupy only a small part of the 256 combination options offered, undesirable long chainings can occur without the use of additional measures. The code compressor CV reduces the bit position number of the code to the necessary degree and excludes all unused combinations from the outset.

An on the EBCDI code off, from dre

Individual components of existing code compressors is ii the F i g. 6 schematically illustrated The code compiler CV uses a prefix VS with 21 bits to compact them on a fragment FRAG with 16 bits A single block of the code compressor CV with S input terminals 0-7 and 6 output terminals 0-ί shows the FIG. 7th It consists of the AND gate elements Al-A 7.demOR-ORG and the inverter INV. Its structure is readily apparent from the drawing. A comparison of both f i g. 6 and 7 show that in the code compression CV on the right side each three input and drc output lines are not used.

The subdivision of an associatively managed!

609 5 SK

Memory in separately associative areas in the manner described can be achieved not only in connection with a main memory with a memory bank but also with a memory arrangement consisting of several equal memory banks.

In the overview of FIG. 8 is an embodiment of a per se known by the already mentioned DT-OS 23 19 468 storage device supplemented by the additional device for dividing the memory into separately associable areas according to the invention. The actual Sipeicher ASPB consists of 6 (preferably 8) memory banks SSO to SB 5, each having a plurality of memory locations PO to Pk. For addressing the memory locations, each memory bank is assigned an address converter ADWO to ADW5. Each address converter has a different translation function, such that a fragment FRAG applied to the inputs of the address transducers supplies a different address for each memory bank. If all storage locations that are addressed by a specific fragment FRAG are connected, then an irregularly running chain line results. By incrementing the extension counter EZ whenever all storage locations along a chain line are already occupied, and by adding its contents to the output variables of the address transducers, extensions of the chain lines are created.

The bit combination at the input of the address transducers is supplied by an oblique provider, which in the manner already described picks up the high-order bits of a fragment FRAG and the low-order bits of an area address BAD. The shift of

Schrο oblique operator is controlled by the control information BGR for area delineation. The derivation of the fragment FRAG from the association concept can be done in any manner known from DT-OS 23 19 468. As in the memory array with multiple

Memory banks can also occur when subdividing into separately associative areas, where overlapping of chain lines can occur, for each input association term, the entire area address BAD, which is used in the derivation of its address, is also used

(partially) codeterminate, filed for the unambiguous identification of the term. As an intersection of chain lines, the case is referred to that a memory space of two or more chain lines is detected.

For this 5 sheets of drawings