GNAT's Protected Objects

GNAT's Protected Objects

[Jeffrey Carter]

I was trying to decide the "optimal" number of tasks for concurrent problems on 
my 2-core system, so I wrote a little program to do matrix multiplication with 
multiple tasks.

When the tasks divide the result matrix among themselves in the obvious way, 
there's a clear decrease in elapsed time as the number of tasks increases to 4.

If I use a Linda-like approach, with a protected procedure doling out (Row, 
Column) pairs on demand, a single task is always fastest, and using multiple 
tasks slows things down. This wasn't what I expected, and wondered if this is 
inherent in such an approach, or specific to GNAT's way of implementing 
protected objects.

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

Re: GNAT's Protected Objects

[Anh Vo]

On Nov 8, 12:34 pm, Jeffrey Carter
<spam.jrcarter....@spam.not.acm.org> wrote:
>
> If I use a Linda-like approach, with a protected procedure doling out (Row,
> Column) pairs on demand, a single task is always fastest, and using multiple
> tasks slows things down. This wasn't what I expected, and wondered if this is
> inherent in such an approach, or specific to GNAT's way of implementing
> protected objects.
>

How may tasks used, two or four, when slowness was observed when
compared to simple task? I will be supprised if the answer is two. It
is logically expected that two tasks should perform better than single
task. However, when it comes to four or greater task, the result may
not be true due to task switching cost.

I would be glad to test it on my two core CPU mahine if the your
little program is posted.

Anh Vo

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/08/2010 02:38 PM, Anh Vo wrote:
>
> How may tasks used, two or four, when slowness was observed when
> compared to simple task? I will be supprised if the answer is two. It
> is logically expected that two tasks should perform better than single
> task. However, when it comes to four or greater task, the result may
> not be true due to task switching cost.

That's what I expected. However, any number of tasks > 1 took longer than a 
single task.

> I would be glad to test it on my two core CPU mahine if the your
> little program is posted.

I have appended the code to this message. Watch for line wrapping.

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

with Ada.Exceptions;
with Ada.Numerics.Float_Random;
with Ada.Real_Time;
with Ada.Text_IO;

with System.Task_Info;

procedure MP_Mult_PO is
    Num_Processors : constant Positive := System.Task_Info.Number_Of_Processors;

    subtype Index_Value is Integer range 1 .. 500;

    type Matrix is array (Index_Value, Index_Value) of Float;

    function Mult (Left : in Matrix; Right : in Matrix; Num_Tasks : in Positive) 
return Matrix;
    -- Perform a concurrent multiplication of Left * Right using Num_Tasks tasks

    function Mult (Left : in Matrix; Right : in Matrix; Num_Tasks : in Positive) 
return Matrix is
       task type Calc_One;

       protected Control is
          procedure Get (Row : out Natural; Col : out Natural);
          -- Returns the row and column of a result to calculate.
          -- Returns zero for both when there are no more results to calculate.
       private -- Control
          Next_Row : Positive := 1;
          Next_Col : Positive := 1;
          Done     : Boolean  := False;
       end Control;

       Result : Matrix;

       task body Calc_One is
          Row : Natural;
          Col : Natural;
       begin -- Calc_One
          All_Results : loop
             Control.Get (Row => Row, Col => Col);

             exit All_Results when Row = 0;

             Result (Row, Col) := 0.0;

             Sum : for K in Index_Value loop
                Result (Row, Col) := Result (Row, Col) + Left (Row, K) * Right 
(K, Col);
             end loop Sum;
          end loop All_Results;
       exception -- Calc_One
       when E : others =>
          Ada.Text_IO.Put_Line (Item => "Calc_One " & 
Ada.Exceptions.Exception_Information (E) );
       end Calc_One;

       protected body Control is
          procedure Get (Row : out Natural; Col : out Natural) is
          begin -- Get
             if Done then
                Row := 0;
                Col := 0;

                return;
             end if;

             Row := Next_Row;
             Col := Next_Col;

             if Next_Col < Index_Value'Last then
                Next_Col := Next_Col + 1;

                return;
             end if;

             Next_Col := 1;
             Next_Row := Next_Row + 1;

             Done := Next_Row > Index_Value'Last;
          end Get;
       end Control;
    begin -- Mult
       Create_Tasks : declare
          type Task_List is array (1 .. Num_Tasks) of Calc_One;

          Tasks : Task_List;
       begin -- Create_Tasks
          null; -- Wait for all tasks to complete
       end Create_Tasks;

       return Result;
    exception -- Mult
    when E : others =>
       Ada.Text_IO.Put_Line (Item => "Mult " & 
Ada.Exceptions.Exception_Information (E) );

       raise;
    end Mult;

    function Random return Float;

    Gen : Ada.Numerics.Float_Random.Generator;

    function Random return Float is
    begin -- Random
       return 200.0 * Ada.Numerics.Float_Random.Random (Gen) - 100.0; -- -100 .. 
