To: J3 08-168r1 From: Bill Long, Aleksandar Donev Subject: Adding locks to the co-array core subset Date: 2008 May 14 References: J3/08-126, J3/08-007r2 (WG5/N1723) Background: ----------- Paper 08-126 is the critique of coarrays from the Rice University group submitted at meeting 183. A reply to that paper was formed following the meeting (see paper J3/08-167). One major issue, the lack of a lock facility, was felt to be sufficiently important to have in the initial Fortran 2008 language. In anticipation of a formal public comment on this topic, Specification, Syntax, and Edits are provided below. Specification: -------------- Locks are scalar variables that have one of two values: locked or unlocked. The operations that change the value of a lock are atomic, so that multiple images might concurrently attempt to set its value to locked (acquire the lock) or unlocked (release the lock), but only one image will succeed. Other parallel programming models contain tools to manipulate locks. A lock variable permits fine-grain disjoint access to a data structure. Critical sections, by contrast, permit disjoint access to a sequence of statements. Using lock variables, one can scale the amount of potential concurrency with the size of a data structure by protecting sections of the data structure (e.g. nodes in a graph) individually with locks, if desired. Locks are scalar objects of an intrinsic opaque derived type, LOCK_T, defined in the intrinsic module ISO_FORTRAN_ENV. This type is default-initialized to unlocked. Typically, locks will be declared to be coarrays. New image control statements, LOCK and UNLOCK, are provided to alter the values of locks. Execution of either statement includes the effect of executing a SYNC MEMORY statement. A lock variable is currently locked by an image if its value was set to locked by that image and has not been subsequently unlocked. Execution of a LOCK statement without a SUCCESS= specifier causes the to be assigned the value of locked. If the lock variable is currently locked by a different image, and no error condition occurs, execution of the LOCK statement completes when the lock is released by the other image and acquired by this image. Execution of a LOCK statement with a SUCCESS= specifier causes the to be assigned the value locked and the value of the SUCCESS variable to true, if it was currently unlocked. Otherwise, the is not changed and the value of the SUCCESS variable is set to false. The in a LOCK statement shall not be currently locked by the image executing the LOCK statement. An error condition occurs if a LOCK statement specifies a lock variable that is currently locked by the executing image. Execution of an UNLOCK statement causes the value of the to be set to unlocked. The shall be currently locked by the executing image. An error condition occurs if the value of the lock variable in an UNLOCK statement is unlocked, or if the variable is currently locked by a different image. Example: -------- USE, INTRINSIC :: ISO_FORTRAN_ENV TYPE(LOCK_T) :: queue_lock[*] ! Lock to manage the work queue INTEGER :: work_queue_size[*] TYPE(Task) :: work_queue(100)[*] ! List of tasks to perform TYPE(Task) :: job ! Current task working on INTEGER :: me me=THIS_IMAGE() DO ! Process the next item in your work queue LOCK(queue_lock) ! New segment A starts ! This segment A is ordered with respect to ! segment B executed by image me-1 below because of lock exclusion IF(work_queue_size>0) THEN ! Fetch the next job from the queue job=work_queue(work_queue_size) work_queue_size=work_queue_size-1 END IF UNLOCK(queue_lock) ! Segment ends ... ! Actually process the task ! Add a new task on neighbors queue: LOCK(queue_lock[me+1]) ! Starts segment B ! This segment B is ordered with respect to ! segment A executed by image me+1 above because of lock exclusion IF(work_queue_size[me+1] <> LOCK ( [, ] ) <> UNLOCK ( [, ] ) is Constraint: shall be a scalar variable of type LOCK_T defined in the intrinsic module ISO_FORTRAN_ENV. <> SUCCESS= <> Edits: ------ ------------------------------------ [28] In 2.2 "High level syntax" rule R214 "" add two new entries alphabetically: "<> " "<> " ------------------------------------ [174:8.1.6p1] Following R819 of "CRITICAL construct" add a new syntax rule and constraint: ------------------------------------ [187:8.5.1p2] In the bullet list of 8.5.1 "Image control statements", after the entry that begins "CRITICAL ..." add a new entry: "LOCK or UNLOCK statement;" ------------------------------------ [191] After subclause 8.5.4 "SYNC MEMORY statement", add a new subclause: "8.5.4a LOCK and UNLOCK statements R862a <> LOCK ( [, ] ) R862b <> SUCCESS= <> R862c <> UNLOCK ( [, ] ) R862d <> C851a (R862d) A shall be of type LOCK_T defined in the intrinsic module ISO_FORTRAN_ENV. A represents two values of a lock: locked and unlocked. A lock is acquired by setting its value to locked, and released by setting its value to unlocked. A lock variable is currently locked by an image if it value was set to locked by that image and has not been subsequently set to unlocked. Execution of a LOCK statement without a SUCCESS= specifier causes the to be assigned the value of locked. If the lock variable is currently locked by a different image, execution of the LOCK statement completes when the lock is released by the other image and acquired by this image. If a has the value unlocked, execution of a LOCK statement with a SUCCESS= specifier causes the to be assigned the value locked and the value of the SUCCESS variable to true. Otherwise, the is not changed and the value of the SUCCESS variable is set to false. The in a LOCK statement shall not be currently locked by the image executing the LOCK statement. Execution of an UNLOCK statement causes the value of the to be set to unlocked. The shall be currently locked by the executing image. NOTE 8.39a A lock variable is effectively defined atomically by a LOCK or UNLOCK statement. If LOCK statements on two images both attempt to acquire a lock, one will succeed and the other will either fail, if a SUCCESS= specifier was provided, or will wait until the lock is later released. [End NOTE] NOTE 8.39b The following example illustrates the use of LOCK and UNLOCK statements to manage a work queue: USE, INTRINSIC :: ISO_FORTRAN_ENV TYPE(LOCK_T) :: queue_lock[*] ! Lock to manage the work queue INTEGER :: work_queue_size[*] TYPE(Task) :: work_queue(100)[*] ! List of tasks to perform TYPE(Task) :: job ! Current task working on INTEGER :: me me=THIS_IMAGE() DO ! Process the next item in your work queue LOCK(queue_lock) ! New segment A starts ! This segment A is ordered with respect to ! segment B executed by image me-1 below because of lock exclusion IF(work_queue_size>0) THEN ! Fetch the next job from the queue job=work_queue(work_queue_size) work_queue_size=work_queue_size-1 END IF UNLOCK(queue_lock) ! Segment ends ... ! Actually process the task ! Add a new task on neighbors queue: LOCK(queue_lock[me+1]) ! Starts segment B ! This segment B is ordered with respect to ! segment A executed by image me+1 above because of lock exclusion IF(work_queue_size[me+1]s in LOCK or UNLOCK statements (\ref{LOCK and UNLOCK statements})." ------------------------------------ [453:16.6.3p1] In the list in 16.6.3 "Variables that are initially defined" in list item (6) replace the final "." with ";" and add to the end of the list: "(7) variables of type LOCK_T defined in the intrinsic module ISO_FORTRAN_ENV." ------------------------------------ [454:16.6.5p1] In the list in 16.6.5 "Events that cause variables to become defined" add two new list items at the end: "(29) Execution of a LOCK statement containing a SUCESS= specifier causes the specified logical variable to become defined. If the logical variable becomes defined with the value true, the in the LOCK statement also becomes defined. (30) Execution of a LOCK statement that does not contain a SUCCESS= specifier causes the to become defined. (31) Execution of an UNLOCK statement causes the to become defined. ------------------------------------ [456:16.6.7p1] In the list in 16.6.7 "Variable definition context", in list item (13) replace the final "." with ";" and add two new items at the end of the list: "(14) a ;" (15) a SUCCESS= specifier in a LOCK statement."