Convergence analysis in multithreaded programs

A basic block within a thread program is characterized for convergence based on mapping the basic block to an indicator subnet within a corresponding Petri net generated to model the thread program. Each block within the thread program may be similarly characterized. Each corresponding Petri net is enumerated to generate a corresponding state space graph. If the state space graph includes an exit node with an odd execution count attribute, such as by Petri net coloring, then the corresponding basic block is divergent. The corresponding basic block is convergent otherwise. Using this characterization technique, a thread program compiler may advantageously identify all convergent blocks within a thread program and apply appropriate optimizations to the convergent blocks.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates generally to compiler systems and, more specifically, to convergence analysis in multithreaded programs.

2. Description of the Related Art

Certain computer systems include a parallel processing subsystem that may be configured to concurrently execute plural program threads that are instantiated from a common program. Such systems are referred to in the art as having single instruction multiple thread (SIMT) parallelism. An application program written for execution in an SIMT model may include sequential C language programming statements and calls to a specialized application programming interface (API) used for configuring and managing parallel execution of program threads. A function within an SIMT application that is destined for concurrent execution on a parallel processing subsystem is referred to as a “thread program” or “kernel.” An instance of a thread program is referred to as a thread, and a set of concurrently executing threads may be organized as a thread group. Each thread may follow a different execution path based on certain identifying index variables or computational results.

During the course of following different execution paths, one set of threads may execute one branch of a conditional statement, while another set of threads may execute a different branch of the same conditional statement. In such a scenario, the two different sets of threads execute divergent paths that need to converge at some point later during execution. A synchronization barrier may be used as an explicit convergence point and may implicate a certain portion of a thread program as convergent. Other techniques are known in the art for detecting convergence based on certain ad-hoc rules, but a general technique for identifying all convergent basic blocks is not presently known in the art. Each basic block includes one entry point and one exit point in execution flow. A given basic block may be represented as a corresponding node in a control flow graph (CFG).

Certain beneficial optimizations may be applied to convergent basic blocks. In one exemplary optimization, a convergent basic block may have related data allocated to common storage for greater access efficiency. In another exemplary optimization, a convergent basic block may be scheduled to run on a specific thread processor for greater execution efficiency. Identifying each convergent basic block generally represents an opportunity to better optimize a thread program. However, as alluded to above, thread program compilers are conventionally unable to fully detect all convergent basic blocks in a general thread program and are therefore unable to fully optimize certain thread programs undergoing compilation.

As the foregoing illustrates, what is needed in the art is a technique for identifying convergent basic blocks in a thread program.

SUMMARY OF THE INVENTION

One embodiment of the present invention sets forth a computer-implemented method for characterizing a thread program, the method comprising selecting a basic block within a control flow graph corresponding to the thread program, wherein the control flow graph includes one or more block nodes corresponding to basic blocks within the thread program, generating a Petri net representation of the control flow graph that includes an indicator subnet corresponding to the selected basic block, enumerating a state space graph from the Petri net representation, wherein the state space graph includes a plurality of state nodes corresponding to a state enumeration of the Petri net representation; and determining whether the basic block is convergent based on the state space graph.

Other embodiments of the present invention include, without limitation, a computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to perform the techniques described herein as well as a computing device that includes a processing unit configured to perform the techniques described herein.

One advantage of the disclosed technique is that a thread program compiler is able to advantageously detect all convergent basic blocks within a thread program. This is in contrast to prior art solutions that are only able to detect certain subsets of convergent blocks. Thus, by implementing the disclosed technique, the execution of a thread program can be more fully optimized relative to prior art approaches.

DETAILED DESCRIPTION

System Overview

FIG. 1is a block diagram illustrating a computer system100configured to implement one or more aspects of the present invention. Computer system100includes a central processing unit (CPU)102and a system memory104configured to communicate via an interconnection path that may include 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 I/O (input/output) 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 communication path106and memory bridge105. A parallel processing subsystem112is coupled to memory bridge105via a bus or other communication path113(e.g., a 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 CRT or LCD based monitor). A graphics driver103may be configured to send graphics primitives over communication path113for parallel processing subsystem112to generate pixel data for display on display device110. 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 USB or other port connections, CD drives, 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 (Peripheral Component Interconnect), PCI-Express, AGP (Accelerated Graphics Port), 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.

