Efficient utilization of synchronization primitives in a multiprocessor computing system
A compiler creates a dependency graph for a function in an input program. The dependency graph includes nodes corresponding to commands in the function and edges that correspond to dependencies between the commands. The compiler performs a forward reachability analysis on the dependency graph to eliminate redundant dependencies. The compiler also adds a minimized set of back-edges to the dependency graph to enforce loop-carried resource dependencies in the input program. The compiler then allocates synchronization primitives provided by a multiprocessor computing system, such as semaphores, to the commands in the function of the input program based on the contents of the dependency graph.
1 . A computer-implemented method, comprising:
minimizing edges in a dependency graph for a function in an input program, the dependency graph comprising nodes corresponding to commands in the function and edges corresponding to dependencies between the nodes;
adding a minimized set of back-edges to the dependency graph to enforce loop-carried resource dependencies in the input program; and
allocating synchronization primitives provided by a multiprocessor computing system to the commands in the function of the input program based on the dependency graph.
2 . The computer-implemented method of claim 1 , wherein the dependencies between the nodes are identified using a shared queue analysis that creates an edge in the dependency graph between a first node corresponding to a first command and a second node corresponding to a second command, the first command and the second command having a same command type.
3 . The computer-implemented method of claim 1 , wherein the dependencies between the nodes are identified using an input/output analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a buffer and a second node corresponding to a second command that uses the buffer.
4 . The computer-implemented method of claim 1 , wherein the dependencies between the nodes are identified using an allocation overlap analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a range of memory addresses and a second node corresponding to a second command that all or a portion of the range of memory addresses.
5 . The computer-implemented method of claim 1 , wherein minimizing the edges corresponding to the dependencies between the nodes in the dependency graph comprises:
performing a forward reachability analysis on the dependency graph to eliminate one or more dependencies; and
adding edges to the dependency graph for dependencies other than artificial dependencies that remain following the forward reachability analysis.
6 . The computer-implemented method of claim 1 , wherein the minimized set of back-edges comprises a first back-edge from a leaf node in a dependency graph for a loop to a first root node in the dependency graph for the loop and a second back-edge from the leaf node to a second root node in the dependency graph for the loop.
7 . The computer-implemented method of claim 1 , wherein the synchronization primitives provided by a multiprocessor computing system comprise semaphores.
8 . A computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by a processing system, cause the processing system to:
create a dependency graph for a function in an input program, the dependency graph comprising nodes corresponding to commands in the function and edges corresponding to dependencies between the nodes;
eliminate at least one of the edges from the dependency graph;
add at least one back-edge to the dependency graph to enforce a loop-carried resource dependency in the input program; and
allocate synchronization primitives provided by a multiprocessor computing system to the commands in the function of the input program based on the dependency graph.
9 . The computer-readable storage medium of claim 8 , wherein the dependencies between the nodes are identified using a shared queue analysis that creates an edge in the dependency graph between a first node corresponding to a first command and a second node corresponding to a second command, the first command and the second command having a same command type.
10 . The computer-readable storage medium of claim 8 , wherein the dependencies between the nodes are identified using an input/output analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a buffer and a second node corresponding to a second command that uses the buffer.
11 . The computer-readable storage medium of claim 8 , wherein the dependencies between the nodes are identified using an allocation overlap analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a range of memory addresses and a second node corresponding to a second command that all or a portion of the range of memory addresses.
12 . The computer-readable storage medium of claim 8 , wherein eliminating at least one of the edges from the dependency graph comprises:
performing a forward reachability analysis on the dependency graph to eliminate one or more dependencies; and
adding edges to the dependency graph for dependencies other than artificial dependencies that remain following the forward reachability analysis.
13 . The computer-readable storage medium of claim 8 , wherein the at least one back-edge comprises a back-edge from a leaf node to a root node in the dependency graph.
14 . The computer-readable storage medium of claim 8 , wherein the synchronization primitives provided by a multiprocessor computing system comprise semaphores.
15 . A processing system, comprising:
a processor; and
a computer-readable storage medium having computer-executable instructions stored thereupon that, when executed by the processing system, cause the processing system to:
create a dependency graph for a function in an input program, the dependency graph comprising nodes corresponding to commands in the function and edges corresponding to dependencies between the nodes;
eliminate at least one of the edges from the dependency graph;
add at least one back-edge to the dependency graph to enforce a loop-carried resource dependency in the input program; and
allocate synchronization primitives provided by a multiprocessor computing system to the commands in the function of the input program based on the dependency graph.
16 . The processing system of claim 15 , wherein the dependencies between the nodes are identified using a shared queue analysis that creates an edge in the dependency graph between a first node corresponding to a first command and a second node corresponding to a second command, the first command and the second command having a same command type.
17 . The processing system of claim 15 , wherein the dependencies between the nodes are identified using an input/output analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a buffer and a second node corresponding to a second command that uses the buffer.
18 . The processing system of claim 15 , wherein the dependencies between the nodes are identified using an allocation overlap analysis that creates an edge in the dependency graph between a first node corresponding to a first command that uses a range of memory addresses and a second node corresponding to a second command that all or a portion of the range of memory addresses.
19 . The processing system of claim 15 , wherein eliminating at least one of the edges from the dependency graph comprises:
performing a forward reachability analysis on the dependency graph to eliminate one or more dependencies; and
adding edges to the dependency graph for dependencies other than artificial dependencies that remain following the forward reachability analysis.
20 . The processing system of claim 15 , wherein the at least one back-edge comprises a back-edge from a leaf node to a root node in the dependency graph.