Dispatching of instructions for execution by heterogeneous processing engines

An embodiment of a computing system is configured to process data using a multithreaded SIMD architecture that includes heterogeneous processing engines to execute a program. The program is constructed of various program instructions. A first type of the program instructions can only be executed by a first type of processing engine and a second type of program instructions can only be executed by a second type of processing engine. A third type of program instructions can be executed by the first and the second type of processing engines. An instruction dispatcher is configured to identify and remove program instruction execution conflicts for the heterogeneous processing engines to improve instruction execution throughput.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to processing data using heterogeneous processing engines and more specifically to a system and method for dispatching instructions for execution by heterogeneous processing engines.

2. Description of the Related Art

Current computing systems configured to execute programs include either fixed function computation units configured to execute a particular program instruction or set of program instructions or homogeneous processing engines configured to execute any valid program instruction. More recently, computing systems include heterogeneous processing engines, where different types of processing engines may each execute a subset of the different program instructions. In order to maximize processing throughput, it is desirable to distributing program instructions to the different processing engines so that each of the different types of processing engines are fully utilized.

Accordingly, what is needed in the art is systems and methods for improving program instruction execution throughput for computing systems that include heterogeneous processing engines.

SUMMARY OF THE INVENTION

An embodiment of a computing system is configured to process data using a multithreaded single instruction, multiple data (SIMD) architecture that includes heterogeneous processing engines to execute a program. The program is constructed of various program instructions. A first type of the program instructions can only be executed by a first type of processing engine and a second type of program instructions can only be executed by a second type of processing engine. A third type of program instructions can be executed by the first and the second type of processing engines. An instruction dispatcher may be configured to dynamically dispatch program instructions based on the type of processing engine that can execute each program instruction, in order to balance the workload between the heterogeneous processing engines.

Various embodiments of a method of the invention for dispatching instructions for execution in a SIMD (single-instruction multiple-data) architecture with heterogeneous processing engines include loading program instruction dispatch slots from dispatch queues and selecting instructions from the dispatch slots for parallel execution by heterogeneous processing engines. First dispatch slots are loaded with first program instructions that are highest priority program instructions from the dispatch queues. Second dispatch slots are loaded with second program instructions that are highest priority non-conflicting program instructions from the dispatch queues. The non-conflicting program instruction is a multi issue program instruction or is a program instruction that can be executed by a different type of the heterogeneous processing engines that can execute the program instruction in the first dispatch slot. When an execution conflict exists between the first program instructions a conflicting first program instruction is swapped with one of the second program instructions in order to output instructions for parallel execution.

Various embodiments of the invention include a system for dispatching program instructions for execution in a SIMD (single-instruction multiple-data) architecture that includes heterogeneous processing engines. The system includes a first dispatch queue, a second dispatch queue, and an instruction selection unit. The first dispatch queue is configured to store program instructions of a first type, program instructions of a second type, and program instructions of a third type. The program instructions of the first type can be executed by a first type of the heterogeneous processing engines. The program instructions of the second type can be executed only by a second type of the heterogeneous processing engines. The program instructions of the third type can be executed by the first type of the heterogeneous processing engines and the second type of the heterogeneous processing engines. The second dispatch queue is configured to store program instructions of the first type, program instructions of the second type, and program instructions of the third type. The instruction selection unit is coupled to the first dispatch queue and the second dispatch queue and configured to select highest priority program instructions from the dispatch queues as first program instructions that are loaded into first dispatch slots and highest priority non-conflicting program instructions from the dispatch queues as second program instructions that are loaded into second dispatch slots.

DETAILED DESCRIPTION

System Overview

