Re: Parallel FIB

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: Parallel FIB
Date	2013-05-04 13:45 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2013May4.154530@mips.complang.tuwien.ac.at> (permalink)
References	<2013May3.142604@mips.complang.tuwien.ac.at> <19891400988434@frunobulax.edu>

Show all headers | View raw

mhx@iae.nl (Marcel Hendrix) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Parallel FIB
>
>> mhx@iae.nl (Marcel Hendrix) writes:
>>>In the context of a benchmark the actual speed of solving the problem 
>>>doesn't matter.
>
>> That's debatable.
>
>Please debate, then :-)

It's easy to produce a "benchmark" that does nothing, slowly, an
parallelizes well.  But what does it show?  Does it show that we can
usefully parallelize the solutions to interesting problems?  No.  So,
what does it show?

If you want to parallelize stuff with a structure similar to the
doubly-recursive Fibonacci benchmark, use mergesort or quicksort as
benchmark.

>> Actually my suggestion (based on your earlier version) is:
>
>> : pfib ( n1 -- n2 )
>>	TO n  n 6 < IF  n fib EXIT  ENDIF
>>	fibs OFF
>>	PAR
>>	  STARTP  n 4 - fib 3 * 
>>	          n 5 - fib 5 * + fibs LOCKED+! DROP  ENDP
>>	  STARTP  n 6 - fib 2*    fibs LOCKED+! DROP  ENDP
>>	ENDPAR
>>	fibs @ ;
>
>You want to swap n 4- with n 6 -

Yes.

>> For getting more cores to work, let's just start with the unoptimized
>> fib and parallelize the recursions:
>
>> : pfib1 ( n1 -- )
>>    dup 2 < if
>>	drop 1 fibs locked+! drop
>>    else {: n :}
>>	PAR
>>         STARTP n 1- recurse ENDP
>>	  STARTP n 2- recurse ENDP
>>        ENDPAR
>>    endif ;
>
>> : pfib ( n1 -- n2 )
>>  0 fibs ! pfib1 fibs @ ;
>
>I am not sure I understand this. We have only 4 (or 6) 
>cores, so this is just a test of how long it takes to queue 
>and dequeue tasks. As every recursive call needs a thread,
>this will be horrendously slow. That's not what I want
>to test.

That's why I then refined it to produce only a few dozen tasks each of
which runs so long that the threading overhead should become
negligible.  And that version should scale up to a dozen or so cores,
and if you want more (or less), you just need to change one parameter.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-02 01:20 +0200
  Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-02 14:13 +0000
    Re: Parallel FIB Paul Rubin <no.email@nospam.invalid> - 2013-05-02 08:25 -0700
    Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 07:04 +0200
      Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-03 12:26 +0000
        Re: Parallel FIB Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-03 15:23 +0200
          Re: Parallel FIB fred <email@address.com> - 2013-05-03 16:56 +0100
          Re: Parallel FIB Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-03 18:13 +0200
        Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 21:14 +0200
          Re: Parallel FIB anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-04 13:45 +0000
        Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 21:29 +0200
          Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-03 23:53 +0200
            Re: Parallel FIB Paul Rubin <no.email@nospam.invalid> - 2013-05-03 18:10 -0700
              Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-04 07:07 +0200
                Re: Parallel FIB mhx@iae.nl (Marcel Hendrix) - 2013-05-06 21:09 +0200
        Re: Parallel FIB albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-05-04 00:26 +0000

csiph-web