Method and apparatus for performing priority encoding in a segmented classification system

• US 7,487,200 B1
• Filed: 12/05/2000
• Issued: 02/03/2009
• Est. Priority Date: 09/23/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Srinivasan, Varadarajan
• Primary Examiner(s): Barot; Bharat N
• Application Number:
  US09/729,871
• Time in Patent Office: 2,982 Days
• Field of Search: 711/100, 711/108, 711/200, 370/392, 370/389, 709201-203, 709/207
• US Class Current: 709/201
• 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

Abstract

A digital signal processor. The digital signal processor includes a first data classification block. The first data classification block outputs a first block priority number associated with a first data stored in the first data classification block that matches a search key. The digital signal processor includes a second data classification block. The second data classification block outputs a second priority number associated with a second data stored in the second data classification block that matches the search key. The digital signal processor includes a device index processor. The device index processor selects a most significant block priority number from the first block priority number and the second block priority number.

Claims

1. A digital signal processor, comprising:

a plurality of data classification blocks each comprising;

a data table for storing uniquely addressable data entries;

a priority index table coupled to the data table;

an encoder coupled to the priority index table; and

a device index processor coupled to the plurality of priority index tables to determine the index for at least one of the data entries that matches a search key.

2. The digital signal processor of claim 1, wherein each priority index table comprises:

memory for storing priority numbers for each corresponding data entry; and

compare logic for determining a most significant priority number for the data classification block.

3. The digital signal processor of claim 1, wherein each of the plurality of data classification blocks further comprises a block identification circuit.

4. The digital signal processor of claim 1, wherein the data table for each of the plurality of data classification blocks each comprise first memory for storing IP addresses, and the priority index tables each comprise second memory for storing prefix data for the IP addresses.

5. The digital signal processor of claim 1, wherein the device index processor comprises:

a compare logic;

a select logic; and

a decoder coupled to the compare logic and the select logic.

6. The digital signal processor of claim 1, wherein the device index processor comprises:

a compare logic;

an index storage unit coupled to the compare logic; and

a device index generator coupled to the compare logic and the index storage unit.

7. The digital signal processor of claim 1, wherein the device index processor comprises:

a compare logic;

a priority encoder coupled to the compare logic;

a decoder coupled to the priority encoder;

an index storage unit coupled to the decoder; and

an index generator coupled to the priority encoder and the index storage unit.

8. A digital signal processor, comprising:

a first data classification block that outputs a first block priority number associated with a first data stored in the first data classification block that matches a search key;

a second data classification block that outputs a second block priority number associated with a second data stored in the second data classification block that matches the search key; and

a device index processor that determines a most significant block priority number from the first block priority number and the second block priority number.

9. The digital signal processor of claim 8, wherein the device index processor outputs a device index for data associated with the most significant block priority number.

10. The digital signal processor of claim 8, wherein the first data classification block outputs a first block index associated with the first data and the second data classification block outputs a second block index associated with the second data.

11. The digital signal processor of claim 10, wherein the device index processor comprises a compare logic that compares a first comparison number, derived from the first block priority number and a first block identifier corresponding to the first data classification block, with a second comparison number, derived from the second block priority number and a second block identifier corresponding to the second data classification block, to determine a most significant comparison number.

12. The digital signal processor of claim 11, wherein most significant bits of the first comparison number are derived from the first block priority number, least significant bits of the first comparison number is derived from the first block identifier, most significant bits of the second comparison number is derived from the second block priority number, and least significant bits of the second comparison number is derived from the second block identifier.

13. The digital signal processor of claim 11, wherein the compare logic determines the most significant block priority number from predetermined most significant bits of the most significant comparison number, and determines a most significant block identifier from predetermined least significant bits of the most significant comparison number.

14. The digital signal processor of claim 13, wherein the device index processor further comprises a select logic that includes:

a first storage element, having a first address, that stores the first block identifier in most significant bits of the first storage element and the first block index in least significant bits of the first storage element;

a second storage element, having a second address, that stores the second block identifier in most significant bits of the second storage element and the second block index in least significant bits of the second storage element.

15. The digital signal processor of claim 14, wherein the device index processor further comprises a decoder that decodes the most significant block identifier into an address of a storage element that stores outputs from a data classification block corresponding to the most significant block identifier.

16. The digital signal processor of claim 11, wherein the device index processor further comprises a select logic that includes:

a first storage element, having a first address, that stores the first block identifier in most significant bits of the first storage element and the first block index in least significant bits of the first storage element;

a second storage element, having a second address, that stores the second block identifier in most significant bits of the second storage element and the second block index in least significant bits of the second storage element.

17. The digital signal processor of claim 16, further comprising a decoder that determines a most significant block identifier by associating predetermined least significant bits of the most significant comparison number with the most significant block identifier, and that decodes the most significant block identifier into an address of a storage element that stores outputs from a data classification block corresponding to the most significant block identifier.

