# US 9,870,599 B2 · Analysis system and method for reducing the control flow divergence in the Graphics Processing Units (GPUs) > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,870,599 B2 - Document ID: US9870599B2 - Status: Granted - Kind: B2 - Application number: 15/263,417 - Filed: 2016-09-13 - Published: 2017-11-16 - Granted: 2018-01-16 - Earliest claimed: 2016-05-13 - Assignees: National Taiwan University; Mediatek Inc. - Applicants: National Taiwan University; Mediatek Inc. - Inventors: Che-Yang Wu; Wei-Chung Hsu - Web page: https://patentgrep.com/patent/US9870599B2 ## CPC - G06F 11/3466: {Performance evaluation by tracing or monitoring} - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 9/30058: {Conditional branch instructions} - G06F 9/3867: {using instruction pipelines} - G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel} - G06F 9/38885: {Divergence aspects} - G06F 11/30: Monitoring - G06F 11/302: {where the computing system component is a software system} - G06F 11/3409: {for performance assessment} - G06F 2201/865: Monitoring of software - G06F 2201/88: Monitoring involving counting - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract The invention discloses an analysis system and method for reducing control flow divergence in the Graphics Processing Units (GPUs). A computing unit is used to count the number of branch, number of cycle, and to calculate at least one direction ratio. A profiler is used to determine whether the code having the optimized control flow structure and the specialized branch or not. The optimization decision unit can determine which transform pattern can be used to transform the sub-control flow structure. ## Claims ### Claim 1 An analysis system for reducing a flow control divergence in a graphics processing unit (GPU), said GPU comprises a computing unit, and a hardware performance profiling support unit, the computing unit is used to count a number of at least one branch and a number of at least one cycle, and to calculate at least a direction ratio of a counting program code, and to send an information to said hardware performance profiling support unit, said analysis system comprises: a compiling unit, said compiling unit loads said counting program code; a profiler unit, said profiler unit is connected to said compiling unit, wherein said profiler unit receiving a number of branch, a number of cycle, and a direction ratio transmitted by said hardware performance profiling support unit, said profiler unit determines whether said counting program code has an optimized sub-flow control structure and an optimized specific branch instruction in accordance with said number of branch, said number of cycle, and said direction ratio; and an optimization unit, said optimization unit being connected to said profiler unit, said optimization unit comprising an optimization decision unit, said optimization decision unit determines which transform pattern is used for transforming said sub-flow control structure in accordance with a branch ratio and said number of said specific branch instruction; wherein, when said profiler unit determines whether said counting program code has said optimized sub-flow control structure and said specific branch instruction or not, said profiler unit calculates said branch ratio of said each branch and a number of a specific branch instruction. ### Claim 2 (depends on 1) The analysis system according to claim 1, wherein said profiler unit further comprises a control flow profiler unit, said control flow profiler unit is connected to a compiling unit, said control flow profiler unit determines whether a counting program code has said sub-flow control structure and said specific branch instruction or not. ### Claim 3 (depends on 1) The analysis system according to claim 1, wherein said profiler unit further comprises an execution profiling unit, said execution profiling unit is connected to a compiling unit, said execution profiling unit determines an execution efficiency of said counting program code in accordance with said number of branch, said number of cycle, and said direction ratio. ### Claim 4 (depends on 1) The analysis system according to claim 1, wherein said profiler unit further comprises a branch data profiler unit, said branch data profiler unit calculates said branch ratio and said number of said specific branch instruction for each branch. ### Claim 5 (depends on 1) The analysis system according to claim 1, wherein said direction ratio is a ratio of a number of execution branch and a number of un-execution branch. ### Claim 6 (depends on 1) The analysis system according to claim 1, wherein said optimization unit further comprises a transform pattern unit, said transform pattern unit transforms said sub-flow control structure in accordance with said transform pattern determined by said optimization unit. ### Claim 7 An analysis method for reducing a flow control divergence in a graphics processing unit (GPU), comprising: loading and executing a counting program code on said graphics processing unit (GPU), said GPU counting a number of at least one branch, a number of at least one cycle, and calculating at least one direction ratio of said counting program code; using a compiling unit to load said counting program code and producing a control flow diagram; using a profiler unit to determine whether said counting program code has a sub-flow control structure or not, wherein said sub-flow control structure is optimized; determining said optimized sub-flow control structure, said profiler unit determines whether said counting program code has a specific branch instruction or not; when said profiler unit determines whether said counting program code has a specific branch instruction or not, said compiling unit compiling said counting program code to form a specific flow control structure; said profiler unit calculating a branch ratio, and said number of said specific branch instruction for each branch; an optimization unit determining a conversion mode according to said branch ratio and said number of said specific branch instruction, and said optimization unit determining said conversion mode to convert said sub-flow control structure. ### Claim 8 (depends on 7) The analysis method according to claim 7, wherein said profiler further comprises a control flow profiler unit, said control flow profiler unit is connected to a compiling unit, said control flow profiler unit determines whether said counting program code has said sub-flow control structure, and said specific branch instruction or not. ### Claim 9 (depends on 7) The analysis method according to claim 7, wherein profiler unit further comprises an execution profiling unit, said execution profiling unit is connected to a compiling unit, said execution profiling unit determines an execution efficiency of said counting program code in accordance with said number of branch, said number of cycle, and said direction ratio. ### Claim 10 (depends on 7) The analysis method according to claim 7, wherein profiler unit further comprises a branch data profiler unit, said branch data profiler unit calculates said branch ratio and said number of said specific branch instruction for each branch. ### Claim 11 (depends on 7) The analysis method according to claim 7, wherein said optimization unit further comprises an optimization decision unit, said optimization decision unit determines which transform pattern to transform said sub-control flow structure in accordance with said branch ratio and said number of said specific branch instruction. ### Claim 12 (depends on 7) The analysis method according to claim 7, wherein said optimization unit further comprises a transform pattern unit, said transform pattern unit determines said conversion mode to convert said sub-flow control structure. ### Claim 13 (depends on 7) The analysis method according to claim 7, wherein when said profiler unit determines there is no optimized sub-flow control structure, then a process is terminated. ### Claim 14 (depends on 7) The analysis method according to claim 7, wherein said profiler unit determines said counting program code does not have said specific branch instruction, said compiling unit uses a common prediction method to compile said counting program code.