Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2000-05-31
2004-03-16
Khatri, Anil (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S124000, C717S140000, C716S030000
Reexamination Certificate
active
06708325
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to reconfigurable computing.
2. State of the Art
Traditionally, an integrated circuit must be designed by describing its structure with circuit primitives such as Boolean gates and registers. The circuit designer must begin with a specific application in mind, e.g. a video compression algorithm, and the resulting integrated circuit can only be used for the targeted application.
Alternatively, an integrated circuit may be designed as a general purpose microprocessor with a fixed instruction set, e.g. the Intel ×86 processors. This allows flexibility in writing computer programs which can invoke arbitrary sequences of the microprocessor instructions. While this approach increases the flexibility, it decreases the performance since the circuitry cannot be optimized for any specific application.
It would be desirable for high level programmers to be able to write arbitrary computer programs and have them automatically translated into fast application specific integrated circuits. However, currently there is no bridge between the computer programmers, who have expertise in programming languages for microprocessors, and the application specific integrated circuits, which require expertise in circuit design.
Research and development in integrated circuit design is attempting to push the level of circuit description to increasingly higher levels of abstraction. The current state of the art is the “behavioral synthesizer” whose input is a behavioral language description of the circuit's register/transfer behavior and whose output is a structural description of the circuit elements required to implement that behavior. The input description must have targeted a specific application and must describe its behavior in high level circuit primitives, but the behavioral compiler will automatically determine how many low level circuit primitives are required, how these primitives will be shared between different blocks of logic, and how the use of these primitives will be scheduled. The output description of these circuit primitives is then passed down to a “logic synthesizer” which maps the circuit primitives onto a library of available “cells”, where each cell is the complete implementation of a circuit primitive on an integrated circuit. The output of the logic synthesizer is a description of all the required cells and their interconnections. This description is then passed down to a “placer and router” which determines the detailed layout of all the cells and interconnections on the integrated circuit.
On the other hand, research and development in computer programming is also attempting to push down a level of abstraction by matching the specific application programs with custom targeted hardware. One such attempt is the Intel MMX instruction set. This instruction set was designed specifically to accelerate applications with digital signal processing algorithms. Such applications may be written generically and an MMX aware compiler will automatically accelerate the compiled code by using the special instructions. Another attempt to match the application with appropriate hardware is the work on parallelizing compilers. These compilers will take a computer program written in a sequential programming language and automatically extract the implicit parallelism which can then be targeted for execution on a variable number of processors. Thus different applications may execute on a different number of processors, depending on their particular needs.
Despite the above efforts by both the hardware and software communities, the gap has not yet been bridged between high level programming languages and integrated circuit behavioral descriptions.
SUMMARY OF THE INVENTION
A computer program, written in a high level programming language, is compiled into an intermediate data structure which represents its control and data flow. This data structure is analyzed to identify critical blocks of logic which can be implemented as an application specific integrated circuit to improve the overall performance. The critical blocks of logic are first transformed into new equivalent logic with maximal data parallelism. The new parallelized logic is then translated into a Boolean gate representation which is suitable for implementation on an application specific integrated circuit. The application specific integrated circuit is coupled with a generic microprocessor via custom instructions for the microprocessor. The original computer program is then compiled into object code with the new expanded target instruction set.
In accordance with one embodiment of the invention, a computer implemented method automatically compiles a computer program written in a high level programming language into a program for execution by one or more application specific integrated circuits coupled with a microprocessor. Code blocks the functions of which are to be performed by circuitry within the one or more application specific integrated circuits are selected, and the code blocks are grouped into groups based on at least one of an area constraint and an execution timing constraint. Loading and activation of the functions are scheduled; and code is produced for execution by the microprocessor, including instructions for loading and activating the functions.
In accordance another aspect of the invention, a computer implemented method automatically compiles a computer program written in a high level programming language into one or more application specific integrated circuits. In accordance with yet another aspect of the invention, a computer implemented method automatically compiles a computer program written in a high level programming language into one or more application specific integrated circuits coupled with a standard microprocessor. In accordance with still another aspect of the invention, a reconfigurable logic block is locked by compiled instructions, wherein an activate configuration instruction locks the block from any subsequent activation and a release configuration instruction unlocks the block. In accordance with a further aspect of the invention, a high level programming language compiler automatically determines a set of one or more special instructions to extend the standard instruction set of a microprocessor which will result in a relative performance improvement for a given input computer program. In accordance with yet a further aspect of the invention, a method is provided for transforming the execution of more than one microprocessor standard instruction into the execution of a single special instruction. In accordance with still a further aspect of the invention, a high level programming language compiler is coupled with a behavioral synthesizer via a data flow graph intermediate representation.
REFERENCES:
patent: 5491694 (1996-02-01), Oliver et al.
patent: 5511067 (1996-04-01), Miller
patent: 5513124 (1996-04-01), Trimberger et al.
patent: 5548587 (1996-08-01), Bailey et al.
patent: 5603063 (1997-02-01), Au
patent: 5625797 (1997-04-01), Ferry et al.
patent: 5729705 (1998-03-01), Weber
patent: 5752035 (1998-05-01), Trimberger
patent: 5794044 (1998-08-01), Yellin
patent: 5864535 (1999-01-01), Basilico
patent: 5870308 (1999-02-01), Dangelo et al.
patent: 5898860 (1999-04-01), Leibold
patent: 6021266 (2000-02-01), Kay
patent: 6058469 (2000-05-01), Baxter
patent: 6075935 (2000-06-01), Ussery et al.
patent: 6212650 (2001-04-01), Guccione
patent: 6216259 (2001-04-01), Guccione et al.
patent: 6510546 (2003-01-01), Blodget
Hartenstein, A decade of reconfigurable computing a visionary retrospective, IEEE, pp 642-649, 2001.*
Crawford, Engineering a production code generator., ACM pp 205-215, 1982.*
Moya et al., Improving embedded system design by means of HW-SW compilation on reconfigurable coprocessors. ACM ISSS, pp 255-260, 2002.*
Athanas, Peter M., “A Functional Reconfigurable Architecture and Compiler for Adaptive Computing”, Virginia Polytechnic Institute and State University, Bradley Department of Electrical Enginee
Cooke Laurence H.
Phillips Christopher E.
Wong Dale
LandOfFree
Method for compiling high level programming languages into... 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 for compiling high level programming languages into..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compiling high level programming languages into... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288225