TREE-BASED THREAD MANAGEMENT

摘要

In one embodiment of the present invention, a streaming multiprocessor (SM) uses a tree of nodes to manage threads. Each node specifies a set of active threads and a program counter. Upon encountering a conditional instruction that causes an execution path to diverge, the SM creates child nodes corresponding to each of the divergent execution paths. Based on the conditional instruction, the SM assigns each active thread included in the parent node to at most one child node, and the SM temporarily discontinues executing instructions specified by the parent node. Instead, the SM concurrently executes instructions specified by the child nodes. After all the divergent paths reconverge to the parent path, the SM resumes executing instructions specified by the parent node. Advantageously, the disclosed techniques enable the SM to execute divergent paths in parallel, thereby reducing undesirable program behavior associated with conventional techniques that serialize divergent paths across thread groups.

主权项

1. A computer-implemented method for managing threads, the method comprising:
causing a first set of threads to execute a first instruction that is specified by a first program counter, wherein the first set of threads and the first program counter are included in a first node of a tree divergence table; if causing the first set of threads to execute the first instruction causes a first execution path to diverge, then:
generating a second node of the tree divergence table that includes a second set of threads that is a subset of the first set of threads and a second program counter that specifies a second instruction,generating a third node of the tree divergence table that includes a third set of threads that is a subset of the first set of threads and a third program counter that specifies a third instruction that is on a second execution path,updating the first program counter to specify a synchronization instruction, andcausing the second set of threads to execute the second instruction and the third set of threads to execute the third instruction; or if causing the first set of threads to execute the first instruction does not cause the first execution path to diverge, then:
updating the first program counter to specify a fourth instruction, andcausing the first set of threads to execute the fourth instruction.