Parallelization of irregular reductions via parallel building and exploitation of conflict-free units of work at runtime

A system for optimizing a program, the system comprising:

• a memory;
• a processor coupled to said memory, said processor running program instructions for performing parallelization of irregular reductions, said method comprising:
• receiving an input program;
• selecting, at compile time, at least one unit of work (UW) from said program, each UW configured to operate on at least one reduction operation, where at least one reduction operation in the UW operates on a reduction variable whose address is only determinable when running said program at a run-time;
• recording, at run time, for each current at least one UW, a list of reduction operations accessed by that current unit of work;
• and,
• determining, at run time, whether reduction operations accessed by a current UW conflict with any reduction operations recorded as having been accessed by prior selected units of work, and assigning said unit of work as a conflict free unit of work (CFUW) when no conflicts are found;
• and,
• scheduling, for parallel run-time operation, at least two or more processing threads to process a respective said at least two or more assigned CFUWs.

A computer program product for performing parallelization of irregular reductions, the computer program product comprising:

• a storage medium readable by a processing circuit and storing instructions for operation by the processing circuit for performing a method comprising:
• receiving an input program;
• selecting, at compile time, at least one unit of work (UW) from said program, each UW configured to operate on at least one reduction operation, where at least one reduction operation in the UW operates on a reduction variable whose address is only determinable when running said program at a run-time;
• recording, at run time, for each current at least one UW, a list of reduction operations accessed by that current unit of work;
• and,
• determining, at run time, whether reduction operations accessed by a current UW conflict with any reduction operations recorded as having been accessed by prior selected units of work, and assigning said unit of work as a conflict free unit of work (CFUW) when no conflicts are found;
• and,
• scheduling, for parallel run-time operation, at least two or more processing threads to process a respective said at least two or more assigned CFUWs.