Parallel Addition

Parallel Addition

Description

While sequential addition of a set of numbers, such as the elements of an array, is well understood, the implementation of a parallel addition algorithm provides both a new set of challenges and an opportunity to use more than one core on your computer.
The concept behind this parallel addition algorithm is to create several tasks, each of which reads a pair of values from the set of values to be added, performs the addition, then puts its result back into the set of values to be added. When the set of values to be added is reduced to 1 the addition is complete, and the remaining value in the set is the final total.
The following figures graphically show a concept of how the algorithm works. In practice the exact pairing of values to be added may differ. That difference is not important to the result of the program because addition is commutative.

Illustration 1: Initial Data Set

In this example each parallel task will extract two values from the set of values and add them together. The result of each addition will then be combined into a new set of values, as shown in Illustration 2.
Illustration 2: First Series of Pair-Wise Additions

Again, the parallel tasks extract pairs of values from the existing set of values, add them together and then combine the results into a new set of values as shown in Illustration 3.


Illustration 3: Second Series of Pair-Wise Additions

Finally, the parallel tasks extract the final pair of values from the set of values, perform the addition, and then place the result back into a new set. This result is the final total of all the initial values.
The set containing the final value will always have only one value in it. There will be no more pairs to add.
Illustration 4: Third Series of Pair-Wise Additions

The example shown in Illustrations 1 through 4 show a data starting data set with eight values. This algorithm will produce the proper value, within the limits of integer representation and data storage on your computer, for any number of values.

Implementation Considerations

It is possible to provide separate sets of values for each series of pair-wise additions. The number of separate lists you will need is log base 2 of the number of initial values in the set. Creation of separate values sets is both complicated and inefficient. The use of separate sets may look appealing because of the example shown above because that example has an initial set of values containing an even number of values. It is very likely that your data set may contain an odd number of values. After the first series of additions you will have one value left over in the initial set that has not been placed in the second set as a result. You will then need to create special rules for data sets with an odd number of values. You will also need to consider how to deal with an empty data set. Producing a total of 0 for an empty data set is incorrect. A total of 0 is not the same as no total. 0 is a valid and normal possible result for a total of positive and negative integer values. 0 is also a valid value in your set of values. You cannot, therefore, use 0, or any other integer, as an indicator of “no more values to process”. As a result of these considerations I decided to place all the data values in a single synchronized FIFO queue. Each parallel pair-wise addition task will dequeue 2 values from the queue, perform the addition, and then enqueue the result of the addition back to the same queue. This approach avoids complexity associated with odd numbered data sets, and avoids having to create separate data sets for each series of additions. Use of a single queue for all data will result in unpredictable data pairings for addition, but that is not a concern.
One of the biggest challenges is determining when the parallel pair-wise addition tasks are done with their work. The addition tasks should only know about their addition responsibilities. They should not know about how many other addition tasks are executing, or how big the current data set is. I chose to create a “master” task that creates the initial data set, determines when the parallel pair-wise addition tasks have completed their work, and prints the resulting total.
I stated earlier that the result will reside in a data set containing only one value. Do not be fooled into thinking that the addition is completed when the data set contains only one value. Remember that each parallel pair-wise addition task dequeues two values from the data set. It is possible that you have an odd number of data values, leaving one unprocessed value in a data set results are added to the data set by the parallel pair-wise addition tasks. The tasks can only be done when all the parallel pair-wise addition tasks are done processing data, with no more pairs of data to process, and the data set contains only one value.
There is a possible race condition in this algorithm when dequeuing pairs of data from the data set. A task may check the data set and determine that there are two values in the data set. That task will then attempt to dequeue its first value followed by a request to dequeue its second value. The race condition exists when another task attempts to dequeue two values at the same time. The two dequeue requests can be interleaved, resulting in each task dequeuing one value, with no more values left in the data set.
I handled this problem by creating a singleton “transaction handler” task responsible for dequeuing all data pairs for the parallel pair-wise addition tasks. Giving only one task the ability to dequeue pairs of data eliminated the race condition.
I welcome comments about improvements for the code shown below.

Source Code

-------------------------------------------------------------------------------

-- Addition of integers in an array using Ada Tasks --

-------------------------------------------------------------------------------

with Ada.Text_IO; use Ada.Text_IO;

with Ada.Calendar; use Ada.Calendar;

with Ada.Containers.Synchronized_Queue_Interfaces;

with Ada.Containers.Unbounded_Synchronized_Queues;

use Ada.Containers;

