--- ai12s/ai12-0242-1.txt 2018/01/16 06:55:09 1.2 +++ ai12s/ai12-0242-1.txt 2018/01/25 07:57:46 1.3 @@ -1,4 +1,4 @@ -!standard 4.5.9 (0) 17-12-28 AI12-0242-1/01 +!standard 4.5.9 (0) 18-01-24 AI12-0242-1/02 !class Amendment 14-06-20 !status work item 14-06-20 !status received 14-06-17 @@ -7,615 +7,758 @@ !subject Reduction Expressions !summary -New syntax and semantics to facilitate reduction and parallelism via Reduction -Expressions. +Two New Attributes to facilitate reduction via a Reduce Attribute for +sequential reduction and Parallel_Reduce Attribute for parallel reduction. !problem -A common computing model is known as MapReduce, which is essentially a technique -used to generate a summary result for a set of data. Such problems are often -good candidates for parallelization using divide and conquer strategies to -process the data set, where the partial results of each portion of the data can -be combined in parallel to produce the final result. Generating such libraries -from scratch is non-trivial, and writing programs that use such libraries can be -difficult to debug and error-prone to create. A general facility to solve such -problems with syntax, where the compiler can provide improved safety and -analysis would be helpful. +A common problem in computing is the need to summarize a set of values. -!proposal - -This proposal depends on the facilities for aspect Global (AI12-0079-1) and for -aspect Nonblocking (AI12-0064-2). Those proposals allow the compiler to -statically determine where parallelism may be introduced without introducing -data races. - -The goals of this proposal are to provide a mechanism for expressing solutions -to MapReduce problems that; - -- Is easy to understand -- Is Easy to write -- Allows parallelization -- Provides safety by eliminating data races and logic errors. -- Fits in well with existing Ada syntax - -Note that in this model the compiler will identify any code where a -potential data race occurs (following the rules for concurrent access -to objects as specified in the Language Reference Manual RM 9.10(11)), -and point out where objects cannot be guaranteed to be independently -addressable. If not determinable at compile-time, the compiler may -insert run-time checks to detect data overlap. +Currently in Ada, one generally has to write a subprogram to do this, which +involves writing a loop to iterate through the set of values, and a global +accumulator variable or set of variables that get updates through each iteration +of the loop. + +One of the most important addition to Ada in Ada 2012 is contract specifications +for subprograms. However to write pre and post conditions that attempt to +summarize inputs or outputs, one has to write a subprogram to express the +summary result, which can add clutter to an API for an abstraction, and also +injects a level of indirection, where if a client wants to understand the +requirements of the pre condition, or the effects of the post condition, one has +to find and examine the body of the subprogram named in the contract +specification. + +It would be useful if such summarizations could be expressed in a simpler, more +concise manner, such as an expression, without always having to write another subprogram. +The proposed solution is to allow an Attribute to be applied to an array object to provide +the summarization. + +Ada 83 was already a pretty good language for "hybrid" functional/imperative +programming, because you can have a sequence of declarations that progressively +compute a desired result. Often it was only because you needed to enter a loop +that you had to do any significant amount of computing after the "begin." In +today's Ada, with conditional expressions, quantified expressions, the recently +approved iterated component association, and our newly proposed container +aggregates, the need for explicit ifs and loops after the "begin" is continuing +to decrease. There appears to be a shift in the a balance between functional +and imperative features, more towards the functional side. There is a +resurgence of interest in functional programming these days, but going all the +way to "pure functional" programming, with "monads" instead of assignment +statements, and recursion only with no iteration, would be too going too far +towards the functional side, but it is important to "complete" the functional +primitives, if only to give the desired power to Ada's contract-based +programming. -Reduction Expressions ---------------------- - -A Reduction Expression is a syntactic construct, similar to a quantified -expression that can be used to combine a set of values into a single result. -This mechanism is called reduction. - -Indeed, a quantified expression can be viewed as being a special purpose +Some of the existing syntax in Ada already can provide forms of summarization. +For example, a quantified expression can be viewed as being a special purpose Reduction Expression that applies an operation, the Predicate, to a set of values to reduce the predicate results to a single Boolean result. Similarly, an array aggregate in the form of an iterated_component_association can also be viewed as being a special purpose Reduction Expression that applies an operation, in place concatenation, to a set of values to reduce into an array -result. - -A Reduction expression is a more general syntactic form where there is -less constraint on the type of operation to be applied to the set of +result. A Reduction expression is a more general syntactic form where there is +less constraint on the type of operation to be applied to summarize the set of values, and the operation can produce result values of types other than Boolean values, or array creation. -Semantics: A Reduction Expression looks like a quantified expression, -except that the quantifier keyword ("all" or "some") is not present, and -the predicate expression is replaced with an expression that evaluates -to a function call returning an object of a nonlimited type, that is -called the combiner_expression. - -The combiner expression must denote a function call that has at least one -parameter of the same type as the type of the Reduction expression. The combiner -expression is evaluated iteratively to accumulate a result, which ultimately -becomes the result of the Reduction Expression. The accumulation of the result -occurs as the result of each iteration is implicitly fed back as an input to the -function denoted by the combiner expression. The implicit parameter substitution -is identified syntactically based on the "<>" box notation syntax, except that -the box notation in this case must enclose the initial value to be used for the -first call to the function, since at that point there would otherwise be no -existing value to pass into the function. The initial value also serves to be -the result of the reduction expression for the case when there are no iterations -performed (E.g. For the case when a when a loop_parameter_specification for a -Reduction Expression specifies a null range). - -If the reduction expression is executed in parallel, then each thread of control -(i.e. tasklet, see AI12-0119-1), needs to accumulate its partial result into an -implicit accumulator variable. This implicit variable is of the type associated -with the reduction expression result, and it is initialized to a special value -called the identity value. The identity value is specified by either applying an -Identity aspect to the declaration of the function denoted by the combiner -expression, or indirectly to another function called a reducer function that is -similarly associated with the combiner expression via the use of a Reducer -aspect applied to the function denoted by the combiner expression. The Identity -aspect of a function identifies a value of the same type as the combiner -expression. If a combiner expression does not have a corresponding Identity -value, then the Reduction expression cannot be parallelized, and it is assumed -to require sequential execution. - -It is recommended that a compiler apply parallelism implicitly to a reduction -expression if it can be determined that there are no data dependences, and the compiler -can determine the reduction operations needed to initialize and combine partial -results. Otherwise, a compiler would fall back to sequential execution for the -construct. - -Once each tasklet has generated its local partial result, it can combine these -results with other tasklets using a reducer function. The Reducer function for a -Reduction expression is a function that accepts two parameters where both -parameters are of the same type, and returns a result of that same type, which -is also the type of the Reduction expression. - -For parallelization, the combiner expression must denote a function that has a -Reducer aspect specified for its declaration if the function itself is not a -Reducer function. The Reducer aspect identifies another function that is to be -used to combine partial results from two tasklets into the final result of the -Reduction expression. The multiple results are combined two at a time. - -The Reducer function is expected to generate an associative result based on the -input parameters. A Reducer function does not need to be commutative (e.g. -vector concatenation), as it is expected that the implementation will ensure -that the results are combined in a manner that is consistent with sequentially -applying the Reducer function to the partial results in iteration order. The -combiner expression does not need to have an associated Reducer function if -the Reduction expression is to be computed sequentially. - -For Reductions Expressions executed in parallel, it is important that the value -of the Identity aspect associated with a function does not affect the result of -the computation. For example, if the reduction result type is Integer and the -reducer is addition, then the Identity value should be zero, since adding zero -to any value does not affect the result value. Similarly, if the reducer is -multiplication then the Identity value should be one, since multiplying any -Integer value by 1 does not affect the result value. If the result type is a -vector and the reducer is concatenation, then the Identity value should be an -empty vector, since concatenating an empty vector to another vector does not -affect the value of the other vector. +Such a reduction capability is the last remaining major component needed to +complete the "iterated" operations. There are many applications of reduction +capabilities, including both sequential and parallelism usage. It will often be +the right way to define, in a postcondition, what is the final value of one +output of the subprogram, even though the subprogram might have multiple outputs +and might do many other things. + +Such a capability can allow programmers to express algorithms more concisely, +which tends to also make the algorithms easier to read, debug, understand, and +maintain. + +Another need is to be able to perform reductions in parallel. Modern computing +platforms typically provide support for multicore computing, yet writing +algorithms that take advantage of these multicore platforms is considerably +difficult to write, very error prone, and difficult to debug. Many of the divide +and conquer parallelism algorithms involve reduction, commonly known as +MapReduce, in the parallelism world. The challenge with such reductions is that +writing a subprogram with a global accumulator value normally would imply a data +race if multiple threads of execution end up updating the global variable in +parallel. + +Parallel reduction is in many ways a separate issue, when compared to sequential +reduction, and where (and whether) it is best inserted depends heavily on the +amount of computing done within a single iteration, the independence of those +computations, and the number of iterations. The advantage of the notations like +quantified expressions, container aggregates, and reduction expressions, is that +they are self-contained, and can often be analyzed holistically by the compiler +to determine whether and where to insert parallelism. It is important in the +context of Ada to have sufficient annotations to allow the compiler to both +check the safety of explicit parallelism, and also safely insert implicit +parallelism. Hence the importance of the Global and Nonblocking annotations. + +One of the strengths of Ada is in the area of safety critical and high integrity +systems. Ada has a unique opportunity to extend its offering in these areas by +providing parallelism capabilities that can be statically checked by the +compiler to help the programmer eliminate data races. -!wording +!proposal -Modify 4.4(1/3) +This proposal depends on the facilities for aspect Global (AI12-0079-1) and for +aspect Nonblocking (AI12-0064-2). Those proposals allow the compiler to +statically determine where parallelism may be introduced without introducing +data races. -"In this International Standard, the term "expression" refers -to a construct of the syntactic category expression or of any of the following -categories: choice_expression, choice_relation, relation, simple_expression, -term, factor, primary, conditional_expression, quantified_expression -{, reduction_expression}." +The goals of this proposal are to provide a mechanism for expressing a +summarization of a set of values. Such a summarization is known as a reduction. +It is desired that such a mechanism; + +- is easy to understand +- is easy to write/express +- allows parallelization +- provides safety by eliminating data races and logic errors. +- fits in well with existing Ada syntax -Modify 4.4(7/3) +Reduction Attributes +--------------------- -"primary ::= - numeric_literal | null | string_literal | aggregate - | name | allocator | (expression) {| <reduction_parameter>} - | (conditional_expression) | (quantified_expression) {| (reduction_expression)}" +This model proposes two new attributes, 'Reduce, and 'Parallel_Reduce which can +be used to combine the values of the prefix which denotes an array object into a +single result. This mechanism is called reduction. The 'Reduce attribute is +intended to provide sequential reductions by default, unless the compiler can +determine it is safe and beneficial to performance to implicitly introduce +parallelism. The 'Parallel_Reduce attribute is intended to allow the programmer +to explicitly request that a reduction be performed in parallel, which is useful +because the compiler is not always able to make a correct assessment statically +whether injecting parallelism with improve instead of detract from performance. +When a compiler cannot make that determination, it is more apt to choose +sequential processing because it is simpler, and more deterministic. By allowing +the programmer to request parallelism explicitly, the compiler does not need to +make the assessment, and the programmer can easily revert to sequential +processing with by simply replacing the parallel version of the attribute with +the sequential one. + +The Parallel_Reduce attribute activates the necessary static checks by the +compiler to ensure that the parallelism can safely be introduced, without +necessarily requiring analysis to determine if there is a performance benefit to +the parallelism. The two attributes are similarly named to make it easier for +the programmer to switch between parallelism and sequential implementations, +such that performance measurements and other similar techniques can be employed +to help the programmer decide which attribute is the better choice for a +particular problem. + +The prefix of the 'Reduce and 'Parallel_Reduce attribute is either an array +object or a container object. This includes objects created by array aggregates, +or container aggregates. + +The 'Reduce attribute and 'Parallel_Reduce attribute both accept two arguments. +The first argument denotes a binary subprogram or operator. If the subprogram is +a function, then the function is of the form; + + function Combiner (L, R : S) return S; + +The type of the parameters and result are of the same type as the component or element +objects associated with the attribute prefix. + +If the subprogram is a procedure, then the procedure is of the form; + + procedure Combiner (L : in out S; R : S); + +In either case, such a subprogram is called a *combiner_subprogram*. The +combiner subprogram is called once for every value associated with the prefix of +the attribute, where each value of the prefix is passed in as the second +argument of the combiner subprogram, and results from previous calls are passed +in as the first argument of the combiner subprogram. + +For the very first call to the combiner subprogram, the second argument of the +attribute is passed as the first argument of the combiner subprogram, since +there are no previous results yet determined. This second argument of the +attribute is called the initial value. + +The initial value also serves to be the result of the attribute for the +case when there are no iterations performed (E.g. For the case when the +attribute prefix denotes a null array). + +In order for a 'Parallel_Reduce attribute reference to be legal, the combiner +subprogram needs to have the Associative aspect. The Associative aspect is a +Boolean aspect indicating that the subprogram can be applied to combine a set of +values and provide equivalent results regardless of the grouping of the values, +given that the order of the values is preserved. For instance, integer addition +is considered to be an associative operation, since (A + B) + C = A + (B + C). +The Associative aspect is more of a documentation artefact, since a compiler is +unlikely to be able to determine if the result of an operation is in fact +associative. We can define the aspect on language defined operations and +libraries which can go a long way to catch errors. For user defined subprograms, +we would require the programmer to apply the Associative aspect, which makes the +programmer give consideration as to whether the operation is in fact associative +or not. + +There is a thread of control associated with each value of the prefix. Each +thread of control (i.e. tasklet, see AI12-0119-1), needs to accumulate its +partial result into an implicit accumulator variable. This implicit variable is +of the type of the combiner subprogram parameters, and is initialized to have +the first value to be processed by the tasklet, unless the tasklet is assigned +to process the first object or element of the prefix, in which case, the +implicit variable is initialized to the value of the Initial_Value of the +attribute reference. + +Once each tasklet has generated its local partial result, it can combine its +result with other tasklets using the combiner subprogram. The multiple tasklet +results are combined two at a time. + +For parallel execution, the 'Parallel_Reduce attribute is expected to generate +an associative result based on the values of the prefix, but otherwise is not +restricted. The combiner for 'Reduce does not need to have the Associative +aspect. The combiner subprogram can be non-commutative (e.g. vector +concatenation), as it is expected that the implementation will ensure that the +tasklet results are combined while preserving the original ordering of the set +of input values of the attribute prefix as would be consistent with sequential +execution. -Add 4.4(15.h) +!wording -"Wording Changes from Ada 2012 +Add after 3.6.2(10) -Added reduction_expression and reduction_parameter to primary." +For a subtype S of a component of an array type A or element of a container type +C, and a corresponding object O of the array or container type, which is denoted +by the prefix of a Reduce or Parallel_Reduce attribute reference: -Replace 4.5.1(2-3) with +kA Combiner_Subprogram is a subprogram that accepts exactly two parameters and +can be iteratively called to summarize the prefix object to produce a single +result. -"The following logical operators are predefined for every boolean type T +A Combiner_subprobram either denotes a function with the following +specification: - function "and"(Left, Right : T) return T with Identity => True - function "or" (Left, Right : T) return T with Identity => False - function "xor"(Left, Right : T) return T with Identity => False" + function Combiner(L, R : S) return S; - The following logical operators are predefined for every modular type T +or denotes a procedure with the following specification: - function "and"(Left, Right : T) return T - function "or" (Left, Right : T) return T with Identity => 0 - function "xor"(Left, Right : T) return T with Identity => 0" + procedure Combiner(L : in out S; R : S); - The following logical operators are predefined for every one-dimensional - array type T whose component type is a boolean type: +O'Reduce(Combiner, Initial_Value) - function "and"(Left, Right : T) return T - function "or" (Left, Right : T) return T - function "xor"(Left, Right : T) return T" + For a prefix denoting an object of an array or container, O'Reduce is an + expression that summarises the components or elements of O by applying the + named Combiner_Subprogram and initial value to all the values associated with + the attribute prefix. + +O'Parallel_Reduce(Combiner, Initial_Value) + + For a prefix denoting an object of an array or container, O'Reduce is an + expression that summarises the components or elements of O by applying the + named Combiner_Subprogram and initial value to all the values associated with + the attribute prefix, using parallel execution. The Combiner_Subprogram shall + have the Associative aspect with the value True. See (9.12). The + Combiner_Subprogram shall have the Non_Blocking aspect with the value True. + See (9.5). The Combiner_Subprogram shall have the Global aspect and the + Global aspect shall not identify any global variables that are not + synchronized. -Add AARM note +Name Resolution Rules -"The Identity aspect for the "and" function for modular types is not specified - because it is difficult to statically specify a value that would work for all - types. eg. type X is mod 97; We could say that it is T'Last for types where the - modulus is a power of 2, for example, but that is not general enough, - similarly, we could say that the Identity for the "and" function for a - one-dimensional array is T'(others => True), but that only works if T is a - constrained array type, so we dont bother trying to specify the Identity aspect - for these operations." +The expected type of a Reduce or Parallel_Reduce attribute reference is any +nonlimited type. -Modify 4.5.3(2) +AARM Note +The prefix can be an array or container aggregate. The prefix can denote an +object of a multi-dimensional array. + + + Dynamic Semantics + +For a Reduce attribute reference, the combiner subprogram denoted by the +attribute reference is first called passing the Initial_Value of the attribute +reference as the first parameter, and the first value associated with the +attribute prefix as the second parameter. The Combiner_Subprogram is then called +repeatedly for each subsequent value associated with the attribute prefix where +the result output by the previous call is passed as the first parameter to the +Combiner_Subprogram, and the subsequent value of the prefix is passed as the +second parameter. This continues until all values of the prefix have been +processed. The result of the last call to the Combiner_Subprogram is the result +of the expression. If the prefix of the attribute reference denotes a null range +of values, then the Initial_Value is the result of the expression. + +For a Parallel_Reduce attribute reference, each component or element of the +prefix is assigned to an executor. (See 9.12). The executor associated with the +first value of the prefix calls the Combiner_Subprogram using the Initial_Value +of the attribute reference as the first parameter of the call, and using the +first value as the second parameter. Any other consecutive values assigned to +the same executor involve repeated calls to the Combiner_Subprogram, where the +result output by the previous call is passed as the first parameter to the +Combiner_Subprogram, and the subsequent value of the prefix is passed as the +second parameter. For executors assigned to other components or elements of the +prefix, the result for that executor is initially assigned the value from the +lowest indexed value assigned to that executor. Any other consecutive values +assigned to the same executor, involve repeated calls to the +Combiner_Subprogram, where the result output by the previous call is passed as +the first parameter to the Combiner_Subprogram, and the subsequent value of the +prefix is passed as the second parameter. The results from the executors are +combined similarly, by calling the Combiner_Subprogram to combine the results +from two Executors whose results corresond to consecutive ranges of value of the +attribute prefix. This process repeats until all Executors have combined all +intermediate results into a final value. This result is the result of the +expression. If the prefix of the attribute reference denotes a null range of +values, then the Initial_Value is the result of the expression. + +AARM Note: + +It is important to specify which argument of the reducer function is used as for +feeding back prior results, because certain reductions, such as vector +concatentation, can be non-commutative operations. In order to return a +deterministic result for parallel execution, it is necessary to specify which +parameter is used for feedback of prior results. When combining results from two +tasklets, the results associated with the array components with the lower index +value are passed as argument L of the reducer function. This is also necessary +for non-commutative reductions to work properly. -"function "+"(Left, Right : T) return T{ with Identity => 0} - function "-"(Left, Right : T) return T{ with Reducer => "+"} -" -Modify 4.5.5(2) +Examples -"function "*" (Left, Right : T) return T{ with Identity => 1} - function "/" (Left, Right : T) return T{ with Reducer => "*"} - function "mod"(Left, Right : T) return T - function "rem"(Left, Right : T) return T" + Calculate the sum of elements of an array of integers -Modify 4.5.5(12) -"function "*"(Left, Right : T) return T{ with Identity => 1.0} - function "/"(Left, Right : T) return T{ with Reducer => "*"} -" + A'Reduce("+",0) -- See 4.3.3(43) -Modify 4.5.5(14) -"function "*"(Left : T; Right : Integer) return T{ with Reducer => "*"} - function "*"(Left : Integer; Right : T) return T{ with Reducer => "*"} - function "/"(Left : T; Right : Integer) return T{ with Reducer => "*"} -" + Determine if all elements in a two dimensional array of booleans are set to + true -Modify 4.5.5(19) -"function "*"(Left, Right : universal_fixed) return universal_fixed{ with Identity => 1.0} - function "/"(Left, Right : universal_fixed) return universal_fixed{ with Reducer => "*" -" + Grid'Reduce("and", true); -- See 3.6(30) -Add Section 4.5.9 + Calculate the minimum value of an array of integers in parallel -"Reduction Expressions" + A'Parallel_Reduce(Integer'Min, Integer'Last) -Reduction expressions provide a way to write a reduction that combines a set of -values into a single result. + Determine how many integers in an array are prime numbers -Syntax + Prime_Count : contant Natural := (for P of A when Is_Prime(P) => 1)'Reduce("+",0); - reduction_expression ::= - for loop_parameter_specification => combiner_expression - | for iterator_specification => combiner_expression + An expression function that returns its result as a Reduction Expression - reduction_parameter ::= expression + function Factorial(N : Natural) return Natural is + ((for J in 1..N => J)'Reduce("*", 1)); -Wherever the Syntax Rules allow an expression, a reduction_expression may be -used in place of the expression, so long as it is immediately surrounded by -parentheses. + An expression function that computes the Sin of X using Taylor expansion -Discussion: The syntactic category reduction_expression appears only as a -primary that is parenthesized. The above rule allows it to additionally be used -in other contexts where it would be directly surrounded by parentheses. This is -the same rule that is used for conditional_expressions; see 4.5.7 for a detailed -discussion of the meaning and effects of this rule. + function Sin(X : Float; Num_Terms : Positive := 5) return Float is + ((for I in 1..Num_Terms => (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1))) + 'Reduce("+", 0.0)); -Name Resolution Rules + A reduction expression that outputs the sum of squares -The expected type of a reduction_expression is any nonlimited type. The -expected type of a combiner_expression is the same type as the immediately -enclosing reduction_expression. - -The expected type of a reduction_parameter is the same type as the immediately -enclosing reduction_expression. - -A reducer_function is a function that has exactly two parameters where -both formal parameters and the result are of the same type. A -reducer_function is called implicitly to combine results from -multiple executions of the combiner_expression of a reduction -expression when the reduction expression has parallel execution. The -function denoted by a combiner_expression can be associated with a -reducer_function. If such an association exists, either the function is -itself a reducer_function or its declaration has the Reducer aspect -which specifies the associated reducer_function. - -An identity_value is a value that can be used to initialize implicit -declarations of variables that accumulate the results of a -reduction_expression when the reduction expression has parallel execution. -The identity_value for the function denoted by a combiner_expression is -determined from either; the Identity aspect specified on the declaration of the -denoted function, or by the Identity aspect specified on the declaration of -another function named by the the Reducer aspect of the denoted function. + Put_Line ("Sum of Squares is" & + Integer'Image((for I in 1 .. 10 => I**2)'Reduce("+", 0)); -Legality Rules - -A reduction_parameter shall only appear in a combiner_expression. + An expression function to compute the value of Pi -A reduction_parameter shall appear exactly once within the immediately enclosing -combiner_expression of a reduction_expression. + -- See 3.5.7(21) + function Pi (Number_Of_Steps : Natural := 10_000) return Real is + (1.0 / Number_Of_Steps * + (for I in 1 .. Number_Of_Steps => + (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2))) + 'Reduce("+", 0.0)); -AARM Ramification A reduction expression may consist of nested reduction -expressions, each with a corresponding combiner_expression and -reduction_expression. +AARM Implementation Advice -The type of an identity_value associated with the reduction_expression and the -type of the reduction_parameter shall be of the same type as the -reduction_expression. +For a prefix of a Reduce or Parallel_Reduce attribute reference that is an +aggregate, the creation of a temporary object is not necessary if each value +of the aggregate object that would have been created is iteratively applied to +the Combiner_Suprogram of the attribute reference. -The result type and the type of both formal parameters of an associated -reducer_function shall be of the same type as the reduction_expression. +Wording Changes from Ada 2012 +Reduce attribute is new. +Parallel_Reduce attribute is new. -Static Semantics +Modify 4.5.1(3) with -For parallel execution, the combiner_expression either needs to denote a -function that is a reducer_function, or the denoted function needs to have the -Reducer aspect specified on its declaration. Otherwise, the reduction expression -is executed sequentially. + function "and"(Left, Right : T) return T {with Associative} + function "or" (Left, Right : T) return T {with Associative} + function "xor"(Left, Right : T) return T {with Associative}" -For parallel execution, the combiner_expression either needs to denote a -function that has the Identity aspect specified on its declaration, or the -denoted function nees to have the Reducer aspect specified on its declaration -and the function named by the Reducer aspect needs to have the Identity aspect -specified on its declaration. Otherwise, the reduction expression is executed -sequentially. +Modify 4.5.3(2) - For a function_specification, the following language-defined - operational aspects may be specified with an aspect_specification - (see 13.1.1): +"function "+"(Left, Right : T) return T{ with Associative} + function "-"(Left, Right : T) return T +" - Identity +Modify 4.5.3(4) -The aspect Identity denotes a value that is to specified as the -identity_value associated with a Reduction_Expression. The aspect shall -be specified by a static expression, and that expression shall be -explicit, even if the aspect has a boolean type. +"function "&"(Left : T; Right : T) return T {with Associative} +function "&"(Left : T; Right : C) return T {with Associative} +function "&"(Left : C; Right : T) return T {with Associative} +function "&"(Left : C; Right : C) return T {with Associative}" -Identity shall be specified only on a function_specification -declaration. +Modify 4.5.5(2) +function "*" (Left, Right : T) return T {with Associative} +function "/" (Left, Right : T) return T +function "mod"(Left, Right : T) return T +function "rem"(Left, Right : T) return T -Reason: The part about requiring an explicit expression is to disallow -omitting the value for this aspect, which would otherwise be allowed by -the rules of 13.1.1. +Modify 4.5.5(12) -Aspect Description for Identity: Identity value for a function. +function "*"(Left, Right : T) return T {with Associative} +function "/"(Left, Right : T) return T -The expected type for the expression specified for the Identity aspect -is the result type of the function_specification declaration on which it -appears. +Modify 4.5.5(14) -Only one Identity aspect may be applied to a single function declaration; +function "*"(Left : T; Right : Integer) return T {with Associative} +function "*"(Left : Integer; Right : T) return T {with Associative} +function "/"(Left : T; Right : Integer) return T + +Modify 4.5.5(16-17) + +function "*"(Left, Right : root_real) return root_real {with Associative} +function "/"(Left, Right : root_real) return root_real + +function "*"(Left : root_real; Right : root_integer) return root_real {with Associative} +function "*"(Left : root_integer; Right : root_real) return root_real {with Associative} +function "/"(Left : root_real; Right : root_integer) return root_real +Modify 4.5.5(19) +function "*"(Left, Right : universal_fixed) return universal_fixed {with Associative} +function "/"(Left, Right : universal_fixed) return universal_fixed - Reducer +Add AARM To Be Honest after 4.5.5(19) -The aspect Reducer shall denote a reducer_function -that is to be associated with a declared function. +Addition and Multiplication operators for discrete and floating point types are +not truly associative, even though the differences may not be important for +typical use. Discrete additions might overflow when different groupings are +applied, and floating point rounding errors can produce different results when +different groupings are applied. We say these are associative though, because +for typical use, the non-associativity is subtle enough to not be a concern. -Reducer The aspect Reducer denotes a function with the following -specification: +Add to new section 9.12 (See AI12-0119-1) - function reducer(L, R : in result_type) return result_type +[Reader Note: I somewhat modelled the Associative aspect after the nonblocking + aspect. There may be content that is not needed, but I figure it makes sense to + start with something that already has pretty good wording, rather than try to + invent new wording] -where result_type statically matches the subtype of the result of the -declared function. +For a noninstance subprogram, predefined operator, generic subprogram, formal +subprogram, formal object of a named or anonymous access-to-subprogram type +(including a formal type) the following language-defined operational aspect is +defined. -Only one Reducer aspect may be applied to a single function declaration; +AARM Ramification: "Noninstance subprogram" excludes a subprogram that is an +instance of a generic subprogram. In that case, the aspect should be specified +on the generic subprogram. If the Associative aspect needs to be added to an +instance of a generic subprogram, it can be accomplished by creating a separate +subprogram specification and then completing that specification with a +renames-as-body of the instance. -Aspect Description for Reducer: Reducer function associated with the -combiner_function_call of a reduction expression. - -Dynamic Semantics - -For the evaluation of a reduction_expression, the loop_parameter_specification -or iterator_specification is first elaborated, and accumulator variables of the -type of the reduction_expression are implicitly declared. Each accumulator -variable corresponds to a unique non-overlapping subset of the iterations to be -performed where all accumulators together cover the full set of iterations to be -executed. For the accumulator dedicated to the first iterations, the accumulator -is initialized to the value of the reduction_parameter of the -combiner_expression, otherwise the accumulators are initialized to the -associated identity_value of the combiner_expression. - -The evaluation of a reduction_expression then evaluates the -combiner_expression for the values of the loop parameter in the order -specified by the loop_parameter_specification (see 5.5) or -iterator_specification (see 5.5.2) within each iteration subset. -For each subsequent evaluation of the combiner_expression within an -iteration subset, the result from the previous evaluation is -substitued as the reduction_parameter of the current evaluation. - -The value of the reduction_expression is determined as follows: As accumulator -results are determined they are reduced into a single result two at a time by -implicit calls to the reducer_function associated with the -combiner_expression. The accumulator results passed to the reducer_function -are always for two adjacent iteration subsets where the result for the lower -iteration subset is passed as the first actual parameter to the reducer_function -and the result for the higher iteration subset is passed as the second actual -parameter to the reducer_function. If the Reduction_Expression does not evaluate -any iterations, then the value of the Reduction_Expression is the -value of the specified reduction_parameter expression. - -Notes: The accumulator results must represent adjacent iteration subsets -as described above to ensure that non-commutative reductions will -produce consistent results for parallel execution. +Associative +The type of aspect Associative is Boolean. +This aspect specifies the associative restriction for the entity; -Examples +Aspect Description for Associative: Specifies that a subprogram or operator +produces an associative result, that is, the operation produces the same +semantic results when applied to a sequence of values, regardless how the values +in the sequence are grouped, so long as the order of the sequence is maintained. - A reduction expression to calculate the sum of elements of an array of integers +Note: For example, addition is associative since (A + B) + C = A + (B + C) - (for Element of A => <0> + Element) -- See 4.3.3(43) +The Associative aspect may be specified for all entities for which it is +defined. In particular, Associative may be specified for generic formal +parameters. - A reduction expression to calculate the minimum value of an array of integers +Ramification: The Associative aspect cannot be specified for enumeration literals +but we don't need to mention that above. One would have to declare a subprogram in +order specify the aspect in that case, but that defines a user-defined subprogram +which is itself not a an enumeration literal. - (for X of A => Integer'Min(<Integer'Last>, X)) +The subprogram or operator associated with the aspect shall have two or more +parameters if the Associative aspect is True. - A reduction expression to create a string containing the alphabet +For a dereference of an access-to-subprogram type, the Associative aspect of the +designated subprogram is that of the access-to-subprogram type. - (for Letter in 'A' .. 'Z' => <""> & Letter) +[For a full type declaration that has a partial view, the aspect is the same as +that of the partial view.] - A reduction expression to determine how many integers in an array are greater than 3 - Four_Or_More : contant Natural := - (for P of A => <0> + (if P > 3 then 1 else 0)); +AARM Proof: Type aspects are never view-specific; they always have the same +value for all views. This is formally stated in 13.1. - An expression function that returns its result as a Reduction Expression +For any inherited subprogram, it is asociative if and only if the corresponding +subprogram of the parent is associative. - function Factorial(N : Natural) return Natural is (for J in 1..N => <1> * J); +Overridings of dispatching operations do not inherit this aspect. - An expression function that computes the Sin of X using Taylor expansion - function Sin(X : Float; Num_Terms : Positive := 5) return Float is - (for I in 1..Num_Terms => <0.0> + (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1))); +Unless directly specified, for a formal type, or formal subprogram, +the aspect is that of the actual type, or subprogram. - A reduction expression that outputs the sum of squares +AAARM Reason: This means that Associative legality checking for the actual +parameters of the instance is only necessary when the aspect is explicitly +specified for the formal type. - Put_Line ("Sum of Squares is" & Integer'Image(for I in 1 .. 10 => <0> + I**2)); +Unless directly specified, for a derived type the Associative aspect is False. - An expression function to compute the value of Pi +AARM Discussion: The expressions that can be specified for a derived type are +limited by a Legality Rule, see below. - -- See 3.5.7(21) - function Pi (Number_Of_Steps : Natural := 10_000) return Real is - (1.0 / Number_Of_Steps * - (for I in 1 .. Number_Of_Steps => - <0.0> + (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2)))); +Legality Rules -Wording Changes from Ada 2012 -Reduction expressions are new. +If aspect Associative is specified for an entity that is not a generic unit or +declared inside of a generic unit, the aspect_definition shall be a static +expression. + + If the prefix of an Associative attribute_reference denotes a generic unit G, + the reference shall occur within the declarative region of G. + +AARM Reason: We want the value of Associative attributes to be static so long as +they occur outside of any generic unit. The Associative aspect of a generic unit +will often depend on the actual parameters of the unit, so it cannot be static +(or have any well-defined value). We need this latter rule in case the attribute +of a generic is used outside of the generic. Note that the previous rule makes +it illegal to use such an attribute to specify aspect Associative outside of a +generic, but we don't want to allow any other uses since it does not have a +known value until instantiated. + +AARM Ramification: This rule does not apply to instances of generic units and +entities declared within them. + +In a generic instantiation (after replacement in the associative expressions by +values of the actuals as described previously): + +the actual subprogram corresponding to an associative formal subprogram shall be +associative [(an actual that is an entry is not permitted in this case)]; + +the actual type corresponding to an associative formal access-to-subprogram type +shall be associative; + +the actual object corresponding to a formal object of an associative +access-to-subprogram type shall be of an associative access-to-subprogram type; + +In addition to the places where Legality Rules normally apply (see 12.3), the +above rules also apply in the private part of an instance of a generic unit. + +AARM Ramification: For a generic formal parameter to be associative (thus, for +these rules to apply), it has to explicitly specify aspect Associative to be +True. In particular, these rules do not apply when it specifies aspect +Associative to be an expression involving attribute Associative of a generic +formal parameter. However, in such a case, these rules do apply in the instance +of the specification of the generic unit (the normal re-checking is needed). For +instance, the body of an expression function might make a prohibited call. + +A program unit P declared inside of a generic unit but not in a generic body or +that is a generic specification not declared in a generic unit is considered +associative for the purposes of checking the restrictions on an associative only +if the value of its Associative aspect is statically True. For the purposes of +checks in P, a call to a subprogram is considered associative unless the value +of its Associative aspect is statically False. + +AARM Reason: This is a typical “assume-the-best” rule. We only make checks if we +know the associative status of both P and the called subprogram. All other +checks will be performed when the generic unit is instantiated. We used the +awkward “inside of a generic unit but not in a generic body” so that a generic +specification declared inside of a generic body uses the following +“assume-the-worst” rule. + +A program unit P declared inside of a generic body or that is a generic body is +considered associative for the purposes of checking the restrictions on an +associative unit unless the value of its Associative aspect is statically False. +For the purposes of checks in P, a call to a subprogram is considered to be +non-associative unless: + +the value of its Associative aspect is statically True, or + +its associative expression (that is, Associative aspect) conforms exactly to +that of P, or conforms to some part of the associative expression of P that is +combined with the remainder of the associative expression of P by one or more +and or and then operations. + +AARM Ramification: That is, if the aspect of the program unit is specified +(directly or via inheritance) with any non-static Associative aspects, it is +considered to be an associative program unit for the purposes of making checks. +This is a typical “assume-the-worst” rule. + +Extensions to Ada 2012 + +Aspect Associative is new; it allows compile-time checks to assist +in determining if 'Reduce attribute evaluations can be performed with parallel +execution. Modify A.1 (9.1) - -- function "and" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => True}; - -- function "or" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => False}; - -- function "xor" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => False}; + -- function "and" (Left, Right : Boolean'Base) return Boolean'Base {with Associative}; + -- function "or" (Left, Right : Boolean'Base) return Boolean'Base {with Associative}; + -- function "xor" (Left, Right : Boolean'Base) return Boolean'Base {with Associative}; Modify A.1 (17) - -- function "+" (Left, Right : Integer'Base) return Integer'Base {with Identity => 0}; - -- function "-" (Left, Right : Integer'Base) return Integer'Base {with Reducer => "+"}; - -- function "*" (Left, Right : Integer'Base) return Integer'Base {with Identity => 1}; - -- function "/" (Left, Right : Integer'Base) return Integer'Base {with Reducer => "*"}; + -- function "+" (Left, Right : Integer'Base) return Integer'Base {with Associative}; + -- function "-" (Left, Right : Integer'Base) return Integer'Base; + -- function "*" (Left, Right : Integer'Base) return Integer'Base {with Associtive}; + -- function "/" (Left, Right : Integer'Base) return Integer'Base; Modify A.1 (25) - -- function "+" (Left, Right : Float) return Float {with Identity => 0.0}; - -- function "-" (Left, Right : Float) return Float {with Reducer => "+"}; - -- function "*" (Left, Right : Float) return Float {with Identity => 1.0}; - -- function "/" (Left, Right : Float) return Float {with Reducer => "*"}; + -- function "+" (Left, Right : Float) return Float {with Associative}; + -- function "-" (Left, Right : Float) return Float; + -- function "*" (Left, Right : Float) return Float {with Associative}; + -- function "/" (Left, Right : Float) return Float; Modify A.1 (29-34) function "*" (Left : root_integer; Right : root_real) - return root_real {with Identity => 1.0}; + return root_real {with Associative}; function "*" (Left : root_real; Right : root_integer) - return root_real {with Identity => 1.0}; + return root_real {with Associative}; function "/" (Left : root_real; Right : root_integer) - return root_real {with Reducer => "*"}; + return root_real; -- The type universal_fixed is predefined. -- The only multiplying operators defined between -- fixed point types are function "*" (Left : universal_fixed; Right : universal_fixed) - return universal_fixed {with Identity => 1.0}; + return universal_fixed {with Associative}; function "/" (Left : universal_fixed; Right : universal_fixed) - return universal_fixed {with Reducer => "*"}; + return universal_fixed; Modify A.4.4 (13-17) function Append (Left, Right : in Bounded_String; Drop : in Truncation := Error) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function Append (Left : in Bounded_String; Right : in String; Drop : in Truncation := Error) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function Append (Left : in String; Right : in Bounded_String; Drop : in Truncation := Error) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function Append (Left : in Bounded_String; Right : in Character; Drop : in Truncation := Error) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function Append (Left : in Character; Right : in Bounded_String; Drop : in Truncation := Error) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; + Modify A.4.4 (21-26) function "&" (Left, Right : in Bounded_String) - return Bounded_String{ with Identity => Null_Bounded_String}; + return Bounded_String {with Associative}; function "&" (Left : in Bounded_String; Right : in String) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function "&" (Left : in String; Right : in Bounded_String) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function "&" (Left : in Bounded_String; Right : in Character) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; function "&" (Left : in Character; Right : in Bounded_String) - return Bounded_String{ with Reducer => "&"}; + return Bounded_String {with Associative}; Modify A.4.5 (15-19) function "&" (Left, Right : in Unbounded_String) - return Unbounded_String{ with Identity => Null_Unbounded_String}; + return Unbounded_String {with Associative}; function "&" (Left : in Unbounded_String; Right : in String) - return Unbounded_String{ with Reducer => "&"}; + return Unbounded_String {with Associative}; function "&" (Left : in String; Right : in Unbounded_String) - return Unbounded_String{ with Reducer => "&"}; + return Unbounded_String {with Associative}; function "&" (Left : in Unbounded_String; Right : in Character) - return Unbounded_String{ with Reducer => "&"}; + return Unbounded_String {with Associative}; function "&" (Left : in Character; Right : in Unbounded_String) - return Unbounded_String{ with Reducer => "&"}; + return Unbounded_String {with Associative}; Modify A.18.2 (15/2-18/.2) + function "&" (Left, Right : Vector) return Vector {with Associative}; - function "&" (Left, Right : Vector) return Vector - { with Identity => Empty_Vector}; - function "&" (Left : Vector; - Right : Element_Type) return Vector - { with Reducer => "&"}; + Right : Element_Type) return Vector {with Associative}; function "&" (Left : Element_Type; - Right : Vector) return Vector - { with Reducer => "&"}; + Right : Vector) return Vector {with Associative}; - function "&" (Left, Right : Element_Type) return Vector - { with Reducer => "&"}; + function "&" (Left, Right : Element_Type) return Vector {with Associative}; Add after A.18.3 (32/2) - - function "&" (Left, Right : List) return List - { with Identity => Empty_List}; + function "&" (Left, Right : List) return List {with Associative}; function "&" (Left : List; - Right : Element_Type) return List - { with Reducer => "&"}; + Right : Element_Type) return List {with Associative}; function "&" (Left : Element_Type; - Right : List) return List - { with Reducer => "&"}; + Right : List) return List {with Associative}; + + function "&" (Left, Right : Element_Type) return List {with Associative}; + +Modify A.18.7(53/2) - function "&" (Left, Right : Element_Type) return List - { with Reducer => "&"}; +procedure Union (Target : in out Set; + Source : in Set) {with Associative}; Modify A.18.7(55/2) - function Union (Left, Right : Set) return Set - { with Identity => Empty_Set}; + function Union (Left, Right : Set) return Set {with Associative}; +Modify A.18.7(57/2) +procedure Intersection (Target : in out Set; + Source : in Set) {With Associative}; + +Modify A.18.7(59/2) + +function Intersection (Left, Right : Set) return Set {With Associative}; + Modify A.18.7(67/2) + + function Symmetric_Difference (Left, Right : Set) return Set {with Associative}; - function Symmetric_Difference (Left, Right : Set) return Set - {with Identity => Empty_Set}; +Modify A.18.8(26/2) + procedure Union (Target : in out Set; + Source : in Set) {with Associative}; Modify A.18.8(27/2) + + function Union (Left, Right : Set) return Set { with Associative}; + +Modify A.18.8(29/2-31/2) + +procedure Intersection (Target : in out Set; + Source : in Set) {with Associative}; + + function Intersection (Left, Right : Set) return Set {with Associative}; - function Union (Left, Right : Set) return Set - { with Identity => Empty_Set}; Modify A.18.8(35/2) - function Symmetric_Difference (Left, Right : Set) return Set - { with Identity => Empty_Set}; + function Symmetric_Difference (Left, Right : Set) return Set {with Associative}; -Modify A.18.9(28/2) +Modify A.18.9(27/2) - function Union (Left, Right : Set) return Set - { with Identity => Empty_Set}; + procedure Union (Target : in out Set; + Source : in Set) {with Associative}; + function Union (Left, Right : Set) return Set { with Associative}; + +procedure Intersection (Target : in out Set; + Source : in Set) {with Associative}; + + function Intersection (Left, Right : Set) return Set {with Associative}; + Modify A.18.9(37/2) - function Symmetric_Difference (Left, Right : Set) return Set - { with Identity => Empty_Set}; + function Symmetric_Difference (Left, Right : Set) return Set {with Associative}; !discussion - -There is a continuing trend of exponential growth of computational -elements embedded on a single chip. This has led to significant -challenges for software designers and implementers. Prior to 2005, the -increase in transistor count corresponded to a similar increase in CPU -clock speed, which boosted performance of sequential algorithms. Since -then, CPU clock speeds have leveled off for reasons of practicality, and -chip manufacturers have instead moved towards multicore technologies as -a means of achieving performance increases. - -As parallel technologies become more prevalent in the form of new -emerging hardware platforms, safety concerns need to consider the -paradigm shift from sequential to parallel behaviour. It is a paradigm -that has been for a long time contained within a specialized domain of -high-performance computing, but that is now required in all domains of -computing systems. - -This proposed model does not define syntax for the explicit -parallelization of reduction expressions, since such parallelization can be -performed implicitly by the compiler, when it knows that the expression is free -of side-effects. This is facilitated by annotations identifying global variable -usage on subprogram specifications (see AI12-0079-1). -A reduction expression provides a concise way to use iteration to combine a set -of values into a single result. +A 'Reduce or 'Parallel_Reduce attribute reference provides a concise way to use +iteration to combine a set of values into a single result. We already have some special purpose reduction expressions in Ada in the form of quantified expressions and array aggregates of the form using an @@ -632,28 +775,62 @@ Here we are in both cases effectively reducing a set of Boolean values into a single result using quantified expressions. -A similar effect can be written using the more generalized Reduction expression -syntax. +A similar effect can be written using a more generalized 'Reduce attribute +expression, in combination with an array aggregate. All_Graduated : constant Boolean := - (for Student of Class => <True> and Passed_Exam (Student)); + (for Student of Class => Passed_Exam (Student))'Reduce("And", True); Someone_Graduated : constant Boolean := - (for Student of Class => <False> or Passed_Exam (Student)); + (for Student of Class => Passed_Exam (Student))'Reduce("Or", False); -Here we use "and" and "or" as the combiner_expression of the Reduction +Here we use "and" and "or" as the combiner_subprogram of the Reduction expression. The initial value plays an important role, since the Identity for "and" must be true, and false for "or". +We considered whether to allow reductions for combiner_functions where the two +parameters are not of the same type. For example, one might want to have a +combiner that appends characters to an array of characters. It was decided that +this would be left out for now. We could decide to add support for it later, but +doing so would add a fair bit more complexity. For instance, it would then be +necessary to define an Identity_Value aspect, because the compiler would not +know how to initialize local accumulators for different tasklets. We currently +only allow combiners where both parameters are of the same type. This allows us +to use the first value associated each tasklet as the initial value, which works +because the result and inputs are of the same type. If the types were different, +we'd also need to define a Reducer aspect that names another subprogram that can +be used to combine results from different tasklets. Such a Reducer subprogram +would necessarily have the same types for both input parameters. Since we are +currently restricting combiner_functions to have that form, there is no need to +define a Reducer aspect. + +Such reducers tend to be concatentation reductions, which Ada already has +concise syntax for, in the form of array aggregate notation, and possibly +container aggregate as they are currently being proposed. There otherwise seems +to be little need for such capability. + +We also considered whether the initial_value was needed or not. We could +alternatively overload the attribute names to provide versions that do not +accept a second argument. + +This however, means that there can be a question about what the expression +should evaluate to, if the prefix of the attribute specifies a null range of +values. Likely, an exception would need to be raised, but that can add +complexity for uses such as contracts, since handling the exception case would +need to be considered. We decided that for now at least, it is better to keep +the interface simple. If an exception is needed for a null range, there are +other ways to do that already in the language. + Another concern might be whether parallel loops can generally be written as -expressions. +expressions, and still have a similar performance benefit. Consider the calculation of Pi: function Pi (Number_Of_Steps : Natural := 100_000) return Long_Float is (1.0 / Number_Of_Steps * (parallel for I in 1 .. Number_Of_Steps => - <0.0> + (4.0 / (1.0 + ((Long_Float (I) - 0.5) * 1.0 / Number_Of_Steps)**2)))); + (4.0 / (1.0 + ((Long_Float (I) - 0.5) * 1.0 / Number_Of_Steps)**2))) + 'Reduce("+", 0.0)); One might feel that the readability of this example might be improved if temporary variable declarations were to be added for intermediate results. @@ -675,29 +852,73 @@ is Step : constant Long_Float := 1.0 / Number_Of_Steps; - function Pi_Slicer (R : Long_Float; Index : Natural) return Float - with Reducer => "+" + function Pi_Slicer (Index : Natural) return Float is X : constant Long_Float := (Long_Float (Index) - 0.5) * Step; begin - return R + 4.0 / (1.0 + X ** 2); + return 4.0 / (1.0 + X ** 2); end Pi_Slicer; + Temp : constant Long_Float := + (for I in 1 .. Number_Of_Steps => + Pi_Slicer (I))'Parallel_Reduce("+", 0.0); begin - Pi : constant Long_Float := Step * - (for I in 1 .. Number_Of_Steps => Pi_Slicer (<0.0>, I)); + return Step * Temp; end Pi; Which leaves a simpler looking Reduction Expression to do computation. + +For performance testing, two versions of this code were created using the +Paraffin libraries, and tested using GNAT on a quadcore Linux machine. + +One version of the code has the parallelism code written inline as in the first +version above, and the second calls a local subprogram idential to the Pi_Slicer +routine above. + +For 10_000_000 steps of iteration, the following results were collected with +optimization turned off. + +Sequential Pi +Elapsed = 00:00:00.65 +Pi = 3.141592653590E+00 + +Work Seeking Pi +Elapsed = 00:00:00.16 +Pi = 3.141592653590E+00 + +'Parallel_Reduce Pi +Elapsed = 00:00:00.19 +Pi = 3.141592653590E+00 + +Both versons of the code produced comparable results compared to the sequential +version of the code. + +After turning on full optimization, and rerunning the same code, the following +results were collected. + +Sequential Pi +Elapsed = 00:00:00.57 +Pi = 3.141592653590E+00 -Another concern might be about the need to perform multiple reductions at the +Work Seeking Pi +Elapsed = 00:00:00.15 +Pi = 3.141592653590E+00 + +'Parallel_Reduce Pi +Elapsed = 00:00:00.14 +Pi = 3.141592653590E+00 + +In this case, the results were even more comparable, and in fact the better +time was found with the version of code that had the extra function call. + +Another concern might be about the need to perform multiple reductions at the same time. Consider: - Sum : Integer := (for X of Arr => <0> + X); - Min : Integer := (for X of Arr => Integer'Min(<Integer'Last>, X)); - Max : Integer := (for X of Arr => Integer'Max(<Integer'First>, X)); + Sum : Integer := A'Reduce("+", 0): + Min : Integer := A'Reduce(Integer'Min, Integer'Last); + Max : Integer := A'Reduce(Integer'Max, Integer'First); Here we have three calculations that might ideally occur in parallel, but here would normally be expected to execute sequentially with respect to each other. @@ -721,21 +942,19 @@ Max => Integer'First); -- Reducer function for the Reduction expression - function Reduce (L, R : Summary) return Summary with Identity => Identity is + function Reduce (L, R : Summary) return Summary with Associative is (Summary'(Sum => L + R, Min => Integer'Min (L, R), Max => Integer'Max (L, R))); - -- Combiner function for the Reduction expression - function Process (L : Summary; X : Integer) return Summary - with Reducer => Reduce is - (Summary'(Sum => L.Sum + X, - Min => Integer'Min (L.Min, X), - Max => Integer'Max (L.Max, X))); - -- Reduction expression to compute all 3 results at once - Result : constant Summary := (for X of Arr => Process (<Identity>, X)); + Result : constant Summary := A'Reduce(Reduce, Identity); +It was also noted here during performance testing that better times were +collected by actually writting 3 separate reductions, however in other more +complicated examples, it was found that writing a composite object as above +provided better performance. + !ASIS ** TBD. @@ -5028,6 +5247,61 @@ but note that while this is not commutative, it is associative, and thus is a candidate for parallelisation. The intent of the proposal is to support both commutative and non-commutative reducer functions. + +**************************************************************** + +From: Brad Moore +Sent: Saturday, January 20, 2018 4:16 PM + +This is my first attempt at rewriting the new AI on Reduction capabilities. +[This is version /02 of the AI - ED.] + +This version is a complete replacement for what I submitted last time, and +introduces two attributes, + +'Reduce + +and + +'Parallel_Reduce + + +The 'Reduce attribute is considered to have sequential semantics, whereas the +'Parallel attribute has parallel semantics. + +I also got rid of the Identity_Value aspect, and Reducer aspect, + +and instead added an Associative aspect which is a boolean aspect that indicates +if the subprogram results are considered to be associative or not. + +For instance, Addition is considered to be associative because; + + (A + B) + C = A + (B + C) + + +The combiner_subprogram of the attribute can be a function or procedure, that +accepts exactly two parameters, both of the same type. The result of the +function is also of this same type. + +It is because of this restriction that we can eliminate the 'Identity_Value and +'Reducer aspects. The first value assigned to a tasklet can be used as the +initial value, except for the case of the tasklet processing the first item of +the prefix, in which case, the initial_Value argument of the attribute is used. + +Comments welcome, of course... + +**************************************************************** + +From: Randy Brukardt +Sent: Thursday, January 25, 2018 1:57 AM + +Mostly looks OK to me, although you don't need some of the generic Nonblocking +rules for Associative (since Associative doesn't control Legality Rules in the +subprogram body like Nonblocking does). + +I fixed a number of typos and formatting issues when I posted this, the worst +being "two parameters are not of the same time" rather than type. This version +will get put on the website Friday with all of the other last minute updates. ****************************************************************

Questions? Ask the ACAA Technical Agent