# US 11,307,862 B2 · Compiling and combining instructions from different branches for execution in a processing element of a multithreaded processor > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,307,862 B2 - Document ID: US11307862B2 - Status: Granted - Kind: B2 - Application number: 16/712,778 - Filed: 2019-12-12 - Published: 2020-04-16 - Granted: 2022-04-19 - Earliest claimed: 2014-08-28 - Assignees: Imagination Technologies Limited - Applicants: Imagination Technologies Limited - Inventors: Jung-Wook Park - Web page: https://patentgrep.com/patent/US11307862B2 ## CPC - G06F 9/3853: {of compound instructions} - G06F 9/30058: {Conditional branch instructions} - G06F 9/3851: {from multiple instruction streams, e.g. multistreaming} - G06F 9/38585: {with result invalidation, e.g. nullification} - G06F 9/3885: {using a plurality of independent parallel functional units} - G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]} - G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel} - G06F 15/76: Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A data processing system includes a processor operable to execute a program partitioned into a number of discrete instructions, the processor having multiple processing elements each capable of executing more than one instruction per cycle, and an interface configured to read a first program and, on detecting a branch operation by that 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 other branch so as to cause a processing element to execute the combined instructions during a single cycle. ## Claims ### Claim 1 A data processing system comprising: a first processor operable to execute a program partitioned into a plurality of discrete instructions, the first processor comprising a plurality of processing elements, each processing element capable of executing n instructions per cycle, wherein n is an integer greater than 1; and an interface configured to mimic a processor comprising a plurality of processing elements each being capable of executing no more than one instruction per cycle, the interface further configured to, on detecting a branch operation by the program creating m number of branches each having a different sequence of instructions, wherein m is an integer greater than 1, cause a compiler to compile the sequence of instructions from each branch so as to be suitable for processing elements that are only capable of executing one instruction per cycle, and combine an instruction from one of the branches with an instruction from at least one other branch to form a combined instruction so as to cause at least one processing element to execute the combined instruction during a single cycle. ### Claim 2 (depends on 1) A data processing system as claimed in claim 1, wherein m is less than n. ### Claim 3 (depends on 1) A data processing system as claimed in claim 1, wherein m and n are equal. ### Claim 4 (depends on 1) A data processing system as claimed in claim 1, wherein instructions from each of the branches are combined so as to cause each processing element of the first processor to execute at least one instruction from each branch per cycle. ### Claim 5 (depends on 1) A data processing system as claimed in claim 1, wherein the first processor is configured such that, per cycle, all processing elements of the first processor execute the same instructions. ### Claim 6 (depends on 1) A data processing system as claimed in claim 1, wherein the sequence of instructions for each branch is independent from the sequence of instructions of the at least one other branch. ### Claim 7 (depends on 1) A data processing system as claimed in claim 1, wherein each sequence of instructions comprises at least one instruction that is dependent on a previous instruction in that sequence and at least one instruction that is independent of a previous instruction in that sequence. ### Claim 8 (depends on 1) A data processing system as claimed in claim 1, wherein each sequence of instructions comprises n sequential instructions that are capable of being executed in parallel and n sequential instructions that are not capable of being executed in parallel. ### Claim 9 (depends on 1) A data processing system as claimed in claim 1, wherein the branches are created in accordance with the program. ### Claim 10 (depends on 1) A data processing system as claimed in claim 1, wherein the interface is configured to generate a message comprising parameters of the mimicked processor and send the message to the compiler. ### Claim 11 (depends on 1) A data processing system as claimed in claim 1, wherein the compiler is configured to read the program and compile the program into a plurality of processing element executable instructions. ### Claim 12 (depends on 1) A data processing system as claimed in claim 1, wherein the first processor is a graphics processing unit (GPU) and the compiler is configured to generate instructions for processing elements from Open Computing Language (OpenCL) code. ### Claim 13 (depends on 1) A data processing system as claimed in claim 1, wherein the first processor is capable of concurrently supporting a plurality of threads. ### Claim 14 (depends on 1) A data processing system as claimed in claim 1, wherein the first processor is a single instruction multiple thread (SIMT) processor. ### Claim 15 (depends on 1) A data processing system as claimed in claim 1, wherein each processing element of the first processor is an n-way very long instruction word (VLIW) processor. ### Claim 16 (depends on 1) A data processing system as claimed in claim 1, further comprising a masking logic circuit configured to prevent the at least one processing element from executing one of the instructions in the combined instruction and allow execution of another instruction in the combined instruction prior to the at least one processing element executing the combined instruction during the single cycle. ### Claim 17 A non-transitory computer readable storage medium having stored thereon a compiler comprising computer readable code, said compiler being configured to compile a program into a plurality of instructions executable at a data processing system comprising a first processor having a plurality of processing elements, each processing element capable of executing n instructions per cycle, wherein n is an integer greater than 1, and an interface configured to mimic a plurality of processing elements each being capable of executing no more than one instruction per cycle, the compiler being configured to: read the program and, on detecting a branch operation creating m number of branches wherein m is an integer greater than 1, each branch having a different sequence of instructions, compile the sequence of instructions from each branch so as to be suitable for processing elements that are only capable of executing one instruction per cycle, and combine an instruction from one of the branches with an instruction from at least one other branch to form a combined instruction so as to cause at least one processing element to execute the combined instruction during a single cycle. ### Claim 18 A method of executing a program partitioned into a plurality of discrete instructions, comprising: detecting a branch operation by a program creating m number of branches, wherein m is an integer greater than 1, each branch having a different sequence of instructions; mimicking a processor comprising a plurality of processing elements each being capable of executing no more than one instruction per cycle; causing a compiler to compile the sequence of instructions from each branch so as to be suitable for processing elements that are only capable of executing one instruction per cycle; combining an instruction from one of the branches with an instruction from at least one other branch to form a combined instruction; and causing at least one processing element of a first processor having a plurality of processing elements each capable of executing more than one instruction per cycle to execute the combined instruction during a single cycle.