Search function for data lookup

• US 6,775,764 B1
• Filed: 04/24/2001
• Issued: 08/10/2004
• Est. Priority Date: 04/24/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Batcher, Kenneth W.
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US09/841,271
• Time in Patent Office: 1,204 Days
• Field of Search: 712/210, 712/227, 712/230, 711/114, 711/125, 711/216, 711/219, 711/212, 711/209, 711/214, 380/264, 380/44, 713/171, 713/190, 707/6, 707/3, 379/355.06
• US Class Current: 712/227
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A SEARCH function preferably built into the instruction set of a microprocessor for quickly and efficiently searching a plurality of memory locations. Data from a significant number of memory locations is searched in a very short period of time, using a minimal number of instruction cycles.

Claims

1. A method of operating a processor to determine the location of one or more tags respectively stored in one of a plurality of memory locations, comprising:

fetching and executing a SEARCH instruction to execute an associated memory read instruction a plurality of times;

wherein said SEARCH instruction includes as an operand said count value that is stored in said count register, wherein execution of the SEARCH instruction stores the count value in said count register;

fetching the associated memory read instruction to read the contents of one or more memory locations;

loading a count register with a count value indicative of a maximum number of memory locations to be searched; and

executing the associated memory read instruction one or more times to respectively read the contents of the one or more memory locations, wherein the associated memory read instruction is executed as many times as indicated by the count value, or until a search hit occurs.

2. A method according to claim 1, wherein said search hit occurs when one of said one or more tags is read from a memory location.

3. A method according to claim 1, wherein said search hit occurs when all of said one or more tags is read from a respective memory location.

4. A method according to claim 1, wherein said search hit is indicated by at least one of:

interrupting a CPU;

storing a hit indicator in a condition code; and

returning a plurality of hit addresses to a respective plurality of registers.

5. A method according to claim 1, wherein a search miss is indicated by at least one of:

interrupting a CPU;

storing a miss indicator in a condition code; and

returning a plurality of miss addresses to a respective plurality of registers, wherein the search miss is indicative that a search hit has not occurred with respect to reading the contents of a memory location.

6. A method of operating a processor according to claim 1, wherein said count value is stored in said count register before execution of said SEARCH instruction.

7. A method of operating a processor according to claim 1, wherein said method further comprises:

decrementing said count value in accordance with each execution of said memory read instruction.

8. A method according to claim 1, wherein the method further comprises:

determining whether said count value is less than zero.

9. A method according to claim 1, wherein the method further comprises:

storing the address of the memory location having the tag in a register.

10. A processor for determining the location of one or more tags respectively stored in one of a plurality of memory locations, comprising:

means for loading a count register with a count value indicative of a number of memory locations to be searched;

means for fetching a SEARCH instruction;

wherein said SEARCH instruction includes said count value that is stored in said count register, wherein execution of the SEARCH instruction stores the count value in said count register;

means for executing the SEARCH instruction to execute an associated memory read instruction a plurality of times;

means for fetching the associated memory read instruction to read the contents of one or more memory locations; and

means for executing the associated memory read instruction one or more times to respectively read the contents of the one or more memory locations, wherein the associated memory read instruction is executed as many times as indicated by the count value, or until a search hit occurs.

11. A processor according to claim 10, wherein said search hit occurs when one of said one or more tags is read from a memory location.

12. A processor according to claim 10, wherein said search hit occurs when all of said one or more tags is read from a respective memory location.

13. A processor according to claim 10, wherein said search hit is indicated by at least one of:

interrupting the processor;

storing a hit indicator in a condition code; and

returning a plurality of hit addresses to a respective plurality of registers.

14. A system according to claim 10, wherein a search miss is indicated by at least one of:

interrupting the processor;

storing a miss indicator in a condition code; and

returning a plurality of miss addresses to a respective plurality of registers, wherein the search miss is indicative that a search hit has not occurred with respect to reading the contents of a memory location.

15. A processor according to claim 10, wherein said count value is stored in said count register before execution of said SEARCH instruction.

16. A processor according to claim 10, wherein said processor further comprises:

means for decrementing said count value in accordance with each execution of said memory read instruction.

17. A processor according to claim 10 wherein the processor further comprises:

means for determining whether said count value is less than zero.

18. A processor according to claim 10, wherein the processor further comprises:

means for storing the address of the memory location having the tag in a register.

19. A processor for searching the location of one or more tags respectively stored in one of a plurality of memory locations, said processor comprising:

a memory address register associated with a main memory;

a memory data register associated with the main memory;

a memory control for generating memory control signals;

a program counter for storing a memory address location of the main memory where read instruction is to be fetched;

an instruction register for storing SEARCH instruction that is to be executed;

wherein said SEARCH instruction includes said count value that is stored in a count register, wherein execution of the SEARCH instruction is adapted to store the count value in said count register;

decode and execute control logic for decoding and executing an instruction stored in the instruction register; and

a state machine for controlling the fetching of the read instruction, and the execution thereof one or more times to respectively determine the contents of one or more memory locations.

20. A processor according to claim 19, wherein said processor further comprises an instruction buffer for storing the one or more associated instructions.

21. A processor according to claim 19, wherein said general purpose register includes a first register for storing a count value indicative of the maximum number of times said memory read instruction is to be executed in accordance with the search instruction.

22. A processor according to claim 21, wherein said state machine generates signals for decrementing the count value stored in the first register.

23. A processor according to claim 21, wherein said state machine generates a signal for executing said memory read instruction stored in said instruction register.

24. A processor according to claim 19, wherein said state machine generates a signal for incrementing said program counter.

25. A processor according to claim 19, wherein said state machine continues to execute said memory read instruction until the memory read instruction has been executed as many times as indicated by the count value, or until a search hit occurs.

26. A processor according to claim 25, wherein said search hit occurs when one of said one or more tags is read from a memory location.

27. A processor according to claim 25, wherein said search hit occurs when all of said one or more tags is read from a respective memory location.