Method of searching for data sequences which correspond to a pre-defined search argument and are contained in a hybrid associative memory

The invention relates to a method of prospecting of a given search key corresponding to a Hybrid associative memory data sequences contained in the a combining means is used, the one of the corresponding number of parallel data sequences to be processed including number of independent linking units, where the search argument and the data sequences in test units are supplied.

Such a method is known from DE-OS 33 34 515 known. contains the hybrid associative memory used there a base memory that stores the data sequences are and an associative surface. The associative surface includes a linking device with independently and operationally independent linking units. In the base memory, the data strings (strings) are based on the associative surface stored vertically, a defined number of data sequences in parallel using the linking units of the linking device can be processed simultaneously.

With the well-known search methods may contained in the base memory unaligned data are sought. To is the linking units a search argument supplied with which the data sequences contained in the base memory sequentially character by character comparison. As soon as one of the Linking units equality between the first mark the search argument and a sign of a data sequence has found in the link unit is a cementing is turned on and then checks whether the following Mark this data sequence with the following signs of Search argument match.

The known method requires a large expenditure of time, to a search argument corresponding data sequence available on the basis of memory. The object underlying the invention therefore the object is to provide a fast operating indicate method by which contained the base storage vertically stored data sequences corresponding to a can be found search argument. This is it assumed that the individual data in the data sequences are aligned and have the same length.

This object is achieved in a method of the specified Art by the characterizing features of claim 1 dissolved.

is The special advantage of the inventive method that with simultaneous checking of a plurality of the data sequences in a field of search immediately will be canceled if it in any data sequence of a field Results will be found. In general, even at are fixed two search operations in a field when this Field possible for a given search argument not to score is. All test units of a search argument are only compared with the test units of the data sequences of a field, if at least one data sequence in all previously checked Test units with the search argument matches.

Other developments of the invention result from the Subclaims.

Reference to an embodiment that shown in the figures is, the invention is further illustrated. Show it<b>Fig.</b> 1 shows the basic structure of a hybrid associative memory,<b>Fig.</b> 2 shows the structure of a linking unit linking device the associative area,<b>Fig.</b> 3 shows the basic structure of the control results according to the linking units <b>Fig.</b> 2,<b>Fig.</b> 4 shows the structure of an address control,<b>Fig.</b> 5 is a flowchart for explaining the method.

The in <b>Fig.</b> 1 hybrid associative memory shown is in a conventional manner from a memory based <i>B-SP</i>, a assozativen surface <i>ASS-FL</i>, A source coupled to the latter Results evaluation <i>T-SEL</i> and the higher-level controller <i>HAS-ST</i>,

The base memory <i>B-SP</i> is preferably based on the DE-OS 33 11 665 designed expressly refer to the becomes. In the example of<b>Fig.</b> 1, it consists of 16 storage groups <i>MD</i><b>0</b> to <i>MD</i><b>15</b>Each of which, z. B. <i>MD</i><b>0</b>, Each of four characters or bytes existing data units in rows to turn on or destaging over the data line system <i>HAS-BUS</i> is controllable. Data units can therefore Direct access line by line as in a conventional Memory selectively in one of the storage groups <i>MD</i><b>0</b> to <i>MD</i><b>15</b> hide or stores. In addition, there is particular for the associative operation of the base memory <i>B-SP</i> the ability of each storage group at the same four Mark, namely corresponding to one another of in each case four different data units of the storage group to drive, and the associative surface <i>ASS-FL</i> supply and from this to take over. In such a driving operation is therefore in one go an entire byte or character disc <i>BS</i> from the present case 4 × 16 = 64 characters from base memory <i>B-SP</i> provided or taken from this. According to the 64 linking units<i>ALV</i><b>0</b> to <i>ALV</i><b>63</b> the assoziataiven surface <i>ASS-FL</i> are simultaneously active.

This type of access control for the base memory <i>B-SP</i> allows on the other hand, that, for. example, in each Bytesäule, z. B. <b>0</b>. base memory the successive signs of Data unit and signs of consecutive data units within a data sequence the same link unit z. B. <i>ALV</i><b>0</b>, The associative area <i>ASS-FL</i> can be fed successively. The data sequences in a column are therefore generally of the same link unit <i>ALV</i> the associative surface processed. Thus, a column or string formation of results Characters of a data sequence, hereinafter referred to as a string. The strings may be the same length and in boxes <i>Fl</i> to <i>Fn</i> In the storage room <i>B-SP</i> be arranged. In field<i>Fl</i> after <b>Fig.</b> 1 are z. B. 64 strings, <i>ZK</i><b>0</b> to <i>ZK</i><b>63</b> arranged.

