Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-12-15
2004-06-22
Das, Chameli C. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S142000, C717S143000, C717S146000, C717S149000, C717S151000, C712S012000, C712S023000, C712S024000, C712S030000, C712S300000
Reexamination Certificate
active
06754892
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computers and, more particularly, to a method for choosing operations to include in instructions for a very long instruction word (VLIW) microprocessor.
2. History of the Prior Art
A very long instruction word (VLIW) processor includes a number of different functional units which provide circuitry for processing a number of individual operations simultaneously. For example, one such processor includes two arithmetic and logic units (ALUs), a floating point unit (FPU), and a memory unit. These units perform their individual operations in parallel by responding to individual commands (sometimes herein called “atoms”) a number of which are contained in a single instruction word (sometimes herein called a “molecule”). Typically, the atoms command such functions as fetch, load, add, move, and store, each of which causes one of the functional units to carry out the commanded operation.
In order to handle a number of operations at the same time in its different functional units, a VLIW processor must receive the atoms in an instruction word arranged in a format which the processor is capable of recognizing and utilizing. One embodiment of a particular VLIW processor is capable of recognizing atoms which appear in six different formats. In two of these formats, molecules each include four individual atoms; while in the remaining four formats, molecules each include two atoms. In any of these formats, all atoms occupy the same number of bits.
Most processors receive instructions for execution which have been generated from original source code by a compiler. One of the jobs of a compiler is to arrange the various instructions into proper formats and to place them in an order in which they may be rapidly executed by the particular processor. Normally, a compiler does this job statically as a part of the programming function long before a program is ready for execution. Once the compiler has finished, the code is simply run by a processor in the ultimate form furnished by the compiler.
However, one particular VLIW processor executes programs designed for other “target processors.” This VLIW processor receives its instructions in a form adapted to be executed by a target processor which typically has an entirely different instruction set than does the VLIW processor. The VLIW processor dynamically translates the stream of target instructions into instructions of its own host instruction set and stores those translated host instructions so that they may be executed without retranslation. This VLIW processor is described in detail in U.S. Pat. No. 5,832,205, Kelly et al issued Nov. 3, 1998, and assigned to the assignee of the present invention.
The translated instructions are atoms representing operations that the functional units of the host VLIW processor can execute but which are arranged in no particular instruction word format recognizable by that processor. Because the atoms are in no recognizable format, the operations (atoms) must be rearranged into the formats (molecules) of the long instruction words which the processor is able to execute.
In order to accomplish the process of placing operations into formats (packing) for a typical VLIW processor of the prior art, a typical compiler designed in accordance with teaching of the prior art creates a data structure for each format which the processor can execute. Initially, each of these data structures is empty. As each new operation is presented, the compiler packing process tests the data structures in serial order to determine whether the operation fits the format of any of those instruction words. If an operation fits a format, the data structure is masked to indicate that a place has been reserved for the operation. Since some operations may be executed by a number of different functional units, the process does not stop after detecting a format into which an operation fits but continues testing and masks each data structure representing a format into which the operation may fit. If an operation may fit into more than one position of a particular format, then duplicate copies of the data structure for the format are created and masked at the different positions. The result is that during the packing process there may be many partially filled data structures representing formats at any time. Because some operations may be executed by a number of different functional units, those data structures masked for the same operation must also be linked by the packing process in some manner so that a format in which space has been reserved but which is not used may be appropriately handled when another format is ultimately selected.
With each succeeding operation, the same serial testing process is carried out to determine when the operation fits a format. Once a format is filled, it is selected to be used and passed on to other processes of the compiler.
As may be seen, this process requires a large number of data structures and a relatively large series of looping and linking operations in order to find formats into which each succeeding operation may be appropriately placed. Although the time consumed by a compiler which accomplishes its operations statically is not significant to the operation of the compiles program, the aforementioned VLIW processor must carry out a packing operation each time a target program is run throughout the operation of the program. Consequently, the time to accomplish this packing function can significantly slow the operation of such a processor. For example, to carry out a single significantly optimized packing operation utilizing a typical compiler process in the above-described processor requires about thirty-four system clock intervals.
It is desirable to provide a new faster process for packing instructions into proper formats for a computer processor.
SUMMARY OF THE INVENTION
The present invention is realized by a method for packing operations into formats including the steps of providing a word value representing an instruction word into which an operation is to be fit be equal to some initial value having a plurality of portions representing constraints, operating on the initial value of the value word with operation class values having a plurality of portions representing constraints of a new operation as the new operation is attempted to be fit into the instruction to affect the processor word value in a manner to indicate when the limit of any constraint for the instruction is reached, and determining a violation of any constraint to determine that the new operation does not fit the format.
REFERENCES:
patent: 4259718 (1981-03-01), Kaman et al.
patent: 4312036 (1982-01-01), Porter et al.
patent: 4314331 (1982-02-01), Porter et al.
patent: 4371927 (1983-02-01), Wilhite et al.
patent: 4491908 (1985-01-01), Woods et al.
patent: 5057837 (1991-10-01), Colwell et al.
patent: 5129066 (1992-07-01), Schmookler
patent: 5179680 (1993-01-01), Colwell et al.
patent: 5301341 (1994-04-01), Vassiliadis et al.
patent: 5485629 (1996-01-01), Dulong
patent: 5649135 (1997-07-01), Pechanek et al.
patent: 5857103 (1999-01-01), Grove
patent: 5862398 (1999-01-01), Hampapuram et al.
patent: 5974539 (1999-10-01), Guttag et al.
patent: 6065106 (2000-05-01), Deao et al.
patent: 6101592 (2000-08-01), Pechanek et al.
patent: 6202142 (2001-03-01), Narayan et al.
patent: 6282633 (2001-08-01), Killian et al.
patent: 6317872 (2001-11-01), Gee et al.
patent: 6343373 (2002-01-01), Koizumi et al.
patent: 6397379 (2002-05-01), Yates et al.
patent: 6442701 (2002-08-01), Hurd
patent: 6453407 (2002-09-01), Lavi et al.
patent: 6571386 (2003-05-01), Figurin et al.
patent: 6618804 (2003-09-01), Steele et al.
TITLE: Architecture and compiler tradeoffs for a long instruction wordprocessor, author: Cohn et al, ACM, 1989.*
TITLE: Combining as a compilation technique for VLIW architectures, Author: Nakatani et al, ACM, 1989.*
TITLE: A VLIW architecture for a trace scheduling compiler, author: Colwell et al, ACM, 1987.*
TITLE: RISC I: a reduced instruction set VLSI c
Das Chameli C.
Transmeta Corporation
LandOfFree
Instruction packing for an advanced microprocessor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Instruction packing for an advanced microprocessor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction packing for an advanced microprocessor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364927