Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1998-12-21
2001-03-27
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S010000, C710S120000, C710S062000, C711S167000, C708S232000, C345S503000
Reexamination Certificate
active
06209077
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention (Technical Field)
The present invention relates to computer architectures for improving speed of execution of repeating short blocks of instructions particularly for general purpose algorithms or data filters.
2. Background Art
Many computer programs perform the largest portion of their processing (measured in time or CPU cycles) in one or several comparatively short blocks of instructions. Programmers have been traditionally taught to make programs “maintainable”, even though that may produce some inefficient computer instruction code, and then go back to identify and optimize the blocks of instructions where the most time is being spent. With a device according to the present invention, compute-intensive blocks of instructions may be placed dynamically into programmable logic devices (PLDs), making thems execute quickly and efficiently.
In the prior art, special-purpose co-processors and accelerators exist, such as numeric co-processors, graphic display accelerators, digital signal processors, and the like, but these are designed to expedite a specific function or narrow set of functions. In other words, they are not general purpose. In the current invention, the data might just as easily be a picture, a series of samples of a data acquisition unit, or the result of the last process step. Processors like the Intel numeric co-processors (8087, 80287, etc.) have a fixed set of microcoded numeric instructions to perform, on demand. Graphic display accelerators are designed to perform graphic manipulations on data passing between the system's bus and the video display unit. Although digital signal processors (DSPs) can be flexibly programmed, their instruction set is designed for signal processing and still have to be decoded before being processed, and so routines written for them do not execute as quickly as routines implemented at the logic gate level, as in the present invention. Image Enhancement Co-Processors (IMECOs) employ PLDs and memory blocks, but do not provide for bi-directional data flows, multiple algorithms, algorithm caching, or memory sub-sampling as provided by the present invention to increase throughput and reduce data congestion of the host microprocessor.
Patents disclosing uses of PLDs quite different from the present invention include: U.S. Pat. No. 5,497,498, to Taylor, entitled “Video Processing Module Using a Second Programmable Logic Device Which Reconfigures a First Programmable Logic Device for Data Transformation”; U.S. Pat No. 5,537,601, to Kimura et al., entitled “Programmable Digital Signal Processor for Performing a Plurality of Signal Processings”; and U.S. Pat. No. 5,603,043, to Taylor et al., entitled “System for Compiling Algorithmic Language Source Code for Implementation in Programmable Hardware”. Each of these disclosures is directed to a specific task rather than to the general acceleration strategy of the present invention.
SUMMARY OF THE INVENTION
The present invention is of a general purpose accelerator board and acceleration method comprising use of: a programmable logic device (or devices); a plurality of memory blocks; bus interface for communicating data between the memory blocks and devices external to the board; and dynamic programming capabilities for providing logic to the programmable logic device to be executed on data in the memory blocks. In the preferred embodiment, the bus interface additionally comprises the capability of communicating logic instructions between the programmable logic device and devices external to the board. The board is preferably a PCI board and includes control logic. The board is configurable to perform a multitude of functions including discrete Fourier transforms, convolutions, encryption, decryption, filtering, image processing, and signal processing, or to execute standard system functions and dynamically linked libraries. The board can also be used for library searches and indexing typically performed on ASCII text files. The bus interface is capable of extracting a subset of data from a memory block during execution of the logic and using this data set, in the case of a photograph, for example, to create a sub-sampled representation of the data. The preferred number of memory blocks is two or other multiple of two memory blocks. A plurality of programmable logic devices may be employed together with scheduling logic for coordinating operations of the plurality of programmable logic devices. A caching scheme may be employed to keep often-used logic in the PLDs for use at a future time.
A primary object of the present invention is to provide a general purpose device for accelerating instructions which must be repetitively performed on a large block of data or to speed execution of algorithms that would be slow if performed in software.
A primary advantage of the present invention is that a variety of different application may be accelerated with the use of, if desired, a single co-processing board according to the invention.
Another advantage of the present invention is that it may be reconfigured quickly enough to service multiple algorithms within a process and multiple processes within a computer system.
An additional advantage of the present invention is that it is easily scalable as PLDs with more logic gates become available.
Yet another advantage of the present invention is that it can be built to interface with any of the popular computer buses, including PCI and VME.
Still another advantage of the present invention is that, with on-board memory buffers, data never leaves the board until processing is complete, reducing congestion on the computer system's buses.
A further advantage of the present invention is the optional ability to extract a small portion of a complete data set or a subsampled representative data set, as part of the data processing thereby reducing bus congestion and time required to view the sampled data set via the application-specific hardware programming loaded into the PLDs.
Other objects, advantages and novel features, and further scope of applicability of the present invention will be set forth in part in the detailed description to follow, taken in conjunction with the accompanying drawings, and in part will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 4831573 (1989-05-01), Norma
patent: 5113500 (1992-05-01), Talbott et al.
patent: 5497498 (1996-03-01), Taylor
patent: 5537601 (1996-07-01), Kimura et al.
patent: 5600263 (1997-02-01), Trimberger et al.
patent: 5603043 (1997-02-01), Taylor et al.
Singh & Sious, Accelerating Adobe Photoshop with Reconfigurable Logic, pp. 1-9.
Altera, The Evolution of PLD Technology, May 5, 1998, pp. 1-2.
Salcic, VHDL and FLPDs in Digital Systems Design, Prototyping and Customization, pp. 491-493.
Robertson Perry J.
Witzke Edward L.
Libman George H.
Pan Daniel H.
Peacock Myers & Adams
Sandia Corporation
LandOfFree
General purpose programmable accelerator board does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with General purpose programmable accelerator board, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General purpose programmable accelerator board will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2477753