FIG. 1is a block diagram illustrating a computer system configured to implement one or more aspects of the present invention.FIG. 1is a block diagram of a computer system100according to an embodiment of the present invention. Computer system100includes a central processing unit (CPU)102and a system memory104communicating via a bus path that includes a memory bridge105. Memory bridge105, which may be, e.g., a Northbridge chip, is connected via a bus or other communication path106(e.g., a HyperTransport™ link) to an input/output (I/O) bridge107. I/O bridge107, which may be, e.g., a Southbridge chip, receives user input from one or more user input devices108(e.g., keyboard, mouse) and forwards the input to CPU102via path106and memory bridge105. A parallel processing subsystem112is coupled to memory bridge105via a bus or other communication path113(e.g., a peripheral component interconnect (PCI) Express, Accelerated Graphics Port, or HyperTransport™ link); in one embodiment parallel processing subsystem112is a graphics subsystem that delivers pixels to a display device110(e.g., a conventional cathode ray tube (CRT) or liquid crystal display (LCD) based monitor). A system disk114is also connected to I/O bridge107. A switch116provides connections between I/O bridge107and other components such as a network adapter118and various add-in cards120and121. Other components (not explicitly shown), including universal serial bus (USB) or other port connections, compact disk (CD) drives, digital versatile disk (DVD) drives, film recording devices, and the like, may also be connected to I/O bridge107. Communication paths interconnecting the various components inFIG. 1may be implemented using any suitable protocols, such as PCI, PCI Express (PCI-E), accelerated graphics port (AGP), HyperTransport™, or any other bus or point-to-point communication protocol(s), and connections between different devices may use different protocols as is known in the art.

An embodiment of parallel processing subsystem112is shown inFIG. 2. Parallel processing subsystem112includes one or more parallel processing units (PPUs)202, each of which is coupled to a local parallel processing (PP) memory204. In general, a parallel processing subsystem includes a number U of PPUs, where1. (Herein, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed.) PPUs202and PP memories204may be implemented, e.g., using one or more integrated circuit devices such as programmable processors, application specific integrated circuits (ASICs), and memory devices.

As shown in detail for PPU202(0), each PPU202includes a host interface206that communicates with the rest of system100via communication path113, which connects to memory bridge105(or, in one alternative embodiment, directly to CPU102). In one embodiment, communication path113is a PCI-E link, in which dedicated lanes are allocated to each PPU202as is known in the art. Other communication paths may also be used. Host interface206generates packets (or other signals) for transmission on communication path113and also receives all incoming packets (or other signals) from communication path113and directs them to appropriate components of PPU202. For example, commands related to processing tasks may be directed to a front end unit212while commands related to memory operations (e.g., reading from or writing to PP memory204) may be directed to a memory interface214. Host interface206, front end unit212, and memory interface214may be of generally conventional design, and a detailed description is omitted as not being critical to the present invention.

Each PPU202advantageously implements a highly parallel processor. As shown in detail for PPU202(0), a PPU202includes a number C of cores208, where C1. Each processing core208is capable of executing a large number (e.g., tens or hundreds) of threads concurrently, where each thread is an instance of a program; one embodiment of a multithreaded processing core208is described below. Cores208receive processing tasks to be executed via a work distribution unit210, which receives commands defining processing tasks from a front end unit212. Work distribution unit210can implement a variety of algorithms for distributing work. For instance, in one embodiment, work distribution unit210receives a “ready” signal from each core208indicating whether that core has sufficient resources to accept a new processing task. When a new processing task arrives, work distribution unit210assigns the task to a core208that is asserting the ready signal; if no core208is asserting the ready signal, work distribution unit210holds the new processing task until a ready signal is asserted by a core208. Those skilled in the art will recognize that other algorithms may also be used and that the particular manner in which work distribution unit210distributes incoming processing tasks is not critical to the present invention.

Cores208communicate with memory interface214to read from or write to various external memory devices. In one embodiment, memory interface214includes an interface adapted to communicate with local PP memory204, as well as a connection to host interface206, thereby enabling the cores to communicate with system memory104or other memory that is not local to PPU202. Memory interface214can be of generally conventional design, and a detailed description is omitted.

