Method and apparatus for selecting a most signficant priority number for a device using a partitioned priority index table

• US 7,110,408 B1
• Filed: 03/24/2001
• Issued: 09/19/2006
• Est. Priority Date: 09/23/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Davis, Cynthia L.
• Application Number:
  US09/815,921
• Time in Patent Office: 2,005 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: G11C 8/04 using a sequential addressing device, e.g. shift register, counter
• CPC Class Codes: H03K 23/56 Reversible counters H03K23/52 and H03K23/548 take precedence
• CPC Class Codes: H03K 3/356139 with synchronous operation

Abstract

A digital signal processor. The digital signal processor includes a content addressable memory (CAM) array for storing entries. The digital signal processor includes a partitioned priority index table having a plurality of rows and columns of priority blocks. Each row of the plurality of rows of priority blocks is capable of storing a priority number associated with an entry in the CAM array. Each column of the plurality of columns of priority blocks has compare logic coupled to each of the priority blocks in its respective column. The digital signal processor includes an encoder coupled to the partitioned priority index table.

Claims

1. A digital signal processor, comprising:

a content addressable memory (CAM) array for storing entries;

a partitioned priority index table having a plurality of rows and columns of priority blocks, the priority blocks of each row for storing a respective portion of a priority number associated with an entry in the CAM array and each column having compare logic coupled to each of the priority blocks in its respective column; and

an encoder coupled to the partitioned priority index table.

2. The digital signal processor of claim 1, wherein the encoder determines an index in the CAM array from among entries that match input data and have a most significant priority number.

3. The digital signal processor of claim 1, wherein the entries comprise policy statements and the priority numbers indicate the relative priority of policy statements.

4. The digital signal processor of claim 1, wherein the entries comprise Internet Protocol addresses and the priority numbers comprise prefix mask data for the Internet Protocol addresses.

5. The digital signal processor of claim 1, wherein the partitioned priority index table comprises:

a first row of priority blocks for storing a first plurality of priority numbers having bits in each of the priority blocks in the first row;

a second row of priority blocks that stores a second plurality of priority numbers having bits in each of the priority blocks in the second row;

a first compare logic circuit that determines a most significant block priority number (MSBPN) for a first column of priority blocks from a first block priority number (BPN) from a first priority block in the first row and a BPN from a second priority block in the second row; and

a second compare logic circuit that determines a MSBPN for a second column of priority blocks from a BPN from a third priority block in the first row and a BPN from a fourth priority block in the second row.

6. The digital signal processor of claim 5, wherein the first compare logic circuit comprises:

a first stage comparator that compares the BPNs from the first and second priority blocks to determine the MSBPN for the first column;

a first second stage comparator that compares the MSBPN for the first column with the BPN from the first priority block to determine whether the MSBPN for the first column matches the BPN of the first priority block; and

a second second stage comparator that compares the MSBPN for the first column with the BPN from the second priority block to determine whether the MSBPN for the first column matches the BPN of the second priority block.

7. A partitioned priority index table, comprising:

a first row of priority blocks for storing a first plurality of priority numbers, each priority number from the first plurality of priority numbers having bits distributed within at least two of the priority blocks in the first row;

a second row of priority blocks that stores a second plurality of priority numbers, each priority number from the second plurality of priority numbers having bits distributed within at least two of the priority blocks in the second row;

a first compare logic circuit that determines a most significant block priority number (MSBPN) for a first column of priority blocks from a first block priority number (BPN) from a first priority block in the first row and a BPN from a second priority block in the second row; and

a second compare logic circuit that determines a MSBPN for a second column of priority blocks from a BPN from a third priority block in the first row and a BPN from a fourth priority block in the second row.

8. The partitioned priority index table of claim 7, wherein the first compare logic circuit comprises:

a first stage comparator that compares the BPNs from the first and second priority blocks to determine the MSBPN for the first column; and

a first second stage comparator that compares the MSBPN for the first column with the BPN from the first priority block to determine whether the MSBPN for the first column matches the BPN from the first priority block; and

a second second stage comparator that compares the MSBPN for the first column with the BPN from the second priority block to determine whether the MSBPN for the first column matches the BPN from the second priority block.

9. The partitioned priority index table of claim 7, further comprising:

match line segments coupled to the first priority block;

match line segments coupled to the second priority block;