100.
    end Random;

    A : constant Matrix := Matrix'(others => (others => Random) );
    B : constant Matrix := Matrix'(others => (others => Random) );

    C : Matrix;

    Elapsed   : Duration;
    Prev      : Duration := Duration'Last;
    Start     : Ada.Real_Time.Time;
    Num_Tasks : Positive := 1;

    use type Ada.Real_Time.Time;
begin -- MP_Mult_PO
    Ada.Text_IO.Put_Line (Item => "Num processors" & Integer'Image 
(Num_Processors) );

    All_Calls : loop
       Start := Ada.Real_Time.Clock;
       C := Mult (A, B, Num_Tasks);
       Elapsed := Ada.Real_Time.To_Duration (Ada.Real_Time.Clock - Start);
       Ada.Text_IO.Put_Line (Item => Integer'Image (Num_Tasks) & ' ' & 
Duration'Image (Elapsed) );

       exit All_Calls when Num_Tasks > 2 * Num_Processors and Elapsed > Prev;

       Prev := Elapsed;
       Num_Tasks := Num_Tasks + 1;
    end loop All_Calls;
exception -- MP_Mult_PO
when E : others =>
    Ada.Text_IO.Put_Line (Item => "MP_Mult_PO " & 
Ada.Exceptions.Exception_Information (E) );
end MP_Mult_PO;

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/08/2010 02:08 PM, Dennis Lee Bieber wrote:
>
> 	Hypothesis: If the sub-sets are running fast enough, they're
> probably blocking at getting access to the procedure to obtain the next
> data pair (or return the previous results).

Between calls to the procedure, a task calculates the sum of the products of 500 
pairs of floating-point values. That would have to be as fast as the procedure, 
which increments a couple of integers.

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

Re: GNAT's Protected Objects

[Robert A Duff]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> That's what I expected. However, any number of tasks > 1 took longer
> than a single task.

I'm not too surprised by that.  Each task is not doing much
work in between calls to Get, so the synchronization overhead
for the protected procedure calls will be high.  If you
split the work up into Num_Tasks pieces, I'd expect it
to be faster, because then the only synchronization overhead
would be in activating and terminating the tasks.

By the way, I don't see the point of the Create_Tasks block.
Seems like it's not needed.

- Bob

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/08/2010 03:43 PM, Robert A Duff wrote:
>
> By the way, I don't see the point of the Create_Tasks block.
> Seems like it's not needed.

I guess not, since the function won't return until the tasks complete. It's a 
general construct I use to wait for a group of tasks to complete before doing 
something else.

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

Re: GNAT's Protected Objects

[Anh Vo]

On Nov 8, 2:32 pm, Jeffrey Carter <spam.jrcarter....@spam.not.acm.org>
wrote:
> On 11/08/2010 02:38 PM, Anh Vo wrote:
>
>
>
> > How may tasks used, two or four, when slowness was observed when
> > compared to simple task? I will be supprised if the answer is two. It
> > is logically expected that two tasks should perform better than single
> > task. However, when it comes to four or greater task, the result may
> > not be true due to task switching cost.
>
> That's what I expected. However, any number of tasks > 1 took longer than a
> single task.
>
> > I would be glad to test it on my two core CPU mahine if the your
> > little program is posted.
>
> I have appended the code to this message. Watch for line wrapping.
>
> --
> Jeff Carter
> "Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
> who had nearly fought the Dragon of Angnor,
> who nearly stood up to the vicious Chicken of Bristol,
> and who had personally wet himself at the
> Battle of Badon Hill."
> Monty Python & the Holy Grail
> 68
>
> with Ada.Exceptions;
> with Ada.Numerics.Float_Random;
> with Ada.Real_Time;
> with Ada.Text_IO;
>
> with System.Task_Info;
>
> procedure MP_Mult_PO is
>     Num_Processors : constant Positive := System.Task_Info.Number_Of_Processors;
>
>     subtype Index_Value is Integer range 1 .. 500;
>
>     type Matrix is array (Index_Value, Index_Value) of Float;
>
>     function Mult (Left : in Matrix; Right : in Matrix; Num_Tasks : in Positive)
> return Matrix;
>     -- Perform a concurrent multiplication of Left * Right using Num_Tasks tasks
>
>     function Mult (Left : in Matrix; Right : in Matrix; Num_Tasks : in Positive)
> return Matrix is
>        task type Calc_One;
>
>        protected Control is
>           procedure Get (Row : out Natural; Col : out Natural);
>           -- Returns the row and column of a result to calculate.
>           -- Returns zero for both when there are no more results to calculate.
>        private -- Control
>           Next_Row : Positive := 1;
>           Next_Col : Positive := 1;
>           Done     : Boolean  := False;
>        end Control;
>
>        Result : Matrix;
>
>        task body Calc_One is
>           Row : Natural;
>           Col : Natural;
>        begin -- Calc_One
>           All_Results : loop
>              Control.Get (Row => Row, Col => Col);
>
>              exit All_Results when Row = 0;
>
>              Result (Row, Col) := 0.0;
>
>              Sum : for K in Index_Value loop
>                 Result (Row, Col) := Result (Row, Col) + Left (Row, K) * Right
> (K, Col);
>              end loop Sum;
>           end loop All_Results;
>        exception -- Calc_One
>        when E : others =>
>           Ada.Text_IO.Put_Line (Item => "Calc_One " &
> Ada.Exceptions.Exception_Information (E) );
>        end Calc_One;
>
>        protected body Control is
>           procedure Get (Row : out Natural; Col : out Natural) is
>           begin -- Get
>              if Done then
>                 Row := 0;
>                 Col := 0;
>
>                 return;
>              end if;
>
>              Row := Next_Row;
>              Col := Next_Col;
>
>              if Next_Col < Index_Value'Last then
>                 Next_Col := Next_Col + 1;
>
>                 return;
>              end if;
>
>              Next_Col := 1;
>              Next_Row := Next_Row + 1;
>
>              Done := Next_Row > Index_Value'Last;
>           end Get;
>        end Control;
>     begin -- Mult
>        Create_Tasks : declare
>           type Task_List is array (1 .. Num_Tasks) of Calc_One;
>
>           Tasks : Task_List;
>        begin -- Create_Tasks
>           null; -- Wait for all tasks to complete
>        end Create_Tasks;
>
>        return Result;
>     exception -- Mult
>     when E : others =>
>        Ada.Text_IO.Put_Line (Item => "Mult " &
> Ada.Exceptions.Exception_Information (E) );
>
>        raise;
>     end Mult;
>
>     function Random return Float;
>
>     Gen : Ada.Numerics.Float_Random.Generator;
>
>     function Random return Float is
>     begin -- Random
>        return 200.0 * Ada.Numerics.Float_Random.Random (Gen) - 100.0; -- -100 ..
> 100.
>     end Random;
>
>     A : constant Matrix := Matrix'(others => (others => Random) );
>     B : constant Matrix := Matrix'(others => (others => Random) );
>
>     C : Matrix;
>
>     Elapsed   : Duration;
>     Prev      : Duration := Duration'Last;
>     Start     : Ada.Real_Time.Time;
>     Num_Tasks : Positive := 1;
>
>     use type Ada.Real_Time.Time;
> begin -- MP_Mult_PO
>     Ada.Text_IO.Put_Line (Item => "Num processors" & Integer'Image
> (Num_Processors) );
>
>     All_Calls : loop
>        Start := Ada.Real_Time.Clock;
>        C := Mult (A, B, Num_Tasks);
>        Elapsed := Ada.Real_Time.To_Duration (Ada.Real_Time.Clock - Start);
>        Ada.Text_IO.Put_Line (Item => Integer'Image (Num_Tasks) & ' ' &
> Duration'Image (Elapsed) );
>
>        exit All_Calls when Num_Tasks > 2 * Num_Processors and Elapsed > Prev;
>
>        Prev := Elapsed;
>        Num_Tasks := Num_Tasks + 1;
>     end loop All_Calls;
> exception -- MP_Mult_PO
> when E : others =>
>     Ada.Text_IO.Put_Line (Item => "MP_Mult_PO " &
> Ada.Exceptions.Exception_Information (E) );
> end MP_Mult_PO;

Below are the test results conducted on GNAT 2010 running on Windows
XP.

Num processors 2
 1  0.077000009
 2  0.055627741
 3  0.023719495
 4  0.018366580
 5  0.018512129

The output looks reasonable. The speed is improved up to 4 tasks. It
slows down with 5 tasks due to tasking switch. However, it is still
better than single task.

As Robert suggested, I would divide work among tasks by passing
paramter into each task. For example, in case of two tasks, one task
handles from rows 1 .. 250 while the other task handle from rows
251 .. 500. By the way, the protected singleton type Control is no
longer needed.

Anh Vo

Re: GNAT's Protected Objects

[Peter C. Chapin]

On 2010-11-08 17:32, Jeffrey Carter wrote:

> I have appended the code to this message. Watch for line wrapping.

I must be missing something. On my Windows 7, 64 bit system (dual core
with hyperthreads), using GNAT GPL 2010 I get this:

raised STORAGE_ERROR : EXCEPTION_STACK_OVERFLOW

I'm not quite sure what this means to me.

Peter

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/08/2010 06:50 PM, Anh Vo wrote:
>
> Below are the test results conducted on GNAT 2010 running on Windows
> XP.
>
> Num processors 2
>   1  0.077000009
>   2  0.055627741
>   3  0.023719495
>   4  0.018366580
>   5  0.018512129

Interesting. Perhaps it's something to do with the GNAT version.

> As Robert suggested, I would divide work among tasks by passing
> paramter into each task. For example, in case of two tasks, one task
> handles from rows 1 .. 250 while the other task handle from rows
> 251 .. 500. By the way, the protected singleton type Control is no
> longer needed.

As I said in my initial msg, I did that and got the expected results. It was 
that this version gave different results that bothered me.

Note also that you didn't have to scroll down through irrelevant parts of 3 msgs 
to read my reply.

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

Re: GNAT's Protected Objects

[Egil Høvik]

On Nov 8, 11:43 pm, Robert A Duff <bobd...@shell01.TheWorld.com>
wrote:
> By the way, I don't see the point of the Create_Tasks block.
> Seems like it's not needed.

In this case, it is, if you want Result to return something
meaningful.

--
~egilhh

Re: GNAT's Protected Objects

[Egil Høvik]

On Nov 8, 11:32 pm, Jeffrey Carter
<spam.jrcarter....@spam.not.acm.org> wrote:
>
>        Result : Matrix;

Result is shared between multiple tasks,
reduce references to a minimum by using a
temporary value:

>
>        task body Calc_One is
>           Row : Natural;
>           Col : Natural;

            Temp_Result : Float;

>        begin -- Calc_One
>           All_Results : loop
>              Control.Get (Row => Row, Col => Col);
>
>              exit All_Results when Row = 0;
>

               Temp_Result := 0.0;

>
>              Sum : for K in Index_Value loop

                 Temp_Result := Temp_Result + Left (Row, K) * Right(K,
Col);

>              end loop Sum;

               Result(Row, Col) := Temp_Result ;

>           end loop All_Results;
>        exception -- Calc_One
>        when E : others =>
>           Ada.Text_IO.Put_Line (Item => "Calc_One " &
> Ada.Exceptions.Exception_Information (E) );
>        end Calc_One;


This should give you a nice speedup :)


--
~egilhh

Re: GNAT's Protected Objects

[Maciej Sobczak]

On 8 Lis, 21:34, Jeffrey Carter <spam.jrcarter....@spam.not.acm.org>
wrote:

> If I use a Linda-like approach, with a protected procedure doling out (Row,
> Column) pairs on demand, a single task is always fastest, and using multiple
> tasks slows things down. This wasn't what I expected, and wondered if this is
> inherent in such an approach, or specific to GNAT's way of implementing
> protected objects.

The protected object is shared between tasks and this sharing forces
the cache to flush and synchronize between cores (or CPUs). Note that
cache operates on entire blocks, which adds to the cost of data
transfer. If you measure the CPU utilization, you will probably see
that it is mostly idle during this test. Adding more CPUs will only
make things worse.

In other words, you have hoped for increased performance thanks to
additional computing resources, but you lost more on communication
between them.

The first version scales better, because it shares less (less often).

--
Maciej Sobczak * http://www.inspirel.com

Re: GNAT's Protected Objects

[Julian Leyh]

On 9 Nov., 11:18, Egil Høvik <egilho...@hotmail.com> wrote:
> This should give you a nice speedup :)

