Efficient generation of SIMD code in presence of multi-threading and other false sharing conditions and in machines having memory protection support

• US 7,730,463 B2
• Filed: 02/21/2006
• Issued: 06/01/2010
• Est. Priority Date: 02/21/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Peng, Eichenberger, Alexandre E., Zhao, Peng, Wang, Kai-Ting Amy
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): PATEL, HIREN P
• Application Number:
  US11/358,372
• Publication Number:
  US 20070226723A1
• Time in Patent Office: 1,561 Days
• Field of Search: 717/3, 717/106, 717/109, 717/136, 717/137, 717149-151, 717154-156, 717159-161, 712/6, 712 20- 22, 712/42, 712/217, 712/224, 712/241
• US Class Current: 717/136
• CPC Class Codes: G06F 8/44 Encoding
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A computer implemented method, system and computer program product for automatically generating SIMD code. The method begins by analyzing data to be accessed by a targeted loop including at least one statement, where each statement has at least one memory reference, to determine if memory accesses are safe. If memory accesses are safe, the targeted loop is simdized. If not safe, it is determined if a scheme can be applied in which safety need not be guaranteed. If such a scheme can be applied, the targeted loop is simdized according to the scheme. If such a scheme cannot be applied, it is determined if padding is appropriate. If padding is appropriate, the data is padded and the targeted loop is simdized. If padding is not appropriate, non-simdized code is generated based on the targeted loop for handling boundary conditions, the targeted loop is simdized and combined with the non-simdized code.

Claims

1. A computer implemented method for automatically generating SIMD code, comprising:

analyzing, by a processing unit, data to be accessed by a targeted loop, the targeted loop comprising at least one statement, each at least one statement having at least one memory reference, to determine whether memory accesses are both memory protection system safe and false sharing safe;

responsive to a determination that memory accesses are both memory protection system safe and false sharing safe, simdizing the targeted loop;

responsive to a determination that memory accesses are not both memory protection system safe and false sharing safe, determining whether a scheme can be applied in which safety does not need to be guaranteed;

responsive to a determination that a scheme in which safety does not need to be guaranteed can be applied, applying the scheme and simdizing the targeted loop according to the applied scheme;

responsive to a determination that a scheme in which safety does not need to be guaranteed cannot be applied, determining whether padding is appropriate;

responsive to a determination that padding is appropriate, padding the data and simdizing the targeted loop; and

responsive to a determination that padding is not appropriate, generating non-simdized code based on the targeted loop for handling boundary conditions, simdizing the targeted loop, and combining the simdized targeted loop with the non-simdized code.

2. The computer implemented method according to claim 1, wherein generating non-simdized code based on the targeted loop for handling boundary conditions comprises:

generating at least one of prologue sequential code and epilogue sequential code to handle boundary conditions in the presence of false sharing conditions.

3. The computer implemented method according to claim 2, wherein generating at least one of prologue sequential code and epilogue sequential code comprises:

generating prologue sequential code only when memory accesses are not safe for an initial set of iterations of the original targeted loop, and generating epilogue sequential code only when memory accesses are not safe for a final set of iterations of the original targeted loop.

4. The computer implemented method according to claim 2, wherein generating at least one of prologue sequential code and epilogue sequential code comprises:

copying each necessary statement from the targeted loop and distributing each such copied statement within each of the at least one of the prologue sequential code and the epilogue sequential code to corresponding distinct loops and causing each distinct loop to iterate precisely over an appropriate number of iterations for that loop'"'"'s copied statement.

5. The computer implemented method according to claim 2, wherein generating at least one of prologue sequential code and epilogue sequential code comprises:

copying each necessary statement from the targeted loop and generating a single loop for each of the at least one of the prologue sequential code and the epilogue sequential code wherein each such single loop contains each copied statement and further contains, for each copied statement, a corresponding conditional statement guarding the copied statement, each such conditional statement comprising a condition that determines precisely which iteration of the copied statement guarded by that conditional statement is executed.

6. The computer implemented method according to claim 2, wherein generating at least one of prologue sequential code and epilogue sequential code comprises:

copying each necessary statement from the targeted loop and generating a single loop for each of the at least one of the prologue sequential code and the epilogue sequential code wherein each such single loop contains each copied statement and further contains, only for each copied statement for which re-execution of that statement would affect an outcome of the targeted loop, a corresponding conditional statement guarding the copied statement, each such conditional statement comprising a condition that determines precisely which iteration of the copied statement guarded by that conditional statement is executed.

