DE2126992A1 - Associative storage system - Google Patents

Description

Applicant's file number: Docket UK 969 006

As so ζ iative storage sys tem

The invention relates to an associative memory system in which several individual associative memories for performing logical and arithmetic operations are connected.

By the German Offenlegungsschrift 1 931 966 z. Legs Data processing system has become known, which consists of several associative memories for performing both logical and arithmetic Basic operations exist.

This data processing system is characterized in that one of several, such as a working memory identification field and word storage locations of existing associative control stores containing a control store identifying label with the working memory identifier via a collecting line

containing one of several identification fields each identifying a working memory and a first working memory data field Word memory locations addressing existing associative working memory and that vice versa the working memory with the first main memory data field is addressed to the control store via a bus. .

109852/1686

However, this arrangement has the disadvantage that it is designed only for one special purpose, namely for more flexible design the control memory of a data processing system.

A universal use of this memory arrangement within a data processing system is therefore not economical possible. In particular, it is only possible to a very limited extent with the known arrangement to perform logical or arithmetic basic operations to execute.

The invention is therefore based on the object of a storage system to create from associative memories that with a minimum of driver and logic circuitry overhead and logical Can perform basic arithmetic operations and can also be used universally in a data processing system can.

The inventive solution to the problem is that several Associative storage groups or levels are connected to one another in such a way that each group or level is used as a storage register or level. whose content serves as a search word for the others and that several simultaneously selected words from a memory group have a common Output ^ form a word, of which only a part is masked as a search argument for another storage group or for other storage groups takes effect.

The advantage of the solution according to the invention is that by connecting the storage levels to one another with a minimum a high degree of flexibility in terms of driver effort and logic switching elements is achieved, which enables the mutual addressing of associative memories. By inserting the familiar masking In this system it is also possible to only use certain Share as a search argument or keyword for the other storage groups to use and thus to carry out specific logical or arithmetic basic operations. The present The system can be used either as a central unit or as a control unit.

10 9 352/1686

Docket UK 969 006

unit can be used in a data processing system.

Embodiments of the invention are shown in the drawings and are described in more detail below. Show it:

Fig. 1 is a block diagram of a split into two groups Associative memory;

Fig. 2 is a block diagram of a link / driver

circuit that is used to connect the in Figs. shown groups is used;

FIG. 3a is a block diagram of one in the circuit of FIG

Fig. 2 logic circuit used;

Figure 3b is a schematic of the circuit shown in Figure 3a;

FIG. 4 is a block diagram of a matrix of groups in FIG

general type shown in Figure 1;

FIG. 5 is a block diagram of one of the groups used in FIG. 4 with a particular illustration of the gate circuits in the group;

Figure 6 is a block diagram of one type of in the group

the gate circuit used in FIG. 5;

Figure 7 is a block diagram of another in the group

the gate circuit used in FIG. 5;

Fig. 8 is a block diagram of a control system for controlling

the group matrix of FIG. 4;

FIG. 9 shows two used in the control system of FIG

Control units;

109852/1686 Docket UK 969 006

Fig. 10 is a circuit diagram of one of the control units the latch circuit used in Fig. 9;

11 is a block diagram of a clock unit in the control system of Fig. 8;

FIG. 12 shows a timing diagram with the input and output signals from and to the clock generator of FIG. 11 and

Fig. 13 is a block diagram showing the in one of the Fig.

shown control units stored data patterns.

In Fig. 1, an associative memory is shown, the upper one Group A and a lower group B includes. Each group consists of a number of multistable memory cells 1, each with a Word line 3 and two bit lines 4a and 4b each are connected. Each cell consists of a transistor circuit that turns can be switched to the states 1, 0 and X or Y. A cell is designed into the appropriate states by simultaneously their supply voltage lowers and the voltage on the word line and raises one or both bit lines. The bit lines represent 1 and 0, respectively, from left to right in FIG. 1 and therefore the cell is switched to its ones state when the word line and the 1-bit line are energized. In a similar way Way, the word line and the O bit line are energized to to switch the cell to its 0 state. To switch the cell to the X or Y state, the word line and both or neither of the two bit lines is correspondingly excited in connection with the above-mentioned lowering of the supply voltage the cell. In order to read a cell without changing its state, the corresponding word line is energized and the cell transmits Current on one or both (Y-state) or neither of both bit lines (X-state) according to their state.

; v, * * "1098 62/1686
Docket UK 969 006

