Binary search engine and method

• US 20050076035A1
• Filed: 10/18/2004
• Published: 04/07/2005
• Est. Priority Date: 03/07/2001
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Lin, Jonathan, Billings, David, Jorda, Mike
• Granted Patent: US 7,010,535 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A network device including a memory, a queue management unit, a memory management unit, and a search switching unit. The memory includes a plurality of memory banks. The queue management unit is configured to receive a plurality of search requests and to prioritize the search requests. The memory management unit is coupled to the queue management unit and the memory, and is configured to initiate a plurality of binary searches based on the plurality of search requests. Each binary search is executed simultaneously in different banks of the plurality of memory banks. The search switching unit is coupled to the memory and the memory management unit, and is configured to switch each binary search from one memory bank of to another memory bank after a predetermined number of search steps are performed by each binary search.

Claims

1. A network device comprising:

a memory to be searched, said memory comprising memory banks;

a queue management unit configured to receive search requests;

a memory management unit coupled to said queue management unit and said memory and configured to initiate binary searches based on said search requests, the binary searches being initiated simultaneously in different banks of said memory banks; and

a search switching unit coupled to said memory management unit and said memory and configured to switch the binary searches from one memory bank to another memory bank after a predetermined number of search steps are performed in each of the binary searches.

2. The network device of claim 1, wherein said search switching unit is configured to switch each of the binary searches such that only one binary search is executed in each memory bank at a time.

3. The network device of claim 1, wherein said memory comprises four memory banks.

4. The network device of claim 1, wherein said predetermined number of steps is set based on a number of rows in each memory bank.

5. The network device of claim 1, wherein said network device further comprises:

gap memory; and

said memory management unit is configured to cache gap cells of the memory banks into gap memory and to read said cached gap cells to each of said binary searches.

6. The network device of claim 1, wherein said network device comprises:

a switch, and

said memory comprises ARL tables and rules tables.

7. The network device of claim 6, wherein said memory to be searched comprises on-chip memory.

8. The network device of claim 1, wherein said memory management unit is configured to initiate searches at a beginning of a search cycle when no existing searches are being executed against said memory, and

said plurality binary searches having a number of searches less than or equal to a number of memory banks.

9. The network device of claim 8, wherein said queue management unit is configured to buffer search requests in a queue and to prioritize said queue in an order to be initiated.

10. The network device of claim 5, wherein said memory management unit is configured to read said cached gap cells into said each of the binary searches before said each of the binary searches performs a first search step.

11. A network device comprising:

memory means to be searched, said memory means comprising memory banks means;

queue management means for receiving search requests;

memory management means coupled to said queue management means and said memory means, for initiating binary searches based on said search requests, said binary searches being initiated simultaneously in different banks of said memory banks; and

search switching means, coupled to said memory management means and said memory means, for switching the binary searches from one memory bank to another memory bank after a predetermined number of search steps are performed in each of the binary searches.

12. The network device of claim 11, wherein said search switching means is configured such that only one binary search is executed in each memory bank at a time.

13. The network device of claim 11, wherein said memory means comprises four memory banks.

14. The network device of claim 11, wherein said predetermined number of steps is set based on a number of rows in each memory bank.

15. The network device of claim 11, wherein said network device further comprises:

gap memory; and

said memory management means configured to cache gap cells of the memory banks into gap memory and to read said cached gap cells to each of the binary searches.

16. The network device of claim 11, wherein said network device comprises:

switching means, and

said memory means comprises ARL tables and rules tables.

17. The network device of claim 16, wherein said memory means comprises on-chip memory.

18. The network device of claim 11, wherein said memory management means is configured to initiate searches at a beginning of a search cycle when no existing searches are being executed against said memory, and

said plurality binary searches having a number of searches less than or equal to the number of banks in said plurality of banks.

19. The network device of claim 18, wherein said queue management means is configured to buffer search requests in a queue and prioritizes said queue in an order to be initiated.

20. The network device of claim 15, wherein said memory management means is configured to read said cached gap cells into said each of the binary searches before said each of the binary searches performs a first search step.

21. A method for searching memory in a network device, said method comprising the steps of:

providing a memory to be searched, said memory having memory banks;

receiving binary search requests;

initiating binary searches in the memory banks at a same time, said binary searches being based on the binary search requests;

switching the binary searches to a different memory bank, at a predetermined step in each of the binary searches; and

continuing to switch said each of the binary searches to a different memory bank until a match is made.

26. The method of claim 21 wherein said providing step further comprises providing gap memory, and said method further comprising the step of:

caching gap cells of each memory bank into said gap memory; and

reading said gap cells into each search.

27. The method of claim 26 wherein said providing step comprises providing ARL tables and rules tables.

28. The network device of claim 27, wherein said providing step comprises providing on-chip memory.

29. The network device of claim 21, wherein said initiating step comprises initiating the binary searches at a beginning of a search cycle when no existing searches are being executed against said memory, the binary searches comprising a number of searches less than or equal in number to a number of banks.

30. The network device of claim 21, wherein said initiating step comprises buffering said search requests into a queue and prioritizing said queue in an order to be initiated.

31. The network device of claim 26, wherein said step of reading said gap cells comprises reading said gap cells into each of the binary searches before said each binary search performs a first search step.

22. The method of step 21 further comprising the step of:

performing a networking function based on each said match.

23. The method of step 22, wherein said performing a networking function step comprises switching a network packet based on each said match.

24. The method of step 21, wherein said binary searches are initiated at a same time at a beginning of a search cycle of said network device in said initiating step.

25. The method of step 24, wherein said each of the binary searches is switched such that only one binary search is executed against each memory bank at a time, during said switching and continuing steps.