I was able to construct a non-recursive implementation of the Ackermann function.
Impressive work!
Maybe you'll have better luck with that.
I couldn't see much opportunity for parallisation in your first version.
Update: Cleaned up code a bit.
That's certainly easier to follow. (*)
The 'obvious' thing would be to async the inner for loop. Except that with maximum realistic values of m being 5, starting a thread for 5 iterations is nonsense.
So then my attention moves to the outer loop, with the thought that you can often split the range of a loop into subranges and run them in parallel.
But, firstly we don't know the range. Secondly, even iteratively, the dependency of each subsequent iteration upon the previous would require lock-stepping the threading--either through complex locking or queuing--and with the minimal effort required for each step of each iteration versus the cost of locking and context switching, again make that a non-starter.
Upshot: I think you called it earlier with your z = F(x); return F(z); comment that went over my head at the time. In the light of that, I've modified my first tentative rule from a post above to be:
For a recursive algorithm--that is not tail recursive--to be a suitable candidate for parallelisation, it requires that it has multiple, independant, recursive calls at each level.
The interesting thing now is: how many recursive algorithms fit that pattern?
m < 4 can be special-cased. Known formula exist for A(0,n), A(1,n), A(2,n) and A(3,n).
Indeed. The following returns all the tractable cases within the machine capability in a blink of an eye:
sub ackermann_c {
use constant INF => exp(~0 >> 1);
my( $m, $n ) = @_;
--$m, $n=1 if $n == 0;
return $n + 1 if $m == 0;
return $n + 2 if $m == 1;
return 2*( $n+3)-3 if $m == 2;
return 2**($n+3)-3 if $m == 3;
return INF unless $m == 4;
my( $p, $r ) = ( $n+3, 2 );
$r = 2**$r while --$p;
return $r - 3;
}
But that now means I need to find a more suitable testcase for my experiments.
An in-place, parallised qsort maybe?
(*)Though wonder why you do a loop initialisation rather than my @n = (-1 ) x $m; my @A = ( 1 ) x $m; given that m will realistically max out at 5. And whilst I'm on unimportant, purely subjective matters, why for(;;) not while( 1 )?
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
|