Since it is an associative memory, each cell can be retrieved one or both of bit lines in response to the Einerbit or the O-bit by energization. A match is indicated by the lack of a current on the word line. So when an interrogation signal for a one-bit is applied, no current flows on the word line when the cell is 1 or X, but when the cell is O or Y, a discrepancy is created by energizing the Word line displayed. Similarly, if an O-bit interrogation signal is applied and the cell is in the 0 state or the X state, no current flows and a difference is indicated by energizing the word line when the cell is in the 1 state or in the Y state. State stands. These query operations do not change the state of the cell.

As seen from Fig. 1 is _f, the bit lines of the upper and lower group are connected to each other by the driving circuits 2. Such a driver circuit is shown in more detail in FIG. 2 and comprises a number of logic circuits _f which are shown in block form in FIG. 3a and schematically in FIG. 3b. These circuits respond to negative signals representing a binary one and provide a 1 output signal at point E and an 0 output signal at point D only when a 1 input signal is applied to points A, B and C.

In Fig. 2, the SCHpEIBEM or SUCEEK lines are energized to to control the data input in the corresponding groups. The lines with the inscriptions FROM THE LINE and, TO THE LINE are used to send input and output data to memory or to be transferred from the memory and the line OUTPUT CONTROL can be energized to provide output information.

As already mentioned, it is an associative memory * in which, as is well known, a selected number of bits can be queried in a stored word in order to read or teach this word:; u wHulcn. In the present memory, the

"^ T _fiK ~; π 'vr ' ■ Ü98B2 / 168B

Number of bits selected by using a masking system. By putting a word in a storage group together with a Mask is read, which controls the bits - which are used as search arguments are to be used. Then the other memory group is queried with the masked bits. On the other hand, at the same time Excitation of a word line of the memory group into which data from the other group is to be put, masked data in this group will be written. Each group can therefore be used as a register for associative addressing or writing to the other Group can be used. The following tables show the effect of the output signals from two corresponding cells in two words in one group (e.g. group A) to the corresponding cell in the other group (e.g. group B) after going through the logic circuit according to FIG. 2.

OUTPUTS TO WRITE (Group A) (Group B) 1 + 1 1 0 + 0 0 1 + X 1 Q + X O 1 + 0 unchanged X + X unchanged

QUERY
(Group B)

1 or X match

0 or X match

1 or X match 0 or X match

0 or 1 or X match 0 or 1 or X match

This table can be used for the outputs of a combination derive the following generalizations from two or more words read at the same time:

a) Results in all ones or zeros in a pair of bitlines a one or O output signal.

·, ■,. =. \ 10 9852/1686

Docket UK 969 006

b) Mixed ones and zeros or all Xs result in a masked output (no output on a bit line)

. c) A Y combination with another output signal results in a masked output signal.

In the embodiment, a masked information z. B. prepared in group A as follows:

a) Reading a data word into the group.

b) Read a word with ones in places where a mask is required and Xen in all others Place in another word passage.

c) Reading a word with zeros in the places where a mask is required and Xen in all others Place in another word passage.

When the data is read into the other group (in this case group B) in all three of the above-mentioned word positions, appear it as a masked version of the data created in step (a). The mask can of course be changed by repeating steps (b and c) be changed. The masked data can be used to query group B and provide match or difference information to be used. On the other hand, with simultaneous excitation of one or more selected word lines in group B the masked data are written in the selected word positions. In this case, of course The unselected word passages are also queried and the selected passages are described.

The associative memory system described above thus comprises two groups of memories connected to one another via bit drivers. Each group can be used as an input register for the other and masked data for writing or writing

109852/1686

Docket UK 969 006

■ - 8 -

deliver questions from the other group.

The system described above can be expanded to form a matrix of groups. Such a matrix is shown in FIG. In this matrix, each word line 3 runs through five groups 5 and each bit line pair _f z. B. the bit lines 4a and 4b by four groups number 5. In this arrangement shown in Fig. 4 with a minimum of detail, the driver 2 of Fig. 1 and then used to select the groups in a column or row, _f are used for a specific operation. This is achieved in the arrangement shown in FIG. 5 by the word gates 6, which connect the word lines 8 within a group to the external word lines 3, and by bit gates 7, which connect the internal bit line pairs 4c and 4d to the external bit line pairs 4a and 4b. The gates 6 are also connected to two control lines W1 and WO, which can be excited to select word information in the group or out of it. The gates 7 are connected to two control lines Dl and DO, which can be excited to select the bit data flow in the group or out of it. FIG. 6 is a block diagram of a bit line gate 7 of FIG. 5. The gate operates with logic circuits of the type shown in FIGS. 3a and 3b and directs the flow of signals into or out of the memory. In addition, the gate takes on the function of decoding data from the group described in connection with FIG. 2.