18. The digital signal processor of claim 11, wherein the compare logic comprises a priority index table.

19. The digital signal processor of claim 11, wherein the compare logic comprises a bit-wise compare circuit.

20. The digital signal processor of claim 14, wherein the select logic comprises a plurality of registers.

21. The digital signal processor of claim 14, wherein the select logic comprises a multiplexer.

22. The digital signal processor of claim 8, wherein the first and second data comprises policy statements.

23. The digital signal processor of claim 8, wherein the first and second data comprises Internet Protocol (IP) addresses.

24. The digital signal processor of claim 8, wherein the first data classification unit comprises:

a data table that stores data;

a priority memory that stores a plurality of priority numbers, each priority number associated with a corresponding data in the data table and indicating a priority of the corresponding data relative to other data in the data table;

a priority logic that compares priority numbers in the priority memory associated with data in the data table that match the search key and provides an indication of a most significant priority number as the first block priority number; and

an encoder that generates an index relative to the first data classification block of information associated with the first block priority number.

25. The digital signal processor of claim 13, wherein the device index processor further comprises an index storage unit that includes:

a first storage element, having a first address, that stores the first block index; and

a second storage element, having a second address, that stores the second block index.

26. The digital signal processor of claim 25, wherein the index storage unit outputs a most significant block index in response to the compare logic selecting an address of a storage element that stores a block index from a data classification block corresponding to the most significant comparison number.

27. The digital signal processor of claim 26, wherein the device index processor further comprises a device index generator that outputs a device index, the device index generator designating the most significant block identifier as most significant bits of the device index and designating the most significant block index as least significant bits of the device index.

28. The digital signal processor of claim 11, wherein the device index processor further comprises an index storage unit that includes:

a first storage element, having a first address, that stores the first block index; and

a second storage element, having a second address, that stores the second block index.

29. The digital signal processor of claim 28, wherein the index storage unit outputs a most significant block index in response to the compare logic asserting an address of a storage element that stores a block index from a data classification block that corresponds to the most significant comparison number.

30. The digital signal processor of claim 29, wherein the device index processor further comprises a device index generator that outputs a device index, the device index generator designating predetermined least significant bits of the most significant comparison number as most significant bits of the device index and designating the most significant block index as least significant bits of the device index.

31. The digital signal processor of claim 11, wherein the device index processor further comprises an index storage unit that includes:

a first storage element, having a first address, that stores the first block identifier in most significant bits of the first storage element and the first block index in least significant bits of the first storage element; and

a second storage element, having a second address, that stores the second block identifier in most significant bits of the second storage element and the second block index in least significant bits of the second storage element.

32. The digital signal processor of claim 31, wherein the index storage unit outputs a device index in response to the compare logic asserting an address of a storage element storing outputs from a data classification block that corresponds to the most significant comparison number.

33. The digital signal processor of claim 10, wherein the device index processor comprises a compare logic that stores the first block priority number and the second block priority number in prioritized locations and that compares the first block priority number and the second block priority number to determine a most significant value.

34. The digital signal processor of claim 33, wherein the device index processor further comprises a priority encoder that outputs a block identifier corresponding to a data classification block that outputs a block priority number having the most significant value and when the first block priority number and the second block priority number have a same value, the priority encoder outputs a block identifier corresponding to a data classification block that has a block priority number in a higher priority location.

35. The digital signal processor of claim 34, wherein the device index processor further comprises an index storage unit that includes:

a first storage element, having a first address, that stores the first block index; and

a second storage element, having a second address, that stores the second block index.

36. The digital signal processor of claim 35, wherein the device index processor further comprises a decoder that decodes the block identifier output from the priority encoder into an address of a storage element that stores a block index output from a data classification block corresponding to the block identifier.

37. The digital signal processor of claim 36, further comprising an index generator that outputs a device index for data associated with the most significant priority number, the index generator designating the block identifier output from the priority encoder as most significant bits of the device index and a block index output from the index storage unit as least significant bits of the device index.

38. The digital signal processor of claim 33, wherein the device index processor further comprises a priority encoder that outputs a block identifier corresponding to a data classification block that outputs a most significant block priority number, where the most significant block priority number is a block priority number having the most significant value and alternatively when both the first block priority number and the second block priority number have the most significant value, a block priority number written in a higher priority location is the most significant priority number.

39. The digital signal processor of claim 38, wherein the device index processor further comprises an index storage unit that includes:

a first storage element, having a first address, that stores the first block index;

a second storage element, having a second address, that stores the second block index.

40. The digital signal processor of claim 39, wherein the device index processor further comprises a decoder that decodes the block identifier output from the priority encoder into an address of a storage element that stores a block index output from a data classification block corresponding to the block identifier.

41. The digital signal processor of claim 40, further comprising an index generator that outputs a device index for data associated with the most significant priority number, the index generator designating the block identifier output from the priority encoder as most significant bits of the device index and a block index output from the index storage unit as least significant bits of the device index.