Automatic pipeline parallelization of sequential code

A computer program product comprising:

• a computer readable hardware storage device having a computer readable program code embodied therein, said computer readable program code containing instructions that perform a method for automatically pipeline parallelizing a nested loop L in sequential code over K number of threads, said method comprising:
• discovering, by a processor of a computer system, all thread allocations that map each subloop of the nested loop L to a subset of said K number of threads;
• said processor configuring all combinations of stage partitions executing the nested loop L by parallelly running said each subloop by said K number of threads pursuant to task dependencies of the nested loop L, wherein each stage partition of said all combinations is associated with each thread allocation from said discovering;
• said processor calculating a respective bottleneck of each combination from said configuring, wherein the respective bottleneck represents a respective highest fraction in percentage of workload of the nested loop L allocated to a Central Processing Unit (CPU) among said K number of threads;
• and
• said processor selecting a smallest bottleneck from said calculating, wherein a first combination associated with the smallest bottleneck is utilized in parallelizing the nested loop L for a most uniformly distributed workload over said K number of threads.

A computer system comprising a processor, a memory coupled to the processor, and a computer readable storage device coupled to the processor, said storage device containing program code configured to be executed by the processor via the memory to implement a method for automatically pipeline parallelizing a nested loop L in sequential code over K number of threads, said method comprising:

• said processor discovering all thread allocations that map each subloop of the nested loop L to a subset of said K number of threads;
• said processor configuring all combinations of stage partitions executing the nested loop L by parallelly running said each subloop by said K number of threads pursuant to task dependencies of the nested loop L, wherein each stage partition of said all combinations is associated with each thread allocation from said discovering;
• said processor calculating a respective bottleneck of each combination from said configuring, wherein the respective bottleneck represents a respective highest fraction in percentage of workload of the nested loop L allocated to a Central Processing Unit (CPU) among said K number of threads;
• and
• said processor selecting a smallest bottleneck from said calculating, wherein a first combination associated with the smallest bottleneck is utilized in parallelizing the nested loop L for a most uniformly distributed workload over said K number of threads.

A process for supporting computer infrastructure, said process comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable code in a computing system, wherein the code in combination with the computing system is configured to perform a method for automatically pipeline parallelizing a nested loop L in sequential code over K number of threads, said method comprising:

• discovering, by a processor of the computing system, all thread allocations that map each subloop of the nested loop L to a subset of said K number of threads;
• said processor configuring all combinations of stage partitions executing the nested loop L by parallelly running said each subloop by said K number of threads pursuant to task dependencies of the nested loop L, wherein each stage partition of said all combinations is associated with each thread allocation from said discovering;
• said processor calculating a respective bottleneck of each combination from said configuring, wherein the respective bottleneck represents a respective highest fraction in percentage of workload of the nested loop L allocated to a Central Processing Unit (CPU) among said K number of threads;
• and
• said processor selecting a smallest bottleneck from said calculating, wherein a first combination associated with the smallest bottleneck is utilized in parallelizing the nested loop L for a most uniformly distributed workload over said K number of threads.