* GNAT's Protected Objects
@ 2010-11-08 20:34 Jeffrey Carter
2010-11-08 21:38 ` Anh Vo
` (3 more replies)
0 siblings, 4 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-08 20:34 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 20:34 GNAT's Protected Objects Jeffrey Carter
@ 2010-11-08 21:38 ` Anh Vo
2010-11-08 22:32 ` Jeffrey Carter
[not found] ` <s5GdnRvDRfR6-0XRnZ2dnUVZ_hOdnZ2d@earthlink.com>
` (2 subsequent siblings)
3 siblings, 1 reply; 17+ messages in thread
From: Anh Vo @ 2010-11-08 21:38 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 21:38 ` Anh Vo
@ 2010-11-08 22:32 ` Jeffrey Carter
2010-11-08 22:43 ` Robert A Duff
` (3 more replies)
0 siblings, 4 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-08 22:32 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
[not found] ` <s5GdnRvDRfR6-0XRnZ2dnUVZ_hOdnZ2d@earthlink.com>
@ 2010-11-08 22:41 ` Jeffrey Carter
0 siblings, 0 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-08 22:41 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:32 ` Jeffrey Carter
@ 2010-11-08 22:43 ` Robert A Duff
2010-11-09 0:27 ` Jeffrey Carter
2010-11-09 10:05 ` Egil Høvik
2010-11-09 1:50 ` Anh Vo
` (2 subsequent siblings)
3 siblings, 2 replies; 17+ messages in thread
From: Robert A Duff @ 2010-11-08 22:43 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:43 ` Robert A Duff
@ 2010-11-09 0:27 ` Jeffrey Carter
2010-11-09 14:21 ` Robert A Duff
2010-11-09 10:05 ` Egil Høvik
1 sibling, 1 reply; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-09 0:27 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:32 ` Jeffrey Carter
2010-11-08 22:43 ` Robert A Duff
@ 2010-11-09 1:50 ` Anh Vo
2010-11-09 3:14 ` Jeffrey Carter
2010-11-09 2:03 ` Peter C. Chapin
2010-11-09 10:18 ` Egil Høvik
3 siblings, 1 reply; 17+ messages in thread
From: Anh Vo @ 2010-11-09 1:50 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:32 ` Jeffrey Carter
2010-11-08 22:43 ` Robert A Duff
2010-11-09 1:50 ` Anh Vo
@ 2010-11-09 2:03 ` Peter C. Chapin
2010-11-09 10:18 ` Egil Høvik
3 siblings, 0 replies; 17+ messages in thread
From: Peter C. Chapin @ 2010-11-09 2:03 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-09 1:50 ` Anh Vo
@ 2010-11-09 3:14 ` Jeffrey Carter
0 siblings, 0 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-09 3:14 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:43 ` Robert A Duff
2010-11-09 0:27 ` Jeffrey Carter
@ 2010-11-09 10:05 ` Egil Høvik
1 sibling, 0 replies; 17+ messages in thread
From: Egil Høvik @ 2010-11-09 10:05 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 22:32 ` Jeffrey Carter
` (2 preceding siblings ...)
2010-11-09 2:03 ` Peter C. Chapin
@ 2010-11-09 10:18 ` Egil Høvik
2010-11-09 11:17 ` Julian Leyh
2010-11-09 18:22 ` Jeffrey Carter
3 siblings, 2 replies; 17+ messages in thread
From: Egil Høvik @ 2010-11-09 10:18 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 20:34 GNAT's Protected Objects Jeffrey Carter
2010-11-08 21:38 ` Anh Vo
[not found] ` <s5GdnRvDRfR6-0XRnZ2dnUVZ_hOdnZ2d@earthlink.com>
@ 2010-11-09 10:36 ` Maciej Sobczak
2010-11-24 7:08 ` Brad Moore
3 siblings, 0 replies; 17+ messages in thread
From: Maciej Sobczak @ 2010-11-09 10:36 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-09 10:18 ` Egil Høvik
@ 2010-11-09 11:17 ` Julian Leyh
2010-11-09 18:22 ` Jeffrey Carter
1 sibling, 0 replies; 17+ messages in thread
From: Julian Leyh @ 2010-11-09 11:17 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-09 0:27 ` Jeffrey Carter
@ 2010-11-09 14:21 ` Robert A Duff
2010-11-09 18:23 ` Jeffrey Carter
0 siblings, 1 reply; 17+ messages in thread
From: Robert A Duff @ 2010-11-09 14:21 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-09 10:18 ` Egil Høvik
2010-11-09 11:17 ` Julian Leyh
@ 2010-11-09 18:22 ` Jeffrey Carter
1 sibling, 0 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-09 18:22 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-09 14:21 ` Robert A Duff
@ 2010-11-09 18:23 ` Jeffrey Carter
0 siblings, 0 replies; 17+ messages in thread
From: Jeffrey Carter @ 2010-11-09 18:23 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: GNAT's Protected Objects
2010-11-08 20:34 GNAT's Protected Objects Jeffrey Carter
` (2 preceding siblings ...)
2010-11-09 10:36 ` Maciej Sobczak
@ 2010-11-24 7:08 ` Brad Moore
3 siblings, 0 replies; 17+ messages in thread
From: Brad Moore @ 2010-11-24 7:08 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2010-11-24 7:08 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-11-08 20:34 GNAT's Protected Objects Jeffrey Carter
2010-11-08 21:38 ` Anh Vo
2010-11-08 22:32 ` Jeffrey Carter
2010-11-08 22:43 ` Robert A Duff
2010-11-09 0:27 ` Jeffrey Carter
2010-11-09 14:21 ` Robert A Duff
2010-11-09 18:23 ` Jeffrey Carter
2010-11-09 10:05 ` Egil Høvik
2010-11-09 1:50 ` Anh Vo
2010-11-09 3:14 ` Jeffrey Carter
2010-11-09 2:03 ` Peter C. Chapin
2010-11-09 10:18 ` Egil Høvik
2010-11-09 11:17 ` Julian Leyh
2010-11-09 18:22 ` Jeffrey Carter
[not found] ` <s5GdnRvDRfR6-0XRnZ2dnUVZ_hOdnZ2d@earthlink.com>
2010-11-08 22:41 ` Jeffrey Carter
2010-11-09 10:36 ` Maciej Sobczak
2010-11-24 7:08 ` Brad Moore
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox