Efficient utilization of synchronization primitives in a multiprocessor computing system

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.

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.