SINGLE INSTRUCTION MULTIPLE DATA (SIMD) CODE GENERATION FOR PARALLEL LOOPS USING VERSIONING AND SCHEDULING

• US 20100011339A1
• Filed: 07/11/2008
• Published: 01/14/2010
• Est. Priority Date: 07/11/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eichenberger, Alexandre E., Zhang, Guansong, Silvera, Raul E., Wang, Amy K.
• Granted Patent: US 8,341,615 B2
• Time in Patent Office: Days
• US Class Current: 717/106
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

Embodiments of the present invention address deficiencies of the art in respect to loop parallelization for a target architecture implementing a shared memory model and provide a novel and non-obvious method, system and computer program product for SIMD code generation for parallel loops using versioning and scheduling. In an embodiment of the invention, within a code compilation data processing system a parallel SIMD loop code generation method can include identifying a loop in a representation of source code as a parallel loop candidate, either through a user directive or through auto-parallelization. The method also can include selecting a trip count condition responsive to a scheduling policy set for the code compilation data processing system and also on a minimal simdizable threshold, determining a trip count and an alignment constraint for the selected loop, and generating a version of a parallel loop in the source code according to the alignment constraint and a comparison of the trip count to the trip count condition.

Claims

1. In a code compilation data processing system, a single instruction multiple data (SIMD) parallel loop code generation method comprising:

identifying a loop in a representation of source code in a code compilation data processing system;

selecting a trip count condition responsive to a scheduling policy set for the code compilation data processing system and also responsive to a minimal simdizable threshold;

determining a trip count and an alignment constraint for the selected loop; and

,

generating a version of a parallel loop in the source code according to the relative alignment condition and a comparison of the trip count to the trip count condition.

2. The method of claim 1, further comprising inserting a prologue splicing operation and an epilogue splicing operation before and after a simdized body of a version of the parallel loop to provide dirty bit information in connection with the prologue and epilogue splicing operations.

3. The method of claim 1, wherein selecting a trip count condition comprises selecting a trip count condition based upon a scheduling policy for a target multiprocessor supporting a shared memory Application Programming Interface (API).

4. The method of claim 3, wherein selecting a trip count condition selecting at least a three times a blocking factor (B) of the selected loop as a trip count condition for flexible scheduling policies, and selecting at least 3B*a maximum number of threads permitted for a parallel region as a trip condition for system imposed, rigid scheduling policies.

5. The method of claim 1, wherein generating a version of a parallel loop in the source code according to the alignment constraint and a comparison of the trip count to the trip count condition comprises:

generating a first version when the trip count for the selected loop is below a minimum SIMD threshold set by the trip count condition and the scheduling policy;

generating a second version when only compile time shifts are required to manage alignment; and

,

generating a third version when both compile time and runtime shifts are required to manage alignment.

6. A code compilation data processing system comprising:

a host computing platform supporting an operating system managing a compiler executing in the operating system;

a shared memory application programming interface (API) supported by the compiler; and

,

single instruction multiple data (SIMD) code generation logic coupled to the compiler and accessing the shared memory API, the logic comprising program code enabled to generate one of three versions of a parallel loop for a selected loop in representation of source code according to a computed alignment constraint and a comparison of a trip count determined for the loop with a specified trip count condition.

7. The system of claim 6, wherein the shared memory API comprises at least a splice sequence of instructions communicating dirty bit information to a cache when executed.

8. The system of claim 6, wherein the specified trip count condition is variable responsive to a scheduling policy set for the compiler and also responsive to a minimal simdizable threshold.

9. A computer program product comprising a computer usable medium embodying computer usable program code for single instruction multiple data (SIMD) parallel loop code generation, the computer program product comprising:

computer usable program code for identifying a loop in a representation of source code in a code compilation data processing system;

computer usable program code for selecting a trip count condition responsive to a scheduling policy set for the code compilation data processing system and also responsive to a minimal simdizable threshold;

computer usable program code for determining a trip count and an alignment constraint for the selected loop; and

,

computer usable program code for generating a version of a parallel loop in the source code according to the alignment constraint and a comparison of the trip count to the trip count condition.

10. The computer program product of claim 9, further comprising computer usable program code for inserting a prologue splicing operation and an epilogue splicing operation before and after a simdized body of a version of the parallel loop to provide dirty bit information in connection with the prologue and epilogue splicing operations.

11. The computer program product of claim 9, wherein the computer usable program code for selecting a trip count condition comprises computer usable program code for selecting a trip count condition based upon a scheduling scheme for a multiprocessor with a shared memory API.

12. The computer program product of claim 11, wherein the computer usable program code for selecting a trip count condition, comprises computer usable program code selecting at least three times a blocking factor (B) of the selected loop as a trip count condition for flexible scheduling policies, and selecting 3B*a maximum number of threads permitted for a parallel region as a trip condition for system imposed, rigid scheduling.

13. The computer program product of claim 9, wherein the computer usable program code for generating a version of a parallel loop in the source code according to the alignment constraint and a comparison of the trip count to the trip count condition comprises:

computer usable program code for generating a first version when the trip count for the selected loop is below a minimum SIMD threshold set by the trip count condition and scheduling policy;

computer usable program code for generating a second version when only compile time shifts are required to manage alignment; and

,

computer usable program code for generating a third version when both compile time and runtime shifts are required to manage alignment.