Cores208can be programmed to execute processing tasks relating to a wide variety of applications, including but not limited to linear and nonlinear data transforms, filtering of video and/or audio data, modeling operations (e.g., applying laws of physics to determine position, velocity and other attributes of objects), image rendering operations (e.g., vertex shader, geometry shader, and/or pixel shader programs), and so on. PPUs202may transfer data from system memory104and/or local PP memories204into internal (on-chip) memory, process the data, and write result data back to system memory104and/or local PP memories204, where such data can be accessed by other system components, including, e.g., CPU102or another parallel processing subsystem112.

Referring again toFIG. 1, in some embodiments, some or all of PPUs202in parallel processing subsystem112are graphics processors with rendering pipelines that can be configured to perform various tasks related to generating pixel data from graphics data supplied by CPU102and/or system memory104via memory bridge105and bus113, interacting with local PP memory204(which can be used as graphics memory including, e.g., a conventional frame buffer) to store and update pixel data, delivering pixel data to display device110, and the like. In some embodiments, parallel processing subsystem112may include one or more PPUs202that operate as graphics processors and one or more other PPUs202that are used for general-purpose computations. The PPUs may be identical or different, and each PPU may have its own dedicated PP memory device(s) or no dedicated PP memory device(s).

In operation, CPU102is the master processor of system100, controlling and coordinating operations of other system components. In particular, CPU102issues commands that control the operation of PPUs202. In some embodiments, CPU102writes a stream of commands for each PPU202to a pushbuffer (not explicitly shown inFIG. 1), which may be located in system memory104, PP memory204, or another storage location accessible to both CPU102and PPU202. PPU202reads the command stream from the pushbuffer and executes commands asynchronously with operation of CPU102.

The connection of PPU202to the rest of system100may also be varied. In some embodiments, PP system112is implemented as an add-in card that can be inserted into an expansion slot of system100. In other embodiments, a PPU202can be integrated on a single chip with a bus bridge, such as memory bridge105or I/O bridge107. In still other embodiments, some or all elements of PPU202may be integrated on a single chip with CPU102.

A PPU may be provided with any amount of local PP memory, including no local memory, and may use local memory and system memory in any combination. For instance, a PPU202can be a graphics processor in a unified memory architecture (UMA) embodiment; in such embodiments, little or no dedicated graphics (PP) memory is provided, and PPU202would use system memory exclusively or almost exclusively. In UMA embodiments, a PPU may be integrated into a bridge chip or processor chip or provided as a discrete chip with a high-speed link (e.g., PCI-E) connecting the PPU to system memory, e.g., via a bridge chip.

As noted above, any number of PPUs can be included in a parallel processing subsystem. For instance, multiple PPUs can be provided on a single add-in card, or multiple add-in cards can be connected to communication path113, or one or more of the PPUs could be integrated into a bridge chip. The PPUs in a multi-PPU system may be identical to or different from each other; for instance, different PPUs might have different numbers of cores, different amounts of local PP memory, and so on. Where multiple PPUs are present, they may be operated in parallel to process data at higher throughput than is possible with a single PPU.

Systems incorporating one or more PPUs may be implemented in a variety of configurations and form factors, including desktop, laptop, or handheld personal computers, servers, workstations, game consoles, embedded systems, and so on.

Core Overview

FIG. 3is a block diagram of a parallel processing unit220for the parallel processing subsystem112ofFIG. 2, in accordance with one or more aspects of the present invention. PPU202includes a core208(or multiple cores208) configured to execute a large number of threads in parallel, where the term “thread” refers to an instance of a particular program executing on a particular set of input data. In some embodiments, SIMD instruction issue techniques are used to support parallel execution of a large number of threads without providing multiple independent instruction units.

In one embodiment, each core208includes an array of P (e.g.,8,16, etc.) parallel processing engines, processing engines301, processing engines302, processing engine303, and processing engine304, that are configured to receive SIMD instructions from instruction issue and dispatch units312via dispatch selection and crossbar310. Multiple instruction issue and dispatch units312, shown as312-0through312-N, are included in core208.

The processing engines may be configured to perform different operations and therefore may execute different instructions. For example, processing engine301may be configured to perform floating point arithmetic operations (e.g., addition and multiplication), processing engine302may be configured to perform fixed point arithmetic operations, processing engine303may be configured to perform texture mapping operations, and processing engine304may be configured to perform load and store operations by reading and writing entries in a shared memory306. Dispatch selection and crossbar310selects instructions for parallel execution and routes each instruction to the processing engine, e.g.,301,302,303, or304that is specified by the instruction and/or configured to execute the instruction.

Each instruction issue and dispatch unit312may be configured to output one instruction per clock cycle. The number of instruction issue and dispatch units312may vary for each embodiment. However, in order to provide enough instructions in a clock cycle for processing engines301,302,303, and304, the number of instruction issue and dispatch units312can match the number of instructions that can be accepted by processing engines301,302,303, and304each clock cycle. Note, a single instruction is provided for parallel execution by one or more processing engines301in a clock cycle. Likewise, a different single instruction is provided for parallel execution by one or more processing engines302in a clock cycle and two other instructions are provided for parallel execution by processing engine303and304. One or more of processing engines301,302,303, and304may be configured to accept a new instruction less frequently than every clock cycle. In an embodiment of the present invention in which processing engine301accepts an instruction every clock cycle and processing engines302303, and304accept an instruction every third clock cycle only two instruction issue and dispatch units312are needed to provide instructions to dispatch selection and crossbar310. Alternatively, a single instruction issue and dispatch unit312(rather than N+1 instruction issue and dispatch units312) may be configured to fetch N+1 instructions in one clock cycle for processing engines301,302,303, and304.

The functional units in each processing engine301,302,303, and304may be pipelined, allowing a new instruction to be issued before a previous instruction has finished, as is known in the art. In one embodiment, the functional units support a variety of operations including comparison operations, Boolean operations (AND, OR, XOR), bit-shifting, and computation of various algebraic functions (e.g., planar interpolation, trigonometric, exponential, and logarithmic functions, etc.). Some operations may be performed by different processing engines, allowing those program instructions to be executed by two or more different processing engines. Program instructions that can only be executed by one type of processing engine, e.g., processing engine301, processing engine302, processing engine303, or processing engine304must be executed by that type of processing engine. An advantage of restricting the operations performed by a particular processing engine is that the performance of the processing engine may be optimized for that operation. Therefore, heterogeneous processing engines may provide in a greater throughput and/or reduced circuitry, which may reduce the overall die area and power consumption compared with homogeneous processing engines. Furthermore, the architecture is easily scaled to increase or decrease processing throughput by adding or omitting additional processing engines and increasing or decreasing the capacity of dispatch selection and crossbar310. This flexibility is possible since any processing engine may execute instructions (of the corresponding type) for any thread.

Each processing engine301,302,303, and304stores its local input data, intermediate results, and the like, in local register files (LRF) within instruction issue and dispatch units312. Register file crossbar320allows each processing engine301,302,303, and304to access any entry in the local register files within instruction issue and dispatch units312. Each processing engine301,302,303, and304also has access (through processing engine304) to an on-chip shared memory306in core208. Shared memory306may be as large as desired, and in some embodiments, any processing engine301,302,303, and304can read to or write from any location in shared memory306with equally low latency (e.g., comparable to accessing local register file304).

In addition to shared memory306, some embodiments also provide an on-chip instruction cache311, which may be implemented, e.g., as a conventional RAM or cache. In some embodiments of the present invention, a parameter cache is also included in core208that can be used, e.g., to hold state parameters and/or other data (e.g., various constants) that may be needed by multiple threads. Processing engines301,302,303, and304also have access via memory interface214to off-chip “global” memory320, which can include, e.g., PP memory204and/or system memory104, with system memory104being accessible by memory interface214via host interface206as described above. It is to be understood that any memory external to PPU202may be used as global memory320. Processing engines301,302,303, and304can be coupled to memory interface214via an interconnect (not explicitly shown) that allows any processing engine301,302,303, and304to access global memory320.