a first signal filtering circuit that de-asserts the match line segments coupled to the first priority block when the MSBPN for the first column does not match the BPN from the first priority block; and

a second signal filtering circuit that de-asserts the match line segments coupled to the second priority block when the MSBPN for the first column does not match the BPN from the second priority block.

10. The partitioned priority index table of claim 9, wherein the first and second signal filtering circuits comprise circuitry that performs an AND function.

11. The partitioned priority index table of claim 9, further comprising a first register coupled to the match line segments coupled to the first priority block and a second register coupled to the match line segments coupled to the second priority block that register match line segment results from the first and second priority blocks for a second group of priority numbers while the third and fourth priority blocks determine block priority numbers for a first group of priority numbers.

12. The partitioned priority index table of claim 9, further comprising:

match line segments coupled to the third priority block;

match line segments coupled to the fourth priority block;

a third signal filtering circuit that de-asserts the match line segments coupled to the third priority block when the MSBPN for the second column does not match the BPN from the second priority block; and

a fourth signal filtering circuit that de-asserts the match line segments coupled to the fourth priority block when the MSBPN for the second column does not match the BPN from the fourth priority lock.

13. The partitioned priority index table of claim 12, further comprising a third compare logic circuit that determines a MSBPN for a third column of priority blocks from a BPN from a fifth priority block in the first row and a BPN from a sixth priority block in the second row.

14. The partitioned priority index table of claim 13, further comprising:

match line segments coupled to the fifth priority block;

match line segments coupled to the sixth priority block;

a fifth signal filtering circuit that de-asserts the match line segments coupled to the fifth priority block when the MSBPN for the third column does not match a BPN from the fifth priority block; and

a sixth signal filtering circuit that de-asserts the match line segments coupled to the sixth priority block when the MSBPN for the third column does not match a BPN from the sixth priority block.

15. The partitioned priority index table of claim 7, wherein the first compare logic circuit comprises a priority index table and the second compare logic circuit comprises a priority index table.

16. The partitioned priority index table of claim 15, further comprising a first compare logic circuit register that registers results from the first compare logic circuit for a second group of priority numbers while the second compare logic circuit determines the most significant block priority number for the second column for a first group of priority numbers.

17. The partitioned priority index table of claim 12, wherein the third and fourth signal filtering circuits comprise circuitry that performs an AND function.

18. The partitioned priority index table of claim 7, wherein the priority numbers comprise prefix mask data for an Internet Protocol address.

19. A partitioned priority index table having a plurality of rows and columns of priority blocks, comprising:

a first priority block in a first row that compares a first plurality of bits of a first plurality of priority numbers including a first priority number having bits distributed in at least two priority blocks in the first row and determines a block priority number (BPN) for the first priority block;

a second priority block in a second row that compares a second plurality of bits of a second plurality of priority numbers including a second priority number having bits distributed in at least two priority blocks in the second row and determines a BPN for the second priority block;

a first compare logic circuit that determines a most significant block priority number (MSBPN) for a first column from a plurality of BPNs including, at least, the BPNs for the first and second priority blocks;

a third priority block in the first row that compares a second plurality of bits of the first plurality of priority numbers and determines a BPN for the third priority block;

a fourth priority block in the second row that compares a second plurality of bits of the second plurality of priority numbers and determines a BPN for the fourth priority block; and

a second compare logic circuit that determines a MSBPN for the second column from a plurality of BPNs including, at least, the BPNs for the third and fourth priority blocks.

20. The partitioned priority index table of claim 19, further comprising:

match line segments coupled to the third priority block;

match line segments coupled to the fourth priority block;

a first signal filtering circuit that de-asserts the match line segments coupled to the third priority block when the MSBPN for the second column does not match the BPN from the third priority block; and

a second signal filtering circuit that de-asserts the match line segments coupled to the fourth priority block when the MSBPN for the second column does not match the BPN from the fourth priority block.

21. The partitioned priority index table of claim 20, further comprising:

a fifth priority block in the first row that compares a third plurality of bits of the first plurality of priority numbers and determines a BPN for the fifth priority block;

a sixth priority block in the second row that compares a third plurality of bits of the second plurality of priority numbers and determines a BPN for the sixth priority block; and

