Re: Parallel FIB

From	mhx@iae.nl (Marcel Hendrix)
Subject	Re: Parallel FIB
Newsgroups	comp.lang.forth
Message-ID	<90969699988434@frunobulax.edu> (permalink)
Date	2013-05-04 07:07 +0200
References	<7xwqrfbldj.fsf@ruckus.brouhaha.com>
Organization	Wanadoo

Show all headers | View raw

Paul Rubin <no.email@nospam.invalid> writes Re: Parallel FIB

> mhx@iae.nl (Marcel Hendrix) writes:
>> A webpage on Erlang suggested to start a PAR from a PAR.
>> The result is quite incredible, I really didn't expect 
>> to get a factor of 12 speedup. But it appears it is possible
>> to use all cores after all.

> What Erlang page was that?

Trigonakis Vasileios; 
http://trigonakis.com/blog/2011/02/27/parallelizing-simple-algorithms-fibonacci/

>                             Also, what Forth was your test run with?

iForth64. You need the current development version. We are
working on a very efficient threadpool-based PAR ENDPAR 
implementation; that's the reason for the recent postings on 
GCD, PDE, bubble and fib.

> I have access to a big machine (16 cores, 32 threads) and would be
> interested in giving the Erlang version (and maybe the Forth version) a
> try.

I'll send you an iForth pre-release when you're ready for the test.

With 16 cores the tree can be unfolded to at least 3 PAR levels. 
Then fib(47) will not be enough work to time accurately.

BTW, here's the current source. I have gone from 350 ms 
to 57 ms. The next version will use Hanno Schwalm's 
extension that does away with global parameters.

-marcel

-- pfib.frt -----------------
ANEW -pfibs

NEEDS -tps

: fib ( n1 -- n2 )
    DUP 2 < IF
	DROP 1
    ELSE
	DUP  1- RECURSE
	SWAP 2- RECURSE
	+
    ENDIF ;

0 VALUE n
VARIABLE fibs

\ ... f5          f4       f3       f2        f1             F0
\ ... (f6+f7)  (f5+f6)  (f5+f4)  (f4+f3)   (f3+f2)       f2+2f3+f4
\ ...                            (2f4+f5)  (f3+2f4+f5)   f3+4f4+2f5
\ ...                            (3f5+2f6) (3f4+2f5)     8f5+5f6

: sfib ( n1 -- n2 )
	LOCAL n  n 6 < IF  n fib EXIT  ENDIF
	n 5 - fib 8 * 
	n 6 - fib 5 * + ;

: pfib0 ( n1 -- n2 )
	TO n  n 6 < IF  n sfib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 4 - sfib 3 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 5 - sfib 5 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 6 - sfib 2*  fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;

: pfib1 ( n1 -- n2 )
	TO n  n 6 < IF  n sfib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 5 - sfib 8 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 6 - sfib 5 * fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;



-- Nested PAR .. ENDPAR. Works for 4 cores.
VARIABLE fibsa  0 VALUE na
VARIABLE fibsb  0 VALUE nb

: pfib1a ( n1 -- n2 )
	TO na  na 6 < IF  na fib EXIT  ENDIF
	fibsa OFF
	PAR
	  STARTP  na 5 - sfib 8 * fibsa LOCKED+! DROP  ENDP
	  STARTP  na 6 - sfib 5 * fibsa LOCKED+! DROP  ENDP
	ENDPAR
	fibsa @ ;

: pfib1b ( n1 -- n2 )
	TO nb  nb 6 < IF  nb fib EXIT  ENDIF
	fibsb OFF
	PAR
	  STARTP  nb 5 - sfib 8 * fibsb LOCKED+! DROP  ENDP
	  STARTP  nb 6 - sfib 5 * fibsb LOCKED+! DROP  ENDP
	ENDPAR
	fibsb @ ;

: pfib1ab ( n1 -- n2 )
	TO n  n 6 < IF  n sfib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 5 - pfib1a 8 * fibs LOCKED+! DROP  ENDP
	  STARTP  n 6 - pfib1b 5 * fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;



-- Idea by Anton Ertl on CLF
: pfib2 ( n1 -- n2 )
	TO n  n 6 < IF  n fib EXIT  ENDIF
	fibs OFF
	PAR
	  STARTP  n 5 - sfib 5 * 
	          n 6 - sfib 2* + fibs LOCKED+! DROP  ENDP
	  STARTP  n 4 - sfib 3 *  fibs LOCKED+! DROP  ENDP
	ENDPAR
	fibs @ ;

: bench	CR ." \ serial FIB(47)         : " TIMER-RESET #47  fib      U. .ELAPSED 
	CR ." \ new FIB(47)            : " TIMER-RESET #47 sfib      U. .ELAPSED 
	CR ." \ parallel FIB(47) (0)   : " TIMER-RESET #47 pfib0     U. .ELAPSED  
	CR ." \ parallel FIB(47) (1)   : " TIMER-RESET #47 pfib1     U. .ELAPSED  
	CR ." \ parallel FIB(47) (1ab) : " TIMER-RESET #47 pfib1ab   U. .ELAPSED  
	CR ." \ parallel FIB(47) (2)   : " TIMER-RESET #47 pfib2     U. .ELAPSED ; 

\ FORTH> bench
\ serial FIB(47)         : 4807526976 45.325 seconds elapsed.
\ new FIB(47)            : 4807526976 6.569 seconds elapsed.
\ parallel FIB(47) (0)   : 4807526976 1.006 seconds elapsed.
\ parallel FIB(47) (1)   : 4807526976 0.615 seconds elapsed.
\ parallel FIB(47) (1ab) : 4807526976 0.057 seconds elapsed.
\ parallel FIB(47) (2)   : 4807526976 1.023 seconds elapsed. ok

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