Don Dailey wrote:
Here is an important snippet, but proofs follow in the paper:
The critical path length C is the time it would take for the program
to run on an infinite-processor machine with no scheduling overheads.
Note that it doesn't mention anything about useful WORK, because this is
W in their paper:
The work W is the number of processor cycles spent doing useful work. W
does not include cycles spent idle when there is not enough work to keep
all the processors busy.
Further:
The ratio Ts/W is the efficiency of the parallel program, and indicates
how much overhead is inherent in the parallel algorithm.
The paper goes on with an analysis of how much parallelism exists in
perfectly ordered trees, a stupid analysis if it's always 100% as
you believe.
No, no, no, and no, I never said this. In fact I denied it. We were
talking about work, not parallelism. Don't try to weasel out on me in
the face of certain defeat, the archives are my proof:
===Don Dailey=======================================================
Here is my assertion (which I admit needs to be checked):
Given perfect move ordering, but not a-priori knowledge of this, a
parallel program will search more nodes on average than a serial
program. And more processors will "waste" more work in this sense.
That's my definition of "wasted work."
====================================================================
This is clearly "efficiency" in the paper per the above definitions.
Now, what does the paper say about it?
====================================================================
Theorem 1
For uniform best ordered trees of degree d and height h,
the efficiency is 1
====================================================================
I rest my case.
--
GCP
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
