### 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;

## Comments

## Post a Comment