a third compare logic circuit that determines a MSBPN for the third column from a plurality of block priority numbers, including, at least, the BPNs for the fifth and sixth priority block.

22. The partitioned priority index table of claim 21, further comprising:

match line segments coupled to the fifth priority block;

match line segments coupled to the sixth priority block;

a third signal filtering circuit that de-asserts the match line segments coupled to the fifth priority block when the MSBPN for the third column does not match the block priority number from the fifth priority block; and

a fourth signal filtering circuit that de-asserts the match line segments coupled to the sixth priority block when the MSBPN for the third column does not match the BPN from the sixth priority block.

23. The partitioned priority index table of claim 19, wherein the first compare logic circuit comprises a priority index table and the second compare logic circuit comprises a priority index table.

24. The partitioned priority index table of claim 19, wherein the first and second plurality of priority numbers comprise prefix mask data for an Internet Protocol address.

25. A method for selecting a most significant priority number for a device, comprising:

determining a first block priority number (BPN) from a first plurality of bits from a first plurality of priority numbers;

determining a second BPN from a first plurality of bits from a second plurality of priority numbers; and

determining a most significant block priority number (MSBPN) for a first column from the first and second BPNs, wherein the first plurality of priority numbers includes a first priority number having bits distributed within at least two priority blocks in a same row.

26. The method of claim 25, further comprising:

determining a third BPN from a second plurality of bits from the first plurality of priority numbers;

determining a fourth BPN from a second plurality of bits from the second plurality of priority numbers; and

determining a MSBPN for a second column from the third and fourth BPNs.

27. The method of claim 26, further comprising:

determining that a priority number associated with the third BPN is the most significant priority number for the device if the MSBPN for the second column is the third BPN; and

determining that a priority number associated with the fourth BPN is the most significant priority number for the device if the MSBPN for the second column is the fourth BPN.

28. The method of claim 26, wherein assigning the LSBPN is performed after determining the third BPN from the second plurality of bits from the first plurality of priority numbers and the fourth BPN from the second plurality of bits from the second plurality of priority numbers.

29. The method of claim 26, further comprising:

registering results from a determination of a fifth BPN from a first plurality of bits from a third plurality of priority numbers while determining the third BPN from the second plurality of bits from the first plurality of priority numbers; and

registering results from a determination of a sixth BPN from a first plurality of bits from a fourth plurality of priority numbers while determining the fourth BPN from the second plurality of bits from the second plurality of priority numbers.

30. The method of claim 26, further comprising:

determining a fifth BPN from a third plurality of bits from the first plurality of priority numbers;

determining a sixth BPN from a third plurality of bits from the second plurality of priority numbers; and

determining a MSBPN for a third column from the fifth and sixth BPN.

31. The method of claim 30, further comprising:

determining that a priority number associated with the fifth BPN is the most significant priority number for the device if the MSBPN for the third column is the fifth BPN; and

determining that a priority number associated with the sixth BPN is the most significant priority number for the device if the MSBPN for the third column is the sixth BPN.

32. A partitioned priority index table, comprising:

a first row of priority blocks that stores a first plurality of priority numbers, each of the first plurality of priority number having bits in at least two of the priority blocks in the first row;

a second row of priority blocks that stores a second plurality of priority numbers, each of the second plurality numbers having bits in at least two of the priority blocks in the second row;

means for determining a most significant block priority number (MSPBN) for a first column of priority blocks from a first block priority number (BPN) from a first priority block in the first row and a BPN from a second priority block in the second row; and

means for determining a MSBPN for a second column of priority blocks from a BPN from a third priority block in the first row and a BPN from a fourth priority block in the second row.

33. The partitioned priority index table of claim 32, wherein the means for determining the MSBPN for the first column comprises:

means for comparing the BPNs from the first and second priority blocks to determine the MSBPN for the first column; and

means for comparing the MSBPN for the first column with the BPN from the first priority block to determine whether the MSBPN for the first column originated from the first priority block; and

means for comparing the MSBPN for the first column with the BPN from the second priority block to determine whether the MSBPN for the first column originated from the second priority block.

34. The partitioned priority index table of claim 32, further comprising:

means for de-asserting asserted match line segments from the first priority block when the MSBPN for the first column did not originate from the first row; and

means for de-asserting asserted match line segments from the second priority block when the MSBPN for the first column did not originate from the second row.