Program translation and transactional memory formation

Disclosed are methods, machine readable medium and systems that dynamically translate binary programs. The dynamic binary translation may include identifying a hot code trace of a program. The translation may further include determining a completion ratio for the hot code trace. The translation may also include packaging the hot code trace into a transactional memory region in response to the completion ratio having a predetermined relationship to a threshold ratio.

BACKGROUND

Historically, processor performance has been greatly influenced by creating processors that operate at higher frequencies. Due to various thermal and power related problems encountered as a result of higher operating frequencies, the industry has recently shifted away from increasing the operating frequency of the processor toward increasing the number of processing cores per a processor. Software generally needs to be designed for multiple threads of execution and/or other forms of parallelization in order to take full advantage of the processing power provided by multiple processing cores. However, much of the software on the market has been designed for systems having a single processor that has a single core. As a result, much of the current software is unable to take full advantage of processors having multiple processing cores and is thus unable to fully enjoy the benefit of the increased processing power of such processors.

DETAILED DESCRIPTION OF THE DRAWINGS

Embodiments of the invention may be implemented in hardware, firmware, software, or any combination thereof. Embodiments of the invention may also be implemented as instructions stored on a non-transitory machine-readable medium, which may be read and executed by one or more processors. A non-transitory machine-readable medium may include any non-transitory mechanism for storing or transmitting information in a non-transitory form readable by a machine (e.g., a computing device). For example, a non-transitory machine-readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; and others.

Referring now toFIG. 1, one embodiment of a computing device100is shown. The computing device100may include a processor102and a memory104coupled to a chipset106. A mass storage device112, a non-volatile storage (NVS) device105, a network interface (I/F)114, and an Input/Output (I/O) device118may also be coupled to the chipset106. Embodiments of computing device100include, but are not limited to, a desktop computer, a notebook computer, a server, a personal digital assistant, a network workstation, or the like. In one embodiment, the processor102may execute instructions stored in memory104.

The processor102may include, but is not limited to, processors manufactured or marketed by Intel Corp., IBM Corp., and Sun Microsystems Inc. In one embodiment, computing device100may include multiple processors102. The processors102may also include multiple processing cores. Accordingly, the computing device100may include multiple processing cores for executing binary code of the computing device100.

The memory104may include, but is not limited to, Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), Synchronized Dynamic Random Access Memory (SDRAM), Rambus Dynamic Random Access Memory (RDRAM), or the like. In one embodiment, the memory104may include one or more memory units that do not have to be refreshed.

The chipset106may include a memory controller, such as a Memory Controller Hub (MCH), an input/output controller, such as an Input/Output Controller Hub (ICH), or the like. In an alternative embodiment, a memory controller for memory104may reside in the same chip as processor102. The chipset106may also include system clock support, power management support, audio support, graphics support, or the like. In one embodiment, chipset106is coupled to a board that includes sockets for processor102and memory104.

The components of computing device100may be connected by various interconnects. In one embodiment, an interconnect may be point-to-point between two components, while in other embodiments, an interconnect may connect more than two components. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI Express, a System Management bus (SMBUS), a Low Pin Count (LPC) bus, a Serial Peripheral Interface (SPI) bus, an Accelerated Graphics Port (AGP) interface, or the like. I/O device118may include a keyboard, a mouse, a display, a printer, a scanner, or the like.

The computing device100may interface to external systems through network interface114. The network interface114may include, but is not limited to, a modem, a Network Interface Card (NIC), or other interfaces for coupling a computing device to other computing devices. A carrier wave signal123may be received/transmitted by network interface114. In the embodiment illustrated inFIG. 1, carrier wave signal123is used to interface computing device100with a network124, such as a Local Area Network (LAN), a Wide Area Network (WAN), the Internet, or any combination thereof. In one embodiment, network124is further coupled to a computing device125such that computing device100and computing device125may communicate over network124.

The computing device100also includes non-volatile storage105on which firmware and/or data may be stored. Non-volatile storage devices include, but are not limited to, Read-Only Memory (ROM), Flash memory, Erasable Programmable Read Only Memory (EPROM), Electronically Erasable Programmable Read Only Memory (EEPROM), Non-Volatile Random Access Memory (NVRAM), or the like.

The mass storage112may include, but is not limited to, a magnetic disk drive, such as a hard disk drive, a magnetic tape drive, an optical disk drive, or the like. It is appreciated that instructions executable by processor102may reside in mass storage112, memory104, non-volatile storage105, or may be transmitted or received via network interface114.

In one embodiment, the computing device100may execute an Operating System (OS). Embodiments of an OS include Microsoft Windows®, the Apple Macintosh operating system, the Linux operating system, the Unix operating system, or the like.

The computing device100may also execute a dynamic binary translator130. The dynamic binary translator130may translate and optimize binary code at runtime for compatibility and performance improvement. The dynamic binary translator130may identify frequently executed code of a program which may be also referred to as hot traces. The dynamic binary translator130may further translate one or more of the hot traces into transactional memory regions to dynamically optimize one or more portions of the running program.