It does speed up for me (4 cores):

./mp_mult_po
Num processors 4
 1  2.932879000
 2  1.766932000
 3  1.709863000
 4  1.644133000
 5  1.640042000
 6  1.638109000
 7  1.654792000
 8  1.649010000
 9  1.668256000

./mp_mult_po_temp
Num processors 4
 1  1.872175000
 2  1.012354000
 3  0.756265000
 4  0.604188000
 5  0.665729000
 6  0.673635000
 7  0.697494000
 8  0.571397000
 9  0.689898000

Re: GNAT's Protected Objects

[Robert A Duff]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> On 11/08/2010 03:43 PM, Robert A Duff wrote:
>>
>> By the way, I don't see the point of the Create_Tasks block.
>> Seems like it's not needed.
>
> I guess not, since the function won't return until the tasks
> complete. It's a general construct I use to wait for a group of tasks to
> complete before doing something else.

No, as Egil H�vik pointed out, I was wrong, because
the return expression will be evaluated before
awaiting dependent tasks.  Your code was right in
the first place!

He also made a good suggestion about cache (false sharing).

- Bob

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/09/2010 03:18 AM, Egil H�vik wrote:
> On Nov 8, 11:32 pm, Jeffrey Carter
> <spam.jrcarter....@spam.not.acm.org>  wrote:
>>
>>         Result : Matrix;
>
> Result is shared between multiple tasks,
> reduce references to a minimum by using a
> temporary value:
>
> This should give you a nice speedup :)

