# US 9,436,473 B2 · Scheduling program instructions with a runner-up execution position > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,473 B2 - Document ID: US9436473B2 - Status: Granted - Kind: B2 - Application number: 14/048,141 - Filed: 2013-10-08 - Published: 2015-04-09 - Granted: 2016-09-06 - Earliest claimed: 2013-10-08 - Assignees: Arm Limited - Applicants: Arm Limited - Inventors: Rune Holm, Jr.; David Hennah Mansell - Web page: https://patentgrep.com/patent/US9436473B2 ## CPC - G06F 9/30145: {Instruction analysis, e.g. decoding, instruction word fields} - G06F 9/321: {Program or instruction counter, e.g. incrementing} - G06F 9/3802: {Instruction prefetching} - G06F 9/3846: {using static prediction, e.g. branch taken strategy} - G06F 9/3851: {from multiple instruction streams, e.g. multistreaming} - 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: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A single instruction multiple thread (SIMT) processor includes scheduling circuitry for calculating a next scheduled execution point for execution circuits which execute respective threads corresponding to a common program. In addition to calculating the next scheduled execution point, the scheduling circuitry determines a runner up execution point which would have been determined as the next scheduled execution point if the threads which actually correspond to the next scheduled execution point had been removed from consideration. This runner up execution point is used to identify points of re-convergence within the program flow and as part of the operation of a static branch predictor. ## Claims ### Claim 1 Apparatus for processing data comprising: a plurality of execution circuits configured to execute a common program as a respective plurality of threads of program execution; and scheduling circuitry configured to determine a next scheduled execution position within said common program corresponding to a next program instruction to be executed by at least one of said plurality of execution circuits while any of said plurality of execution circuits at a current execution position in an execution path through said common program not followed by said next scheduled position do not execute said next program instruction; wherein said scheduling circuitry is configured to: calculate a runner up execution position that would have been determined as said next scheduled execution position if said next program instruction was excluded from serving as said next scheduled execution position; determine said next scheduled execution position so as to follow an execution path corresponding to consecutive instructions in program counter order unless a point of full determination is detected by said scheduling circuitry whereupon said scheduling circuitry performs a full determination of said next scheduled execution position that provides for one or more possible execution paths not corresponding to consecutive instructions in program counter order; calculate said runner up execution position upon said detection of a current point of full determination; and detect a further point of full determination if said execution path reaches said runner up execution position. ### Claim 2 (depends on 1) Apparatus as claimed in claim 1, wherein said scheduling circuitry is configured to detect as said further point of full determination if said execution path reaches a branch instruction corresponding to said execution path not corresponding to consecutive instructions in program counter order. ### Claim 3 (depends on 1) Apparatus as claimed in claim 1, wherein said determination of said next scheduled execution position and said runner-up execution position determined at said point of full determination are performed by: (i) selecting as one or more candidate threads among said plurality of threads having a deepest function call depth, each of said one or more candidate threads having a next candidate instruction to be executed; and (ii) among said next candidate instructions of said one or more candidate threads determining said next scheduled execution position to correspond to a next candidate instruction having a least advanced program counter value in program counter order. ### Claim 4 (depends on 1) Apparatus as claimed in claim 1, wherein said scheduling circuitry uses shared determination hardware to determine both said next scheduled execution position and said runner up execution position. ### Claim 5 (depends on 4) Apparatus as claimed in claim 4, wherein said shared determination hardware is configured to determine said next scheduled execution position during a given processing cycle and to determine said runner up execution position during a processing cycle immediately following said given processing cycle. ### Claim 6 (depends on 1) Apparatus as claimed in claim 1, wherein said common program is formed of program instruction from an instruction set not including marker instructions for marking points of full determination. ### Claim 7 (depends on 1) Apparatus as claimed in claim 1, comprising branch prediction circuitry configured to use said runner up execution point as at least a part of a branch prediction result for a branch instruction. ### Claim 8 (depends on 7) Apparatus as claimed in claim 7, wherein an instruction following said branch instruction in non-branching instruction execution flow has a no-branch address and said branch prediction result includes a predicted branch target address and a new runner up execution point. ### Claim 9 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, unconditional backward branch instruction specifying a branch target address, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said branch target address and said new runner up execution point is said runner up execution point. ### Claim 10 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, conditional backward branch instruction specifying a branch target address, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said branch target address and said new runner up execution point is said no-branch address. ### Claim 11 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, unconditional forward branch instruction specifying a branch target address and said branch target address is before said runner up execution point in consecutive execution program order, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said target branch address and said new runner up execution point is said runner up execution point. ### Claim 12 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, conditional forward branch instruction specifying a branch target address and said branch target address is before said runner up execution point in consecutive execution program order, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said no-branch address and said new runner up execution point is said branch target address. ### Claim 13 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, unconditional forward branch instruction specifying a branch target address and said branch target address is after said runner up execution point in consecutive execution program order, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said runner up execution point and said new runner up execution point is said branch target address. ### Claim 14 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct, conditional forward branch instruction specifying a branch target address and said branch target address is after said runner up execution point in consecutive execution program order, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said no-branch address and said new runner up execution point is said runner up execution point. ### Claim 15 (depends on 8) Apparatus as claimed in claim 8, wherein when said branch instruction is a direct function call specifying a branch target address, said branch prediction circuitry generates a branch prediction result in which said predicted branch target address is said branch target address and said new runner up execution point is said runner up execution point. ### Claim 16 Apparatus for processing data comprising: a plurality of means for executing a common program as a respective plurality of threads of program execution; and means for determining a next scheduled execution position within said common program corresponding to a next program instruction to be executed by at least one of said plurality of means for executing while any of said plurality of means for executing at a current execution position in an execution path through said common program not followed by said next scheduled position do not execute said next program instruction; wherein said means for determining is configured to also calculate a runner up execution position that would have been determined as said next scheduled execution position if said next program instruction was excluded from serving as said next scheduled execution position; and wherein said means for determining is configured to: determine said next scheduled execution position so as to follow an execution path corresponding to consecutive instructions in program counter order unless a point of full determination is detected by said means for determining whereupon said means for determining is configured to perform a full determination of said next scheduled execution position that provides for one or more possible execution paths not corresponding to consecutive instructions in program counter order; calculate said runner up execution position upon said detection of a current point of full determination; and detect a further point of full determination if said execution path reaches said runner up execution position. ### Claim 17 A method of processing data comprising the steps of: executing a common program as a respective plurality of threads of program execution with a plurality of execution circuits; and scheduling including determining a next scheduled execution position within said common program corresponding to a next program instruction to be executed by at least one of said plurality of execution circuits while any of said plurality of execution circuits at a current execution position in an execution path through said common program not followed by said next scheduled position do not execute said next program instruction; wherein said step of scheduling includes: calculating a runner up execution position that would have been determined as said next scheduled execution position if said next program instruction was excluded from serving as said next scheduled execution position; determining said next scheduled execution position so as to follow an execution path corresponding to consecutive instructions in program counter order unless a point of full determination is detected by said scheduling circuitry whereupon said a full determination of said next scheduled execution position is performed that provides for one or more possible execution paths not corresponding to consecutive instructions in program counter order; calculating said runner up execution position upon said detection of a current point of full determination; and detecting a further point of full determination if said execution path reaches said runner up execution position.