Associative memory

• US 5,325,501 A
• Filed: 08/02/1991
• Issued: 06/28/1994
• Est. Priority Date: 08/02/1990
• Status: Expired due to Fees

• Current Assignee: Carlstedt Elektronik Ab
• Original Assignee: Carlstedt Elektronik Ab
• Inventors: Carlstedt, L. Gunnar
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): Nguyen, Hiep T.
• Application Number:
  US07/739,541
• Time in Patent Office: 1,061 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/400, 395/425, 365/49
• US Class Current: 365/49.18
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G11C 11/419 Read-write [R-W] circuits
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

An associative memory is provided having a first control bus arrangement (any type, Vr, cpb, set.s, match, r/w.s, r/w.b, r/w.r, Wand.a, Wand.b, Wor, s.a, reset.b, mode.a mode.a*, prech, ba, mode.b, grant.b, prio etc) for external control and a second memory bus arrangement (t1, t2, id, anv, v0, v1, v2, v3) for data. The memory includes several storage cells (1) for storing a composed information. Each storage cell stores at least one mark, which indicates at least select state(s) or non select state(s) for said storage cell. The mark(s) are set by search operations among said cells. A priority decoder (2) is provided to which all said storage cells are coupled and which selects one out of several of said storage cells. At least one global bus (4, 5) is provided for making logical operations of the type AND and OR between said storage cells. A closure head (11) is provided in each storage cell for communicating with said buses and to control said storage cell to take part in an actual logical operation. Each storage cell includes a number of data object storage fields (IDENTITY, ENVIRONMENT, VALUE/DES.₀, VALUE/DES.₁, VALUE/DES.₂, VALUE/DES.₃), which are able to store a data word and at least one of said marks, being in form of tags.

Claims

1. An associative memory having a first control bus arrangement (any_-- type, Vr, cpb, set.s, match, r/w.s, r/w.b, r/w.r, Wand.a, Wand.b, Wor, s.a, reset.b, mode.a mode.a*, prech, ba, mode.b, grant.b, prio etc) for external control, a second memory bus arrangement (t1, t2, id, env, v0, v1, v2, v3) for data comprising:

several storage cells (1) connected to said memory bus arrangement for storing a composed information, all of said storage cells being simultaneously controllable by said control bus arrangement in accordance with an operation to be performed, means (LAZY,

     8) in each of said storage cells for storing at least one mark, said mark(s) indicating at least select state(s) or non select state(s) for said storage cell,

means internal to the associative memory for making search operations through the memory bus among said cells to set at least one mark, and

means (11) in each storage cell for communicating with said buses and to control said storage cells to take part in an actual logical operation by setting a priority request state for said storage cells when said operation requests selection, said priority request state being based on said mark(s) in said means (8) in each of said storage cells, and

a priority decoder (2) to which all said storage cells are coupled which selects one out of several of said storage cells by reading said priority request state from the means (11) setting said priority request state in all storage cells and simultaneously returning an individual signal to each storage cell in the memory indicating said select of non select state(s).

2. A memory according to claim 1, further comprising at least one global bus (4, 5) connected to each said storage cell for making logical operations of a type AND and OR between said storage cells.

3. A memory according to claim 1, wherein each storage cell includes at least one state storage field indicating a state or states of a content in said storage cell.

4. A memory according to claim 1, wherein said storage cells are connected to a combinational central control unit through said control bus arrangement which is distributed to all said storage cells, data words being able to be transferred into or out of said memory on said memory bus arrangement by a composed information provided on said control bus arrangement.

5. A memory according to claim 1, wherein said storage cell includes a number of data object storage fields (IDENTITY, ENVIRONMENT, VALUE/DES.₀, VALUE/DES.₁, VALUE/DES.₂, VALUE/DES.₃), each data object storage field being able to store a data word and at least one of said marks, being in form of tags.

6. A memory according to claim 5, further comprising at least one second bus (a, b) is provided for said storage fields (6) in each said storage cell in order to make logical operations of the type WIRED AND and WIRED OR between said storage fields, and said priority decoder (2), each of said storage fields being able to read said buses and to take part in an actual logical operation.

7. A memory according to claim 3, wherein each said storage field includes a control element head (8) storing said marks, being in form of tags, and a number of bit cells in which the bits of said data word are stored, each cell being connected to each other and to said head.

8. A memory according to claim 7, wherein said bit cells are controllable from said element head (8) to perform one of the following operations at a time

rest in which each said bit cell keeps a stored bit value stored,

read in which stored bit values in said bit cells are read,

write in which bit values are written in said bit cells,

compare in which a data word composed by bit values stored in said bit cells is compared with another data word.

9. A memory according to claim 8, wherein said control from said element head (8) is dependent on logical conditions each being a function of data on said second buses (a, b), earlier mark(s) being in form of tag(s), the result of said comparison in case of said comparison operation and a control signal from said central control unit to said memory.

10. A memory according to claim 8, wherein said mark(s) being in form of tag(s) is settable in dependence on logical conditions each being a function of data on said second buses (a, b), earlier mark(s) being in form of tag(s), the result of said comparison in case of said comparison operation and a control signal from said central control unit to said memory.

11. A memory according to claim 7, wherein a first wire (acc) connected to said element head (8) interconnects all said bit cells within a storage field (6) and wherein all said bit cells are controlled by signals on said wire, and wherein other wires (d, d*) connected to said bit cells are connected to corresponding bit cells in the other storage cells in said memory.

