BACKGROUND OF THE INVENTION

This invention relates to efficiently executing instructions at a processor.

With some types of data, such as graphics data, large blocks of data often need to undergo the same processing operations. One example is when changing the brightness of an image. Processing such blocks of data in parallel can reduce the processing time compared with serial processing. Parallel processing can be carried out on a single instruction multiple thread (SIMT) or single instruction multiple data (SIMD) processor, which are microprocessors with execution units, caches and memories as with any other processor, but additionally incorporates the concept of parallel execution of multiple threads or data streams. Each thread executes the same set of instructions but on different data which, instead of having each thread individually fetch data from memory, can be provided to the threads by a single fetch operation to fetch a block of data for each of the threads. SIMT and SIMD processing can provide improved processing efficiency as compared with traditional single instruction single data (SISD) processing.

SIMT and SIMD processors comprise a plurality of processing elements that can concurrently execute the same instructions. Each processing element supports its own thread and each thread runs the same program code, but with different data. One problem with SIMT and SIMD processing is the high cost of a branch operation (as might be caused by a conditional statement in the program code) which results in some data in a block being operated on by one branch of instructions and the remaining data by another branch of instructions the identity of which is not known until the condition has been met. Such an operation can cause idling and underutilisation of processing elements as well as an increase in the processing time for the program. There is therefore a need for more efficient parallel processing of programs that have branching operations.

BRIEF SUMMARY OF THE INVENTION

According to a first aspect there is provided a data processing system comprising: a processor operable to execute a program partitioned into a plurality of discrete instructions, the processor comprising a plurality of processing elements, each processing element capable of executing n instructions per cycle, wherein n is greater than 1; and an interface configured to, on detecting a branch operation by a program creating m number of branches each having a different sequence of instructions, combine an instruction from one of the branches with an instruction from at least one of other branch so as to cause a processing element to execute the combined instructions during a single cycle.

m may be greater than 1.

m may be less than n. Alternatively, m and n may be equal.

Instructions from each of the branches may be combined so as to cause each processing element to execute at least one instruction from each branch per cycle.

The processor may be configured such that, per cycle, each processing element executes the same instructions as the other processing elements.

The sequence of instructions for each branch may be independent from the sequence of instructions of the other branches.

Each sequence of instructions may comprise at least one instruction that is dependent on a previous instruction in the sequence and at least one instruction that is independent on a previous instruction in the sequence.

Each sequence of instructions may comprise n sequential instructions that are capable of being executed in parallel and n sequential instructions that are not capable of being executed in parallel.

The branches may be created in accordance with the program.

The data processing system may further comprise a compiler configured to read the program and compile the program into a plurality of instructions.

The interface may be configured to mimic a processor comprising a plurality of processing elements, each processing element being capable of executing no more than one instruction per cycle.

The interface may be configured to generate a message comprising parameters of said mimicked processor and send the message to the compiler.

The interface may comprise a compiler configured to read the program and compile the program into a plurality of instructions.

The processor may be a GPU (Graphics Processing Unit) and the compiler may be configured to generate instructions for the processing elements from OpenCL code.

The processor may be capable of concurrently supporting a plurality of threads. The processor may be a single instruction multiple thread (SIMT) processor.

The processor may be an n-way VLIW processor.

The data processing system may further comprise masking logic configured to prevent the processing element from executing one of the instructions in the combined instruction and allow execution the other instruction in the combined instruction during the single cycle.

According to a second aspect there is provided compiler for compiling a program into a plurality of instructions executable at a processor comprising a plurality of processing elements, each processing element capable of executing n instructions per cycle, wherein n is greater than 1, the compiler being configured to: read the program and, on detecting a branch operation creating m number of branches and each branch having a different sequence of instructions, combine an instruction from one of the branches with an instruction from at least one other branch so as to cause a processing element to execute the combined instructions during a single cycle.

According to a third aspect there is provided a method for a processor operable to execute a program partitioned into a plurality of discrete instructions, the processor comprising a plurality of processing elements, each processing element capable of executing n instructions per cycle, wherein n is greater than 1, the method comprising: on detecting a branch operation by a program creating m number of branches each having a different sequence of instructions, combining an instruction from one of the branches with an instruction from at least one other branch so as to cause a processing element to execute the combined instructions during a single cycle.

According to a fourth aspect there is provided machine readable code for generating the data processing system described above.

According to a fifth aspect there is provided a machine readable storage medium having encoded thereon non-transitory machine readable code for generating the data processing system described above.

According to a sixth aspect there is provided a data processing system and/or method substantially as described herein with reference to any ofFIGS. 1-5.

