Hit ahead hierarchical scalable priority encoding logic and circuits

• US RE45,259 E1
• Filed: 01/20/2012
• Issued: 11/25/2014
• Est. Priority Date: 03/04/2004
• Status: Expired due to Fees

• Current Assignee: Xiaohua Huang
• Original Assignee: Xiaohua Huang
• Inventors: Huang, Xiaohua
• Primary Examiner(s): Yang, Han
• Application Number:
  US13/355,449
• Time in Patent Office: 1,040 Days
• Field of Search: 365/49.1, 365/230.01, 365/230.05, 365/230.06
• US Class Current: 365/49.1
• CPC Class Codes: G06F 7/74 Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders with shifting G06F5/01
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

In this invention a hit ahead multi-level hierarchical scalable priority encoding logic and circuits are disclosed. The advantage of hierarchical priority encoding is to improve the speed and simplify the circuit implementation and make circuit design flexible and scalable. To reduce the time of waiting for previous level priority encoding result, hit signal is generated first in each level to participate next level priority encoding, and it is called Hit Ahead Priority Encoding (HAPE) encoding. The hierarchical priority encoding can be applied to the scalable architecture among the different sub-blocks and can also be applied with in one sub-block. The priority encoding and hit are processed completely parallel without correlation, and the priority encoding, hit generation, address encoding and MUX selection of the address to next level all share same structure of circuits.

Claims

1. A content address able memory(CAM) and hit ahead priority encoding(HAPE) logic, comprising:

a group of blocks which is arranged in column and row, each block has equal number of CAM match signals which are the input signals of priority encoding logic, each block has same priority encoding logic of CAM match signals within the block, the CAM match signals or input signals are arranged from lower priority to higher priority or from higher priority to lower priority, each CAM match signals or input signal has either high logic level “

one”

which is called hit or low logic level “

zero”

which is called miss, each block generates block hit when there is at least one CAM match signal is high logic “

one”

within the block or block miss signal when all the CAM match signals are in low logic level “

zero”

within the block and block binary address signal corresponding to the CAM match signals of highest priority within the block, a priority encoding logic of block hit or miss signals of each column, each column generates a column hit signal when there is at least one block hit signal within the column or column miss signal when there is only block miss signals within the column and column binary address corresponding to the CAM match signals of highest priority within the column, a priority encoding logic of column hit or miss signals of a group column, a group of column generates a hit signal when there is at least one column hit signal within the group column or a miss signal when there is only column miss signals within the group column and a group column binary address corresponding to the CAM match signals of highest priority within the group column.

2. A content address able memory(CAM) and hit ahead priority encoding(HAPE) logic of claim 1, further comprising:

a block multiplexer to select the binary address from the block of highest priority hit within the column as less significant portion of the column binary address; and

a priority encoding logic of block hit signals to generate the block multiplexer control signal which select the block of highest priority hit within the column, and a binary address encoding logic of block hit signals to generate the more significant portion of the column highest priority binary address.

3. A content address able memory(CAM) and hit ahead priority encoding(HAPE) logic of claim 1, wherein each block comprises:

a group of sub-blocks, each sub-block has equal number of input signals, each sub-block has priority encoding and binary address encoding logic to generate sub-block highest priority binary address as well as hit or miss generating logic to generate sub-block hit or miss signal, and the sub-block hit or miss signal is generated independently before sub-block binary address;

a block hit or miss generating logic to generate block hit or miss signal and block hit or miss signal is generated independently before the block binary address is generated;

a sub-block multiplexer to select the binary address from the highest priority sub-block within the block as less significant portion of block binary address; and

a priority encoding logic of each sub-block hit signals to generate the control signal of sub-block multiplexer, and a binary address encoding logic of each sub-block hit signals to generate the more significant portion of block binary address.

4. A content addressable memory(CAM) and hit ahead priority encoding(HAPE) logic of claim 3, wherein priority encoding logic, address encoding logic and multiplexer have the logic circuit of same structure.

5. A content address able memory(CAM) and hit ahead priority encoding(HAPE) logic of claim 4, wherein the hit generating logic, priority encoding logic, address encoding logic and multiplexer have dynamic NOR logic.

