US 5,491,803 AGranted

Response resolver for associative memories and parallel processors

AssigneeMassachusetts Institute of Technology

InventorsFrederick P. Herrmann, Charles G. Sodini

Life of this patent

Estimating the term…

Loading patent…

Abstract

A logic circuit for a content-addressable-memory or parallel-processor array cell implements both prioritizing and counting functions for response resolution. It includes a means for receiving from a prior cell a response-resolution token and a means for receiving the positive or negative response of the current cell to a pattern to be matched. It also includes a means for deriving as a function of the prior cell's response-resolution token a response-resolution token for the current cell that implements prioritization and counting response-resolution functions for positive or negative pattern-matching responses of the current cell. Finally, it includes a means for selecting for the current cell the appropriate response-resolution token based on the cell's positive or negative pattern-matching response and a means for sending that response-resolution token to a subsequent cell. In a preferred embodiment of the invention, the means for selecting the current cell's response-resolution token for a positive or negative pattern-matching response uses a simple pass-transistor switching circuit.

Claims19

Dependent claims

A logic circuit for both prioritizing and counting responses from a plurality of cells of an array comprising:

a means for generating a first token in an initial state;
a plurality of stages wherein each stage is associated with one cell of the plurality of cells and each stage comprises
a) a first input for receiving an input token, wherein possible states of the input token include an initial state, a first toggle state, and a second toggle state,
b) a second input for receiving a response from the said cell associated with said stage,
c) a first output for sending an output token, wherein possible states of the output token include the initial state, the first toggle state, and the second toggle state,
d) a second output for sending the input token, and
e) logic means for determining the state of the output token wherein the state of the output token is the same as the state of the input token if the response from the associated cell is negative, the state of the output token may be either the first toggle state or the second toggle state if the response from the associated cell is positive and the input token is in the initial state, the state of the output token is the first toggle state if the response from the associated cell is positive and the input token is in the second toggle state, and the state of the output token is the second toggle state if the response from the associated cell is positive and the input token is in the first toggle state;
means for connecting the means for generating the first token to the first input of a first stage;
and
means for connecting the first output of each stage except for a last stage to the first input of a next stage, whereby a chain of stages is formed and
whereby the responses from the plurality of cells may be prioritized and counted based on the second output of each stage and the first output of the last stage.

8 more elements

Dependencies are inferred from the claim text.