Electrical computers and digital data processing systems: input/ – Intrasystem connection
Reexamination Certificate
2000-06-19
2003-09-02
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
C711S118000, C711S202000, C712S205000
Reexamination Certificate
active
06615300
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to an improvement in digital processors (the “host processors”) that dynamically translate instructions of a computer application program (the “target application”) designed for processing by a digital processor (the “target processor”) that functions with a different instruction set than the instruction set of the host processor, executing the translated instructions in real time to carry out the purpose of the target application, and, more particularly, relates to a new method and apparatus for processing of indirect branch instructions of the target application to reduce latency in processing by the host processor.
BACKGROUND
A unique digital processing system is described in U.S. Pat. No. 6,031,992, granted Feb. 29, 2000, entitled Combining Hardware and Software to provide an Improved Microprocessor, assigned to Transmeta Corporation, (referred to as the '992 Transmeta patent), the content of which is incorporated by reference herein in its entirety. The Transmeta processor serves as the host processor capable of executing software programs, the target application, designed with an instruction set intended to run on a processor of different design, the “target” processor, that contains an instruction set unique to the target processor, but different from that of the host processor. The present invention improves upon the host processor and, hence, the host processing system.
The microprocessor of the '992 Transmeta patent is formed by a combination of a hardware processing portion (sometimes called a “morph host”), and a software portion, referred to as “code morphing software.” Among other things, the code morphing software carries out a significant portion of the functions of digital processors in software, reducing the hardware required for processing, and, hence, reducing power consumption. The morph host processor executes the code morphing software which translates the target application programs dynamically into host processor instructions that are able to accomplish the purpose of the original software. As the instructions are translated, they are stored in a translation buffer where they may be subsequently accessed and executed, as needed, during continued program execution without further translation.
A set of host registers (in addition to normal working registers) is included in the Transmeta processor. The host registers store “state” (also referred to as “context”) of the target processor which exists at the beginning of any sequence of target instructions being translated. In one embodiment, the results of translations are held in a gated store buffer until the translations execute. If the sequence of translated instructions execute without raising an exception the results are stored in memory by a commit instruction. Further, the registers holding the target state are updated to the target state at the point at which the results from the sequence of translated instructions was committed. The information contained in those registers are used to advantage in the present invention as a “tag” for a translation.
The '992 Transmeta processor is capable of processing target applications programs designed for other processors. Application programs contain indirect branch instructions, in which the instruction execution requires the processor to “branch” to a specified address (in memory) and execute the instruction found at that address before returning to process the next instruction of the application program. When that branch address is not known, that is, is not included in the branch instruction, the branch instruction is referred to as “indirect”. The latter is the type of instruction with which the present invention is principally concerned. Thus, any reference herein to a branch instruction should be understood to refer to an indirect branch instruction, unless the text expressly states to the contrary.
Given that the branch address is not initially known, to complete execution of the branch instruction, the processor must first calculate or otherwise determine the unknown branch target address. The processor makes the calculation, determines the branch address, jumps to that address and executes the instruction found at that address.
In processors that include a memory “stack” and “call” and “return” instructions, the return instruction constitutes one important class of indirect branch instruction. The call instruction constitutes a kind of branch. To transfer the flow of the application program to the procedure, such as a subroutine, to which a jump is made, the target processor employs the CALL instruction. Then to return to the program following the execution of a branch instruction (and any other intervening instruction executions, as may include additional call and return instructions (called a nested branch), as example, that target processor employs the RETURN instruction.
When a CALL is made, the return address of the next instruction of the application program is saved in a memory stack (e.g. is “pushed” onto the stack) so that the flow of the program may continue later, when a RETURN instruction is executed. The RETURN instruction in turn “pops” the next instruction address of the target application off of the stack, and that succeeding instruction is then executed by the target processor (e.g. the processor jumps to that address and executes the instruction). That combination of software and hardware of the target processor reduces the latency in obtaining the next instruction of the program for execution.
When an indirect branch instruction of an application program intended for operation in a target type system is to be executed by the host Transmeta processor, in order to correctly translate that branch instruction into instructions of the host processor, the host must not only generate code to perform the effect of the branch instruction, but must also generate code to determine the address of the translation of the target of the branch. Thus in order for the host processor to execute the target branch instruction, the target program address and other target processor state information that was earlier saved by the host processor must be converted into the address of a corresponding translation followed by a transfer of control of the host processor to that translation.
A translation corresponds to a target address if the execution of the (machine language) code in the translation has the same effect on the state of the target processor stored in the context registers of the host processor as would be caused by a target processor executing that same target processor code. The host processor also associates additional information with each translation, called “tags”. One tag may contain information of the state of the target processor at the time the translation was made, as example, and other tags will contain other information, as later herein described. Those tags may be used to enable the processor to later identify (and, as appropriate, retrieve) the particular translation when again needed.
To find a pre-existing translation (e.g. host instruction) of an instruction address of the target processor, the host processor first searches (e.g. “looks”) through the translation memory, the library of translations stored in a memory earlier referred to, to find a translation whose tags match the current target state. As example, that memory may contain tens of thousands of translations. A conventional approach to efficient searching of the translation buffer is to establish an index of the stored information, known as a hash table, to make the search easier to accomplish. A hash table or “hashing” is the creation of an index to the table content that is derived from a transformation of the information stored. As example, see Schildt, “C: The Complete Reference”, third edition, Osborne-McGraw-Hill Ch 21 p 587 (1995). In practice one finds that searching a physical memory of the processing system in that way or any other way that requires searching through all translations is slower t
Banning John
Choy Brian
Coon Brett
Gainer Patrick
Torvalds Linus
Ray Gopal C.
Transmeta Corporation
Wagner , Murabito & Hao LLP
LandOfFree
Fast look-up of indirect branch destination in a dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast look-up of indirect branch destination in a dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast look-up of indirect branch destination in a dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032379