This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array.
• A sequential summation using a single Ada task.
• A concurrent summation using 16 Ada tasks coordinating using the Ada Rendezvous mechanism.
• A concurrent summation using 16 Ada tasks coordinating using a shared buffer.
This test personal computer has the following characteristics.
• Processor : AMD Ryzen 7 7800X3D 8-Core Processor with baseline speed of 4.20 Ghz
• RAM: 64.0 GB (63.2 GB usable) of DDR5 RAM
• Operating System: Windows 11 Home
The software for this test is written in the Ada programming language using the GNAT Community Edition 2021 compiler.
The program source code is contained in three files.
There is one custom Ada package defined for this test. The package is named array_sums. Ada packages separate the interface definition from the implementation. The interface definition, or package specification, as it is called in Ada, is in a file named array_sums.ads.
generic
Num_Tasks : Positive;
package array_sums is
type Data_Array is array (Integer range <>) of Integer;
type Data_Access is access all Data_Array;
function Sum_Sequential (Item : in not null Data_Access) return Integer;
function Sum_Buffered (Item : in not null Data_Access) return Integer;
function Sum_Rendezvous (Item : in not null Data_Access) return Integer;
end array_sums;
This is a generic package. The generic parameter is named Num_Tasks. Num_Tasks must be an integer value greater than 0. The package specification defines two data types.
• Type Data_Array is an unconstrained array of Integer values indexed by the Integer type.
• Type Data_Access is an access type accessing an instance of Data_Array. Access types are similar to references in C++ or Java.
The three functions to be compared are declared.
• Function Sum_Sequential sums an instance of Data_Access, which cannot be null, and returns the sum.
• Function Sum_Buffered sums an instance of Data_Access, which cannot be null, and returns the sum.
• Function Sum_Rendezvous sums an instance of Data_Access, which cannot be null, and returns the sum.
This article will compare the time taken to execute each of the three functions above.
Implementation Source Code
All three functions to sum the Data_Array references by an instance of Data_Access are implemented in the package body. I will first isolate and explain each function.
Sum_Sequential
This function is the simplest function to write and explain. It operates in a single Ada task which sequentially sums all the elements in the array passed to it.
function Sum_Sequential (Item : in not null Data_Access) return Integer is
total : Integer := 0;
begin
for value of Item.all loop
total := total + value;
end loop;
return total;
end Sum_Sequential;
This function uses a single for loop to iterate through every value in the array, adding that value to the local variable total in each iteration. Upon completing the iterations the value of total is returned.
Sum_Buffered
This function is the largest function of the three because a thread-safe shared buffer is defined to collect the total of all the concurrent tasks iterating through distinct slices of the array passed to the Sum_Buffered function.
function Sum_Buffered (Item : in not null Data_Access) return Integer is
protected final_Total is
procedure Add (Value : in Integer);
function Report return Integer;
private
Total : Integer := 0;
end final_Total;
protected body final_Total is
procedure Add (Value : in Integer) is
begin
Total := Total + Value;
end Add;
function Report return Integer is
begin
return Total;
end Report;
end final_Total;
task type Adder is
entry Set (Min : Integer; Max : Integer);
end Adder;
task body Adder is
Total : Integer := 0;
First : Integer;
Last : Integer;
begin
accept Set (Min : Integer; Max : Integer) do
First := Min;
Last := Max;
end Set;
for I in First .. Last loop
Total := Total + Item (I);
end loop;
final_Total.Add (Total);
end Adder;
begin
declare
type Adders is array (1 .. Num_Tasks) of Adder;
The_Adders : Adders;
Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
Slice_Start : Integer := Item.all'First;
Slice_Max : Integer := Item.all'First;
begin
for I in The_Adders'Range loop
if I = The_Adders'Last then
Slice_Max := Item'Last;
else
Slice_Max := Slice_Max + Num_Elements;
end if;
The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
if I < The_Adders'Last then
Slice_Start := Slice_Max + 1;
else
Slice_Start := Slice_Start + Num_Elements;
end if;
end loop;
end;
return final_Total.Report;
end Sum_Buffered;
Shared buffer
The shared buffer is defined as an Ada protected object named final_Total. The protected object implicitly handles locking to prevent race conditions. It contains two methods. A procedure named add which takes an IN parameter of type Integer and adds that integer to the data field in final_Total named Total. A protected procedure implicitly implements a read-write lock on the data. The second method is a function named Report which returns the value of Total. Ada protected functions are not allowed to modify the value of the protected object. Protected functions are read-only methods. Ada protected functions implicitly implement a shared read lock on the data, allowing multiple functions to access the data simultaneously.
Adder task type
Ada tasks are analgous to threads and are often implemented using operating system threads. A task type defines the behavior of a particular kind of task which can be duplicated by creating multiple instances of the task type, just as if the task type were a data type.
Ada task types, like packages, have separate specifications and implementations. The specification for the Adder task type is:
task type Adder is
entry Set (Min : Integer; Max : Integer);
end Adder;
This task type specification declares the Adder type to have one entry named Set. The Set entry has two parameters named Min and Max. Each parameter passes an integer into the instance of the task type. Languages such as C++ and Java would accomplish this through the use of a constructor for a thread class.
The task type implementation is defined in the task body.
task body Adder is
Total : Integer := 0;
First : Integer;
Last : Integer;
begin
accept Set (Min : Integer; Max : Integer) do
First := Min;
Last := Max;
end Set;
for I in First .. Last loop
Total := Total + Item (I);
end loop;
final_Total.Add (Total);
end Adder;
The task encounters an accept statement before it does anything else. The accept statement implements an Ada Rendezvous with a calling task. This Rendezvous completes the entry specified in the task specification. The task will suspend until another task passes the Min and Max values to the instance of the task type. Within the accept statement the entry parameter values are copied into the local variables First and Last.
The task instance then iterates through the set of array values starting with the index value contained in the First variable through the index value contained in the Last variable, totalling all the values. Upon completion of the for loop the value of Total is added to the final_Total protected object.
Sum_Buffered execution
The Sum_Buffered function begins its execution at the begin reserved word following the end of the declaration of the Adder task type.
An inner block is declared within the Sum_Buffered function in which all the instances of the Adder task type are declared and executed. The Sum_Buffered function outer block will wait for all the tasks defined in the inner block to complete. This behavior is similar to calling a join method in C++ or Java for each of the declared task instances.
begin
declare
type Adders is array (1 .. Num_Tasks) of Adder;
The_Adders : Adders;
Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
Slice_Start : Integer := Item.all'First;
Slice_Max : Integer := Item.all'First;
begin
for I in The_Adders'Range loop
if I = The_Adders'Last then
Slice_Max := Item'Last;
else
Slice_Max := Slice_Max + Num_Elements;
end if;
The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
if I < The_Adders'Last then
Slice_Start := Slice_Max + 1;
else
Slice_Start := Slice_Start + Num_Elements;
end if;
end loop;
end;
return final_Total.Report;
end Sum_Buffered;
The inner block declares an array type and four variables which only exist within the inner block.
• Type Adders is an array of Adder indexed by the values 1 through Num_Tasks. Rememer that Num_Tasks was the generic parameter passed to the package specification.
• The_Adders is an instance of Adders. All the tasks in the Adders array implicitly start at this point, and are immediatly suspended waiting for their Set entry to be called.
• Num_Elements is an Integer containing the number of array elements processed by each of the Num_Elements task objects, except the last task in the array which may contain more tasks because the number of data elements may not evenly divide into Num_Tasks and the extra elements are processed by the last task in the array.
• Slice_Start is an data_array index value specifying the first index value to be processed by a particular task.
• Slice_Max is a data_array index value specifying the maximum index value to be processed by a particular task.
The for loop iterates through all the index values in the The_Adders array, assigning Slice_Start and Slice_Max to each instance by calling that instance’s Set entry.
The inner block completes when all Num_Tasks of the array have completed. At that point all the data elements declared in the inner block are recovered and the Sum_Buffered function returns the value produced by calling final_Total.Report.
Sum_Rendezvous
Sum_Rendezvous has many similarities with Sum_Buffered. Sum_Rendezvous does not use a shared buffer to collect the subtotals from all the tasks. Instead it uses a second entry to report the subtotals.
Sum_Rendezvous also does not use an inner block because the second entry will cause the Sum_Rendezvous function to suspend until the task it calls accepts the Report entry.
function Sum_Rendezvous (Item : in not null Data_Access) return Integer is
task type Adder is
entry Set (Min : Integer; Max : Integer);
entry Report (Total : out Integer);
end Adder;
task body Adder is
Subtotal : Integer := 0;
First : Integer;
Last : Integer;
begin
accept Set (Min : Integer; Max : Integer) do
First := Min;
Last := Max;
end Set;
for I in First .. Last loop
Subtotal := Subtotal + Item (I);
end loop;
accept Report (Total : out Integer) do
Total := Subtotal;
end Report;
end Adder;
type Adders is array (1 .. Num_Tasks) of Adder;
The_Adders : Adders;
Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
Slice_Start : Integer := Item.all'First;
Slice_Max : Integer := Item.all'First;
Subtotal : Integer;
Grand_Total : Integer := 0;
begin
for I in The_Adders'Range loop
if I = The_Adders'Last then
Slice_Max := Item'Last;
else
Slice_Max := Slice_Max + Num_Elements;
end if;
The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
if I < The_Adders'Last then
Slice_Start := Slice_Max + 1;
else
Slice_Start := Slice_Start + Num_Elements;
end if;
end loop;
for T of The_Adders loop
T.Report (Subtotal);
Grand_Total := Grand_Total + Subtotal;
end loop;
return Grand_Total;
end Sum_Rendezvous;
Adder task specification
The Adder task specification for Sum_Rendezvous adds a second entry to the Adder task specification declared in the Sum_Buffered function.
task type Adder is
entry Set (Min : Integer; Max : Integer);
entry Report (Total : out Integer);
end Adder;
The Set entry passes two values into an instance of the Adder task type. The Report entry passes a single value out of the instance of the Adder task type.
Adder task body
task body Adder is
Subtotal : Integer := 0;
First : Integer;
Last : Integer;
begin
accept Set (Min : Integer; Max : Integer) do
First := Min;
Last := Max;
end Set;
for I in First .. Last loop
Subtotal := Subtotal + Item (I);
end loop;
accept Report (Total : out Integer) do
Total := Subtotal;
end Report;
end Adder;
The Adder instance suspends on the accept call for the Set entry, just as we say in the Sum_Buffered function. It then iterates through the array slice of the Data_Array just as the function in the Sum_Buffered function. The difference is seen after the for loop completes. Instead of calling a protected procedure to add the subtotal to a total, the function simply accepts the Report entry and passes the subtotal out to the calling task.
Array_sums_main
The entry point for this comparison program is a procedure named array_sums_main. The purpose of this procedure is to execute each of the three array summing functions in the adder_sums package and display the results and timing for each function.
with Array_Sums;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;
procedure array_Sums_main is
Start : Time;
Finis : Time;
Final_Total : Integer;
exec_time : Duration;
package sums is new Array_Sums(16);
use Sums;
The_Array : Data_Access := new Data_Array (1 .. Integer'Last);
begin
The_Array.all := (Others => 1);
Put_Line
("The size of the data array is" & Integer'Image (The_Array'Length));
New_Line;
Put_Line ("Sequential algorithm");
Start := clock;
Final_Total := Sum_Sequential(The_Array);
Finis := clock;
Put_Line ("Array total:" & Final_Total'Image);
New_Line;
exec_time := Finis - Start;
Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
Put_Line
("Time per addition operation:" &
Float'Image (Float (exec_time) / Float (The_Array'Length)) & "
seconds");
New_Line;
Put_Line("Concurrent algorithm coordinating using Rendezvous");
Start := clock;
Final_Total := Sum_Rendezvous(The_Array);
Finis := clock;
Put_Line ("Array total:" & Final_Total'Image);
New_Line;
exec_time := Finis - Start;
Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
Put_Line
("Time per addition operation:" &
Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");
New_Line;
Put_Line("Concurrent algorithm coordinating using shared buffer");
Start := clock;
Final_Total := Sum_Buffered(The_Array);
Finis := clock;
Put_Line ("Array total:" & Final_Total'Image);
New_Line;
exec_time := Finis - Start;
Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
Put_Line
("Time per addition operation:" &
Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");
end array_sums_main;
The array_sums generic package is instantiated passing the value 16 as the generic parameter. This causes the concurrent functions each to use 16 tasks to complete their calculations.
Comparison output
The output of this procedure is:
The size of the data array is 2147483647
Sequential algorithm
Array total: 2147483647
Elapsed calculation time: 6.531004600 seconds
Time per addition operation: 3.04124E-09 seconds
Concurrent algorithm coordinating using Rendezvous
Array total: 2147483647
Elapsed calculation time: 0.410473000 seconds
Time per addition operation: 1.91141E-10 seconds
Concurrent algorithm coordinating using shared buffer
Array total: 2147483647
Elapsed calculation time: 0.360019200 seconds
Time per addition operation: 1.67647E-10 seconds
It is clear that all three functions totaled the same set of values. The timings of the concurrent algorithms are clearly faster than the timing for the sequential algorithm, with the best timing coming from the Sum_Buffered function.
No comments:
Post a Comment