Fig. 7 is a block diagram of a word line gate 6 (Fig. 5). This gate uses two logic circuits in FIGS. 3a and 3b. It directs the flow of signals between one internal word line 8 on the group and an external word line 3 according to the excitation of either the control line WO or the control line Wl.

Fig. 8 shows the connection of the control lines DO, Dl, WO and -Wl

10 9852/1686

Docket UK 969.006

from the groups of the matrix shown in Fig. 4 to a common clock and control unit. Each control line from a group 5 in a row of the matrix (shown in detail in Figure 8) is connected to a common line for that row. Thus, all DO lines are connected to a common DO number line _f the W1 lines to a common W1 row line, etc. These common lines and the matrix word lines are connected to timing blocks (TCB) 10, one of which is provided for each matrix row. Each TCB 10 is connected to a corresponding clock control block (CCB) 12 via lines 15 which correspond in number to the word lines 3. The TCBs 10 and the CCBs 12 are connected to one another in columns and via the lines C1, C2 and C3 as well as LP1, LP2 and LP3 to the clock circuit 13.

The TCB's 10, CCB's 12 and the clock circuit 13 jointly determine the direction of the data flow between the groups 5 in the matrix. As is well known, this data transfer can be used for reading or writing or searching for selected groups using other groups as registers as shown in FIGS. 1 to 3 to be used.

Subsequently, the TCB's 10, the CCB ¹ s 12 and the clock circuit 13 are described in detail and, afterwards, their mode of operation in connection with the matrix,

9 shows one connected to a TCB 12 via lines 15 TCB 10. Both include groups with multistable cells 1 of the type described in connection with FIG. 1 work * The TCB 9 is arranged so that its word lines through the Group run down and its two bit lines the group pass across. The word lines of the CCB 12 run across the group and its two bit lines connect the cells of one each column with each other.

Circuit 14 connects the word lines from the matrix and

IG 98 S 27 188 6

Docket UK 969 006 SAD ORKUNAL

- ίο - ■

the lines DO, Dl, WO and Wl to the TCB 10. One of these circuits is shown in FIG. The circuit comprises logic circuits of the above in connection with FIGS. 3a and 3b and acts as a lock. The lock is set by signals on the lines BO and B1 with positive inputs and the line 15 is thereby energized. This condition represents a lack of timing on the word line from the groups, together with a TCB setting ^K X ^s:. The interlock is reset by the TCB position Y regardless of the condition on the word line.

The word lines of the TCB 10 are connected to the input lines C1, C2 and C3 ? receive the signals from the clock circuit 13 (Fig. 8).

The output lines 15 from the latches 14 (FIG. 9) are not connected to the memory cells of the TCBs but instead run from the latches to the word lines of the CCb ¹ S 12. Each CCB has no further circuit, with the exception of cells 1 and the corresponding one Word and bit lines. In practice, only the one bit line of each bit line pair is used. Each of these one-bit lines is connected in such a way that the corresponding lines LP1. LP2 and LP3 signals are applied to the clock circuit 13 *

Figure 11 is a block diagram of the clock unit 13. The unit comprises 18 logic circuits of the in FIGS. 3a and 3b Kind of, but all of them only use the D-out connector and some contain only two of the three input ports. The clock is a ring counter and works with regular sequential pulses S1; S2, - S3 and S4 from a master clock (not shown) A special feature of the clock is that each stage can be removed from the ring "", indeir, one has a positive input signal to the input terminal corresponding to this level. The input terminals are shown in FIG. 11 as lines LP1. LP2 and LP3, which are known to contain signals from the one-bit

10 9 8 5 2/1686 _ftAD ORIGINAL

Docket UK 969 006

services of the CCB 12 (Fig. 9) received. Output signals are on the lines labeled Cl, C2 and C3 are applied and represent inputs to the word lines TCB 10.

12 shows pulse shapes of the input and output signals of the clock unit 13. As can be seen from the upper four waveforms, the signals S1 to S4 follow. on each other. The pulse trains Sl and S3 deliver negative running pulses with regular
Distance and the curves S2 and S4 positive running pulses with regular spacing, which are pushed between the pulses S1 and S3.

The pulse shapes ClA, C2A and C3A show the correspondingly generated output signals from the output lines Cl, C2 and C3 (Fig. 11) when all three input terminals LP1, LP2 and LP3 (Fig. 11)
receive negative signals. As can be seen from these pulse shapes, each output line produces a series of output pulses which occur in sequence on a line-by-line basis.