In one embodiment, the parallel processing subsystem112incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry, and constitutes a graphics processing unit (GPU). In another embodiment, the parallel processing subsystem112may be integrated with one or more other system elements, such as the memory bridge105, CPU102, and I/O bridge107to form a system on chip (SoC).

In one embodiment, a thread program is compiled for execution by parallel processing subsystem112by a thread program compiler150. The thread program compiler translates a source representation of the thread program into a compiled representation of the thread program. For example, the source representation may comprise original source code, such as source code written by a developer, and the compiled representation may comprise an intermediate code easily translated for execution by parallel processing subsystem112. The compiled representation may also comprise an executable thread program suitable for direct execution by parallel processing subsystem112. Thread program compiler150may be implemented within a driver module for the parallel processing subsystem that compiles the executable thread program, or as an application level module that generates either the intermediate code or executable thread program.

In addition to generating the compiled representation of the thread program, thread program compiler150also performs convergence analysis, described below in greater detail. In one embodiment, a convergence analysis function152performs convergence analysis, which allows the thread program compiler to statically determine when threads within a basic block are known to be convergent or divergent. Such analysis is significant for both program correctness and performance. In particular, thread program compiler150may use uniform (or “scalar”) operations for thread-invariant values when threads are known to be convergent. Uniform operations may include uniform loads, scalar register accesses, and scalar instructions. Convergence analysis may enable scalarization to factor out uniform work from single instruction multiple thread (SIMT) threads. The uniform work may then be advantageously assigned to shared scalar resources to improve utilization efficiency of resources within parallel processing subsystem112. Persons skilled in the art will recognize that convergence analysis techniques described herein are broadly applicable to many different multi-threaded system architectures, including any processor system that provides or models multi-threaded execution in combination with scalar resources.

One way of interpreting thread convergence in a basic block is that all or none of the threads within a given basic block will be collected at the barrier, which represents a convergence point. On exemplary type of barrier implemented in the CUDA™ runtime from NVIDIA™ is a _syncthreads( ) call, which blocks all associated threads until all the threads execute the same _syncthreads( ) call.

Basic block convergence analysis begins with thread program compiler150identifying basic block boundaries within a thread program. Each basic block is then represented as a node within a control flow graph (CFG). Each CFG node is annotated to reflect whether the corresponding basic block includes a synchronization barrier, such as the _syncthreads( ) call.

FIG. 2Aillustrates an exemplary CFG fragment210and a corresponding Petri net (PN) fragment212, according to one embodiment of the present invention. CFG fragment210includes node p1220and node p2222, neither of which is annotated as being synchronization barrier nodes. PN fragment212includes place p1230, transition t1232, and place p2234. Here, place p1230corresponds to node p1220and place p2234corresponds to node p2222. Transition t1232is required for structural correctness within PN fragment212. In general, for each node within a CFG that is not annotated as having a synchronization barrier, a corresponding place is added within a Petri net representation of the CFG. For convenience, each CFG node and corresponding PN place is labeled herein with the same label. For example, node p1220is labeled place p1230. Furthermore, PN tokens may be labeled herein as numbers along an associated network edge.

Persons skilled in the art will recognize that a PN constructed with two tokens in an entry basic block faithfully captures the complete dynamic behavior of a corresponding thread program executed by two threads. An initial marking of the entry basic block may include two tokens.

FIG. 2Billustrates an exemplary CFG synchronization barrier240and a corresponding PN fragment242, according to one embodiment of the present invention. Here, synchronization barrier240is represented by a CFG node p1250, which includes a synchronization barrier, such as a _syncthreads( ) call. PN fragment242represents node p1250using an input place p1—i, a transition262, and an output place p1—o. PN242is illustrated for two independently executing threads, each able to post one of two input tokens, shown as “[1, 1]” along an edge connecting place p1—i260and transition262. When both input tokens are present at input place p1—i260, transition t1262consumes the two input tokens and posts two output tokens to output place p1—o264. In this way, PN fragment242models two independently executing threads arriving asynchronously at a synchronization barrier.

In general, a CFG may be modeled as a corresponding PN. For CFG nodes having a synchronization barrier, the mapping illustrated inFIG. 2Bmay be applied in generating portions of the corresponding PN. For CFG nodes without a synchronization barrier, the mapping illustrated inFIG. 2Amay be applied in generating remaining portions of the corresponding PN.

