CVS difference for ai12s/ai12-0119-1.txt

Differences between 1.17 and version 1.18
Log of other versions for file ai12s/ai12-0119-1.txt

--- ai12s/ai12-0119-1.txt	2018/04/14 04:21:00	1.17
+++ ai12s/ai12-0119-1.txt	2018/06/12 01:43:50	1.18
@@ -1,4 +1,4 @@
-!standard 5.5.2(2/3)                               18-03-29    AI12-0119-1/08
+!standard 5.5.2(2/3)                               18-06-10    AI12-0119-1/09
 !class Amendment 14-06-20
 !status work item 14-06-20
 !status received 14-06-17
@@ -132,91 +132,108 @@
 Note that the same rules presented for parallel blocks above also apply to
 the update of shared variables and the transfer of control to a point
 outside of the loop, and for this purpose each iteration can be considered
-as being equivalent to a separate sequence of a concurrent block.
+as being equivalent to a separate sequence of a parallel block.
 
 !wording
 
-Append to Introduction (28)
-"A parallel block statement requests that two or more sequences of
- statements should execute in parallel with each other."
+Add to the end of Introduction (28):
+  A parallel block statement comprises two or more sequences of
+  statements that should execute in parallel with each other. A parallel
+  loop statement has a loop body that is to be executed in parallel for
+  each iteration of the loop.
 
-Modify 2.9(2/3)
-Add "parallel" to the list of reserved words.
+Modify 2.9(2/3):
+  Add "parallel" to the list of reserved words.
 
-Modify 5.1(5/2)
-add "parallel_block_statement" to the list of compound statements
+Modify 5.1(5/2):
 
-Replace 5.5(3/3)
+  add "parallel_block_statement" to the list of compound statements.
 
+Replace 5.5(3/3):
+
 Iteration_scheme ::= while condition
    | [parallel] for loop_parameter_specification
    |            for iterator_specification
-
-Add after 5.5(6/5)
-
-{Legality Rules}
-A loop_statement shall not have both reserved words reverse and parallel present.
 
-Add after 5.5(7)
+Add after 5.5(6/5):
 