12. A memory according to claim 1, wherein said priority decoder (2) is a combinational circuit and includes one section for each storage cell, each section having a first connection for REQUEST, on which a bit value `true` represents NEED and a bit value `false` NO NEED, and a second connection for grant, on which a bit value `true` represents CHOSEN and `false` NOT CHOSEN.

13. A memory according to claim 1, wherein a search is made by making a comparison of said mark(s), being in form of tag(s), by control of said element head (8) and to get the result FIT or DIFFERENT, and wherein the search is made in one of the following ways:

(1) searching each storage field (6) individually and independently of the composed information in other storage fields,

(2) searching using a comparison to selected storage fields (6) in a storage cell, the result being FIT in every selected storage field, and

(3) searching using a comparison to selected storage fields (6) in a storage cell, the result being FIT in at least one of the selected storage fields.

14. A memory according to claim 13, wherein a comparison is made in one of the following ways:

(1) comparing two bit patterns, which comparison results in FIT only when all corresponding bits are alike, and

(2) coding the two bit patterns to be compared or only one of them such that at least one of the bits states that the bit pattern information corresponds to an ARBITRARY and a SPECIFIC information value v, if, at a comparison, one of the information values corresponds to ARBITRARY then the result is FIT, otherwise the result is FIT only when the two specific information values v are identical.

15. A memory according to claim 1 including bit cells, all of said bit cells being able to store a bit value, said value being either `true` or `false`, said cell including:

a first connection (Vcc) which is constantly provided with a supply voltage,

a second, a third and a fourth connection (acc, d, d*) each of which is settable in different control states;

said cell circuit being such that each combination of said control states on said second, third and fourth connection is setting said memory bit cell in an individual among a set of functional states.

16. A memory according to claim 15, wherein said control states are high level, low level, no current into cell, current into cell for all said second, third and fourth wires and also current out of cell for at least one of said wires.

17. A memory according to claim 16, wherein said second wire is an access wire (acc) and said third and fourth wires (d, d*) having signals inverted relative to each other when writing or reading said cells.

18. A memory according to claim 17, wherein, between said second wire (acc) and said first wire (V_cc), a first and a second series connection are provided in parallel, each including the source/drain path of a transistor and a load (T1,L1 and T2, L2), the interconnection between said load and the drain of said transistor in said first series connection being said first node (n1) and being connected to the gate of said transistor in said second series connection and the drain of said transistor in said second series connection being connected to the gate of the transistor in said first series connection, wherein a first rectifying element (D1) is connected between said third wire (d) and said first node permitting current to flow only in one direction relative to said third wire and a second rectifying element (D2) is connected between said fourth wire (d*) and said second node (n2) permitting current to flow only in one direction relative to said fourth wire.

19. A memory according to claim 18, wherein said rectifying elements (D1 and D2) are chosen among the following components:

(1) n-channel MOS FET in which the drain and the gate are interconnected (positive voltages),

(2) p-channel MOS FET in which the drain and the gate are interconnected (negative voltages),

(3) pn-diode (positive voltages, negative voltages with the diode reversed),

(4) Schottky-diode (positive voltages, negative voltages with the diode reversed.

20. A memory according to claim 18, wherein said transistor (T1 and T2) are chosen among the following components:

(1) n-channel MOS FET (positive voltages),

(2) p-channel MOS FET (negative voltages),

(3) npn bipolar transistor (positive voltages),

(4) pnp bipolar transistor (negative voltages).

21. A memory according to claim 18, wherein said loads (L1 and L2) are chosen among the following components:

(1) a resistor,

(2) n-channel enhancement type MOS FET having its drain and gate interconnected (positive voltages),

(3) p-channel enhancement type MOS FET having its drain and gate interconnected (negative voltages),

(4) n-channel depletion type MOS FET having its source and gate interconnected (positive voltages),

(5) p-channel depletion type MOS FET having its source and gate interconnected (negative voltages),

(6) n-channel MOS FET having its gate as a control electrode and the source and the drain as drive connections (positive voltages),

(7) p-channel MOS FET having its gate as a control electrode and the source and the drain as drive connections (negative voltages),

(8) pnp bipolar transistor having the base as the control electrode and the emitter and collector as drive connections (positive voltages),

(9) npn bipolar transistor having the base as the control electrode and the emitter and collector as drive connections (negative voltages).

22. A memory according to claim 15, in which a bit value is storable, said value being either `true` or `false`, wherein the following functional states are settable by said control states:

rest in which said cell is just storing said bit value,

read in which said bit value can be read,

don'"'"'t read in which said cell is just storing said bit value,

write false in which said stored bit value is set to `false`,

write true in which said stored bit value is set to `true`,

don'"'"'t write in which said cell is just storing said bit value,

comp. false in which said stored bit value is compared to a value `false`,

comp. true in which said stored bit value is compared to a value `true`,

don'"'"'t comp. in which said cell is just storing said bit value.

23. A memory according to claim 15, wherein said bit cells contain a flip-flop controlable from each side via said third and fourth wires (d, d*), wherein said flip-flop has a first and a second node settable on essentially a first and a second voltage level, and wherein said flip-flop has its supply voltage between said first (Vcc) and second wires (acc), said second wire being controllable to different voltage levels.