Mechanism for increasing parallelization in computer programs with read-after-write dependencies associated with prefix operations

A system for increasing parallelization in a computer program, comprising:

• a set of processors configured to execute the computer program;
• and
• a parallelization apparatus configured to:
• obtain a binary associative operator and an ordered set of elements associated with a prefix operation in the computer program;
• divide the elements into multiple sets of contiguous iterations associated with the processors;
• calculate, in parallel on the processors, a set of local reductions from the contiguous operations, wherein the parallelization apparatus is configured to calculate each local reduction in the set by applying the binary associative operator between all elements in a corresponding contiguous iteration from the set of the contiguous iterations;
• for each given local reduction in a subset of the local reductions, calculate a first boundary prefix for the given local reduction by using the given local reduction and a second boundary prefix for a second local reduction in a second subset that precedes the given local reduction, wherein the second boundary prefix is calculated from the second local reduction and a third boundary prefix for a third local reduction in a third subset that precedes the second subset;
• and
• obtain a set of prefixes for the ordered set of elements by applying, in parallel on the processors, the boundary prefixes to the contiguous iterations using the binary associative operator.

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for increasing parallelization in a computer program, the method comprising:

• obtaining a binary associative operator and an ordered set of elements associated with a prefix operation in the computer program;
• dividing the elements into multiple sets of contiguous iterations based on a number of processors used to execute the computer program;
• calculating, in parallel on the processors, a set of local reductions from the contiguous iterations, wherein each local reduction in the set is calculated by applying the binary associative operator between all elements in a corresponding contiguous iteration from the set of the contiguous iterations;
• for each given local reduction in a subset of the local reductions, calculating a first boundary prefix for the given local reduction by using the given local reduction and a second boundary prefix for a second local reduction in a second subset that precedes the given local reduction, wherein the second boundary prefix is calculated from the second local reduction and a third boundary prefix for a third local reduction in a third subset that precedes the second subset;
• and
• obtaining a set of prefixes for the ordered set of elements by applying, in parallel on the processors, the boundary prefixes to the contiguous iterations using the binary associative operator.