The control of the strings <i>ZK</i> in the fields <i>F</i> done by means of an address control <i>AD-ST</i>Through which the Byte strings or byte or character slices can be addressed. Given receives address control<i>AD-ST</i> a control command <i>CMD SP</i> from the parent control <i>HAS-ST</i> the hybrid associative memory. In this Command can be, for. Example, the start and end address of the to processed string region or the initial address and length of this string region be given.

The address of the controller <i>AD-ST</i> addressed letter <i>BS</i> are the <i>HAS-BUS</i> the associative area <i>ASS-FL</i>. hereinafter referred to as linking device, supplied. The link device processes the signs of disc <i>BS</i> according to one of the control <i>HAS-ST</i> votes command <i>CMD-ST</i>, Since each column in base memory<i>B-SP</i> each link unit <i>ALV</i>-<b>0</b> to <i>ALV</i><b>63</b> firmly is assigned and each of these link units independently works, can by linking means parallel and independently of one another each string character by character be or byte processed.

In search process must be determined whether the base memory <i>B-SP</i> Strings or parts of strings are included that match a given search key. These search arguments can in a separate memory <i>PAR-SP</i> be contained, the expedient in the same Manner can be constructed as the base memory <i>B-SP</i>. however, with the difference that the same type as a result of Applying all linkage units <i>ALV</i> the combination device with uniform external Search arguments needs only a storage group for becomes. With each by the controller<i>HS-ST</i> caused Control of the parameter memory is a z. B. Characters of the search argument <i>PAR</i> the link device, namely all linkage units <i>ALV</i>Supplied. If the strings <i>ZK</i> not by character or byte, but bit by bit or in other units supplied for processing the link device will then have the settings memory, the search arguments in correspondingly large units on the link device be transmitted. These units can also Test units are called.

The structure of the individual link units <i>ALV</i> is in <b>Fig.</b> 2 shown and described in detail in German Offenlegungsschrift 33 19 581 describes the hereby the present description is incorporated. core This combination device <i>ALV</i> is an arithmetic logical unit <i>ALU</i> with a working width of one character, z. B. 8 bit. The two operand inputs of<i>ALU</i> each is a masking <i>A-MASK</i> and <i>B-MASK</i>, on Operand register <i>A-REG</i> or. <i>B-REG</i> and a selection switch <i>A MUX</i> or. <i>B-MUX</i> upstream. About the latter, the two operand register from the various sources be selectively loaded. In this case, z. B. the registry <i>B-REG</i> with characters from the base memory <i>B-SP</i> the hybrid associative memory loaded, the register <i>A-REG</i> with characters from the parameter memory <i>PAR-SP</i>, With the help of Masking, the operand corresponding to a mask control <i>M-ST</i> be masked.

The result of the operation by the <i>ALU</i> may at Searches in a signal <i>SIG</i> made that a display control <i>ANZ-ST</i> is supplied with a Results control <i>T-ST</i> coupled. This is a function of ads each present <i>SG</i> and each carried out association or relation Search condition a hit <i>T</i> from or not from.

Results of Results Control <i>T-ST</i> can then use Meet the evaluator circuit <i>T-SEL</i> be evaluated.

From the already mentioned DE-OS 33 19 581, the additional Functioning of the link unit to <b>Fig.</b> 2 taken are, however, not for the present search process needs to be further explained.

Details about the structure of control results <i>T-ST</i> are <b>Fig.</b> 3 removed. The hit control detail explained in DE-OS 33 34 515, which is incorporated into the Description is incorporated. The assigned by the<i>ALU</i>- votes result signals <i>SIG</i> be the display controller <i>ANZ-ST</i> supplied. This determined known in itself Way from the signals <i>SIG</i> the required display, eg. B. the ads <b>0</b> Volts for the overflow, <i>Z</i> for the result <b>0</b> and <i>VZ</i> for the sign of the respective operation result. These ads are in the device <i>T-SIG</i> corresponding to the individual association relations Hit signals formed, of which the selection switch <i>MUX-TA</i> the respective provisions hit signal selected and the results display <i>TA</i> is forwarded.

The determined and selected results display <i>TA</i> is now not just as a hit <i>T</i> passed, but they is possibly dependent appropriate by the respective application modified boundary conditions. To this end is one of the AND gates <i>U</i><b>1</b> to <i>U</i><b>4</b> and OR gates <i>O</i><b>1</b> and <i>O</i><b>2</b> existing link network <i>VN</i> provided the set and reset signals <i>S</i> or. <i>R</i> for a downstream flip-flop <i>PH - FF</i> supplies. In the figure is the flop <i>PH-FF</i> from eight flip-flops <i>PH-FF</i><b>0</b> to <i>PH-FF</i><b>7</b>However, it is also possible, that only a single flip-flop is provided. respectively one of the flip-flops, with the aid of an upstream selector switch <i>DMUX K</i> driven.

