Reconfigurable logic for table lookup

Details Reconfigurable logic for table lookup Reconfigurable logic for table lookup

1999-01-26

2002-05-14

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

Reexamination Certificate

active

06389579

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to hardware for performing a table lookup in a large relatively sparse lookup table with limited types of entries.
2. State of the Art
With the advent of inexpensive high performance processors, a growing number of applications are using standard RISC processors to perform dedicated tasks within non-computing products. In many applications these embedded processors' most frequent task is to access large external memory arrays. External memory can take anywhere from four to tens of system clock cycles to access. As a result, these repetitious “table lookup” functions have become the activity which limits the performance of the products they are embedded in. It has become possible to create single semiconductor integrated circuits which incorporate the processor and some amount of memory. An on-chip memory access can take as little as two clock cycles, so for small lookup tables, a much faster single chip implementation is feasible. Unfortunately, if the application requires a large lookup table, the memory and processor cannot be integrated into a single chip.
If the table never changes, such as the case where the table that is accessed is contained in a Read Only Memory (ROM), and the data contained in the ROM is relatively sparse, i.e. contains many repeating values or empty entries, then the ROM could be converted into random logic and integrated into a single chip with the processor, since the amount of logic would be far smaller than the silicon area required for the ROM. The logic synthesis technique for doing this is well known, and tools exist to do this conversion automatically.
This hard-wired logic approach will not work if the data changes. Many applications, most notably networking routers, have data in large tables, in this case routing directories, which may change every few minutes. Reconfigurable logic on the other hand, is designed to be frequently updated, so reconfigurable logic could be used to contain the lookup table information. One example of reconfiguration logic is a PLA (Programmable Logic Array).
FIG. 3
a
shows the AND/OR planes of a PLA, while
FIG. 3
b
shows a typical horizontal input line driving an n-channel transistor connected to an AND line and GROUND. The output and line is charged up and any of the transistors in the column can pull the entire vertical wire low.
Most programmable logic solutions require hundreds of milliseconds to reprogram. Unfortunately, in many applications, the memory must be read frequently, which eliminates the ability to reconfigure it without unacceptably interrupting service. Furthermore, it usually takes a number of hours to place and route a new design in programmable logic, so the new changes would take a long time to incorporate.
A problem addressed by the present invention is shown in the prior art of FIG.
2
. In this case, a processor looks up data in an external memory to translate information coming into a chip from one IO bus (the arrow pointing in) and then send it out (the arrow pointing out) to another external IO bus. This operation requires four external bus operations, and the processor must wait for the memory to return the proper value.
SUMMARY OF THE INVENTION
The present invention, generally speaking, provides hardware speedup for a table lookup operation. In an exemplary embodiment, a processor is integrated with a special type of reconfigurable logic. Preferably, the reconfigurable logic has the feature of being both partially and fully reconfigurable as necessary. The partial reconfiguration can be used to update the tables while in full operation, and the full reconfiguration can be done when it is necessary to reorganize the entire lookup table. This approach has the advantage of flexibility and speed which the other options lack.


REFERENCES:
patent: 5610829 (1997-03-01), Trimberger
patent: 5812414 (1998-09-01), Butts

Affiliated with

Also associated with

Rating

Reconfigurable logic for table lookup does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reconfigurable logic for table lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconfigurable logic for table lookup will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2893233