CODE VERSIONING FOR ENABLING TRANSACTIONAL MEMORY PROMOTION

• US 20150113229A1
• Filed: 10/02/2014
• Published: 04/23/2015
• Est. Priority Date: 10/22/2013
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Boettiger, Hans, Gao, Yaoqing, Ohmacht, Martin, Wang, Kai-Ting Amy
• Granted Patent: US 9,405,596 B2
• Time in Patent Office: Days
• US Class Current: 711/145
• CPC Class Codes: G06F 8/4436 Exlining; Procedural abstraction
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

Code versioning for enabling transactional memory region promotion may include receiving a portion of candidate source code; outlining the portion of candidate source code received for parallel execution; wrapping a critical region with entry and exit routines to enter into a speculation sub-process, wherein the entry and exit routines also gather conflict statistics at run time; and generating an outlined code portion comprising multiple loop versions using a processor.

Claims

1. A computer-implemented process for code versioning for enabling transactional memory region promotion, the computer-implemented process comprising:

receiving a portion of candidate source code;

outlining the portion of candidate source code received for parallel execution;

wrapping a critical region with entry and exit routines to enter into a speculation sub-process, wherein the entry and exit routines also gather conflict statistics at run time; and

generating an outlined code portion comprising multiple loop versions using a processor.

2. The computer-implemented process of claim 1, further comprising:

executing the outlined code portion comprising multiple loop versions;

determining whether a predetermined threshold for transactional memory (TM) promotion with a first versioning condition is being met using an expression of ((number of loads+stores in single loop iteration)*(k from Equation

     1)<

Equation

     2) &

&

!conflictH1, wherein k is a number of iterations of a loop to be bundled into a single transaction, and Equation 1 is defined as k>

x/((c+nc)*(t−

1)) and Equation 2 is defined as (M/T)/cache line, wherein M is a number of bytes in a speculative buffer cache, T is a number of hardware threads and cache line represents a machine specific value of a size of a line of cache in bytes and wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, a machine specific value of transaction region enter and exit overhead of x number of cycles and t number of threads;

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the first versioning condition is met, determining whether a predetermined threshold for transaction memory (TM) promotion with a second versioning condition is met using the expression; and

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the second versioning condition is met;

using a default lock based approach.

3. The computer-implemented process of claim 2, wherein responsive to a determination the predetermined threshold for transactional memory (TM) promotion with the first versioning condition is not met using the expression, using a TM promotion approach.

4. The computer-implemented process of claim 2, wherein responsive to a determination the predetermined threshold for transactional memory (TM) promotion with the second versioning condition is not met using the expression, using a TM approach.

5. The computer-implemented process of claim 1, further comprising parallelizing the loop with a critical region using TM promotion using a costing expression defined as n*(c+x+nc)/t cycles wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, transaction region enter and exit overhead of x number of cycles and t number of threads.

6. The computer-implemented process of claim 1, further comprising parallelizing the loop with a critical region using global locking using a costing expression defined as one of n*(c+y) for nc<

=(c+y)*(t−

1) and as n*(c+y+nc)/t for nc>

(c+y)*(t−

1), for a workload dominated case wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, a global locking overhead of y cycles and t number of threads.

7. The computer-implemented process of claim 1, further comprising executing the code sequentially using a single thread, thus requiring no locking, using a costing expression defined as n*(c+nc), wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region.

8. A computer program product for code versioning for enabling transactional memory region promotion, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processor to perform a method comprising:

receiving a portion of candidate source code;

outlining the portion of candidate source code received for parallel execution;

wrapping a critical region with entry and exit routines to enter into a speculation sub-process, wherein the entry and exit routines also gather conflict statistics at run time; and

generating an outlined code portion comprising multiple loop versions.

9. The computer program product of claim 8, wherein the method further comprises:

executing the outlined code portion comprising multiple loop versions;

determining whether a predetermined threshold for transactional memory (TM) promotion with a first versioning condition is being met using an expression of ((number of loads+stores in single loop iteration)*(k from Equation

     1)<

Equation

     2) &

&

!conflictH1, wherein k is a number of iterations of a loop to be bundled into a single transaction, and Equation 1 is defined as k>

