Parallel constructs

Parallel operations (AI12-0119 ) is the prime AI for satisfying the first instruction from WG 9 to the ARG, i.e. "Improving the capabilities of Ada on multi-core and multi-threaded architectures". Parallel block statements and parallel loops are two of the new parallel constructs that are provided.

A parallel block statement (see RM 5.6.1) consists of a set of concurrent activities each specified by a sequence of statements, separated by the reserved word and, analogous to the syntax for a select statement where the alternatives are separated by the reserved word or.

A parallel loop (see RM 5.5) defines a loop body which is designed such that the various iterations of the loop can run concurrently. The implementation is expected to group the iterations into "chunks" to avoid creating an excessive number of physical threads of control, but each iteration is nevertheless considered for most purposes as its own separate logical thread of control.

Both of these constructs start with the new reserved word parallel to clearly indicate that these constructs are designed for parallel execution. The implementation might still not execute the constructs in parallel, but the intent is that if multiple processors are available, some or all of them should be allocated to the execution of the construct.

type Expression is tagged null record;
   -- Components will be added by each extension
type Expr_Ptr is access all Expression'Class;
type Binary_Operation is new Expression with
   record
   -- An internal node in an Expression tree
      Left, Right : Expr_Ptr;
   end record;
procedure Traverse (T : Expr_Ptr) is
begin
   -- Recurse down the binary tree
   if T /= null and then
      T.all in Binary_Operation'Class then
      parallel do
         Traverse (T.Left);
      and
         Traverse (T.Right);
      and
         Ada.Text_IO.Put_Line ("Processing " & Ada.Tags.Expanded_Name (T'Tag));
      end do;
   end if;
end Traverse;

function Search (S : String;
                    Char : Character) return Boolean is
begin
   if S'Length <= 1000 then
      -- Sequential scan
      return (for some C of S => C = Char);
   else
      -- Parallel divide and conquer
      declare
         Mid : constant Positive := S'First + S'Length/2 – 1;
      begin
         parallel do
           for C of S(S'First .. Mid) loop
               if C = Char then
                  return True;     -- Terminates enclosing do
               end if;
            end loop;
         and
            for C of S(Mid + 1 .. S'Last) loop
               if C = Char then
                  return True;     -- Terminates enclosing do
               end if;
            end loop;
         end do;
         -- Not found
         return False;
       end;
   end if;
end Search;

parallel
for I in Grid'Range(1) loop
Grid(I, 1) := (for all J in Grid'Range(2) =>
Grid(I,J) = True);
end loop;

It is intended that the parallel constructs use lightweight threading so as to incur less overhead than tasking. To reduce implementation complexity and reduce the risk of deadlock, blocking is not allowed in a parallel construct, thus it is a bounded error to invoke an operation that is potentially blocking during the execution of a parallel construct. The compiler may complain if a parallel sequence calls a potentially blocking operation. It may also complain if parallel sequences have conflicting global side-effects.

Whereas Parallel operations (AI12-0119) provides the mechanism for iterating in parallel over the elements of an array, Parallel Container Iterators (AI12-0266) provides the equivalent mechanism for iterating over containers. The optional reserved word parallel may be placed before a for statement for its iterator form, not just its loop parameter form. The interfaces in Ada.Containers.Iterator_Interfaces are extended to include two new interfaces, a parallel iterator interface, and a reversible parallel iterator interface.

type Matrix is array
         (Integer range <>, Integer range <>) of Real;
Board : Matrix (1 .. 8, 1 .. 8);
parallel
for Element of Board loop
   Element := Element * 2.0;
   -- Double each element of the two-dimensional array Board
end loop;

2.1 Parallel constructs