Dispatch selection and crossbar310is configured such that, for any given processing cycle, instructions (INSTR) may be issued to all processing engines301,302,303, and304. Thus, at the level of a single clock cycle, core208implements a P-way SIMD microarchitecture for each type of processing engine, where P is the number of processing engines of a particular type. As previously explained, instruction issue and dispatch units312are configured to output program instructions for processing engines301,302,303, and304to dispatch selection and crossbar310at a rate that those engines can consume the program instructions. Since each processing engine301,302,303, and304is pipelined, supporting up to G threads concurrently, core208in this embodiment can have up to P*G threads executing concurrently for each type of processing engine. For instance, if P=16 and G=24, then core208supports up to 384 concurrent threads for one type of processing engine.

Because dispatch selection and crossbar310issues an instruction to a processing engines of a particular type in parallel, core208is advantageously used to process threads in “SIMD thread groups.” As used herein, a “SIMD thread group” refers to a group of up to P threads of execution of the same program on different input data, with one thread of the group being assigned to each processing engine of the particular type. A SIMD thread group may include fewer than P threads, in which case some of the processing engines of the particular type will be idle during cycles when that SIMD thread group is being processed. A SIMD thread group may also include more than P threads, in which case processing will take place over consecutive clock cycles. Since each processing engine301,302,303, and304can support up to G threads concurrently, it follows that up to G SIMD thread groups can be executing in core208at any given time.

On each clock cycle, an instruction that is issued to up to P threads making up a selected one of the SIMD thread groups. To indicate which thread is currently active, an “active mask” for the associated thread may be included with the instruction. Processing engines301,302,303, and304use the active mask as a context identifier, e.g., to determine which portion of its assigned subunit in local register files304should be used when executing the instruction. Thus, in a given cycle, the same type of processing engines301,302,303, or304in core208are nominally executing the same instruction for different threads in the same SIMD thread group. (In some instances, some threads in a SIMD thread group may be temporarily idle, e.g., due to conditional or predicated instructions, divergence at branches in the program, or the like.)

Operation of core208is advantageously controlled via a core interface303. In some embodiments, core interface303receives data to be processed (e.g., primitive data, vertex data, and/or pixel data) as well as state parameters and commands defining how the data is to be processed (e.g., what program is to be executed) from work distribution unit210. Core interface303can load data to be processed into shared memory306and parameters into a parameter memory. Core interface303also initializes each new thread or SIMD thread group in instruction issue and dispatch units312, then signals instruction issue and dispatch units312to begin executing the threads by issuing instructions. When execution of a thread or SIMD thread group is completed, core208advantageously notifies core interface303. Core interface303can then initiate other processes, e.g., to retrieve output data from shared memory306and/or to prepare core208for execution of additional threads or SIMD thread groups.

It will be appreciated that the core architecture described herein is illustrative and that variations and modifications are possible. Any number of processing engines may be included. In some embodiments, each processing engine has its own local register file, and the allocation of local register file entries per thread can be fixed or configurable as desired. Further, while only one core208is shown, a PPU202may include any number of cores208, which are advantageously of identical design to each other so that execution behavior does not depend on which core208receives a particular processing task. Each core208advantageously operates independently of other cores208and has its own processing engines, shared memory, and so on.

Multithreaded Instruction Processing

FIG. 4Ais a block diagram of one of the instruction issue and dispatch units312for the parallel processing unit202ofFIG. 3, in accordance with one or more aspects of the present invention. Instruction issue and dispatch unit312includes an instruction fetch unit400, operand collector445, local register file304, and dispatch queue440, and sequencer442. Instruction fetch unit400receives data to be processed and a program identifier corresponding to a program that should be used to process the data. A program counter storage405stores the active program counter, indicating the next program instruction (INSTR) that should be executed for each SIMD thread group. When G=24, program counter storage405stores24active program counters. Similarly, thread state storage420stores an active mask for each SIMD thread group, where each bit of the active mask corresponds to an integer number of the P processing engines of each type301,302,303, and304. Therefore, the number of bits in the active mask for each processing engine type is the number of threads in a SIMD thread group.