Interesting. That does help, presumably by reducing cache misses. I'm not sure 
how relevant that is for my purposes, which were to determine the optimal number 
of tasks, not obtaining the minimum running time.

The version with the PO now shows a speedup, but is still slower than the 
version without. No surprise there.

-- 
Jeff Carter
"I was in love with a beautiful blonde once, dear.
She drove me to drink. That's the one thing I'm
indebted to her for."
Never Give a Sucker an Even Break
109

Re: GNAT's Protected Objects

[Jeffrey Carter]

On 11/09/2010 07:21 AM, Robert A Duff wrote:
>
> No, as Egil H�vik pointed out, I was wrong, because
> the return expression will be evaluated before
> awaiting dependent tasks.  Your code was right in
> the first place!

I'll have to remember that.

-- 
Jeff Carter
"I was in love with a beautiful blonde once, dear.
She drove me to drink. That's the one thing I'm
indebted to her for."
Never Give a Sucker an Even Break
109

Re: GNAT's Protected Objects

[Brad Moore]

On 08/11/2010 1:34 PM, Jeffrey Carter wrote:
> I was trying to decide the "optimal" number of tasks for concurrent
> problems on my 2-core system, so I wrote a little program to do matrix
> multiplication with multiple tasks.
>

In my paper that was presented at the recent 2010 SigAda conference 
(Parallelism Generics for Ada 2005 and Beyond) a few weeks
ago, I describe an algorithm for determining the optimal number of tasks
for iterative parallelism.