To the hit indicator <i>TA</i> with preceding Records <i>TA</i> or to otherwise modify chains can, the Trefferkippschaltung <i>PH-FF</i> through the link network <i>VN</i> both absolutely and conditionally be set or reset, by the control signals <i>S</i> and <i>R</i> for the unconditional attitude and by the control signals <i>SB</i> and <i>RB</i> for the conditional, ie for the respective one of the hit indicator <i>TA</i> dependent adjustment is made possible. For example, at the beginning of Seek the associated flip-flop <i>PH-FF</i> with the help the signal <i>S</i> and a clock signal <i>CL</i> are set and at no occurrence of a hit list <i>TA</i> and concerns of the control signal <i>RB</i> reset. The Kettungsflipflop<i>PH-FF</i> reset also remains when upon application of the control signal <i>RB</i> later Records <i>TA</i> occur. With the aid of the control signal<i>RB</i> can thus Concatenation between consecutive scoring <i>TA</i> be achieved.

Of the Kettungsflipflop <i>Ph-FF</i> questions available Results signals of a downstream selection switch <i>MUX-H</i> switched through to output and give the hit signal <i>T</i>,

The further in <b>Fig.</b> 3 units shown, which do not have been explained, and the operation of which have for the description of the inquiry procedure a subordinate Importance. Their duties may include. For example, DE-OS 33 34 515 be removed.

The hit signals <i>T</i><b>0</b> to <i>T</i><b>63</b> the link device <i>ASS-FL</i> can a Meet evaluator circuit <i>T-SEL</i> are fed, which in the simplest case as OR Member is realized. That is if at least one hit<i>T</i> occurs, the Meet evaluator circuit <i>T-SEL</i> on Signal for controlling <i>HAS-ST</i> and displays the fact that at least in one of the strings <i>ZK</i> the search process there is a hit.

The address control <i>AD-ST</i> , according to <b>Fig.</b> running 4 be. It is made after<i>ALU</i><b>1</b> and <i>ALU</i><b>2</b>, registers <i>RGL, RGS, RGD, RGE</i>, Counter <i>ZH</i> and a comparator <i>COM</i>, From the upper controller<i>HS-ST</i> are the registers <i>RGL, RGS</i> and <i>RGD</i> the corresponding data provided. In the register <i>RGS</i> is the starting address for a disc <i>BS</i> in base memory <i>B-SP</i> stored. outgoing from this starting address is an area in the base memory processed, its length in the register <i>RGL</i> is stored. In the register <i>RGD</i> finally, the distance from a Field stored to the next field. The start address is from the register <i>RGS</i> first to <i>ALU</i><b>1</b> transmitted and passes from there into the register <i>RGE</i>, The length to be tested the Region is on the <i>ALU</i><b>2</b> in the comparator <i>COM</i> stored. The start address enters the counter <i>ZH</i> (By a clock signal <i>CL</i>) And this starts counting. He is the first address<i>AD</i> to the base memory <i>B-SP</i> from. This is followed by the next address, etc. until the counter <i>ZH</i> given address with the comparator <i>COM</i> saved Address matches. If this is the case, then is the desired range in base memory <i>B-SP</i> processed been. Now the comparator<i>COM</i> a signal for register <i>RGE</i> from the basis of which the of the <i>ALU</i><b>1</b> calculated Value is taken. Namely, there is the start address from the register <i>RGS</i> and the distance to the address the next field in the register <i>RGD</i> been added, for example. and as new start address has been found. Accordingly, using the preceding starting address and the length in register <i>RGL</i> with the help of <i>ALU</i><b>2</b> the end to be machined of Area in the next field is calculated and in the comparator <i>COM</i> stored.

The higher-level controller <i>HAS-ST</i>Which, for. Example, as in DE-OS 32 16 905, may be formed as a microprocessor may, controls in a conventional manner the entire workflow of the hybrid-associative memory on the basis of of externally supplied instructions for performing predetermined Tasks then the hybrid associative memory autonomously be executed.

