Single thread performance in an in-order multi-threaded processor

A mechanism is provided for improving single-thread performance for a multi-threaded, in-order processor core. In a first phase, a compiler analyzes application code to identify instructions that can be executed in parallel with focus on instruction-level parallelism and removing any register interference between the threads. The compiler inserts as appropriate synchronization instructions supported by the apparatus to ensure that the resulting execution of the threads is equivalent to the execution of the application code in a single thread. In a second phase, an operating system schedules the threads produced in the first phase on the hardware threads of a single processor core such that they execute simultaneously. In a third phase, the microprocessor core executes the threads specified by the second phase such that there is one hardware thread executing an application thread.

BACKGROUND

The present application relates generally to an improved data processing apparatus and method and more specifically to the design of multithreaded microprocessors.

Modern microprocessors are designed out of complementary metal oxide semiconductor (CMOS) technology, which has heretofore obeyed the Moore's conjecture, which predicted that the number of transistors within a given chip area would double roughly every 18 months. This doubling comes from predictable and continuous improvement, in lithography that allows the mask of a CMOS chip to improve in resolution by a factor of two every 18 months. Microprocessor design has benefited greatly from this progress, which has translated over the years to improved processor performance as smaller transistors allow faster switching, which in turn allows the processor to run at increasing frequency.

Furthermore, designers have used techniques that allow a processor to execute instructions of a program in a different order than the one specified in the application code. This mode, called out-of-order processing, enables processors to extract more performance than was possible by just exploiting frequency improvement. In its simplest mode, the hardware examines a plurality of instructions that are about to run on the processor, and executes as many of them in parallel as far as it can determine that the resulting execution would be equivalent to a sequential execution of the code. This enables the processor to extract instruction-level parallelism (ILP) from application code, resulting in improved performance at the expense of complexity in processor design and more power consumption.

The technique was refined further to include speculative execution, in which the processor would speculatively execute instructions further down the stream in the hope that prior instructions in flight would not violate the equivalence to a sequential execution (e.g., branch prediction, pre fetch data, etc.). If the speculative assumptions hold, the result is faster execution as more instructions are executed per unit of time, whereas if the speculative assumptions turn out to be invalid, the results of the speculation are simply discarded. These techniques exploit all possible avenues to improve performance of a single-thread application at the expense of more complexity and power consumption.

Recently, however, it has become difficult to harness additional frequency increases due to transistor miniaturization, as the resulting heat dissipated by a transistor at higher frequency becomes too concentrated in such a small area that it cannot be removed effectively. As a result, the frequency growth of microprocessors has reached a limit, and designers have resorted to using the additional devices on the processor chip to increase the number of processor cores, compensating for the limited speed of a single core by providing more cores. Additionally, designers have resorted to increasing the number of hardware threads that run in each core, again compensating for the limited speed of a single core by providing more contexts within the core to run additional application codes.

Additionally, techniques for speculative executions, and the power overhead necessary to identify ILP also added to the power consumption of the processor. These techniques have become unattractive because of the limited ability to supply power to a single chip due to the physical characteristics of the power supply connections, and the decreasing ability to remove heat concentrated in smaller and smaller devices. These limitations have driven processor designers to focus on simpler cores that run instructions in order of the sequential code specified by the application. These cores, typically called in-order cores, are usually simple in design, consume less power, and are unable to exploit ILP. The designers have compensated for these limitations by increasing the number of threads per core and the number of cores per processor chip.

Increasing the number of cores and the number of threads in a core is beneficial for applications that show natural parallelism, such as throughput-oriented workloads (e.g., Web servers). However, the performance of legacy application code and applications that are not amenable to parallelization cannot benefit from multi-core or multi-threaded processors. These applications have traditionally enjoyed improved performance by relying on the processor design to extract ILP, and on frequency increase, to run applications faster. Such features are no longer dependable due to limited power consumption and heat extraction as mentioned above, and thus single-threaded applications cannot benefit from newer processors. These newer processors are designed for low power consumption and benefit throughput-oriented applications, at the expense of single-thread performance. Therefore, there is a need for a method to allow single-threaded applications to benefit from newer multi-core and multithreaded processors that have limited single thread performance.