6. A content address able memory(CAM) and hit ahead priority encoding(HAPE) logic of claim 2, wherein the signal of controlling the multiplexer is generated before or in the same time that the less significant portion of the highest priority local address is generated.

7. A content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic, comprising:

a group of blocks which are arranged in columns and rows, each block having an equal number of CAM match signals which are the input signals of priority encoding logic, each block having a same priority encoding logic of CAM match signals within the block, the CAM match signals or input signals arranged from lower priority to higher priority or from higher priority to lower priority, each CAM match signal or input signal being either a high logic level “

one which is called hit or a low logic level “

zero”

which is called miss, each block configured to generate a block hit signal when there is at least one CAM match signal that is a high logic level “

one”

within the block or a block miss signal when all the CAM match signals are a low logic level “

zero”

within the block and a block binary address signal corresponding to the CAM match signals of highest priority within the block;

a priority encoding logic of block hit or miss signals of each column, each column configured to generate a column hit signal when there is at least one block hit signal within the column or a column miss signal when there are only block miss signals within the column and a column binary address corresponding to the CAM match signals of highest priority within the column; and

a priority encoding logic of column hit or miss signals of a group column, the group column configured to generate a hit signal when there is at least one column hit signal within the group column or a miss signal when there are only column miss signals within the group column and a group column binary address corresponding to the CAM match signals of highest priority within the group column.

8. The content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic of claim 7, further comprising:

a block multiplexer configured to select a binary address from the block having the highest priority hit within the column as a less significant portion of the column binary address,

the priority encoding logic of block hit signals being configured to generate a block multiplexer control signal for selecting the block having the highest priority hit within the column; and

a binary address encoding logic of block hit signals configured to generate a more significant portion of the column binary address.

9. The content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic of claim 7, wherein each block comprises:

a group of sub-blocks, each sub-block having an equal number of input signals, each sub-block having priority encoding and binary address encoding logic configured to generate a sub-block highest priority binary address as well as hit or miss generating logic configured to generate a sub-block hit or miss signal, the sub-block hit or miss signal being generated independently before the sub-block binary address;

a block hit or miss generating logic configured to generate a block hit or miss signal, the block hit or miss signal being generated independently before the block binary address is generated;

a sub-block multiplexer configured to select a binary address from a highest priority sub-block within the block as a less significant portion of the block binary address; and

a priority encoding logic of each sub-block hit signals configured to generate a control signal of the sub-block multiplexer; and

a binary address encoding logic of the sub-block hit signals configured to generate a more significant portion of the block binary address.

10. The content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic of claim 9, wherein the priority encoding logic, the address encoding logic, and the multiplexer have logic circuitry of the same structure.

11. The content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic of claim 10, wherein the hit generating logic, the priority encoding logic, the address encoding logic, and the multiplexer have dynamic NOR logic.

12. The content addressable memory (CAM) and hit ahead priority encoding (HAPE) logic of claim 8, wherein a signal for controlling the multiplexer is generated before or at the same time that the less significant portion of the highest priority local address is generated.

13. A content addressable memory (CAM) system, comprising:

one or more columns comprising a plurality of circuit segments, at least one of the circuit segments configured to generate a first circuit segment output based on whether at least one of a plurality of circuit segment inputs received by the at least one of the circuit segments corresponds to a first logic level,

at least one of the one or more columns configured to generate first address information based on a selected one of the first circuit segment outputs that corresponds to a second logic level, to set a node to a third logic level in response to a first input signal, and to subsequently change the node to a fourth logic level in response to one or more of a plurality of second input signals.

14. The CAM system of claim 13, wherein the first circuit segment output represents circuit segment hit information.

15. The CAM system of claim 13, wherein the at least one of the plurality of circuit segment inputs represents match information.

16. The CAM system of claim 13, wherein the selected one of the first circuit segment outputs is a highest priority one of the first circuit segment outputs that corresponds to the second logic level.

17. The CAM system of claim 13, wherein:

the one or more columns are a plurality of columns, and

the plurality of circuit segments are arranged in the plurality of columns and a plurality of rows.

18. The CAM system of claim 13, wherein:

