Patent Publication Number: US-2016246601-A1

Title: Technique for translating dependent instructions

Description:
BACKGROUND 
     1. Field of the Disclosure 
     The present disclosure generally relates to processors, and more particularly to processing of dependent instructions at a processor. 
     2. Description of the Related Art 
     Processors sometimes enhance processing efficiency by employing out-of-order execution, whereby instructions are executed in an order different from the instructions&#39; program order. In order to avoid errors, a processor executing instructions out of order uses disambiguation techniques to account for dependencies between instructions. One such disambiguation technique is the use of a scheduler to ensure that a dependent instruction is not executed until after execution of the instruction from which it depends. However, this technique can increase the execution latency of the dependent instruction, thereby reducing the efficiency of the processor. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present disclosure may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings. 
         FIG. 1  is a block diagram of a processor in accordance with some embodiments. 
         FIG. 2  is a diagram illustrating a timeline showing an example operation of a mapper of the processor of  FIG. 1  in accordance with some embodiments. 
         FIG. 3  is a diagram illustrating a timeline showing another example operation of the mapper of the processor of  FIG. 1  in accordance with some embodiments. 
         FIG. 4  is a flow diagram illustrating a method of translating a dependent instruction at a processor in accordance with some embodiments. 
         FIG. 5  is a flow diagram illustrating a method for designing and fabricating an integrated circuit device implementing at least a portion of a component of a processing device in accordance with some embodiments. 
       The use of the same reference symbols in different drawings indicates similar or identical items. 
     
    
    
     DETAILED DESCRIPTION 
       FIGS. 1-5  illustrate techniques for reducing the execution latency of an instruction at a processor by translating (mapping) a dependent operation of the instruction so that the operation is no longer dependent. In some embodiments, to translate an operation, a mapper of the processor determines the source registers of the operation from which the dependent operation depends. The mapper translates the dependent operation to a new operation that uses as its source operands at least one of the determined source registers and a source register of the dependent operation. The new operation achieves the same result as the dependent operation but is independent of other pending operations and therefore can be executed without waiting for execution of the other the operation it was initially dependent on, thus allowing reduced execution latency. 
     To illustrate by way of example, the mapper can determine that Operation B is an ADD operation that adds two addends: the result of Operation A, also an ADD instruction, and another addend. Accordingly, Operation B uses as its source registers the destination register of Operation A and a source register storing the other addend. The mapper therefore translates Operation B into a new instruction that adds three addends: the two addends stored at the source registers of Operation A and the independent addend. The new instruction is not dependent on Operation A and can therefore be executed before or in parallel with Operation A. Accordingly, the result of Operation B is achieved with less latency than awaiting execution of Operation A. 
       FIG. 1  illustrates a block diagram of a processor  100  in accordance with some embodiments. The processor  100  can be incorporated into any system or electronic device that employs a processor to execute sets of instructions, including a personal computer, server, tablet, cell phone or other telephone, game console, and the like. The sets of instructions executed by the processor  100  are arranged as computer programs stored at a memory (not shown). Each of the computer programs defines a corresponding order, referred to as the program order, of its set of instructions. As described further herein the processor  100  is configured to execute at least a subset of the operations mandated by the instructions in an out-of-order fashion with respect to the program order, but is configured to take steps to ensure that the results of the out-of-order execution matches the results if the operations were executed in program order. 
     To execute the instructions, the processor  100  includes an instruction pipeline having a front end  102 , a mapper  105 , a register file  104 , a scheduler  106 , and execution units  108 . The front end  102  is configured to retrieve the sets of instructions from the memory and to decode each instruction into one or more operations. When the operations of an instruction are executed, the task associated with the instruction is achieved. An instruction thus provides a level of abstraction for its associated operations. To illustrate, an instruction to add a number to a variable can be decoded into at least three operations: an operation to load the variable value to one register, an operation to load the number to another register, and an operation to add the contents of the registers. An example operation  145  is illustrated at  FIG. 1 . The operation  145  includes a micro-operation (uOp) field  151 , source register fields  152  and  153 , and a destination register field  154 . It will be appreciated that different instructions can be decoded such that they have different combinations of the illustrated fields. For example, some instructions will have fewer or more than two source register fields. 
     The uOp field  151  stores a code (e.g., an opcode) indicating the micro-operation associated with the instruction. The code therefore indicates the particular operation that is to be executed for the operation  145 . For example, the code can indicate whether the operation is to execute an integer addition operation, a floating point multiply operation, a load/store operation, and the like. The source register fields  152  and  153  indicate architectural registers where source operands for the operation to be executed are located and the destination register field  154  indicates an architectural register where the result of the operation is to be stored. To illustrate, in some embodiments, the sets of instructions executed at the processor  100  are configured to operate on an architectural register space having a plurality of architectural registers. The registers indicate locations in the architectural register space. As described further herein, the processor  100  maps the architectural registers to a set of physical registers at the register file  104 , whereby the physical register mapped to a given architectural register can change according to conditions at the instruction pipeline. The architectural register space provides, for the executing set of instruction, a common set of referents as to the locations of operands independent of the particular hardware of the processor  100 . To illustrate by way of example, an integer add instruction can be decoded to have source operands representing two corresponding addends. The source register fields  152  and  153  indicate the architectural registers that store the addends and the destination register field  154  indicates the architectural register where the sum of the addends is stored in response to execution of the instruction. 
     The source fields  142  and  143  and destination field  144  of operations are used to identify dependency between operations. In particular, as used herein, Operation B is dependent on Operation A if Operation B is later in the program order than Operation A and a source operand of Operation B matches the destination operand of Operation A, and there is no intervening operation that writes the architectural register that is the destination of Operation A. Operation B is independent of Operation A if: 1) Operation B is prior to Operation A in the program order; 2) Operation B does not have a source operand that matches a destination operand of Operation A; or 3) there is an operation between Operation A and Operation B in the program order that writes the architectural register that is the destination of Operation A. Conventionally, dependent operations are executed in program order relative to the operation from which they depend in order to avoid errors. However, as described further herein, the processor  100  can translate selected decoded dependent instructions to new operations and thereby remove the dependency, allowing out-of-order execution for the new operations. 
     The mapper  105  is configured to receive operations and to map the architectural registers indicated by the operands of the operations to physical registers at the register file  104 . The mapper  105  maintains a table (map) that indicates which of the physical registers at the register file  104  is assigned to each architectural register. The mapper  105  updates the table based on dependencies between instructions and on the state of execution of operations pending at the instruction pipeline to allow for out-of-order execution of independent instructions. In addition, the mapper  105  can translate selected operations into new operations in response to determining the selected operations are dependent on another operation that has not yet completed execution. The new operations achieve the same result as the corresponding selected operations, but use the source operands rather than the destination operand, of the operation from which they depend. The new operation is therefore independent and can be executed in an out-of-order fashion relative to a program order. 
     To illustrate by way of example, Operation B is an integer add operation having a destination operand R 5  and source operands R 3  and R 4 , where R 3 , R 4  and R 5  indicate different architectural registers. Operation A precedes Operation B in the program order and is an integer add operation having a destination operand R 3  and source operands R 1  and R 2 . Operation A and Operation B can be operations resulting from decoding of a single instruction or operations decoded from different instructions. For purposes of the example, there are no instructions between Instruction A and Instruction B in the program order that write architectural register R 3 . Thus, because one of the source operands of Operation B is the destination operand of Operation A, Operation B depends on Operation A. In response to determining this dependency, the mapper  105  translates the Operation B into a new Operation C, where Operation C is an integer add operation that adds 3 source operands R 1 , R 2 , and R 4 , and has a destination operand of R 5 . Accordingly, Operation C achieves the same result as Operation B. However, the source operands of Operation C do not include the destination operand of Operation A. Accordingly, Operation C is independent of Operation A. Operation C can therefore be executed before or concurrently with Operation A, increasing processing efficiency. 
     In some embodiments, the mapper  105  processes several operations in parallel to support out of order execution. In the course of mapping the architectural register operands of the operations to physical registers, the mapper  105  determines dependencies between the operations being processed. For selected ones of operations that are determined to be dependent, the mapper  105  can translate operations as described further herein. 
     In some embodiments, the mapper  105  includes a set of tables to facilitate translation of an operation. One of the tables maintains operation information for received operations that have not yet completed execution. The other table is a table of micro-operations that indicates 1) which micro-operations are candidates for translation and 2) the corresponding micro-operation to which the candidate is to be translated if the received operation is a dependent instruction. For each received operation, the mapper  105  compares the operation&#39;s source operands to the destination operands of the pending decoded operations and concurrently compares the micro-operation of the received operation to the table. In response to the comparison indicating that the received operation is 1) a candidate for translation and 2) is dependent on a pending operation, the mapper  105  translates the received operation by substituting the received micro-operation with the micro-operation indicated by the table. The mapper  105  also substitutes at least one of the source operands of the received operation with a source operand of the operation from which it depends. In addition, the mapper  105  can insert any other source operands of the operation from which it depends as additional source operands of the received operation thereby translating the received operation into a new operation whose result matches the received operation. 
     The scheduler  106  receives operations from the mapper  105  and schedules the operations for execution at the execution units  108 . In addition, the scheduler  106  determines dependencies between the instructions based on the physical, rather than the architectural registers. The scheduler  106  then schedules the operations for execution such that dependent instructions are executed according to the program order relative to the instructions from which they depend. That is, the scheduler  106  schedules the operations for execution to ensure that dependent instructions are executed after the instructions from which they depend. 
     As discussed above, the new instructions generated at the mapper  105  described above are no longer dependent on the instructions from which their “parent” instruction depended. Accordingly, the new instruction can be executed before or concurrently with the instruction from which the parent instruction depended. To illustrate, in the depicted example of  FIG. 1  the execution units  108  include two integer units, designated integer units  131  and  132 , and two floating point units (FPUs), designated FPUs  136  and  137 . Using the example above, integer add Instruction B depends from integer add Instruction A. Accordingly, without translation of Instruction B the scheduler  106  would determine that Instruction B depends on Instruction A and would therefore schedule the instructions such that, for example, Instruction A must complete execution at integer unit  131  before Instruction B can be scheduled for execution at one of integer unit  131  and integer unit  132 . However, in the example above operation B is translated to operation C. The scheduler  106  determines that Instruction C is independent of Instruction A, and therefore schedules operation A and operation C for concurrent execution at the integer unit  131  and the integer unit  132 , respectively. Thus, the result of Instruction B is determined more quickly than without translation, thereby reducing latency and improving performance. 
       FIG. 2  depicts a timeline  200  illustrating an example operation of the mapper  105  of the processor  100  of  FIG. 1  in accordance with some embodiments. In particular, the timeline  200  illustrates the translation of an operation  203  based on its dependency on an operation  202  that precedes the operation  203  in the program order. The operation  202  performs an integer addition of two source operands, designated R 1  and R 2 , and stores the result at a destination operand designated R 3 . The operation  203  performs an integer addition the source operand R 3  to a source operand designated R 4  and stores the result at the destination operand R 5 . Accordingly, the result of the operation  203  can be expressed as follows: 
         R 5= R 3+ R 4=( R 1+ R 2)+ R 4 
     At time  210 , the mapper  105  receives the operation  203 . In response, the mapper  105  compares the source operands of operation  203  to the destination operand of operation  202  and determines a match, indicating that the operation  203  is dependent on the operation  202 . In addition, the mapper  105  concurrently compares the micro-operations of the operation  202  and  203  and determines that they are both integer add instructions that add two corresponding source operands. The mapper  105  therefore determines that the operation  203  is eligible for translation. In response, at time  211  the mapper  105  translates the operation  203  by replacing its micro-operation with the micro-operation ADD 3 , which is configured to perform an integer addition of three source operands. In addition, the mapper  105  replaces the source operand of the operation  203  that matches the destination operand of the operation  202  (the operand R 3 ) with one of the source operands (R 1 ) of the operation  202 . The mapper  105  also adds the other source operand (R 2 ) of the operation  202  as an additional operand for the translated instruction. Accordingly, at time  212  the mapper  105  provides a new, translated operation  205 . The operation  205  adds the source operands of the operation  202  R 1  and R 2  to the source operand R 4  of the operation  203  and stores the result at the destination operand R 5 . Accordingly, the result of the operation  205  can be expressed as follows: 
         R 5 =R 1 +R 2 +R 4 
     Thus, the result of the operation  205  matches the result of the operation  203 . However, the operation  205  does not use the destination operand of the operation  202 , and therefore is not dependent on the operation  202 . The operation  205  can therefore be executed prior to or concurrent with the operation  202 . 
       FIG. 3  depicts a timeline  300  illustrating another example operation of the mapper  105  in accordance with some embodiments. In particular, the timeline  300  illustrates the translation of an operation  303  based on its dependency on an operation  302  that precedes the operation  303  in the program order. The operation  302  performs a floating point multiply of two source operands, designated R 1  and R 2 , and stores the result at a destination operand designated R 3 . The operation  303  performs a floating point addition of the source operand R 3  to a source operand designated R 4  and stores the result at the destination operand R 5 . Accordingly, the result of the operation  303  can be expressed as follows: 
         R 5 =R 3+ R 4=( R 1 *R 2)+ R 4 
     At time  310 , the mapper  105  receives the operation  303 . In response, the mapper  105  compares the source operands of operation  303  to the destination operand of operation  302  and determines a match, indicating that the operation  303  is dependent on the operation  302 . In addition, the mapper  105  concurrently compares the micro-operations of the operation  302  and  303  and determines that the operation  303  is eligible for translation. In response, at time  311  the mapper  105  translates the operation  303  by replacing its micro-operation with the micro-operation FMAC, which is configured to perform a floating point multiply-accumulate operation that multiplies two source operands and adds the result to a third source operand three source operands. The mapper  105  replaces the source operand of the operation  203  that matches the destination operand of the operation  2302  (the operand R 3 ) with one of the source operands (R 1 ) of the operation  302 . The mapper  105  also adds the other source operand (R 2 ) of the operation  302  as an additional operand for the translated instruction. Accordingly, at time  312  the mapper  105  provides a new, translated operation  305 . The operation  305  multiplies the source operands of the operation  302  R 1  and R 2  and adds the result to the source operand R 4  of the operation  303 . The operation  305  stores the result at the destination operand R 5 . Accordingly, the result of the operation  305  can be expressed as follows: 
         R 5= R 1 *R 2+ R 4 
     Thus, the result of the operation  305  matches the result of the operation  303 . However, the operation  305  does not use the destination operand of the operation  302 , and therefore is not dependent on the operation  302 . The operation  305  can therefore be executed prior to or concurrent with the operation  302 . 
     Other operations in addition to the above examples can also be translated. For example, some operations invoke a logical operation, such as an OR or AND operation, where the logical operation combines an operand with the resulting operand of an addition operation. The logical operation is therefore dependent on the addition operation. The logical operation can be translated to a new operation that adds the operands of the addition operation and performs the logical operation on the result. The new operation is therefore independent of the addition operation, but achieves the same result as the logical operation. 
       FIG. 4  illustrates a flow diagram of a method  400  of a method of translating a dependent instruction at a processor in accordance with some embodiments. For ease of explanation, the method  400  is described with respect to an example implementation at the processor  100  of  FIG. 1 . At block  402  the mapper  105  receives an operation from the front end  102 . At block  404  the mapper  105  determines if the received operation is dependent on another pending operation by examining the respective source and destination operands of the received operation and the pending operation. If the received operation is not dependent on a pending operation, the method flow moves to block  406  and the mapper  105  provides the received operation to the scheduler  106 . 
     Returning to block  404 , if the mapper  105  determines that the received operation is dependent on a pending operation, the method flow proceeds to block  408 , where the mapper  105  determines whether the micro-operation of the received operation indicates that the received operation is eligible for translation. In some embodiments, this determination is made based both on the micro-operation of the received operation and on the micro-operation of the operation from which it depends. If the determination indicates that the received operation is not eligible for translation, the method flow moves to block  406  and the mapper  105  provides the received operation to the scheduler  106 . At block  416  the scheduler  106  schedules the translated operation for execution at the execution units  108 . 
     If the determination at block  408  indicates that the received operation is eligible for translation, the method flow moves to block  410  and the mapper  105  substitutes the micro-operation of the received operation with a new micro-operation. The new micro-operation performs a similar function as the replaced micro-operation, but removes the dependency of the received operation. The method flow proceeds to block  412 , and the mapper  105  substitutes the source operands of the received operation by replacing a subset of the source operands with the source operands of the operation from which the received operation depends. The mapper  105  also adds additional operands so that the translated operation includes all of the source operands of the operation from which the received operation depends. The destination operand of the received operation is not replaced, so that the translated operation has the same destination operand as the received operation. Accordingly, the translated operation achieves the same result as the received operation but does not depend from a pending operation. Therefore, at block  414  the mapper  105  provides the translated operation to the scheduler  106 . At block  416  the scheduler  106  schedules the translated operation for execution at the execution units  108  so that it is executed before or concurrent with the operation from which the received operation depends. Thus, by translating the received operation such that it is no longer dependent on a pending operation, processing latency is reduced and performance is enhanced. 
     In some embodiments, at least some of the functionality described above may be implemented by one or more processors executing one or more software programs tangibly stored at a computer readable medium, and whereby the one or more software programs comprise instructions that, when executed, manipulate the one or more processor cores to perform one or more of the functions described above. Further, in some embodiments, serial data interfaces described above are implemented with one or more integrated circuit (IC) devices (also referred to as integrated circuit chips). Electronic design automation (EDA) and computer aided design (CAD) software tools may be used in the design and fabrication of these IC devices. These design tools typically are represented as one or more software programs. The one or more software programs comprise code executable by a computer system to manipulate the computer system to operate on code representative of circuitry of one or more IC devices so as to perform at least a portion of a process to design or adapt a manufacturing system to fabricate the circuitry. This code can include instructions, data, or a combination of instructions and data. The software instructions representing a design tool or fabrication tool typically are stored in a computer readable storage medium accessible to the computing system. Likewise, the code representative of one or more phases of the design or fabrication of an IC device may be stored in and accessed from the same computer readable storage medium or a different computer readable storage medium. 
     A computer readable storage medium may include any storage medium, or combination of storage media, accessible by a computer system during use to provide instructions and/or data to the computer system. Such storage media can include, but are not limited to, optical media (e.g., compact disc (CD), digital versatile disc (DVD), or Blu-Ray disc), magnetic media (e.g., floppy disc, magnetic tape, or magnetic hard drive), volatile memory (e.g., random access memory (RAM) or cache), non-volatile memory (e.g., read-only memory (ROM) or Flash memory), or microelectromechanical systems (MEMS)-based storage media. The computer readable storage medium may be embedded in the computing system (e.g., system RAM or ROM), fixedly attached to the computing system (e.g., a magnetic hard drive), removably attached to the computing system (e.g., an optical disc or Universal Serial Bus (USB)-based Flash memory), or coupled to the computer system via a wired or wireless network (e.g., network accessible storage (NAS)). 
       FIG. 5  is a flow diagram illustrating an example method  500  for the design and fabrication of an IC device implementing one or more aspects. The code generated for each of the following processes is stored or otherwise embodied in computer readable storage media for access and use by the corresponding design tool or fabrication tool. 
     At block  502  a functional specification for the IC device is generated. The functional specification (often referred to as a micro architecture specification (MAS)) may be represented by any of a variety of programming languages or modeling languages, including C, C++, SystemC, Simulink, or MATLAB. 
     At block  504 , the functional specification is used to generate hardware description code representative of the hardware of the IC device. In some embodiments, the hardware description code is represented using at least one Hardware Description Language (HDL), which comprises any of a variety of computer languages, specification languages, or modeling languages for the formal description and design of the circuits of the IC device. The generated HDL code typically represents the operation of the circuits of the IC device, the design and organization of the circuits, and tests to verify correct operation of the IC device through simulation. Examples of HDL include Analog HDL (AHDL), Verilog HDL, SystemVerilog HDL, and VHDL. For IC devices implementing synchronized digital circuits, the hardware descriptor code may include register transfer level (RTL) code to provide an abstract representation of the operations of the synchronous digital circuits. For other types of circuitry, the hardware descriptor code may include behavior-level code to provide an abstract representation of the circuitry&#39;s operation. The HDL model represented by the hardware description code typically is subjected to one or more rounds of simulation and debugging to pass design verification. 
     After verifying the design represented by the hardware description code, at block  506  a synthesis tool is used to synthesize the hardware description code to generate code representing or defining an initial physical implementation of the circuitry of the IC device. In some embodiments, the synthesis tool generates one or more netlists comprising circuit device instances (e.g., gates, transistors, resistors, capacitors, inductors, diodes, etc.) and the nets, or connections, between the circuit device instances. Alternatively, all or a portion of a netlist can be generated manually without the use of a synthesis tool. As with the hardware description code, the netlists may be subjected to one or more test and verification processes before a final set of one or more netlists is generated. 
     Alternatively, a schematic editor tool can be used to draft a schematic of circuitry of the IC device and a schematic capture tool then may be used to capture the resulting circuit diagram and to generate one or more netlists (stored on a computer readable media) representing the components and connectivity of the circuit diagram. The captured circuit diagram may then be subjected to one or more rounds of simulation for testing and verification. 
     At block  508 , one or more EDA tools use the netlists produced at block  906  to generate code representing the physical layout of the circuitry of the IC device. This process can include, for example, a placement tool using the netlists to determine or fix the location of each element of the circuitry of the IC device. Further, a routing tool builds on the placement process to add and route the wires needed to connect the circuit elements in accordance with the netlist(s). The resulting code represents a three-dimensional model of the IC device. The code may be represented in a database file format, such as, for example, the Graphic Database System II (GDSII) format. Data in this format typically represents geometric shapes, text labels, and other information about the circuit layout in hierarchical form. 
     At block  510 , the physical layout code (e.g., GDSII code) is provided to a manufacturing facility, which uses the physical layout code to configure or otherwise adapt fabrication tools of the manufacturing facility (e.g., through mask works) to fabricate the IC device. That is, the physical layout code may be programmed into one or more computer systems, which may then control, in whole or part, the operation of the tools of the manufacturing facility or the manufacturing operations performed therein. 
     Note that not all of the activities or elements described above in the general description are required, that a portion of a specific activity or device may not be required, and that one or more further activities may be performed, or elements included, in addition to those described. Still further, the order in which activities are listed are not necessarily the order in which they are performed. 
     Also, the concepts have been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the disclosed embodiments as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of the disclosed embodiments. 
     Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any feature(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature of any or all the claims.