The pulse trains ClB, C2B and C3B represent the derived clock output signals when one of the input terminals receives a positive and the other a negative signal. In the case shown in Fig. ■ the input terminal LP3 is positive and thus the output line C3B does not provide any output pulses due to the input signals S1 to S4. Similarly, none appear
Output pulses from Cl when the input terminal LP1 is positive and no output pulses from C2 when the input terminal LP2
is positive.

Fig. 13 shows two TCB's 10 which have been programmed so that the the bit line pairs corresponding cells were placed in the illustrative state, which the output signals DO, Dl, Wl and WHERE deliver. In this figure, instead of only three word lines in FIGS. 9 and 10 six word lines are shown as well the corresponding output signals from the clock circuit of the Fig. 11. The last-mentioned figures were drawn on the three lines

'■ - ■> ^Λ ^ - - ** 109852/1686

Docket UK 969 006

limited to Cl, C2 and C3, - to simplify the description, however, the timing arrangement can easily be modified so that successive pulses are sent to six output lines instead of appear on three, - with the CCB's modified accordingly to provide six input control signals.

If in the illustration of FIG. 13 it is assumed that the CCB's are not set and do not block an output pulse of the clock unit, so the lines C1 to C6 are energized in sequence.

When Cl is excited. generates the O bit in the upper TCB group an output on line CO. This data output signal is routed to all groups in the corresponding row of the matrix (Fig. 8). The one bit in the upper TCB group generates an output signal on line Wl. This word input signal is applied to all groups in the corresponding line given the matrix. This combination of signals on lines CO and Wl switches the row of groups for a read operation .

Similarly, the respective lines Dl and TtfO are energized by the lower TCB group. This prepares the group-w pen before in the corresponding line for a search operation. Thus, the program contained in this part of the TCB word line Cl can be expressed as follows:

"Read the groups on the top line and use this information to find the groups on the bottom line Row."

The excitation of the TCB word line then changes to line C2. The bit pattern from this line leads to the excitation of the lines Dl and WO of the upper TCB and the Leitxmgen CO and Wl of the lower TCB. This is the reverse of the situation on line C1 and the program can therefore be expressed as follows will:

Docket UK 969 006 109 * 62/1686

Read the groups on the bottom line and use this information to find the groups on the top line. ^B.

The line C3 now receives pulses and the lines DO and Wl the upper group and the lines Cl and Wl of the lower group get excited. As shown above, the top line will be the Group thereby set to a read condition and a write condition is set on the lines Dl and Wl in the lower line. These conditions can be expressed as follows:

"Read the groups on the top line and write the resulting information in the bottom line. "

Next, line C4 is tested. In this case, both the upper and the lower TCB contain the bit pattern 1 _f 0 for energizing the lines Dl and WO. Therefore, both lines of the group are switched for a search operation. This can be expressed as follows.

"'Find the groups in the top and bottom lines using a search argument generated outside of these lines. "

The search argument can of course be generated by a read operation on one or more other lines in the group.

When the line C5 is energized, both output lines DO and Wl of both TCBs are energized , which corresponds to a read operation in both corresponding group lines and can be expressed as follows:

"Read the groups in the top and bottom lines and put the information on other lines and / or as an output from the matrix. "

«AD OfUQlNAL 109852/1686

Docket UK 969 006

Finally, line C6 is energized. The upper group aroused the lines Dl and El, since it contains an egg pattern 1, 1. the lower group contains the egg pattern X, X and therefore does not excite any Output line. This condition can be expressed as follows:

'■ Write on the top line of the group of one Source, do not perform any operation on the bottom line. "

The operations of the TCB's 10 can be summarized as follows: They can be programmed to control the data flow within the matrix of groups 5 (Figs. 4 and 8). By this programming can select reading, writing and searching and also the direction of the data flow within the matrix be determined. Information can be masked using two or more words. This operation can be performed by the TCB program as this determines the number of groups and therefore the number of words that are read at the same time can.

In the above description, the TCB word lines Gl to C6 were supplied with a pulse by the clock unit 13 in turn, each once in a cycle. This sequence shows the control exercised by the various data stored in the cells corresponding to the various lines. In practice, such an order is not normally used and only certain lines of the group C1 to CS are selected during each cycle according to the functions to be carried out with the data in the matrix.

In the operation of the clock unit 13, as explained above certain output lines are skipped in one cycle. The lines to be dropped are indicated by signals to the Input terminals LP (Figs. 9 and 13) selected. These signals are transmitted from the one-bit lines of the CCB groups 12 (FIGS

/ ** '"" "■■ 109852/1686

Docket UK 969 006

9) derived.