The transactional memory regions provide a concurrency control mechanism similar to database transactions for controlling access to shared memory. Transactional memory regions may be implemented using hardware transactional memory and/or software transactional memory. In software transactional memory, the transaction memory regions comprise a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time in that intermediate states are not visible to other successful transactions. Transaction memory regions are optimistic in that all threads complete modifications to shared memory without regard to other threads, but recording every read and write that the thread makes in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, transaction memory regions place the onus on the reader. The reader after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. In particular, the transaction memory regions have a commit operation in which the changes of a transaction are validated and, if validation is successful, made permanent. The transaction memory regions may also execute an abort operation if a transaction cannot be committed due to conflicting changes or as indicated below early exit from a hot trace. In hardware transactional memory, the transactional memory regions operate in a manner similar to above except hardware actively checks conflict between both writers and readers at memory access time. By packaging hot traces into transaction memory regions, the dynamic binary translator130may dynamically optimize existing binary programs and more fully utilize processing power of computing devices100that provide multiple processing cores.

The dynamic binary translator130may also perform one or more optimization techniques on the identified hot traces based on runtime profiling information. It should be appreciated that the “optimized” code resulting from the one or more optimization techniques does not necessarily result in “optimal” code or code that could not be further improved. The optimization techniques attempt to generate better code based upon some performance category of interest such as bettering the code's memory use, execution time, cache performance, and the like. Such optimization techniques, however, may in fact result in optimized code that performs worse in one or more of the categories of interest than the original code.

Referring now toFIG. 2, aspects of binary translation process200of the dynamic binary translator130are shown. The dynamic binary translator130at block210may identify hot traces of the binary code. The dynamic binary translator130may use a most recent execution tail (MRET) approach to identify hot traces of the binary code. In the MRET approach, hot trace heads are first identified based on profiling information. In one embodiment, each loop head (e.g., a backward branch target) is treated as a candidate trace head. Each candidate trace head is instrumented such that a counter is incremented after each execution of the candidate trace head. When the counter exceeds a certain threshold, the candidate trace head becomes a hot trace head. Then, the dynamic binary translator130may select the hot trace as the execution path from the hot trace head to the most recent execution tail. In another embodiment, the dynamic binary translator130may use a two-pass MRET (MRET2) approach. In the MRET2approach, the hot trace is not simply selected as the execution path from a hot trace head to the most recent execution tail. Instead, hot traces are selected from at least two passes of the MRET approach. In the first pass, the MRET approach is used to select one trace as a potential hot trace. A performance counter is then cleared, the counter is restarted, and another potential hot trace is selected using the MRET in the second pass. Thus, two potential hot traces are identified with the same hot trace head but possible different trace tails. The different trace tails indicate that even though the trace head is hot, the trace tails may not be hot. Embodiments of the MRET2approach select the hot trace as the common path of the two potential hot traces, which is likely to have both a hot head and a hot tail. Additional details regarding the MRET2approach are provided in copending U.S. patent application Ser. No. 11/241,527.

After identifying the hot traces of the binary code, the dynamic binary translator130at block220may insert software counters in off-trace paths that increment each time their respective off-trace code is executed. As shown inFIG. 3-6, hot code traces may have one or more exits310from the hot code trace. The dynamic binary translator130may insert software counters in the off-trace code associated with each of these one or more exits310to obtain runtime metrics for the hot code traces via the off-trace paths. By placing the software counters in the off-trace paths, the runtime performance of the binary code is not generally effected by the dynamic binary translator130gathering runtime metrics as such metrics are gathered in off-trace paths and not the hot traces which account for a large portion of the execution time of the binary code.

In response to one or more software counters exceeding a threshold value, the dynamic binary translator130may record the software counter values at block230in order to retain the runtime metrics associated with the hot traces. Furthermore, the dynamic binary translator130at block240may remove the software counters. For example, the dynamic binary translator130may remove the software counters through relinking of the binary code or via other techniques.

At block250, the dynamic binary translator130may analyze the gathered performance metrics to identify hot traces with high completion ratios. The dynamic binary translator130at block260may select hot traces that have high completion ratios. In one embodiment, the dynamic binary translator130may select hot traces that have a completion ratio that has a predetermined relationship to a threshold value. For example, the dynamic binary translator130may select hot traces that have a completion ratio of at least a 90%.

At block270, the dynamic binary translator130may identify a main exit and side exits of the hot trace. As depicted inFIGS. 3-6, a hot trace may have one or more exits310,320. The dynamic binary translator130may label the most frequently executed exit as the main exit320of the hot trace and the other exits as side exits320of the trace.