The algorithm is;

if iterations count is significant relative to the processor count then
    if iteration count >= processor count then
       select worker count that is the smallest factor of the iteration
         count that is >= the number of processors
    else
       use Iteration count
    end if
else
    use processor count
end if

Incidentally, your code compiled on my system, an ASUS notebook running 
on Windows on a dual core atom processor, and 4 threads, using index 
ranges of 1 .. 250, instead of 1 .. 500 (to prevent Storage_Error 
exceptions being raised) produced the following output.

Num processors 4
  1  7.216035603
  2  5.227005507
  3  4.427877415
  4  3.636320293
  5  3.638031600
  6  3.560718135
  7  3.623521965
  8  3.482307103
  9  3.442896474
  10  3.512802807

After applying my parallel generics to the code, this resulted in the 
following output;

Num processors 4
  1  3.490789402
  2  1.307300640
  3  1.072091225
  4  0.888874454
  5  1.009769300
  6  0.977095744
  7  0.921706085
  8  0.966491909
  9  0.910645945
  10  0.961553821

...
with Parallel.Iterate;

procedure MP_Mult_PO_Generic
is
    subtype Index_Value is Integer range 1 .. 250;

    procedure Matrix_Iterate is new Parallel.Iterate
      (Iteration_Index_Type => Index_Value);

    type Matrix is array (Index_Value, Index_Value) of Float;

    function Mult
      (Left : Matrix; Right : Matrix;
       Num_Tasks : Parallel.Worker_Count_Type) return Matrix
    --  Perform a concurrent multiplication of Left * Right
    --  using Num_Tasks tasks
    is
       Result : Matrix;

       procedure Matrix_Multiply
         (Start, Finish : Index_Value) is
          Temp_Result : Float;
       begin

          for Row in Start .. Finish loop
             for Col in Index_Value loop
                Temp_Result := 0.0;
                for K in Index_Value loop
                   Temp_Result :=
                     Temp_Result + Left (Row, K) * Right (K, Col);
                end loop;
                Result (Row, Col) := Temp_Result;
             end loop;
          end loop;
       end Matrix_Multiply;
    begin  --  Mult
       Matrix_Iterate
         (Worker_Count => Num_Tasks,
          Process => Matrix_Multiply'Access);
       return Result;
    end Mult;
...

The generics allow the code to be written more closely to the
sequential form. The worker tasks are hidden in the generic.

Brad Moore