Execution stacks455include a stack for each SIMD thread group that is used during control instruction processing to push and pop state information. In some embodiments of the present invention, execution stacks455may spill entries to global memory320for any execution stacks455that overflow and restore spilled entries when space is available in execution stacks455. Controller415pushes and pops entries from execution stacks455as control instructions, such as branch, return, call, and break instructions are executed.

Controller415provides an active program counter and active mask for a SIMD thread group to instruction buffer430. Instruction buffer430obtains the instruction corresponding to the active program counter and outputs the instruction and active mask to dispatch selection and crossbar310. Instruction buffer430reads the instructions from instruction memory (global memory320or other memory) as needed, using caching techniques known to those skilled in the art. Instruction buffer430outputs the instructions to dispatch queue440. Dispatch queue440interfaces with operand collector440to gather the operands that are specified for each instruction. Once all of the operands are gathered for an instruction, the instruction is eligible for dispatch by dispatch selection and crossbar310.

In one embodiment, local register file304is physically or logically divided into subunits, each having some number of entries (where each entry might store, e.g., a 32-bit word). One subunit is assigned to each processing engine301,302,303, and304, and corresponding entries in different subunits can be populated with data for different threads executing the same program to facilitate SIMD execution. In some embodiments, each processing engine301,302,303, and304can only access LRF entries in the subunit assigned to it and register file crossbar320may be omitted. The total number of entries in local register files304is advantageously large enough to support multiple concurrent threads per processing engine301,302,303, and304.

Dispatch queue440presents the eligible instructions to dispatch selection and crossbar310. When an instruction is selected for dispatch by dispatch selection and crossbar310, sequencer442outputs any target program counter (address) specified by the instruction to controller415. Some program instructions, such as control instructions that do not perform branching based on a register value or other data are intercepted by sequencer442and processed within instruction issue and dispatch unit312. Those control instructions are not output to dispatch selection and crossbar310. Other eligible instructions from dispatch queues440are presented to dispatch selection and crossbar310. Dispatch selection and crossbar310selects instructions for execution from the eligible instructions presented by instruction queues440, as described in conjunction withFIGS. 4B, 5A, and 5B.

Note that sequencer442presents a variety of instructions for execution some of which are multi issue (can be executed by more than one type of processing engine) and others that can only be executed by one type of processing engines301,302,303, and304. Dispatch selection and crossbar310selects instructions for each type of processing engine and stores each selected instruction to a set of slots that is coupled to each dispatch queue440. Dispatch selection and crossbar310dispatches the selected instructions from the slots through a crossbar to processing engines301,302,303, and304. In some embodiments of the present invention, each dispatch queue440narrows the number of eligible instructions that dispatch selection and crossbar310selects from. For example, dispatch queue440may be configured to present a small number of eligible instructions, multi issue instructions and one instruction for each type of processing engine that can only by executed by that type of processing engine.

FIG. 4Bis a block diagram of dispatch selection and crossbar310for the parallel processing unit202ofFIG. 3, in accordance with one or more aspects of the present invention. Dispatch selection and crossbar310includes a set of slots460for each dispatch queue440, shown as slot sets460-0through460-N, corresponding with instruction issue and dispatch unit312-0through312-N. Dispatch selection and crossbar310also includes a crossbar435that is configured to route the instructions from first slots470-0through470-N for output to processing engines301,302,303, and304. As previously explained, all processing engines of a particular type received the same instruction. In the embodiment shown inFIG. 4B, some of the processing units do not accept a new instruction for processing each clock cycle, therefore the number dispatch queues440is not equal to the number of different processing unit types.

In some embodiments of the present invention, a first type of program instructions can only be executed by processing engines301. The first type of program instructions may include floating point arithmetic operations (excluding the multiply operation since it is included in the second type). A second type of program instructions can be executed by processing engines301and processing engines302and are referred to as “multi issue” instructions, meaning that any processing engine configured to receive instructions from dispatch selection and crossbar310is capable of executing the instruction. The second type of program instructions may include move and a floating point multiply operations. A third type of program instructions can only be executed by processing engines302. The third type of program instructions may include fixed integer arithmetic operations such as addition, subtraction, and reciprocal. In some embodiments of the present invention, processing engine303may be configured to process program instructions of a fourth type, such as texture mapping program instructions, e.g., level of detail, texture address, and other computations for point sample, bilinear, trilinear, anisotropic texture mapping, and the like. Processing engine304may be configured to process load and store program instructions to read and write entries in shared memory306.