The dynamic binary translator130at block280may package the hot trace280based upon the identified main exit320and side exit310. As shown in Table 1, the dynamic binary translator may package the hot traces280based upon the type of hot trace. In particular, a Group 1 trace corresponds to a hot trace that has no back edge and thus does not form a loop and has at least a threshold number of instructions (e.g. 20). An example of a Group 1 trace is shown inFIG. 3. Moreover, as shown inFIG. 3the dynamic binary translator130may associate a transaction start with the beginning of the hot trace, a transaction commit with the end or main exit320of the hot trace, and a transaction abort with any side exits310. In one embodiment, the dynamic binary translator130may associate the transaction abort with a branch instruction by changing the target of the branch instruction to a transaction abort stub label. The transaction abort stub may include instructions that abort the transaction.

TABLE 1GroupSignaturesPackaging1Trace Size >=20TM_START: begin of traceInstructionsTM_COMMIT: end of traceno back edge (no loop)TM_ABORT: any side exit(s) ontrace2Trace Size >=20TM_START: immediatelyInstructionsbefore the back edge's branchHas unconditionaltargetback edgeTM_COMMIT: the exit(s) on(unconditional loop)trace with the highest off-tracecounter valueTM_ABORT: any other exit(s)within the back edge coveredarea on trace3Trace Size >=20 InstructionTM_START: immediatelyHas conditional back edgebefore the back edge's branch(conditional loop)targetTM_COMMIT: immediatelyafter the back edge's branchsourceTM_ABORT: any side exit(s) ontrace4Trace Size <20 InstructionsUnroll a certain factor such thatHas either conditional orthe unrolled trace size reachesunconditional20 Instructionsback edge (loop)Match Group 2 or Group 3,depending on its back edgetype, and use respectivepackaging scheme

Group 2 corresponds to a hot trace that has an unconditional back edge thus forming an unconditional loop and at least a threshold number of instructions (e.g. 20). An example of a Group 2 trace is shown inFIG. 4. As shown inFIG. 4, the trace includes an unconditional branch or jump instruction330that targets a prior instruction340of the hot trace thus forming an unconditional loop between instructions330,340. The dynamic binary translator130in response to identifying a Group 2 trace may associate a transaction start with an instruction345that is before the target instruction340of the unconditional branch330. The dynamic binary translator130further associates a transaction commit with the main exit320of the hot trace, and a transaction abort with any side exits310.

Group 3 corresponds to a hot trace that has a conditional back edge thus forming a conditional loop and at least a threshold number of instructions (e.g. 20). An example of a Group 3 trace is shown inFIG. 5. As shown inFIG. 5, the trace includes a conditional branch or jump instruction370that targets a prior instruction375of the hot trace thus forming an conditional loop between instructions370,375. The dynamic binary translator130in response to identifying a Group 3 trace may associate a transaction start with an instruction380that is before the target instruction375of the conditional branch370. The dynamic binary translator130further associates a transaction commit with the main exit320of the hot trace which is the instruction following the conditional branch370, and a transaction abort with any side exits310.

Group 4 corresponds to a hot trace that has a conditional back edge or an unconditional back edge thus forming a conditional loop or an unconditional loop but has less than a threshold number of instructions (e.g. 20). An example of a Group 4 trace is shown inFIGS. 6A and 6B. As shown inFIGS. 6A and 6B, the trace includes a branch or jump instruction390that targets a prior instruction395of the hot trace thus forming a loop between instructions390,395. The dynamic binary translator130in response to identifying a Group 4 trace may unroll the loop a certain factor of times (e.g. 4) to obtain a trace having at least the threshold number of instructions (e.g. 20).FIG. 6Ashows the Group 4 trace prior to unrolling the loop andFIG. 6Bshows the Group 4 trace after unrolling the loop. After unrolling the loop, the dynamic binary translator130may handle the unrolled loop in the manner similar to a Group 2 or Group 3 trace.

Referring back toFIG. 2, the dynamic binary translator130after packaging the hot traces in transaction memory regions may analyze the transaction memory regions at block285and optimize the transaction memory regions at block290based upon the analysis. Since the binary codes are generally produced by optimizing compilers with highest optimization level turned on, the dynamic binary translator130may utilize optimizations that are unlikely to conflict with the optimizations of the static optimizing compiler used to produce the original binary code. In one embodiment, the dynamic binary translator130includes a single pass optimizer that covers many different types of optimizations. In particular, the optimizer may perform Local Value Numbering (LVN) optimizations. Local Value Numbering optimizations natively covers Copy Propagation (CP) optimizations, Constant Subexpression Elimination (CSE) optimizations and Dead Code Elimination (DCE) optimizations in a single pass. Further, the optimizer implements the LVN optimizations without a Control Flow Graph (CFG) or Data Flow Analysis (DFA) thus reducing overhead associated with the dynamic optimizations of the dynamic binary translator130.

Finally, after optimizing the transaction memory regions, the dynamic binary translator130may replace the original hot traces with the optimized transaction memory regions at block295. Accordingly, the computing device100may continue with the execution of the binary program and the optimized transaction memory regions. In particular, multiple threads of the computing device100may execute the optimized transaction memory regions in parallel thus resulting in fuller usage of the multiple cores of the computing device100than the original binary.