SUMMARY

In one illustrative embodiment, a method is provided in a data processing system for improving single-thread performance in an in-order multi-threaded processor core. The method comprises receiving, by a compiler executing on one or more processors in the data processing system, single-threaded application code, analyzing, by the compiler, the single-threaded application code to identify instructions that can be executed in parallel, and generating, by the compiler, multi-threaded application code. The multi-threaded application code comprising a plurality of threads that execute the instructions that can be executed in parallel in separate threads. The method further comprises storing the multi-threaded application code in a memory of the data processing system and outputting the multi-threaded application code to be executed in the in-order multi-threaded processor. The in-order multi-threaded processor core operates in a special mode in which a register file of a first thread within the plurality of threads is shared by all threads executing the multi-threaded application code.

DETAILED DESCRIPTION

The illustrative embodiments provide a mechanism for improving single-thread performance of a multithreaded in-order processor core. According to the illustrative embodiments, a compiler extracts instruction-level parallelism (ILP) from application code by analyzing the code and determining which instructions can be executed on different threads in parallel with a first thread. The compiler decides the number of threads and resulting code for each thread. Additionally, the compiler inserts synchronization (sync) instructions to ensure that the threads remain in sync and that the execution of all threads will be equivalent to a sequential execution of the application code by a single thread. Further, according to the illustrative embodiments, an operating system schedules the threads belonging to the same application which were the output of the compiler unto a single, multithreaded core such that each application thread runs on a given hardware thread. Moreover, according to the illustrative embodiments, the processor core operates in a special mode in which the register file of a first thread is shared by all threads executing the application program. The register file of the first thread will contain the values that would otherwise be computed by running the original, sequential application code in a single thread.

In the following detailed description of example embodiments of the invention, specific example embodiments in which the invention may be practiced are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, architectural, programmatic, mechanical, electrical and other changes may be made without departing from the spirit or scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined by the appended claims and equivalents thereof.

Within the descriptions of the figures, similar elements are provided similar names and reference numerals as those of the previous figure(s). Where a later figure utilizes the element in a different context or with different functionality, the element is provided a different leading numeral representative of the figure number. The specific numerals assigned to the elements are provided solely to aid in the description and not meant to imply any limitations (structural or functional or otherwise) on the described embodiment.

It is understood that the use of specific component, device and/or parameter names (such as those of the executing utility/logic described herein) are for example only and not meant to imply any limitations on the invention. The invention may thus be implemented with different nomenclature/terminology used to describe the components/devices/parameters herein, without limitation. Each term used herein is to be given its broadest interpretation given the context in which that term is used.

With reference now to the figures and in particular with reference toFIG. 1, an example diagram of a data processing environment is provided in which illustrative embodiments of the present invention may be implemented. It should be appreciated thatFIG. 1is only an example and is not intended to assert or imply any limitation with regard to the environments in which aspects or embodiments of the present invention may be implemented. Many modifications to the depicted environments may be made without departing from the spirit and scope of the present invention.

FIG. 1is an example block diagram of a conventional dual threaded processor design showing functional units and registers in which aspects of the illustrative embodiments may be implemented. Processor100comprises a single integrated circuit superscalar microprocessor with dual-thread simultaneous multi-threading (SMT) that may also be operated in a single threaded mode. Accordingly, as discussed further herein below, processor100includes various units, registers, buffers, memories, and other sections, all of which are formed by integrated circuitry.