An advantage of configuring more than one of the heterogeneous processing engines to process some instructions is that those program instructions, i.e., the second type or other non-conflicting instructions, can be selected and dispatched for execution by the type of heterogeneous processing engine with a lower workload to dynamically balance the workload. Balancing the workload permits better utilization of each processing engine to improve overall instruction execution throughput. When commonly used instructions are multi issue instructions dispatch selection and crossbar310is better able to balance the processing workload more evenly than when only a small portion of the instructions in a program are multi issue.

Dispatch selection and crossbar310outputs program instructions stored in one or more first slots470to one or more of processing engines301,302,303, and304each clock cycle. When at least one program instruction is present in a first queue of dispatch queues440, dispatch selection and crossbar310selects and loads the highest priority program instruction for dispatch queue440-0into first slot470-0.

The highest priority program instruction is the instruction that has been present in the dispatch queue440for the greatest number of clock cycles. In some embodiments of the present invention, the greatest number of clock cycles is measured once the program instruction is eligible for dispatch. In other embodiments of the present invention, the greatest number of clock cycles is measured from the time the program instruction is issued to dispatch queue440. Alternatively, the highest priority instruction may be an instruction in the instruction issue and dispatch unit312that has the least number of eligible instructions or that has the most instructions in dispatches queue440. The highest priority program instruction may be a multi issue instruction or an instruction that can only be executed by one type of processing engine, e.g., the first, third, fourth, or fifth type of program instruction.

When at least one non-conflicting program instruction is present in the first queue, dispatch queue440-0, dispatch selection and crossbar310selects and loads the highest priority non-conflicting program instruction for the first queue into second slot480-0. A multi issue program instruction is a non-conflicting program instruction since more than one processing engine can execute the multi issue instruction. Therefore, the multi issue program instruction can be output for execution in parallel with the program instruction in first slot470-1. However, it is possible to select a non-conflicting program instruction for second slot480that is not a multi issue instruction. Importantly, selecting the instructions for each slot sets460is performed independently, so the selection and loading of the slot sets460may be performed in parallel for dispatch queues440.

When at least one program instruction is present in a second queue, dispatch queue440-1, dispatch selection and crossbar310selects and loads the highest priority program instruction for the second queue into first slot470-1. Finally, when at least one multi issue program instruction is present in the second queue, dispatch selection and crossbar310selects and loads the highest priority non-conflicting program instruction for the second queue into second slot480-1. In other embodiments of the present invention, program instructions are selected based on a different set of criteria, such as thread priority, to load first slots470and second slots480. Instruction selection unit450also loads the first and second slots of slot sets460-2and460-3when eligible instructions are available in dispatch queue440-2and440-3, respectively.

Instruction selection unit450determines if an execution conflict exists between the program instructions stored in first slots470, i.e., the highest priority program instruction from the first, second, third, and fourth dispatch queues. A conflict exists between the two or more program instructions when some of the instructions can only be executed by the same type of processing engine since only one program instruction can be dispatched in a single clock cycle for execution by each processing engine. Instruction selection unit450also determines if a program instruction is not stored in any first slots470and transfers a non-conflicting program instruction from a second slot480to populate the empty slot.

In some embodiments of the present invention, a compiler specifies a target, the type of heterogeneous processing engine, e.g., processing engine301,302,303, or304, that one or more program instructions are assigned to for execution. The following sequence includes move (MOV) instructions that are specified for execution by a particular target or are specified for dynamic dispatching by dispatch selection and crossbar310at execution time.

Instruction selection unit450may be configured to use the specified targets when determining whether or not an execution conflict exists. An advantage of postponing the determination until the program is executing is that instruction selection unit450may perform better load balancing by accounting for varying execution conditions as they occur, such as memory access latencies, branch execution, and the like.