One of these possible tasks is in prospect for Data based on a given search argument from the Base memory stored data sequences or strings. Here, it is assumed that the character strings in fields <i>F</i> are arranged in the base memory and same have length. Furthermore, it is assumed that the character strings per field parallel to the link device <i>ASS-FL</i> be processed in each case one character or byte. Of course, it is also possible the individual strings <i>ZK</i> bit in the link device edit, or in other units. The now to be described search process then accordingly.

The inquiry procedure is based on the <b>Fig.</b> 5 illustrates, in of a flow diagram. must at the beginning by the controller <i>HAS-ST</i> an alert to the hybrid associative memory are given. For this purpose, control commands<i>CMD SP</i> and <i>CMD-ST</i> leave. For example, in the parameter memory <i>PAR</i> the search arguments loaded and in the address control <i>AD-ST</i> the starting address, length and distance between the fields entered. In the linking units<i>ALV</i> be in the results control by a control signal <i>S</i> the Trefferkippstufen <i>PH-FF</i> set. Subsequently, a control signal <i>RB</i> the results control applied and thus set a concatenation.

The search process begins with a first character the search argument from the parameter memory <i>PAR-SP</i> z. B. the <i>A</i>-Register <i>A-REG</i> the linking units <i>ALV</i> stored becomes. Subsequently, by the address control<i>AD-ST</i> a disk <i>BS</i> with the first signs of to checked strings <i>ZK</i> z. B. in the field <i>F</i><b>1</b> the associated linking units <i>ALV</i><b>0</b> to <i>ALV</i><b>63</b> supplied namely, z. B. in the <i>B</i>Register inscribed. Now may by <i>ALU</i> the individual link units <i>ALV</i> the Association command are performed. To the Example, according to the search condition, the mark the search argument with the sign of the strings are checked for equality. The linking units<i>ALV</i><b>0</b> to <i>ALV</i><b>63</b>, The equality between the characters the search argument and the sign of the strings notice give a hit signal <i>T</i> from which the Meet evaluator circuit <i>T-SEL</i> is supplied. All other logic units<i>ALV</i>Who find no equality, give a miss signal which causes the assigned Trefferflipflop locked in the results control becomes. For these linking units<i>ALV</i> is thus interrupted the Trefferkettung and occurring later Results not taken into account, ie for later occurring equality between a character of the search argument and a sign of the strings give this Linking units no longer hit signal from.

If the Meet evaluator circuit <i>T-SEL</i> a hit signal indicates - this is always the case if, in a testing procedure at least one hit occurred, - then must are first checked whether all the characters of the search argument have already been tested or not. Are not edit all the characters, then by the address control <i>AD-ST</i> the address for the next slice <i>BS</i> generated, as the address for the next character of the search argument in the parameter memory <i>PAR-SP</i> and the newly addressed Characters in the linking units <i>ALV</i><b>0</b> to <i>ALV</i><b>63</b> Loading. Again, the association instruction in the linking units running, this has, however, only for unlocked linking units meaning. In the locked linking units are, as already explained above, already interrupted the Kettungen.

This search process is executed until either all the characters of the search argument has been verified or none of the linking units <i>ALV</i> a hit signal outputs. If no hit signal at the output of more linking units <i>ALV</i> on, even though the characters of the search argument not all have been processed, then there is in the relevant field, eg. B. <i>F</i><b>1</b>, Not the Search argument corresponding string. In this case is the start address for the search argument in the parameter memory <i>PAR-SP</i> reset to the initial value and by the address control <i>AD-ST</i> as the next address <i>AD</i> the address of the next field, eg. as the field <i>F</i><b>2</b> generated. is then searched for in a corresponding manner in this field, if the search argument one or more strings equivalent.

Are all characters in a search argument tested against it been and are the Meet evaluator circuit <i>T-SEL</i> at all characters of the search argument from hit signals, then corresponds to at least one string in the scanned field <i>F</i> the search argument. Using the results of the signals linking units <i>ALV</i> then, the character string corresponding to be found in the field and, if desired, the string or character string are returned.

can be removed from the process described in that the search process in a field <i>F</i> just as long as performed is, as long as at least one link unit <i>ALV</i>, the a string is assigned to the field, a hit signal write. Once all Trefferkettungen are interrupted, finished searching the field and the search in the next Field started. If there is no the search argument corresponding String in the field, then the probability is high, that the search operation after two searches, so after processing of two slices <i>BS</i> is completed since then all Trefferkettungen in the linking units <i>ALV</i> are interrupted. This value of two slices<i>BS</i> is in the Moreover, regardless of the string length. Then you can already begin processing the next field. Using the hybrid associative memory according <b>Fig.</b> 1 can thus determined very quickly whether a search argument corresponding strings in memory <i>B-SP</i> contain are.