Author: Robert Hyatt
Date: 11:03:13 10/04/01
Go up one level in this thread
On October 04, 2001 at 12:40:53, J. Wesley Cleveland wrote: >Take an iterative function F(a), i.e. F1(a) = a, F2(a) = F(a), F3(a) = F(F(a)), >... Assume the function is complicated enough to use all the available registers >on your machine and requires the same number of machine cycles for each >iteration. Now find the first iteration for which F(b) > F(a). A serial >implementation will spend a significant amount of time saving and restoring >state as it goes between the two functions, while the two processor solution >will only have to spend a minimal amount of time syncronizing at the end of each >iteration (due to my second condition). Explain how you are going to do a recursive function (I assume you mean recursive and not iterative above due to the way you defined the thing) in a parallel manner. It would be impossible to calculate f2(a) until you have successfully calculated f1(1). That is a purely sequential algorithm that has no parallel solution at all. Any more than you can parallelize the following loop: a[0]=127; for (i=1;i<n;i++) a[i]=a[i-1]*f(i); because you can't compute a[i] for any i until a[i-1] has been calculated. This is a classic order dependency. I don't see how you could parallelize your function for that same reason, unless I misunderstood what you are asking. Also, if you run out of registers on any machine, you have a minor problem. But if you run out on a serial algorithm, you will also run out on a parallel algorithm. Since they are written the same way at that level...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.