As shown inFIG. 1, instruction fetch unit (IFU)102connects to instruction cache104. Instruction cache104holds instructions for multiple programs (threads) to be executed. Instruction cache104also has an interface to level 2 (L2) cache/memory106. IFU102requests instructions from instruction cache104according to an instruction address, and passes instructions to instruction decode unit108. In an example embodiment. IFU102may request multiple instructions from instruction cache104for up to two threads at the same time. Instruction decode unit108decodes multiple instructions for up to two threads at the same time and passes decoded instructions to instruction sequencer unit (ISU)109.

Processor100may also include issue queue110, which receives decoded instructions from ISU109. Instructions are stored in the issue queue110while awaiting dispatch to the appropriate execution units. For an in-order processor, issue queue110issues the instructions in order for each thread, and outputs or issues instructions for each thread to execution units112,114,116,118,120,122,124,126, and128of the processor. This process will be described in more detail in the following description.

In an illustrative embodiment, the execution units of the processor may include branch unit112, load/store units (LSUA)114and (LSUB)116, fixed point execution units (FXUA)118and (FXUB)120, floating point execution units (FPUA)122and (FPUB)124, and vector multimedia extension units (VMXA)126and (VMXB)128. Execution units112,114,116,118,120,122,124,126, and128are fully shared across both threads, meaning that execution units112,114,116,118,120,122,124,126, and128may receive instructions from either or both threads. The processor includes multiple register sets130,132,134,136,138,140,142,144, and146, which may also be referred to as architected register files (ARFs).

An ARF is a file where completed data is stored once an instruction has completed execution. ARFs130,132,134,136,138,140,142,144, and146may store data separately for each of the two threads and by the type of instruction, namely general purpose registers (GPRs)130and132, floating point registers (FPRs)134and136, special purpose registers (SPRs)138and140, and vector registers (VRs)144and146. Separately storing completed data by type and by thread assists in reducing processor contention while processing instructions.

The processor additionally includes a set of shared special purpose registers (SPR)142for holding program states, such as an instruction pointer, stack pointer, or processor status word, which may be used on instructions from either or both threads. Execution units112,114,116,118,120,122,124,126, and128are connected to ARFs130,132,134,136,138,140,142,144, and146through simplified internal bus structure149.

In order to execute a floating point instruction, FPUA122and FPUB124retrieves register source operand information, which is input data required to execute an instruction, from FPRs134and136, if the instruction data required to execute the instruction is complete or if the data has passed the point of flushing in the pipeline. Complete data is data that has been generated by an execution unit once an instruction has completed execution and is stored in an ARF, such as ARFs130,132,134,136,138,140,142,144, and146. Incomplete data is data that has been generated during instruction execution where the instruction has not completed execution. FPUA122and FPUB124input their data according to which thread each executing instruction belongs to. For example, FPUA122inputs completed data to FPR134and FPUB124inputs completed data to FPR136, because FPUA122, FPUB124, and FPRs134and136are thread specific.

During execution of an instruction, FPUA122and FPUB124output their destination register operand data, or instruction data generated during execution of the instruction, to FPRs134and136when the instruction has passed the point of flushing in the pipeline. During execution of an instruction, FXUA118, FXUB120, LSUA114, and LSUB116output their destination register operand data, or instruction data generated during execution of the instruction, to GPRs130and132when the instruction has passed the point of flushing in the pipeline. During execution of a subset of instructions, FXUA118, FXUB120, and branch unit112output their destination register operand data to SPRs138,140, and142when the instruction has passed the point of flushing in the pipeline. Program states, such as an instruction pointer, stack pointer, or processor status word, stored in SPRs138and140indicate thread priority152to ISU109. During execution of an instruction, VMXA126and VMXB128output their destination register operand data to VRs144and146when the instruction has passed the point of flushing in the pipeline.

Data cache150may also have associated with it a non-cacheable unit (not shown) which accepts data from the processor and writes it directly to level 2 cache/memory106. In this way, the non-cacheable unit bypasses the coherency protocols required for storage to cache.