FIG. 3Aillustrates an exemplary CFG300, according to one embodiment of the present invention. As shown, CFG300includes entry node p1310and exit node314. In this example, node312includes a synchronization barrier. CFG300is mapped to a corresponding PN (not shown).

A state space graph of a PN, such as the corresponding PN, represents instantaneous state of the PN. A marking is associated with each node of the state space graph. The marking is a list of places and a token count for each place. In general, a place may have an arbitrary number of tokens, however embodiments of the present invention limit each place in the corresponding PN to two tokens. Each one of the two tokens is associated with one of two different threads. A state space graph marking of the form “pi pk” is used herein, where pi and pk each indicate the presence of one token in the indicated place within the corresponding PN. For example, a state space graph marking of “p1p2” on a particular node indicates place p1and place p2within the corresponding PN each have one token. The state space graph is therefore a state graph with nodes comprising all possible states of the PN and edges comprising all possible state transitions within the PN.

FIG. 3Billustrates a state space graph302mapped from the exemplary CFG300ofFIG. 3A, according to one embodiment of the present invention. CFG to PN mappings illustrated inFIGS. 2A and 2Bare used to generate a corresponding PN. State space graph302is then generated from the corresponding PN using any technically feasible technique. Persons skilled in the art will recognize that various well-known techniques may be implemented to generate state space graph302by enumerating all states associated with the corresponding PN.

As shown, state space graph302includes an entry node320and an exit node322. Exit node322is marked “p6p6” representing an instance in time when both of two executing threads have arrived at node p6within CFG300. Equivalently, marking “p6p6” indicates that both of two possible tokens are in place p6within the corresponding PN.

FIG. 4illustrates a branch in a CFG fragment400, according to one embodiment of the present invention. The branch occurs at node p3of CFG300ofFIG. 3A, where execution flow may proceed from node p3to either node p4or node p5. If this branch is divergent, then during some execution instant of an associated thread program there will be one thread in p4and another thread in p5. This state would be marked as “p4p5” in state space graph302ofFIG. 3B. If marking “p4p5” is present in state space graph302, then the branch at node p3is divergent. However, marking “p4p5” is not present, indicating the branch at node p3is actually convergent.

FIG. 5illustrates an indicator subnet500within a Petri net, according to one embodiment of the present invention. Indicator subnet500may be substituted for a selected node within a CFG being analyzed rather than either of the direct mappings illustrated inFIGS. 2A and 2B. To analyze convergence for a given basic block within a complete CFG, indicator subnet500is used to map the basic block to a complete PN for the CFG. Divergence for the basic block is then assessed in the context of the complete PN by mapping the PN to a state space graph and searching the state space graph for divergence, as described below inFIGS. 6 and 7.

Indicator subnet500introduces an input place p_i510, an output place p_o516, two indicator places q1512and q2514, and two transitions t1520, t2522. Input place p_i510and output place p_o516respectively indicate arrival at and departure from the basic block as executed by a thread. Indicator place q1512and indicator place q2514together track how many times (modulo2) the basic block was traversed by two different threads during execution. Indicator place q1512indicates an odd number of traversals, while indicator place q2514indicates an even number of traversals. At some instant in time, if indicator place q1512has a marking of 1, then the basic block was traversed an odd number of times by the two different threads. In one embodiment, indicator place q2514starts with an initial marking of [1], indicating the basic block was traversed zero times or an even number of times.

FIG. 6illustrates a state space graph600generated from a PN enumeration for a modified node p2in CFG300ofFIG. 3A, according to one embodiment of the present invention. In this example, node p2of CFG300is modified to reflect a mapping to PN subnet500, described above inFIG. 5. Other nodes of CFG300are mapped according toFIG. 2Afor nodes without synchronization barriers andFIG. 2Bfor nodes with synchronization barriers. In particular, node p4312includes a synchronization barrier and is therefore mapped according toFIG. 2B.

Markings that include p2—ior p2—oarise because node p2of CFG300was modified in a corresponding PN (not shown) to an include input (“_i”) place and output (“_o”) place, as illustrated inFIG. 5. Markings that include p4—ior p4—oarise because node p4of CFG300includes a synchronization barrier and is mapped to include an input place and an output place, as illustrated inFIG. 2B. Entry node610is marked “p1p1” to indicate both threads start in p1310of CFG300.

