Priority encoder circuit and method

Details Priority encoder circuit and method Priority encoder circuit and method

2001-09-18

2004-02-17

Robertson, David L. (Department: 2186)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189080, C341S050000, C340S870030

Reexamination Certificate

active

06693814

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to content addressable memory (CAM). In particular, the present invention relates to a priority encoder and method for high speed encoding of input data signals into addresses in accordance with predetermined priorities.
BACKGROUND OF THE INVENTION
In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM's most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not.
A typical CAM block diagram is shown in FIG.
1
. The CAM
10
includes a matrix, or array
100
, of CAM cells (not shown) arranged in rows and columns. For a ternary CAM, the cells are typically either DRAM or SRAM type, and store one of three states: logic “1”, logic “0” and “don't care”, as two bits of data. An array of DRAM based ternary CAM cells, as described in Canadian Patent Application No. 2,266,062, filed Mar. 31, 1999, the contents of which are incorporated herein by reference, have the advantage of occupying significantly less silicon area than their SRAM based counterparts. The description of the operation of the ternary DRAM cell is detailed in the aforementioned reference. A predetermined number of CAM cells in a row store a word of data. An address decoder
12
is used to select any row within the CAM array
100
to allow data to be written into or read out of the selected row. Although most commonly, data is written or loaded into the CAM and searched. Data access circuitry such as bitlines and column selection devices, are located within the array
100
to transfer data into and out of the array
100
. Located within CAM array
100
for each row of CAM cells are matchline sense circuits (not shown) used for search-and-compare operations. The various registers
15
receive and hold data from the data I/O block
20
for search-and-compare operations, and other components of the CAM include the control circuit block
14
, the flag logic block
16
, the voltage supply generation block
18
, various control and address registers
22
, refresh counter
28
and JTAG block
24
.
The matchline sense circuits are used during search-and-compare operations for outputting a result indicating a successful or unsuccessful match of a search word against the stored word in the row. The results for all rows are processed by the priority encoder
200
to output the address (Match Address) corresponding to the location of a matched word. The match address is stored in match address registers
25
before being output by the match address output block
26
. The generation of the match address is relatively simple when there is only one stored word which matches the search word. However, when there are many stored words matching the search word, the priority encoder is still limited to provide only one match address. Hence, a rule is applied in which only the highest priority matching word is accepted, and all lesser priority matching words are ignored. Within the context of CAM's, the highest priority matching word is located at the lowest physical address in the CAM array and accordingly, the lowest priority matching word is located at the highest physical address in the CAM array. For example, if two words located at binary address 0001 and 1001 match the search word, the word stored at binary address 0001 would have the highest priority. In general, the priority encoder
200
of the CAM is responsible for determining the highest priority matching word among many matching words, and generating the address corresponding to the highest priority matching word.
A more detailed block diagram of a typical priority encoder
200
is shown in FIG.
2
. The priority encoder includes a mutliple match resolver block
204
and a ROM address decoder block
206
for generating an 8-bit address. Multiplexors
202
receive matchline sense output signals ML_OUT
0
to ML_OUT
255
from the matchline sense circuits, and an empty data signal EMPTY
0
to EMPTY
255
. A common control signal SELECT EMPTY connected to each multiplexor
202
selects empty data for input to the multiple match resolver block
204
when active. However, for the purposes of the following discussion, it is assumed that SELECT EMPTY is inactive, and only the matchline sense output signals are passed to the multiple match resolver block
204
. For each input of the multiple match resolver block
204
, there is exactly one corresponding output
208
supplied to ROM decoder block
206
. In general operation, when multiple match resolver block
204
receives one or more active ML_OUT signals, ie. when a match between the stored word in the CAM and search word occurs, multiple match resolver block
204
determines which stored word has the highest priority and activates the corresponding output signal
208
. ROM block
206
then generates an 8-bit address corresponding to the active output signal
208
. Although the input signals are arranged in sequential order, it is the logical order assigned to the physical connection of the signal within multiple match resolver block
204
which is significant. In other words, if it is understood that ML_OUT
0
is the highest priority location and ML_OUT
255
is the lowest priority location, then the ML_OUT inputs could be connected in any order as long as the internal connections within multiple match resolver block
204
are correspondingly assigned according to their logical priority.
A disadvantage with the scheme shown in
FIG. 2
is the long duration of time required to produce the match address after the matchline sense output signals are presented to the multiple match resolver block
204
. The delay in receiving the match address is approximately 12 ns, a significant amount of time which delays subsequent CAM operations. Most of this delay is contributed by the memory access operation of the ROM.
It is therefore desirable to provide a searchline control circuit capable of operating at high speed to improve CAM performance.
SUMMARY OF THE INVENTION
It is an object of the present invention to obviate or mitigate at least one disadvantage of the prior art. In particular, it is an object of the present invention to provide a high speed priority encoder circuit, a method of using such a circuit, and a content addressable memory using such a priority encoding circuit, that generates highest priority match addresses quickly.
In a first aspect, the present invention provides a priority encoder for generating an address of a highest priority active data signal. The priority encoder has a first stage for receiving a plurality of active data signals, and generates at least one flag signal and at least one first add

Affiliated with

Also associated with

Rating

Priority encoder circuit and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Priority encoder circuit and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority encoder circuit and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3331746