When an execution conflict does exist, instruction selection unit450swaps the conflicting program instruction that is stored in a first slot470with a non-conflicting program instruction that is stored in a second slot480, as described in conjunction withFIGS. 5A and 5B.

FIG. 5Ais a flow diagram of method steps for dispatching the instructions for execution by the heterogeneous processing engines301,302,303, or304, in accordance with one or more aspects of the present invention.FIG. 5Aillustrates instruction dispatching when four types of heterogeneous processing engines are used, e.g., processing engines301,302,303, and304. In other embodiments of the present invention, fewer or additional heterogeneous processing engines may be used, and those skilled in the art may extend the described method to include those additional heterogeneous processing engines in the dispatching process.

In step500instruction selection unit450loads a first slot470with the highest priority program instruction from a first dispatch queue440. Note that the highest priority program instructions from any dispatch queue440may be of the first type, second type, or third type. In step505instruction selection unit450loads second slot480with the highest priority non-conflicting program instruction from the first dispatch queue440. When a non-conflicting instruction is not available in a dispatch queue440, the corresponding second slot480is left empty. Similarly, when a dispatch queue440is empty, both slots in the corresponding slot set460are left empty.

In step510instruction selection unit450determines if there is another dispatch queue440and slot set460to be filled with instructions, and if so, steps500and505are repeated. Otherwise, all of the slots460that can be filled with eligible instructions have been filled, and in step512instruction selection unit450determines if any instruction conflicts exist between the first slots470. If all of the instructions stored in first slots470can be output by dispatch selection and crossbar310in parallel, i.e., in a single clock cycle, then no instruction conflict exists. In some cases, it may not be necessary to output all of the instructions in a single clock cycle since some processing units may not be able to accept an instruction during that clock cycle. In those cases, no instruction conflict exists if all of the instructions that can be accepted can be output in parallel.

If, in step512instruction selection unit450determines that an instruction conflict exist between the first slots470, then in step515instruction selection unit530removes the first slot470conflicts, as described in conjunction withFIG. 5B, and then proceeds to step525. In step525instruction selection unit450determines if at least one of the first slots470is empty, and, if not, instruction selection unit450proceeds directly to step535. Otherwise, in step530instruction selection unit450fills the empty first slots470with non-conflicting instructions from second slots480. Instruction selection unit450may be configured to select the highest priority non-conflicting instructions from second slots480.

When an execution conflict does not exist, in step535instruction selection unit530outputs the selected instructions that are in first slots470to the processing engines301,302,303, and304that are able to accept an instruction. Instruction selection unit530provides information identifying the type of processing engine that should be used to execute the selected instructions in order for dispatch crossbar to route each instruction to a processing engine of a corresponding type. Note that when instructions remain in slot sets460, those instructions are retained and not overwritten when steps500and505are completed.

FIG. 5Bis a flow diagram of step515ofFIG. 5A, in accordance with one or more aspects of the present invention. In step512instruction selection unit450selects a conflicting instruction that has the lowest priority and occupies a first slot460. In step514instruction selection unit450swaps a non-conflicting instruction that occupies a second slot480with the selected instruction to remove the conflict. In step516instruction selection unit450determines if another conflict exists, and, if so, steps512and514are repeated. Otherwise, instruction selection unit450proceeds to step525.

Swapping a non-conflicting instruction from one of second slots480into a first slot460ensures that the program instructions stored in first slots460can be dispatched simultaneously since the execution conflict is removed. In some embodiments of the present invention, a round robin scheme is used to override the preference given to the highest priority slot so that some program instructions from the dispatch queue440that does not include the highest priority program instructions are dispatched.

An advantage of the disclosed system and method is that instruction execution throughput may be improved by eliminating any execution conflicts during instruction dispatch to the different heterogeneous processing engines. A compiler can specify a target processing engine for each multi issue instruction or the compiler can specify that one or more of the multi issue instructions should be dynamically dispatched to balance the processing workload between the different processing engines to improve overall instruction execution throughput.