Patent ID: 8468508
Filing Date: 2013-06-18
Classification: G06F

Abstract:
1. A method in a computer system for performing parallelization of irregular reductions, the method comprising: receiving, at a compiler device, a program; selecting, at compile time, at least one unit of work (UW) from said program, each said UW of work corresponding to a program loop iteration operation in which reduction variable instances are determined during a program run time, each UW configured to operate on at least one reduction operation, where at least one reduction operation in the UW operates on one or more reduction variable instances; determining one or more reduction variable instances operated on by said current selected UW; recording, at run time, for said current selected UW, a list of reduction variable instances accessed by that current unit of work; and, determining, at run time, whether reduction variable instances accessed by the current selected UW conflict with any prior reduction variable instances recorded as having been accessed by prior selected units of work, and accumulating determined non-conflicting reduction variable instances as conflict free units of work (CFUW) when no conflicts are found, wherein accumulated CFUW are scheduled for parallel run-time operation by at least two or more processing threads.