Each node of state space graph600is designated as being either a “red” node or “green” node. A “red” node is depicted herein using a hash fill, while a “green” node does not include a hash fill. A green node indicates that indicator place q2514of the modified node p2in the corresponding PN had a [1] marking just before the thread program reached a state for the green node. That is, just before the thread program reached a state associated with the node, the basic block associated with p2had been executed an even number of times by both threads. Similarly, a red node indicates that just before the thread program reached a state associated with the red node, the basic block associated with p2had been executed an odd number of times by both threads.

Exit node p6314has two different corresponding exit nodes in state space graph600. Node622is a red node while node620is a green node. Both nodes620and622have marking “p6p6,” indicating both of two different threads arrived at node p6. However, in the process, node p2was executed an odd number of times by one of the two different threads, while node p2was executed an even number of times by the other of two different threads. In other words, the execution count of the basic block associated with node p2is different for each of the two different threads, indicating the basic block is not convergent.

FIG. 7illustrates a state space graph700generated from a PN enumeration for a modified node p5in CFG300ofFIG. 3A, according to one embodiment of the present invention. Here, node p5of CFG300is modified (rather than mode p2) to reflect a mapping to PN subnet500, described above inFIG. 5. Again, node p4312includes a synchronization barrier and is therefore mapped according toFIG. 2B. State space graph700begins in entry node710and terminates at exit node720. Only a green node with marking “p6p6” exists in state space graph700. That is, for all possible legal executions of CFG300, the basic block associated with node p5is always executed an even number of times and therefore the basic block for node p5is convergent.

FIG. 8sets forth a flowchart of method steps for identifying convergent basic blocks within a thread program, according to one embodiment of the present invention. Although the method steps are described in conjunction with the system ofFIG. 1, persons of ordinary skill in the art will understand that any system configured to perform the method steps, in any order, is within the scope of the invention. In one embodiment, the method steps are performed by CPU102ofFIG. 1.

As shown, method800begins in step810, where a convergence analysis function, such as convergence analysis function152within thread program compiler150, generates a control flow graph (CFG) from a thread program. The CFG may be generated for a thread program using any technically feasible technique. In alternative embodiments, a function other than the convergence analysis function generates the CFG. The thread program may be specified as source code, tokenized code, an intermediate code, or any other technically feasible representation. In step812, the convergence analysis function selects a basic block from the CFG. In step814, the convergence analysis function generates a modified Petri net (PN) for the CFG based on the selected basic block. The modified PN represents the selected basic block as an indicator subnet, such as indicator net500ofFIG. 5. In one embodiment, the modified PN represents basic blocks within the CFG other than the selected basic block according to mappings illustrated inFIG. 2AorFIG. 2B. In step816, the convergence analysis function generates a state space graph based on the modified PN.

If, in step820, the state space graph includes a red exit node, then the method proceeds to step822, where the convergence analysis function marks the selected basic block as divergent. Otherwise, if the state space graph does not include a red exit node, then the method proceeds to step824, where the convergence analysis function marks the selected basic block as convergent. Assessing whether the state space graph includes a red exit node may be implemented using any technically feasible technique, such as performing a graph search or identifying the red exit node upon generating the state space graph.

If, in step830, the convergence analysis function is done, then the method terminates in step890. Otherwise, the method proceeds back to step812, previously described herein. In one embodiment, the convergence analysis function is done after all basic blocks within the CFG have been selected and marked as either divergent or convergent.

In sum, a technique for characterizing each basic block within a thread program as being either convergent or divergent is disclosed. The technique involves representing the thread program as a control flow graph having one or more basic blocks, which are then individually analyzed for convergence. Analysis involves representing a selected basic block as an indicator subnet within a Petri net mapping of the control flow graph. State information for the Petri net is then enumerated to generate a state space graph corresponding to the selected basic block. If the state space graph includes a red exit node, then the selected basic block is identified as divergent, otherwise the selected basic block is identified a convergent.

One advantage of the disclosed technique is that a thread program compiler is able to advantageously detect all convergent basic blocks within a thread program. This is in contrast to prior art solutions that are only able to detect certain subsets of convergent blocks. Thus, by implementing the disclosed technique, the execution of a thread program can be more fully optimized relative to prior art approaches.

In view of the foregoing, the scope of the invention is determined by the claims that follow.