From Fig. 9 it can be seen that the inputs to the word lines of the CCB's are provided by the latches 14 in the TCE's IO will. These interlock circuits (see also Fig. 10} are corresponding to the signals from the groups in the matrix via the word lines 3 and the bit lines of the cells of the TCB's 10 set or postponed. Although only three columns of cells are shown in the CCB of Figure 9, there may of course be more than one be. In the arrangement described in connection with FIG. 13, where the clock unit provided six output signals, e.g. B. six LP ports are provided which would require six columns in the CCB's.

The cells in the CCB's can be programmed to determine which LP line is energized when one of lines 15 (Fig. 9) is energized. This programming is done by offsetting of the cells in the X state or the ones state. An X state means that the corresponding LP line is set to the positive state and no output signals from the corresponding Clock output supplies. If a CCB is in one's state stands, - the corresponding LP line switches the associated Cycle level like this. that this provides output signals, this case only occurs, of course. when the word line to the CCB cell is over line 15 is energized. Fig. 9 shows that lines 15 are energized by latch circuits 14, apart from of the lines which are connected to the lines Dl ,. DO, Wl and VJO connected are. Each interlock is activated to provide an output signal on line 15 by a positive signal the corresponding word line 3 and the two corresponding TCB bit lines are set. This corresponds to a difference signal on the word line and an X signal from the bit lines. Each interlock is activated by its associated upon receipt of a Y signal TCB lines reset regardless of the condition of the associated word line. Din read signal · is from each lock as long as via the associated line 15 to the CCB

109852/168 6

Docket ÜK 969 006

Practicing how the lock is on "match" or with others Words is deferred.

Thus, by programming the CCB and using it Program under control of the difference signals from the Matrix together with the program in the top 5 lines of the TCB's the operations to be performed sequentially on the data in the group steer. For most routines where the operations are read / find followed by find / read and this operation is then repeated, would.ein CCB program z. B. how look like this:

1 1 X X X X (assuming a six bit word is used).

This means that only the PCB inputs C1 and C2 are energized in this cycle.

When a write operation is to be performed, a second CCB word and the mismatched in turn can be chosen for a cycle. That word would look like this:

XXlXXX

This means, of course _r word that only the input C3 is energized the TCB for this cycle, which corresponds, as shown in Fig. 13 a write operation.

⁴ ^ "" 10-985-2 / 1686

Docket UK 969 006

Claims (1)

P A T ENTANSP R ti C H E Associative memory system in which several individual associative memories are connected for performing logical and arithmetic operations, characterized in that that several associative memory groups or levels (A and B) are linked so that each group or level serves as a storage register or its content as a search word for the others and that several at the same time selected words from a memory group form a common output word, of which only a part takes effect by masking it as an argument for another storage group or storage groups. Associative memory system according to Claim 1, characterized in that each memory group (A and B) consists of multistable memory cells (1), each with a word line (3) and two bit lines (4a and 4b) are connected. 3. Associative memory according to claims 1 and 2, characterized in that the bit lines (4a and 4b) both the one storage group (A) as. also the other memory group (B) with each other through driver circuits (2) are connected. 4. Associative memory system according to claims 1 to 3, characterized in that one of a memory group (e.g. A) read out word is read simultaneously with a mask that masks the bits within the word, which are forwarded as a search term for another storage group (e.g. B). 5. Associative storage system according to Claims 1 to A ₁ . characterized in that word lines (8) within 10 9852/168 6 Docket UK 969 006 a memory group (ζ. B. 5) are connected to the external word lines (3) via word gate circuits (6) and the internal bit line pairs (e.g. 4c and 4d) with the external bit line pairs (4a and 4b) via bit gates (7) are connected, the word gate circuits (6) being connected to control lines (Wl and WO) are, which are used to select words and that the bit gate circuits (7) with two control lines (Dl and DO), which are used to select the bits within a word in the memory group. 6 »Storage system according to claims 1 to 5, characterized in that that the control lines (Dl, DO and Wl or WO) on a common clock and control unit (CCB 10) and (CCB 12) are connected. 7. Associative memory system according to claims 1 to 6, characterized in that the input signals to the word lines of the clock control circuit (CCB) are supplied by locking circuits (14) of the timing control circuit (TCB), which in turn are supplied by signals from the groups in the matrix via the word lines ( 3) and the bit W lines of the memory cells are controlled. 10 9852/1686
Docket UK 969, 006 A3 L. blank