the one or more columns are a group of columns;

each column in the group configured to generate a column output based on the first circuit segment output of the at least one of the circuit segments; and

the group configured to generate second address information based on a selected one of the column outputs that corresponds to a fifth logic level.

19. The CAM system of claim 13, wherein:

the at least one of the one or more columns is configured to pre-charge the node in response to the first input signal; and

the at least one of the one or more columns is configured to subsequently discharge the node in response to the one or more of the plurality of second input signals.

20. The CAM system of claim 13, wherein the first input signal is configurable independently of the one or more of the plurality of second input signals.

21. The CAM system of claim 13, wherein the first logic level and the second logic level are the same logic level.

22. The CAM system of claim 13, wherein the one or more columns comprise:

a first logic circuit configured to generate a first logic circuit output based on the selected one of the first circuit segment outputs that corresponds to the second logic level;

a second logic circuit configured to generate a second logic circuit output based on whether the first circuit segment output corresponds to the second logic level; and

a third logic circuit configured to generate the first address information based on the selected one of the first circuit segment outputs that corresponds to the second logic level.

23. The CAM system of claim 22, wherein at least one of the first logic circuit, the second logic circuit, and the third logic circuit is configured to set the node to the third logic level in response to the first input signal, and to subsequently change the node to the fourth logic level in response to the one or more of the plurality of second input signals.

24. The CAM system of claim 22, wherein:

the at least one of the circuit segments is configured to generate a second circuit segment output representing second address information; and

the one or more columns further comprise;

a fourth logic circuit configured to select one of the second circuit segment outputs as a less significant portion of the first address information; and

a fifth logic circuit configured to generate a more significant portion of the first address information.

25. The CAM system of claim 24, wherein at least one of the fourth logic circuit and the fifth logic circuit is configured to set the node to the third logic level in response to the first input signal, and to subsequently change the node to the fourth logic level in response to the one or more of the plurality of second input signals.

26. The content addressable memory (CAM) system of claim 24, wherein the one or more columns are each configured to generate a control input for the third logic circuit before or at the same time when the second circuit segment output is generated.

27. The content addressable memory (CAM) system of claim 22, wherein:

the plurality of circuit segment inputs is divided into a plurality of subsets of the circuit segment inputs; and

the first logic circuit comprises;

a plurality of fourth logic circuits each configured to generate a fourth logic circuit output based on whether at least one of a corresponding subset of the circuit segment inputs corresponds to the first logic level; and

a fifth logic circuit configured to generate the first circuit segment output based on whether at least one of the fourth logic circuit outputs corresponds to the first logic level.

28. The CAM system of claim 27, wherein:

at least one of the fourth logic circuit and the fifth logic circuit is configured to set the node to the third logic level in response to the first input signal, and to subsequently change the node to the fourth logic level in response to the one or more of the plurality of second input signals; and

the fourth logic circuit output is an input to the fifth logic circuit.

29. A content addressable memory (CAM) system, comprising:

a circuit segment configured to generate a circuit segment output based on whether at least one of a plurality of circuit segment inputs received by the circuit segment corresponds to a first logic level,

the circuit segment configured to set a node to a second logic level in response to an input signal, and to subsequently change the node to a third logic level in response to the plurality of circuit segment inputs,

the circuit segment output corresponding to said third logic level.

30. The CAM system of claim 29, wherein at least one of the plurality of circuit segment inputs corresponds to a match line output.

31. The CAM system of claim 29, wherein the circuit segment output represents circuit segment hit information.

32. The CAM system of claim 29, wherein at least one of the plurality of circuit segment inputs represents match information.

33. The CAM system of claim 29, wherein:

the circuit segment is configured to pre-charge the node in response to the input signal; and

the circuit segment is configured to subsequently discharge the node in response to the plurality of circuit segment inputs.

34. The CAM system of claim 29, wherein the input signal is configurable independently of the plurality of circuit segment inputs.

35. The CAM system of claim 29, wherein the first logic level and the third logic level are the same logic level.

36. The CAM system of claim 29, wherein the circuit segment is a first circuit segment, and further comprising a second circuit segment configured to generate address information based on the circuit segment output.