procedure Array_Addition is

   type Target_Array is array(Positive range <>) of Integer;

   type Target_Access is access all Target_Array;

   type Array_Set is array(Positive range 1..3) of Target_Access;

   package Integer_Interface is new

           Synchronized_Queue_Interfaces(Element_Type => Integer);

   package Unbounded_Integer_Queues is new

           Unbounded_Synchronized_Queues(Queue_Interfaces => Integer_Interface);

   My_Queue : Unbounded_Integer_Queues.Queue;

   Id_Queue : Unbounded_Integer_Queues.Queue;

   subtype Adder_Count is Positive range 1..4;

   type Status_Array is array(Adder_Count) of boolean;

   protected Adder_Status is

      procedure Set(Id : in Adder_Count; State : in Boolean);

      entry All_False;

   private

      Status : Status_Array := (Others => False);

   end Adder_Status;

   protected body Adder_Status is

      procedure Set(Id : in Adder_Count; State : in Boolean) is

      begin

         Status(Id) := State;

      end Set;

      entry All_False when

            (for all I in Status'range => Status(I) = False) is

      begin

         null;

      end All_False;

   end Adder_Status;

   ----------------------------------------------------------------------------

   -- Create a transaction interface to the unbounded buffer so that each --

   -- addition task can either get two integers or nothing --

   ----------------------------------------------------------------------------

   task Transaction_Handler is

      entry Get_Values(Value_1, Value_2 : out Integer;

                       Succeeded : out Boolean);

   end Transaction_Handler;

   task body Transaction_Handler is

   begin

      loop

         select

            accept Get_Values(Value_1, Value_2 : out Integer;

                              Succeeded : out Boolean) do

               if My_Queue.Current_Use >= 2 then

                  My_Queue.Dequeue(Value_1);

                  My_Queue.Dequeue(Value_2);

                  Succeeded := True;

               else

                  Value_1 := 0;

                  Value_2 := 0;

                  Succeeded := False;

               end if;

            end Get_Values;

         or

            terminate;

         end select;

      end loop;

   end Transaction_Handler;

   -- Each adder task requests two values from My_Queue, adds them together

   -- and puts the result back in My_Queue

   task type Adder is

      entry Stop;

   end Adder;

   task body Adder is

      Value_1    : Integer;

      Value_2    : Integer;

      Got_Values : Boolean;

      Id         : Adder_Count;

   begin

      Id_Queue.Dequeue(Id);

      loop

         select

            accept Stop;

            exit;

         else

            Transaction_Handler.Get_Values(Value_1, Value_2, Got_Values);

            Adder_Status.Set(Id, Got_Values);

            if Got_Values then

               My_Queue.Enqueue(Value_1 + Value_2);

            end if;

         end Select;

      end loop;

   end Adder;

   procedure Print_Result is

      Result : Integer;

   begin

      delay 0.001;

      Loop

      -- All the adders are done with the current set of values

      -- when every element in the Adder_Status internal status array

      -- is set to false and there is only one element left in My_Queue.

      -- Simply looking for a single element in My_Queue fails when there

      -- is an odd number of initial values and an even number of adder

      -- tasks.

      -- The single remaining value when the adders have completed is the

      -- final total.

         Adder_Status.All_False;

         if My_Queue.Current_Use = 1 then

            delay 0.001;

            My_Queue.Dequeue(Result);

            Put_Line("Total:" & Integer'Image(Result));

            exit;

         elsif My_Queue.Current_Use = 0 then

            Put_Line("No data for total.");

            exit;

         end if;

      end loop;

   end Print_Result;

   Adders : array(Adder_Count) of Adder;

   First_Array : aliased Target_Array := (4, 2, 1, 3, 1, -2, 0, 20);

   Second_Array : aliased Target_Array := (5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5);

   Third_Array : aliased Target_Array := (1, 2, 3, 4, 5, 6);

begin

   -- Set up the Id values in the Id queue so that each adder will have

   -- a unique Id number for indicating its completion for the Adder_Status

   -- protected object

   for I in Adder_Count'range loop

      Id_Queue.Enqueue(I);

   end loop;

   -- Populate My_Queue with the first set of values

   for I of First_Array loop

      My_Queue.Enqueue(I);

   end loop;

   Print_Result;

   -- Populate My_Queue with the second set of values

   for I of Second_Array loop

      My_Queue.Enqueue(I);

   end loop;

   Print_Result;

   -- Populate My_Queue with the third set of values

   for I of Third_Array loop

      My_Queue.Enqueue(I);

   end loop;

   Print_Result;

   -- Populate My_Queue with a single value

   My_Queue.Enqueue(100);

   Print_Result;

   -- Print result from an empty queue

   Print_Result;

   for worker of Adders loop

      worker.Stop;

   end loop;

end Array_Addition;