-When the reserved word parallel is present and a transfer of control out of the
-loop occurs, an attempt is made to cancel further parallel execution of the
-sequence_of_statements that has not yet started. The completion of a
-loop_statement for a transfer of control out of the loop is delayed until all
-parallel execution of the sequence_of_statements is complete. If a transfer of
-control out of the loop occurs in multiple parallel executions of the
-sequence_of_statements then only the run time action of the first encountered
-transfer of control occurs.
-
-Modify 5.5(9/4)
-
-For the execution of a loop_statement with the iteration_scheme being for
-loop_parameter_specification, the loop_parameter_specification is first
-elaborated. This elaboration creates {objects of} the loop parameter and
-elaborates the discrete_subtype_definition. {If the keyword parallel is present,
-multiple objects of the loop parameter are created where each iteration is
-associated with a specific loop parameter object, otherwise a single loop
-parameter object is created. Each loop parameter object is associated with a
-thread of control where each thread proceeds independently and concurrently
-between the points where they interact with other tasks and with each other.} If
-the discrete_subtype_definition defines a subtype with a null range, the
-execution of the loop_statement is complete. Otherwise, the
-sequence_of_statements is executed once for each value of the discrete subtype
-defined by the discrete_subtype_definition that satisfies the predicates of the
-subtype (or until the loop is left as a consequence of a transfer of control).
-Prior to each such iteration, the corresponding value of the discrete subtype is
-assigned to [the]{a} loop parameter {object}. These values are assigned in
-increasing order unless the reserved word reverse is present, in which case the
-values are assigned in decreasing order {, or unless the reserved word parallel
-is present, in which case the order is arbitrary}.
-
-AARM - An implementation should statically treat the
-sequence_of_statements as being executed by separate threads of control,
-but whether they actually execute in parallel or sequentially should be a
-determination that is made dynamically at run time, dependent on factors
-such as the available computing resources.
+  [editor: still part of syntax rules]
+  An iteration_scheme that begins with the reserved word parallel shall
+  not have the reserved word reverse in its loop_parameter_specification.
+
+Modify 5.5(7):
+
+  For the execution of a loop_statement, the sequence_of_statements is
+  executed [repeatedly,] zero or more times, until the loop_statement is
+  complete. The loop_statement is complete when a transfer of control
+  occurs that transfers control out of the loop, or, in the case of an
+  iteration_scheme, as specified below.
+
+Modify 5.5(9/4):
+
+  For the execution of a loop_statement with the iteration_scheme being
+  for loop_parameter_specification, the loop_parameter_specification is
+  first elaborated. This elaboration creates the loop parameter and
+  elaborates the discrete_subtype_definition. If the
+  discrete_subtype_definition defines a subtype with a null range, the
+  execution of the loop_statement is complete. Otherwise, the
+  sequence_of_statements is executed once for each value of the discrete
+  subtype defined by the discrete_subtype_definition that satisfies the
+  predicates of the subtype (or until the loop is left as a consequence
+  of a transfer of control). Prior to each such iteration, the
+  corresponding value of the discrete subtype is assigned to the loop
+  parameter. {If the reserved word parallel is present (a /parallel/
+  loop), each iteration is a separate logical thread of control (see 9),
+  with its own copy of the loop parameter; otherwise the} [These] values
+  are assigned {to the loop parameter} in increasing order unless the
+  reserved word reverse is present, in which case the values are
+  assigned in decreasing order.
+
+Add after 5.5(9/4):
+
+  Within a parellel loop, if a transfer of control out of the loop is
+  initiated by one of the iterations, an attempt is made to cancel all
+  other iterations of the loop. Once all other iterations of the loop
+  either complete or are canceled, the transfer of control occurs.  If
+  two or more iterations initiate such a transfer of control
+  concurrently, one of them is chosen arbitrarily and the others are
+  canceled.
+
+  AARM Implementation note: -- Each iteration of a parallel loop is a
+  separate logical thread of control.  Normally these logical threads of
+  control will be grouped into "chunks" for the purpose of execution to
+  reduce the cost of creating large numbers of (physical) threads of
+  control.
+
+Add after 5.5(9.1/3):
+
+  Bounded (Run-Time) Errors
+
+  During the execution of one of the iterations of a parallel loop, it
+  is a bounded error to invoke an operation that is potentially blocking
+  (see 9.5).
 
-Add after 5.5(21)
+Add after 5.5(21):
 
-Example of a parallel loop
+  Example of a parallel loop:
 