x/((c+nc)*(t−

1)) and Equation 2 is defined as (M/T)/cache line, wherein M is a number of bytes in a speculative buffer cache, T is a number of hardware threads and cache line represents a machine specific value of a size of a line of cache in bytes and wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, a machine specific value of transaction region enter and exit overhead of x number of cycles and t number of threads;

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the first versioning condition is met, determining whether a predetermined threshold for transaction memory (TM) promotion with a second versioning condition is met using the expression; and

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the second versioning condition is met;

using a default lock based approach.

10. The computer program product of claim 9, wherein the method further comprises, responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the first versioning condition is not met using the expression, further comprises computer executable program code for using a TM promotion approach.

11. The computer program product of claim 9, wherein the method further comprises, responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the second versioning condition is not met using the expression, further comprises computer executable program code for using a TM approach.

12. The computer program product of claim 8, wherein the method further comprises parallelizing the loop with a critical region using TM promotion using a costing expression defined as n*(c+x+nc)/t cycles wherein there are n iterations in a loop, each iteration having c number of cycles in a critical section, and nc number of cycles in a non-critical region, transaction region enter and exit overhead of x number of cycles and t number of threads.

13. The computer program product of claim 8, wherein the method further comprises parallelizing the loop with a critical region using global locking using a costing expression defined as one of n*(c+y) for nc<

=(c+y)*(t−

1) and as n*(c+y+nc)/t for nc>

(c+y)*(t−

1) for a workload dominated case wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, and a global locking overhead of y cycles and t number of threads.

14. The computer program product of claim 8, wherein the method further comprises running sequentially using a single thread, thus requiring no locking, using a costing expression defined as n*(c+nc), wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region.

15. An apparatus for code versioning for enabling transactional memory region promotion, the apparatus comprising:

a communications fabric;

a memory connected to the communications fabric, wherein the memory contains computer executable program code; and

a processor unit connected to the communications fabric, wherein the processor unit, responsive to executing the computer executable program code, initiates executable operations comprising;

receiving a portion of candidate source code;

outlining the portion of candidate source code received for parallel execution;

wrapping a critical region with entry and exit routines to enter into a speculation sub-process, wherein the entry and exit routines also gather conflict statistics at run time; and

generating an outlined code portion comprising multiple loop versions.

16. The apparatus of claim 15, wherein the executable operations further comprise:

executing the outlined code portion comprising multiple loop versions;

determining whether a predetermined threshold for transactional memory (TM) promotion with a first versioning condition is being met using an expression of ((number of loads+stores in single loop iteration)*(k from Equation

     1)<

Equation

     2) &

&

!conflictH1, wherein k is a number of iterations of a loop to be bundled into a single transaction, and Equation 1 is defined as k>

x/((c+nc)*(t−

1)) and Equation 2 is defined as (M/T)/cache line, wherein M is a number of bytes in a speculative buffer cache, T is a number of hardware threads and cache line represents a machine specific value of a size of a line of cache in bytes and wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, a machine specific value of transaction region enter and exit overhead of x number of cycles and t number of threads;

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the first versioning condition is met, determining whether a predetermined threshold for transaction memory (TM) promotion with a second versioning condition is met using the expression; and

responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the second versioning condition is met;

using a default lock based approach.

17. The apparatus of claim 16, wherein the executable operations further comprise, responsive to a determination the predetermined threshold for transactional memory (TM) promotion with the first versioning condition is not met using the expression, using a TM promotion approach.

18. The apparatus of claim 16, wherein the executable operations further comprise, responsive to a determination the predetermined threshold for transaction memory (TM) promotion with the second versioning is not met using the expression, using a TM approach.

19. The apparatus of claim 15, wherein the executable operations further comprises parallelizing the loop with a critical region using TM promotion using a costing expression defined as n*(c+x+nc)/t cycles wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, transaction region enter and exit overhead of x number of cycles and t number of threads.

20. The apparatus of claim 15, wherein the executable operations further comprise parallelizing the loop with a critical region using global locking using a costing expression defined as one of n*(c+y) for nc<

=(c+y)*(t−

1) and as n*(c+y+nc)/t for nc>

(c+y)*(t−

1), for a workload dominated case wherein there are n iterations in a loop, each iteration having c number of cycles in a critical region, and nc number of cycles in a non-critical region, a global locking overhead of y cycles and t number of threads.