7. The computer implemented method according to claim 1, wherein the scheme comprises:

performing a memory location analysis to determine if all of the memory references are relatively aligned; and

responsive to a determination that all of the memory references are relatively aligned, simdizing the targeted loop.

8. The computer implemented method according to claim 7, wherein the scheme further comprises:

responsive to a determination that all of the memory references are not relatively aligned, determining whether alignment of the memory references can be determined statically; and

responsive to a determination that alignment of the memory references can be determined statically, simdizing the targeted loop using statically determined memory references to prevent unnecessary loads.

9. The computer implemented method according to claim 8, wherein the scheme further comprises:

responsive to a determination that alignment of the memory references cannot be determined statically, determining whether modified stream shifting is appropriate;

responsive to a determination that modified stream shifting is appropriate, simdizing the targeted loop;

responsive to simdizing the targeted loop, determining which statements within the targeted loop include a stream shifting operation; and

responsive to determining which statements within the targeted loop include a stream shifting operation, modifying each such statement in a first and last simdized iteration of the simdized targeted loop by replacing each stream shifting operation within each such statement with a modified stream shifting operation that results in one of a first safe situation in which any data located in any memory reference accessed by the modified stream shifting operation is actually used and is guaranteed to be safe, and a second safe situation in which any data located in any memory reference accessed by the modified stream shifting operation is discarded without having an adverse impact on any result of the simdized targeted loop.

10. The computer implemented method according to claim 1, wherein generating non-simdized code based on the targeted loop for handling boundary conditions comprises:

applying memory access guarding to at least one of a prologue statement and an epilogue statement for handling boundary conditions in the presence of a memory protection support system.

11. A computer program product, comprising:

a computer readable storage medium storing computer usable program code configured for automatically generating SIMD code, the computer usable program code comprising;

computer usable program code configured for analyzing data to be accessed by a targeted loop, the targeted loop comprising at least one statement, each at least one statement having at least one memory reference, to determine whether memory accesses are both memory protection system safe and false sharing safe;

computer usable program code configured for simdizing the targeted loop in response to a determination that memory accesses are both memory protection system safe and false sharing safe;

computer usable program code configured for determining whether a scheme can be applied in which safety does not need to be guaranteed in response to a determination that memory accesses are not both memory protection system safe and false sharing safe;

computer usable program code configured for applying the scheme and simdizing the targeted loop according to the applied scheme in response to a determination that a scheme in which safety does not need to be guaranteed can be applied;

computer usable program code configured for determining whether padding is appropriate in response to a determination that a scheme in which safety does not need to be guaranteed cannot be applied;

computer usable program code configured for padding the data and simdizing the targeted loop in response to a determination that padding is appropriate; and

computer usable program code configured for generating non-simdized code based on the targeted loop for handling boundary conditions, simdizing the targeted loop, and combining the simdized targeted loop with the non-simdized code, in response to a determination that padding is not appropriate.

12. The computer program product according to claim 11, wherein the computer usable program code configured for generating non-simdized code based on the targeted loop for handling boundary conditions comprises:

computer usable program code configured for generating at least one of prologue sequential code and epilogue sequential code to handle boundary conditions in the presence of false sharing conditions.

13. The computer program product according to claim 12, wherein the computer usable program code configured for generating at least one of prologue sequential code and epilogue sequential code comprises:

computer usable program code configured for generating prologue sequential code only when memory accesses are not safe for an initial set of iterations of the original targeted loop, and generating epilogue sequential code only when memory accesses are not safe for a final set of iterations of the original targeted loop.

14. The computer program product according to claim 12, wherein the computer usable program code configured for generating at least one of prologue sequential code and epilogue sequential code comprises:

computer usable program code configured for copying each necessary statement from the targeted loop and distributing each such copied statement within each of the at least one of the prologue sequential code and the epilogue sequential code to corresponding distinct loops and causing each distinct loop to iterate precisely over an appropriate number of iterations for that loop'"'"'s copied statement.

15. The computer program product according to claim 12, wherein the computer usable program code configured for generating at least one of prologue sequential code and epilogue sequential code comprises:

computer usable program code configured for copying each necessary statement from the targeted loop and generating a single loop for each of the at least one of the prologue sequential code and the epilogue sequential code wherein each such single loop contains each copied statement and further contains, for each copied statement, a corresponding conditional statement guarding the copied statement, each such conditional statement comprising a condition that determines precisely which iteration of the copied statement guarded by that conditional statement is executed.

16. The computer program product according to claim 12, wherein the computer usable program code configured for generating at least one of prologue sequential code and epilogue sequential code comprises:

computer usable program code configured for copying each necessary statement from the targeted loop and generating a single loop for each of the at least one of the prologue sequential code and the epilogue sequential code wherein each such single loop contains each copied statement and further contains, only for each copied statement for which re-execution of that statement would affect an outcome of the targeted loop, a corresponding conditional statement guarding the copied statement, each such conditional statement comprising a condition that determines precisely which iteration of the copied statement guarded by that conditional statement is executed.

17. The computer program product according to claim 11, wherein the computer usable program code configured for applying the scheme and simdizing the targeted loop according to the applied scheme comprises:

computer usable program code configured for performing a memory location analysis to determine if all of the memory references are relatively aligned; and

computer usable program code configured for simdizing the targeted loop in response to a determination that all of the memory references are relatively aligned.

18. The computer program product according to claim 17, wherein the computer usable program code configured for applying the scheme and simdizing the targeted loop according to the applied scheme further comprises:

computer usable program code configured for determining whether alignment of the memory references can be determined statically in response to a determination that all of the memory references are not relatively aligned; and

computer usable program code configured for simdizing the targeted loop using statically determined memory references to prevent unnecessary loads in response to a determination that alignment of the memory references can be determined statically.

19. The computer program product according to claim 18, wherein the computer usable program code configured for applying the scheme and simdizing the targeted loop according to the applied scheme further comprises:

computer usable program code configured for determining whether modified stream shifting is appropriate in response to a determination that alignment of the memory references cannot be determined statically;

computer usable program code configured for simdizing the targeted loop in response to a determination that modified stream shifting is appropriate;

computer usable program code configured for determining which statements within the targeted loop include a stream shifting operation in response to simdizing the targeted loop; and

computer usable program code configured for, in response to determining which statements within the targeted loop include a stream shifting operation, modifying each such statement in a first and last simdized iteration of the simdized targeted loop by replacing each stream shifting operation within each such statement with a modified stream shifting operation that results in one of a first safe situation in which any data located in any memory reference accessed by the modified stream shifting operation is actually used and is guaranteed to be safe, and a second safe situation in which any data located in any memory reference accessed by the modified stream shifting operation is discarded without having an adverse impact on any result of the simdized targeted loop.

20. The computer program product according to claim 11, wherein the computer usable program code configured for generating non-simdized code based on the targeted loop for handling boundary conditions comprises:

computer usable program code configured for applying memory access guarding to at least one of a prologue statement and an epilogue statement for handling boundary conditions in the presence of a memory protection support system.

21. A system for automatically generating SIMD code, comprising:

a processing unit for analyzing data to be accessed by a targeted loop comprising at least one statement, each at least one statement having at least one memory reference;

a simdizer for simdizing the targeted loop, wherein the simdizer simdizes the target loop in response to a determination by the processing unit that memory accesses are both memory protection system safe and false sharing safe;

wherein, responsive to a determination by processing unit that memory accesses are not both memory protection system safe and false sharing safe, the processing unit determines whether a scheme can be applied in which safety does not need to be guaranteed;

wherein, responsive to a determination by the processing unit that a scheme in which safety does not need to be guaranteed can be applied, the simdizer simdizes the targeted loop according to the scheme;

wherein, responsive to a determination by the processing unit that a scheme in which safety does not need to be guaranteed cannot be applied, the processing unit determines whether padding is appropriate;

a padding mechanism, responsive to a determination by the processing unit that padding is appropriate, for padding the data, wherein the simdizer simdizes the targeted loop in response to application of padding;

a code generator, wherein responsive to a determination by the processing unit that padding is not appropriate, the code generator generates non-simdized code based on the targeted loop for handling boundary conditions, and wherein the simdizer simdizes the targeted loop; and

a combining mechanism for combining the simdized targeted loop with the non-simdized code in response to generation of the non-simdized code and to the simdizer simdizing the targeted loop.