Electrical computers and digital data processing systems: input/ – Intrasystem connection
Reexamination Certificate
2000-07-25
2004-03-09
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
C716S030000, C711S103000, C708S231000, C708S232000
Reexamination Certificate
active
06704816
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to an apparatus and method for execution of standard functions in a computer system.
Past developments in computer systems to improve the execution speed of programs have seen the emergence of floating point numeric co-processors. These evolved due to the demand for repetitive calculations, typically in scientific applications where a number of complex trigonometric or floating point operations are required. In the early days of 8-bit processors, a square root function could take in the order of 5 milliseconds to execute. Floating point co-processors could perform this operation in around 1 microsecond, i.e. around 5000 times faster.
Recent developments have been aimed at speeding up more complex numeric functions, such as digital fourier transforms (DFT's). To perform such a complex numeric function, the processor may be required to perform many thousands of floating point applications. Processors designed to perform such complex numeric functions are generally referred to as digital signal processors (DSP's). The goal is to reduce the execution time to such an extent that real time operation can be achieved. Real time operation is highly desirable for applications such as image processing, holographic television and mobile telephone communication, for example.
With the focus on numeric and then DSP applications, some of the more mundane data processing functions have largely been ignored by hardware designers. The lack of interest in data processing functions can be understood by the fact that these functions do not consume as much processor time as numeric functions, such as the traditional square root function, or complex functions such as DFT's.
One example of a simple data processing function is a basic string search. The task is to find if a string such as “fred” appears in any of a number of other strings such as “rolling stones”, “manfred mann” and “pink floyd”, and if so where. The processor performs a byte-by-byte comparison of the first character in the required string “f” in the other strings until a match is found. The second character “r” is then compared with the next character of the string being compared, and so on. To perform the calculation, data is required to be loaded from system memory into the processor registers, interleaved with the processor instructions, also held in memory. The transactions on the system bus, the loading of internal processor registers and decision making are all executed in processor clock periods and represent a significant overhead of the string search function.
As databases become ever larger, repetitive applications of the simplest functions can be expected to consume increasing proportions of the total processor power, notwithstanding the fact that the functions individually are not computationally intensive. Imagine a database where many thousands of records have to be scanned for matching strings, or sorted into a different order.
It is thus an aim of the invention to provide a computer system in which standard functions, especially non-numeric functions such as those related to database applications, can be performed more efficiently than with conventional execution.
SUMMARY OF THE INVENTION
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Features of the dependent claims may be combined with those of the independent claims as appropriate and in combinations other than those explicitly set out in the claims.
According to one aspect of the invention there is provided a computer system comprising a processor unit connected to a system bus, a mass storage medium including a library of functions, and a field programmable gate array (FPGA). The function library includes a number of functions stored in a pre-compiled form derived from compilation of firmware code and comprising a set of configuration data for configuring the field programmable gate array. The firmware code from which the pre-compiled form is derived may be written in a high-level description language (HDL). The FPGA has a set of configuration line connections operatively associated with the mass storage medium to allow configuration of the FPGA with the pre-compiled form of the function concerned. The FPGA also has a set of bus line connections operatively connected to communicate with the processor, for example through the system bus or a bus internal to the processor unit. The processor is operable to execute a call to one of said functions by delegating the principal data processing content of the function to the FPGA which is configured with the appropriate set of configuration data for that function. The function library may be held in system memory connected to the system bus, or held in an external device accessible through an I/O port of the computer system.
Returning to the example of a string search cited in the introduction, comparison of whole substrings can now take place in nanoseconds rather than hundreds of nanoseconds with a computer system based on current processor and FPGA technology. In the specific example from the introduction, the complete string “fred” could be compared concurrently against the first four characters “roll” in less than 10 nanoseconds. By comparison, with conventional software-based execution, four distinct load/compare cycles are required, consuming hundreds of nanoseconds of processor time.
An additional speed advantage is gained by the inherent parallelism of the high-level description languages (HDL's) used to write FPGA firmware. In this regard, most processors are essentially sequential devices and can only execute one instruction at a time. (Exceptions to this are parallel processors such as the Transputer). As a result, conventional hardware execution of a software function will in essence be a sequential process, even if pipelining is used to allow several instructions along an instruction stream to be worked on simultaneously. By contrast, HDL's are inherently parallel, allowing more than one command level function to be performed by the FPGA at the same time.
Referring once more to the string search described above. The string “fred” is searched for in the substring “manf” of “manfred mann”. A byte-by-byte comparison indicates no match. At the same time, the first byte “f” of the string “fred” can be compared with every byte of “manf” to indicate where the rest of the search should begin, in this case at the fourth character. Both these operations can take place contemporaneously in the FPGA hardware. Incidentally, two redundant comparisons are also removed by this procedure, namely the search for a match between “f” (the first character of “fred”) and each of “a” and “n” (the second and third characters of “manfred mann”).
Thus, by transferring tasks from the processor to the FPGA, a change from sequential to parallel execution can be achieved. The processor is thus not only freed up for carrying out its other tasks, but the functions are executed more efficiently with parallelism.
Another significant advantage of the FPGA approach is that it allows retention of a level of flexibility comparable with conventional software-based execution. By contrast, transfer of numeric functions to a dedicated co-processor, or to specific integrated circuit portions of a DSP, sacrifices the flexibility of conventional software-based execution.
One way in which the inherent flexibility of the firmware approach can be exploited is as follows. Taking a library of standard functions as a starting point, the most time consuming standard functions can be committed to firmware first. Attention can then be directed to developing firmware versions of those functions that previously took seemingly insignificant amounts of processor time. The new firmware versions of the functions can then be added to existing computer systems, simply by supplying a ROM or other recording medium on which is stored the firmware representation of the standard function. The firmware for each function will principa
King Justin I.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Ray Gopal C.
LandOfFree
Method and apparatus for executing standard functions in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for executing standard functions in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for executing standard functions in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3233894