--- 
-parallel
-for I in Grid(1)'Range loop
-   Grid(I, 1) := (for all J in Grid(2)'Range => Grid(I,J) = True);
-end loop;
+  -- See 3.6(30/2)
+  parallel
+  for I in Grid(1)'Range loop
+     Grid(I, 1) := (for all J in Grid(2)'Range => Grid(I,J) = True);
+  end loop;
 
 Add a new subclause
 
 5.6.1 Parallel Block Statements
 
-A parallel_block_statement encloses two or more handled_sequence_of_statements
-where all the handled_sequence_of_statements can execute in parallel with each
-other.
+A parallel_block_statement encloses two or more
+handled_sequence_of_statements where each represents a separate logical
+thread of control.
 
 Syntax
 
-parallel_block_statement ::=
+  parallel_block_statement ::=
     parallel
     do
       handled_sequence_of_statements
@@ -225,41 +242,38 @@
    {and
       handled_sequence_of_statements}
     end do;
-
-Legality Rules
 
-A parallel_block_statement shall not update variables global to the statement unless
-the action is sequential (see 9.10).
+Static Semantics
 
-A handled_sequence_of_statements of a parallel_block_statement shall not consist
-of a statement that can invoke a potentially blocking operation (see 9.5).
+Each handled_sequence_of_statements represents a separate logical thread
+of control that proceeds independently and concurrently between the
+points where they interact with other logical threads of control.
+
+The execution of a parallel_block_statement consists of the concurrent
+execution of the handled_sequence_of_statements. The
+parallel_block_statement is complete once every one of the
+handled_sequence_of_statements has completed, either by reaching the end
+of its execution, or due to a transfer of control out of the construct
+by one of the handled_sequence_of_statements. When a transfer of control
+to a point outside the construct is initiated by one of the
+handled_sequence_of_statements, an attempt is made to cancel all of the
+other handled_sequence_of_statements.  Once all of these either reach
+the end of their execution or are canceled, the transfer of control
+occurs.  If two or more of the handled_sequence_of_statements initiate
+such a transfer of control concurrently, one of them is chosen
+arbitrarily and the others are canceled.
+
+AARM Implementation Note -- Each handled_sequence_of_statements of a parallel
+block is a separate logical thread of control.  The implementation may
+choose to combine two or more such logical threads of control into a single
+physical thread of control to reduce the cost of creating numerous physical
+threads of control.
 
-Static Semantics
+Bounded (Run-Time) Errors
 
-Each handled_sequence_of_statements represents a separate thread of control that
-proceeds independently and in parallel between the points where they
-interact with other tasks and with each other.
-
-For the execution of a parallel_block_statement, each
-handled_sequence_of_statements is executed once, until the
-parallel_block_statement is complete. The parallel_block_statement is complete
-when all handled_sequence_of_statements have completed execution or when
-transfer of control occurs that transfers control out of the parallel block.
-When a transfer of control out of the parallel block occurs, an attempt is made
-to cancel further parallel execution of a handled_sequence_of_statements that
-have not yet started. The completion of a parallel_block_statement for a
-transfer of control out of the parallel block is delayed until all parallel
-execution of the handled_sequence_of_statements is complete. If a transfer of
-control out of the loop occurs in multiple parallel executions of
-handled_sequence_of_statements then only the run time action of the first
-encountered transfer of control out of the parallel block occurs.
-
-
-AARM - An implementation should statically treat each
-handled_sequence_of_statements as a separate thread of control, but whether they
-actually execute in parallel or sequentially should be a determination
-that is made dynamically at run time, dependent on factors such as the
-available computing resources.
+During the execution of one of the handled_sequence_of_statements of a
+parallel_block_statement, it is a bounded error to invoke an operation that is
+potentially blocking (see 9.5).
 
 Examples
 
@@ -294,40 +308,63 @@
       return X + Y;
    end Fibonacci;
 
-Modify 9.10(13)
+Modify 9(1/3):
 
-Both actions occur as part of the execution of the same task {unless
-either are part of a;
-   - different handled_sequence_of_statements of a parallel block statement,
-   - sequence_of_statements of a parallel loop statement.}
-
-Add a new subclause 9.12
-
-9.12 Executors and Tasklets
-
-A task may distribute execution across different physical processors in
-parallel, where each execution is a separate thread of control that
-proceeds independently and concurrently between the points where they
-interact with other tasks and with each other. Each separate thread of
-control of a task is an Executor, and the execution that each executor
-performs between synchronization is a tasklet. When a task distributes
-its execution to a set of executors, it cannot proceed with its own
-execution until all the executors have completed their respective
-executions.
-
-A parallel block statement or parallel loop statement may assign a set of
-executors to execute the construct, if extra computing resources are available.
-
-Add after C.7.1(5)
-
-The Task_Id value associated with each handled_sequence_of_statements of a
-parallel_block_statement, or of each sequence_of_statements of a parallel loop
-statement is the same as that of the enclosing statement.
-
-AARM - Each handled_sequence_of_statements of a parallel block or of each
-sequence_of_statements of a parallel loop are treated as though they are all
-executing as the task that encountered the parallel construct.
+  The execution of an Ada program consists of the execution of one or
+  more tasks. Each task represents a [separate thread of control]
+  {separable activity} that proceeds independently and concurrently
+  between the points where it interacts with other tasks. {A single
+  task, when within the context of a parallel construct, can represent
+  multiple logical threads of control which can proceed in parallel; in
+  other contexts, each task represents one logical thread of control.
+
+  }The various forms of task interaction are described in this clause,
+  and include:
+
+Add a sentence to the end of 9(10):
+  ... In the context of a parallel construct, a single task can utilize
+  multiple processing resources simultaneously.
+
+Modify 9(11) (aka "Note 1"):
+  1  Concurrent execution may be implemented on multicomputers,
+     multiprocessors, or with interleaved execution on a single physical
+     processor. On the other hand, whenever an implementation can
+     determine that the required semantic effects can be achieved when
+     parts of the execution of a [given task] {single logical thread of
+     control} are performed by multiple physical processors acting in
+     parallel, it may choose to perform them in this way.
+
+Modify 9.10(1/3):
+
+  If two different objects, including nonoverlapping parts of the same
+  object, are independently addressable, they can be manipulated
+  concurrently by two different [tasks] {logical threads of control}
+  without synchronization. Any two nonoverlapping objects are
+  independently addressable if either object is specified as
+  independently addressable (see C.6). Otherwise, two nonoverlapping
+  objects are independently addressable except when they are both parts
+  of a composite object for which a nonconfirming value is specified for
+  any of the following representation aspects: (record) Layout,
+  Component_Size, Pack, Atomic, or Convention; in this case it is
+  unspecified whether the parts are independently addressable.
+
+Modify 9.10(2):
+
+  [Redundant: Separate [tasks] {logical threads of control} normally
+  proceed independently and concurrently with one another. However, task
+  interactions can be used to synchronize the actions of two or more
+  [tasks] {logical threads of control} to allow, for example, meaningful
+  communication by the direct updating and reading of variables shared
+  between [the tasks] {them}.] The actions of two different [tasks]
+  {logical threads of control} are synchronized in this sense when an
+  action of one [task] signals an action of the other [task]; an action
+  A1 is defined to signal an action A2 under the following circumstances:
 
+Modify 9.10(13):
+
+  Both actions occur as part of the execution of the same [task]
+  {logical thread of control};
+
 !discussion
 
 There is a continuing trend of exponential growth of computational
@@ -357,7 +394,11 @@
 parallelization can be performed implicitly by the compiler, when it
 knows that the calls are free of side-effects. This is facilitated by
 annotations identifying global variable usage on subprogram
-specifications (see AI12-0079-1).
+specifications (see AI12-0079-1). Furthermore, a single subprogram call
+is rarely the best unit of parallelism. More frequently there is some
+setup and/or some post-call actions that should be grouped with the
+call, so the parallel block notation was felt the more appropriate way to
+perform a "parallel" call.
 
 Parallel Blocks
 ---------------
@@ -409,34 +450,42 @@
          Log ("Unexpected Error");
    end Fibonacci;
 
-We considered allowing the parallel block construct to be preceded with an
-optional declare part, but it was observed that it was more likely to be useful
-to have objects that are shared across multiple parallel sequences to outlive
-the parallel block. Therefore we reverted to the simpler syntax proposed
-above. Because there are no local declarations, there was
-also no point in having a statement_identifier (block label) for a
-parallel block. Allowing an exit statement to replace a goto that targets the
-location following the end of the parallel block statement seems useful, and to
-allow such a statement, a block label might be needed to identify the parallel
-block that is being exited. However, allowing exit statements is problematic
-for the same reason that exit statements are not currently allowed in block
-statements. It could be confusing if an exit occurred within a loop enclosed
-by the parallel block. Some might see it as syntax to exit the loop, others
-might see it as syntax to exit the parallel block. Rather than deal with this
-now, it was felt that if there was strong enough of a need for allowing an exit
+We considered allowing the parallel block construct to be preceded with
+an optional declare part, but it was observed that it was more likely to
+be useful to have objects that are shared across multiple parallel
+sequences to outlive the parallel block. Therefore we reverted to the
+simpler syntax proposed above. Because there are no local declarations,
+there was also no point in having a statement_identifier (block label)
+for a parallel block. Allowing an exit statement to replace a goto that
+targets the location following the end of the parallel block statement
+seems useful, and to allow such a statement, a block label might be
+needed to identify the parallel block that is being exited. However,
+allowing exit statements is problematic for the same reason that exit
+statements are not currently allowed in block statements. It could be
+confusing if an exit occurred within a loop enclosed by the parallel
+block. Some might see it as syntax to exit the loop, others might see it
+as syntax to exit the parallel block. Rather than deal with this now, it
+was felt that if there was strong enough of a need for allowing an exit
 statement in a parallel block, it could be the subject of a separate AI.
 
-We considered what the semantics might be for a parallel block if the parallel
-keyword were absent. This might be a good syntactic construct to use for
-supporting coroutines, for example. Rather than deal with that question in this
-AI, we leave that for consideration in separate AI's.
-
-We considered whether blocking calls should be allowed in a parallel block
-statement. We felt that allowing that could add significant complexity for
-the implementor, as well as introduce safety concerns about potential deadlocking.
-While such a capability is possible, it was felt that it should be disallowed
-for now. If the demand and need is felt in the future, it could be added then,
-but it is better to not standardize that capability until we know it is needed.
+We considered what the semantics might be for a parallel block if the
+parallel keyword were absent. This might be a good syntactic construct
+to use for supporting coroutines, for example. Rather than deal with
+that question in this AI, we leave that for consideration in separate
+AI's.
+
+We considered whether blocking calls should be allowed in a parallel
+block statement. We felt that allowing that could add significant
+complexity for the implementor, as well as introduce safety concerns
+about potential deadlocking. While such a capability is possible, it was
+felt that it should be disallowed for now. If the demand and need is
+felt in the future, it could be added then, but it is better to not
+standardize that capability until we know it is needed.
+
+By disallowing potentially blocking operations, we can permit the
+implementation to group the various "logical" threads of the parallel
+block into a smaller number of "physical" threads. If blocking
+operations were permitted, this could easily lead to deadlock.
 
 Parallel Loops
 --------------
@@ -447,10 +496,6 @@
 solution space. To benefit from parallel hardware, the computation
 associated with a loop should be spread across the available processors.
 
-Note: Allowing the parallel keyword on while loops was considered, but
-was discarded since while loops cannot be easily parallelized, because
-the control variables are inevitably global to the loop.
-
 For example, here is a simple use of a parallelized loop, to add two
 arrays together to produce a result array:
 
@@ -459,18 +504,31 @@
     Result (I)  := A(I) + B(I);
   end loop;
 
-Note that the compiler, using the rules specified in AI12-0079-1, may
-complain if the parallel sequences might have conflicting global
-side-effects. We considered extending the syntax to allow reductions to be
-performed with parallel loops, but we discovered that parallel reduction
-expressions can provide the same capability more concisely, so for now we allow
-parallel loops to work if there are no global conflicts. A separate AI could be
-created to add reduction loop capability if it is decided that this is needed.
-In the meantime, Reduction Expressions appear to better fill this need. The main
-purpose of a loop is to apply processing iteratively. The main purpose of a
-reduction however, is to generate a result value. Iteration is a means to
-achieve that end, but a reduction expression seems better suited since it is
-designed to produce a result value.
+Note: Allowing the parallel keyword on while loops was considered, but
+was discarded since while loops cannot be easily parallelized, because
+the control variables are inevitably global to the loop.
+
+We have introduced the term "logical thread of control" to describe the
+new kinds of parallelism introduced by these parallel constructs, rather
+than "tasklet" or "executor" or other such term. In various existing
+rules, we have substituted "logical thread of control" for "task."
+Shared variables now include any variable shared between two logical
+threads of control, even if they are from the same task. Note that the
+compiler, using the rules specified in AI12-0079-1, may complain if the
+parallel sequences might have conflicting access to shared variables.
+We don't define such rules in this AI.
+
+We considered extending the syntax to allow reductions to be performed
+with parallel loops, but we discovered that parallel reduction
+expressions can provide the same capability more concisely, so for now
+we allow parallel loops to work if there are no global conflicts. A
+separate AI could be created to add reduction loop capability if it is
+decided that this is needed. In the meantime, Reduction Expressions
+appear to better fill this need. The main purpose of a loop is to apply
+processing iteratively. The main purpose of a reduction however, is to
+generate a result value. Iteration is a means to achieve that end, but a
+reduction expression seems better suited since it is designed to produce
+a result value.
 
 !ASIS
 
@@ -7037,5 +7095,77 @@
 Sent: Wednesday, April 4, 2018  2:11 PM
 
 Indeed - something like that.
+
+***************************************************************
+
+From: Tucker Taft
+Sent: Sunday, June 10, 2018  8:49 PM
+
+Here is a significant revision of the Parallel Operations AI. [This is version
+/09 of the AI - Editor.] I dropped the use of terms like "tasklet" and
+"executor" and used "logical thread of control" more widely.  I tried to
+simplify the rules as far as I could, to avoid over-specification, and
+because simple is usually good.  Comments welcome!
+
+Note that the !proposal is essentially unchanged, and only a bit was added to
+the !discussion.  So I recommend folks start with the revised !wording rather
+than wading through the other material which really hasn't changed much.
+
+***************************************************************
+
+From: Randy Brukardt
+Sent: Monday, June 11, 2018  8:41 PM
+
+> Here is a significant revision of the Parallel Operations AI.
+
+As usual, I fixed a number of typos in it while posting: a number of colons were
+missing (you added many that were missing, but missed a few), a couple of
+spelling errors (like "modfiy"), and I got rid of the extra spaces after periods
+that some of us were taught to include on a typewriter, but never have been used
+in AIs.
+
+> I dropped the use of terms like "tasklet" and "executor" and used
+> "logical thread of control" more widely.
+
+The wording wasn't long enough already? ;-)
+
+I guess I would have expected to use some short term for this, as it is going to
+need to be frequently referenced in AIs, discussions, and (especially)
+educational material. I'm already exhausted of writing "logical thread of
+control", and there isn't even a pronouncable acronym for it (LToC isn't that).
+There's 18 occurrences in this AI, and I presume there will be more in the
+related AIs.
+
+I realize that it is clearer in some sense, 'cause there's no chance of
+confusion, as there might be just calling it a "thread". Maybe just shorten it
+to "logical thread" except in 9(1)?
+
+In any case, if we're not going to use "tasklet", the !proposal needs to be
+rewritten to purge the term. It ought not be used outside of the "reject
+options" discussion (which you already have).
+
+> I tried to simplify the rules as far as I could, to avoid
+> over-specification, and because simple is usually good.
+> Comments welcome!
+
+Overall the wording looks good. I didn't see anything that didn't make sense,
+but I didn't try very hard to look for omissions.
+
+> Note that the !proposal is essentially unchanged, and only a bit was
+> added to the !discussion.  So I recommend folks start with the revised
+> !wording rather than wading through the other material which really
+> hasn't changed much.
+
+I usually use a file compare to read updated AIs, not always the best idea but
+it works great when a lot of the discussion material is little changed.
+
+> We don't define such rules in this AI.
+
+Shouldn't we at least mention that such rules are proposed in another AI?
+(AI12-0267-1 in particular).
+
+It might also make sense to mention the reduction expression AIs (AI12-0242-1,
+AI12-0262-1) in the discussion on that topic (rather than just leading the
+reader hanging).
 
 ***************************************************************

Questions? Ask the ACAA Technical Agent