Recursive use of multiple hardware lookup structures in a transactional memory

Abstract

A lookup engine of a transactional memory (TM) has multiple hardware lookup structures, each usable to perform a different type of lookup. In response to a lookup command, the lookup engine reads a first block of first information from a memory unit. The first information configures the lookup engine to perform a first type of lookup, thereby identifying a first result value. If the first result value is not a final result value, then the lookup engine uses address information in the first result value to read a second block of second information. The second information configures the lookup engine to perform a second type of lookup, thereby identifying a second result value. This process repeats until a final result value is obtained. The type of lookup performed is determined by the result value of the preceding lookup and/or type information of the block of information for the next lookup.

What is claimed is: 
     
       1. An integrated circuit, comprising:
 a lookup engine that reads a first result value and a first indicator from a memory and determines if the first result value is a final result value, wherein the lookup engine outputs the first result value when the first indicator indicates that the first result value is the final result value, and wherein the lookup engine does not output the first result value and reads a second result value and a second indicator from the memory when the first indicator indicates that the first result value is not the final result value. 
 
     
     
       2. The integrated circuit of  claim 1 , wherein the lookup engine reads the first result value and the first indicator from the memory in response to receiving a lookup command from a processor across a bus. 
     
     
       3. The integrated circuit of  claim 2 , wherein the lookup engine reads the second result value and the second indicator from memory without any additional communication with the processor. 
     
     
       4. The integrated circuit of  claim 2 , wherein the bus is a Command/Push/Pull (CPP) bus. 
     
     
       5. The integrated circuit of  claim 2 , wherein the processor is not located on the integrated circuit, and wherein the processor communicates with the lookup engine via a bus port and the bus. 
     
     
       6. The integrated circuit of  claim 2 , wherein the processor is located on the integrated circuit. 
     
     
       7. The integrated circuit of  claim 2 , wherein the lookup engine generates an address based on the contents of the lookup command, and wherein the address is used by the lookup engine to read the first result value and the first indicator from the memory. 
     
     
       8. The integrated circuit of  claim 2 , wherein the lookup engine initiates a pull of an Internet Protocol (IP) address in response to receiving the lookup command from the processor. 
     
     
       9. The integrated circuit of  claim 1 , wherein the first indicator is a Final Result Bit (FRB) included in the first result value. 
     
     
       10. The integrated circuit of  claim 1 , wherein the first indicator is a Final Result Bit (FRB) and is not included in the first result value. 
     
     
       11. The integrated circuit of  claim 1 , wherein the first result value includes lookup configuration information to be used in the reading the second result value and the second indicator from the memory when the first indicator indicates that the first result value is not the final result value. 
     
     
       12. The integrated circuit of  claim 1 , wherein the lookup engine returns the first result value to a processor across a bus when the first indicator indicates that that the first result value is the final result value. 
     
     
       13. The integrated circuit of  claim 12 , wherein the first result value and first indicator are read by performing a first type of lookup operation, and wherein the second result value and the second indicator are read by performing a second type of lookup operation. 
     
     
       14. The integrated circuit of  claim 13 , wherein the first and second lookup operations are selected from the group consisting of: a multi-bit lookup operation, a direct 32-bit lookup operation, a direct 24-bit lookup operation, and an algorithmic lookup operation. 
     
     
       15. The integrated circuit of  claim 1 , wherein the bit width of the first result value is different from the bit width of the second result value. 
     
     
       16. The integrated circuit of  claim 1 , wherein the memory is not located on the integrated circuit. 
     
     
       17. The integrated circuit of  claim 1 , wherein the memory is located on the integrated circuit. 
     
     
       18. The integrated circuit of  claim 1 , wherein the lookup engine further comprises:
 a translator circuit that generates a plurality of opcodes; and 
 a pipeline circuit that includes a plurality of pipeline stages, wherein each of the opcodes are executed by one of the pipelines stages in the pipeline circuit. 
 
     
     
       19. The integrated circuit of  claim 1 , wherein the first result value, the first indicator, the second result value, and the second indicator are read from the memory unit in a single 128-bit wide read operation. 
     
     
       20. The integrated circuit of  claim 1 , wherein the integrated circuit is an Island-Based Network Flow Processor (IB-NFP) that includes multiple islands, wherein the lookup engine and the memory are located on a first island of the IB-NFP, and wherein the processor is located on a second island of the IB-NFP.