* 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 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-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 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 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 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-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: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-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-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 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
[parent not found: <s5GdnRvDRfR6-0XRnZ2dnUVZ_hOdnZ2d@earthlink.com>]
* 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 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-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