In response to the instructions input from instruction cache104and decoded by instruction decode unit108, ISU109selectively dispatches the instructions to issue queue110and then onto execution units112,114,116,118,120,122,124,126, and128with regard to instruction type and thread. In turn, execution units112,114,116,118,120,122,124,126, and128execute one or more instructions of a particular class or type of instructions. For example, FXUA118and FXUB120execute fixed point mathematical operations on register source operands, such as addition, subtraction, ANDing, ORing, and XORing. FPUA122and FPUB124execute floating point mathematical operations on register source operands, such as floating point multiplication and division. LSUA114and LSUB116execute load and store instructions, which move operand data between data cache150and ARFs130,132,134, and136. VMXA126and VMXB128execute single instruction operations that include multiple data. Branch unit112executes branch instructions which conditionally alter the flow of execution through a program by modifying the instruction address used by IFU102to request instructions from instruction cache104.

Instruction completion unit154monitors internal bus structure149to determine when instructions executing in execution units112,114,116,118,120,122,124,126, and128are finished writing their operand results to ARFs130,132,134,136,138,140,142,144, and146. Instructions executed by branch unit112, FXUA118, FXUB120, ISUA114, and LSUB116require the same number of cycles to execute, while instructions executed by FPUA122, FPUB124, VMXA126, and VMXB128require a variable, and a larger number of cycles to execute. Therefore, instructions that are grouped together and start executing at the same time do not necessarily finish executing at the same time. “Completion” of an instruction means that the instruction is finishing executing in one of execution units112,114,116,118,120,122,124,126, or128, has passed the point of flushing, and all older instructions have already been updated in the architected state, since instructions have to be completed in order. Hence, the instruction is now ready to complete and update the architected state, which means updating the final state of the data as the instruction has been completed. The architected state can only be updated in order, that is, instructions have to be completed in order and the completed data has to be updated as each instruction completes.

Instruction completion unit154monitors for the completion of instructions, and sends control information156to ISU109to notify ISU109that more groups of instructions can be dispatched to execution units112,114,116,118,120,122,124,126, and128. ISU109sends dispatch signal158, which serves as a throttle to bring more instructions down the pipeline to the dispatch unit, to IFU102and instruction decode unit108to indicate that it is ready to receive more decoded instructions. While processor100provides one detailed description of a single integrated circuit superscalar microprocessor with dual-thread simultaneous multi-threading (SMT) that may also be operated in a single threaded mode, the illustrative embodiments are not limited to such microprocessors. That is, the illustrative embodiments may be implemented in any type of processor using a pipeline technology.

FIG. 2is a block diagram representation of multithreaded processor core according to an illustrative embodiment. In the depicted example, the processor core supports eight hardware threads. Each hardware thread has a corresponding register file. Thus, register file0200corresponds to thread0, register file1201corresponds to thread1, and so on up to register thread7207corresponding to thread7. An eight-stage pipeline210includes the various processing elements of the processor such as Arithmetic Logical Unit (ALU), Floating Point Unit (FPU), etc. The pipeline is fed from an instruction decode unit220and uses the register files200through207to obtain operands and save results. The design of the pipeline is such that one stage of the pipeline can finish its operation in one clock cycle. The eight threads are scheduled in strict round-robin order, such that at any given cycle, the pipeline contains the eight threads at different stages.

For example, at cycle8, thread0is at stage0, thread1is at stage7, thread2is at stage6, and so on. In the next cycle, thread0is at stage1, thread1is at stage0, thread2is at stage7, and so on. Thus, it takes one thread eight cycles to complete an instruction under the best of circumstances. The core executes as if it is running a single instruction per cycle in aggregate. This design is different from conventional out-of-order (OOO) processors in that no single thread can be at two or more stages of the pipeline. Additionally, the design stipulates that no register is written until stage7(the last pipeline stage). This way, instructions can be aborted without producing any side effects, if necessary. An instruction may be aborted in two cases: 1) when conditional branches are resolved, in which case the thread has to restart from stage0of the pipeline (when its turn on stage0comes); and 2) when a cache read operation fails to get the data because of a cache miss (in which case the thread is postponed until its next turn on the stage). The design stipulates also that stage3is the one at which conditional branches are resolved and cache loads are obtained, and that by stage3all reads of register operands necessary to carry out the operation would have been loaded.

Under normal operation, the processor core has eight simultaneous threads running. All share the pipeline in the manner described. This mode of operation is excellent for throughput-oriented workloads and applications that can be parallelized by the programmer. The eight-stage pipeline including the necessary feedbacks can be implemented with relatively small area and excellent power consumption. However, since every instruction takes 8 cycles to complete, it is clear that this design does not offer good single thread performance.

FIG. 3shows an example program according to an illustrative embodiment. The sample code consists of nine instructions that belong to a single thread. As the example shows, the first instruction completes at cycle I. Eight cycles later, the second instruction completes, and so on, with each instruction completion separated by eight cycles. In the example, the sample code completes by the 65th cycle.

FIG. 4is a block diagram illustrating a compiler for improving single-threaded performance in an in-order multi-threaded processor in accordance with an illustrative embodiment. To improve performance, compiler410analyzes single-threaded code402, such as the sample code shown inFIG. 3, looking for instructions that can be interleaved in parallel. Thus, in this invention, ILP is decided at compile time instead of by the hardware at run time. Compiler410then generates multi-threaded code404.FIG. 5shows an example multi-threaded program in accordance with an illustrative embodiment.

As seen inFIG. 5, compiler410has determined that the original single-thread stream of instructions can be broken into two threads, where the instructions within one thread do not interfere with the other thread. Among the criteria for interference is the use of the register value written by the other thread, or reading an item from the cache written by the other thread, or writing an item to the cache that would overwrite a value to be read by the other thread. The resulting two threads inFIG. 5, for example, do not have any of these interferences. Because the sample code completes with a branch instruction, the two produced threads must be synchronized before proceeding to the branch instructions. This example shows only two threads by way of example to simplify the description. Those skilled in the art may appreciate that the concept extends to more than two threads.

However, running the two threads shown inFIG. 5in two independent hardware threads may not be advantageous. First, the registers must be copied from the first thread's register file to the other before the threads can start. Second, the execution snippet is very short, four instructions per thread. This is too short to justify the context switching required to start the second thread and the associated operating system overhead. Instead, the embodiment according to this invention introduces two new features to the processor. First, the sync instruction is introduced to block progress of the calling thread until all the threads running within the same application would reach the same synchronization. The hardware according to the illustrative embodiment thus provides for a very fast barrier instruction that enables all threads belonging to the application to adjust their progress without introducing the overhead of a context switch or an operating system supported synchronization primitive.

Second, the processor core according to the illustrative embodiment introduces a new mode of operation in which all threads use register file0. This is possible because all accesses to registers by the threads do not interfere with the accesses by other threads. Thus, the actual registers may be used safely within one register file. This obviates the need to copy registers between register files which would have wasted power and reduced performance further.

To support this operation, the operating system scheduler must be modified in the following manner. For applications that were processed by the compiler, such as shown inFIG. 5, for example, the operating system scheduler must schedule the various threads belonging to the application simultaneously. Additionally, the operating system must set the processor mode such that all threads belonging to the application will use the same register file. It is beneficial, though not necessary, that all threads are context switched out and in simultaneously. These modifications are simple in an operating system that supports gang scheduling.

As will be appreciated by one skilled in the art, the present invention may be embodied as a system, method, or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.”Furthermore, aspects of the present invention may take the form of a computer program product embodied in any one or more computer readable medium(s) having computer usable program code embodied thereon.

