Electrical computers and digital processing systems: processing – Instruction decoding – Decoding instruction to accommodate variable length...
Reexamination Certificate
2000-11-30
2004-05-25
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Instruction decoding
Decoding instruction to accommodate variable length...
C712S212000, C712S213000, C717S116000, C717S118000, C717S141000, C717S148000
Reexamination Certificate
active
06742109
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to computer instructions. More specifically, the present invention relates to a method and apparatus for representing and executing variable-size computer instructions.
2. Related Art
Modem computing devices execute a series of “executable” instructions from an instruction set to perform operations specified in a computer program. At times these instruction sets are specified in the native language of a central processing unit (CPU). At other times these operations are specified in a platform-independent code that is executed by a platform-independent virtual machine (VM). For example, INTEL™ x86 architecture instructions and SUN SPARC instructions are instruction sets in the native language of a CPU, and JAVA™ bytecodes are a platform-independent code for a platform-independent VM.
The terms JAVA, JVM and JAVA VIRTUAL MACHINE are registered trademarks of SUN Microsystems, Inc. of Palo Alto, Calif. Intel is a registered trademark of the Intel Corporation of Santa Clara, Calif.
Executable instructions have two portions. A first portion specifies an action to be performed and a second portion provides a source for data that may be required for the instruction. Note that some instructions, such as a no-operation instruction, do not require data, while other instructions require data. This data can be provided in the form of immediate data values, or alternatively, in the form of pointers to the data values.
The x86 instruction “add eax, ebx” exemplifies an instruction which has both action and data portions. The action in this case is addition, while the data portion indicates that the value in register ebx is to be added to the value in register eax with the result remaining in register eax. Since the data size varies from instruction to instruction in these instruction sets, the size of the entire instruction varies as well.
Variable-size instructions have many drawbacks. Each instruction has to be decoded to determine its size, and therefore, the location of the next instruction. Also, some computing devices require multiple fetch cycles to retrieve variable-size instructions since not all instructions are stored at convenient locations for fetching in a single fetch cycle. Since a given variable-size instruction may not start on a word boundary, the given instruction may require fetches of multiple words that contain the instruction and then subsequent reassembly of the given instruction from the parts located within the multiple words.
The biggest drawback is that the CPU does not know how many bytes/words to fetch until it decodes at least the first byte of an instruction. If an instruction is positioned in memory in such a way that it is split between two cache lines, the CPU does not know that it has to fetch the next line until it decodes the first byte of the instruction. The time penalty can be significant. To avoid this penalty, compilers try to generate code without splitting instructions by inserting padding bytes or reordering instructions.
Thus, using variable-size instructions can result in computer programs that run more slowly because of the additional processing and the additional fetch cycles included in processing variable-size instructions.
What is needed is a method and apparatus which alleviates the above-described problems in using variable-size instructions.
SUMMARY
One embodiment of the present invention provides a system for executing variable-size computer instructions, wherein a variable-size computer instruction includes an action component that specifies an operation to be performed and a data component of variable size that specifies data associated with the operation. The system operates by first retrieving the variable-size computer instruction from a computing device's memory. The system then decodes the variable-size computer instruction by separating the variable-size computer instruction into the “action” component and the “data” component. Next, the system stores the action component in a first store and the data component in a second store so they can be reused without repeated decoding. Finally, the system provides a first flow path for the action component and a second flow path for the data component.
In one embodiment of the present invention, the data component of the variable-size computer instruction has a length of zero or greater.
In one embodiment of the present invention, the first flow path and the second flow path are synchronized so that the action component and data component are retrieved together.
In one embodiment of the present invention, the system executes the action component from the first store and receives the data component associated with the action component from the second store.
In one embodiment of the present invention, if the action component is a branch instruction to a previously decoded variable-size computer instruction, the system uses the action component from the first store and the data component from the second store for the previously decoded variable-size computer instruction.
In one embodiment of the present invention, a given entry in the first store contains a pointer to the data component in the second store associated with the action component stored in the first store.
In one embodiment of the present invention, the action component stored in the first store has a fixed size, so that the action component can be accessed with a single fetch operation.
REFERENCES:
patent: 4633389 (1986-12-01), Tanaka et al.
patent: 5590294 (1996-12-01), Mirapuri et al.
patent: 5668985 (1997-09-01), Carbine et al.
patent: 5758114 (1998-05-01), Johnson et al.
patent: 5898851 (1999-04-01), Narayan et al.
patent: 6065108 (2000-05-01), Tremblay et al.
patent: 0 969 357 (2000-05-01), None
Publication entitled “Improving CISC Instruction Decoding Performance Using a Fill Unit,” by Mark Smotherman and Manoj Franklin, Proceedings of MICRO-28, 1995 IEEE, pp. 219-229.
Sokolov Stepan
Wallman David
Grundler Edward J.
Pan Daniel H.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for representing variable-size computer... 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 representing variable-size computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for representing variable-size computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3251095