FIG. 6is a flowchart illustrating operation of a mechanism for improving single-thread performance for a multi-threaded, in-order processor core in accordance with an illustrative embodiment. Operation begins, and in a first phase, a compiler analyzes the application code to identify instructions that can be executed in parallel with focus on instruction-level parallelism (ILP) (block600). The output of the first phase is a number of execution threads corresponding to the maximum level of parallelism that was detected by analyzing the application code, not to exceed the number of threads in a single core, and a corresponding application code for each thread. Additionally, the compiler inserts as appropriate synchronization (sync) instructions supported by the apparatus to ensure that the resulting execution of the threads is equivalent to the execution of the application code in a single thread (block601), in a second phase, an operating system schedules the threads produced in the first phase on the hardware threads of a single processor core such that they execute simultaneously (block602). In a third phase, the processor core executes the threads specified by the second phase such that there is one hardware thread executing an application thread (block603). Thereafter, operation ends. The processor in this case operates in a mode of operation in which all said threads within the processor cores share the register file of a single thread, and use synchronization instructions to ensure that threads stop at execution points specified by the compiler in the first phase. The result is an equivalent execution to a single thread performance in logical results, but with a faster execution time due to the exploitation of ILP by the various threads.

FIG. 7is a flowchart illustrating operation of determining how to split a sequential thread into multiple threads that exploit instruction-level parallelism (ILP). First, the instruction is read into a variable (block700). Then, the compiler decides which of the previous instructions produces a result on which instruction depends (block701). In the example shown inFIG. 3, the second instruction depends on the first one, whereas the third instruction depends on neither.

The compiler determines whether the set of instructions that produces a result on which the current instruction depends is empty (block702). If so, the compiler is free to add this instruction to any of the threads, and thus in the illustrative embodiment compiler adds the current instruction to the thread with the fewest number of assigned instructions (block704), and operation returns to block700to read the next instruction. In the example shown inFIG. 3, the third instruction depends on no other instruction in the set, in which case it is added to the thread with the shortest number of instructions assigned (the second thread).

If the compiler determines that the set of instructions that produces a result on which the current instruction depends is not empty, the compiler determines whether the instructions are in the same thread, T (block703). If so, the compiler assigns the current instruction to join its predecessors in the corresponding thread (block705), and operation returns to block700to read the next instruction. In the example ofFIG. 3, the second instruction is shown to have its dependent in the first thread, and therefore it is added to that thread.

If the compiler determines that the set of instructions that produce a result on which the current instruction depends are not in the same thread in block703, the compiler declares that the current phase is over by adding synchronization (sync) instructions to all threads (block706), and operation returns to block700to read the next instruction.

The example inFIGS. 3 and 5shows that when a branch instruction is encountered, a sync instruction is added to all threads (this is not shown in the flow chart ofFIG. 7to simplify the presentation). The same applies to all control flow instructions such as return from subroutine, conditional branches, and subroutine calls. Note also that it is possible to optimize the flowchart inFIG. 7to postpone the addition of sync instructions in block706, for example, by reordering instructions in a mariner that include subsequent instructions that may not force the sync instructions to be added.

Thus, the illustrative embodiments provide mechanisms for improving single-thread performance for a multi-threaded, in-order processor core. In a first phase, a compiler analyzes the application code to identify instructions that can be executed in parallel with focus on instruction-level parallelism (ILP). The output of the first phase is a number of execution threads corresponding to the maximum level of parallelism that was detected by analyzing the application code, not to exceed the number of threads in a single core, and a corresponding application code for each thread. Additionally, the compiler inserts as appropriate synchronization instructions supported by the apparatus to ensure that the resulting execution of the threads is equivalent to the execution of the application code in a single thread. In a second phase, an operating system schedules the threads produced in the first phase on the hardware threads of a single processor core such that they execute simultaneously. In a third phase, the microprocessor core executes the threads specified by the second phase such that there is one hardware thread executing an application thread. The processor in this case operates in a mode of operation in which all said threads within the processor cores share the register file of a single thread, and use synchronization instructions to ensure that threads stop at execution points specified by the compiler in the first phase. The result is an equivalent execution to a single thread performance in logical results, but with a faster execution time due to the exploitation of ILP by the various threads.