The cost is f(m,n) at each level in the tree (not at each node).
Thus, you have f(m,n) x the number of levels which gives f(m,n) log (P).
I might be way off here but this is what I guess.
~ Niranjan
On Mar 27, 2008, at 12:08 PM, Hao Zheng wrote:
let it be a tree of depth log(P), then the total communication cost
will be
f(m,n)*(1/2+1/4+1/8+...)*P = f(m,n)*P, but not log(P)
do I see what you mean?
2008/3/27 Niranjan Balasubramanian <[EMAIL PROTECTED]>:
On Mar 26, 2008, at 12:06 AM, Hao Zheng wrote:
it's log(P). I just don't know how log(P) is obtained.
I am doing some guess work here but I think the log (P) factor
arises
out of the combining the data that is passed back from the various
processors. Imagine tree of processors with depth log (P) and at
each
level the communication amounts to some function of n and m, f(m,n),
then the total communication cost would be
f(m,n) log (P).
~ Niranjan
On 3/26/08, Grant Ingersoll <[EMAIL PROTECTED]> wrote:
On Mar 25, 2008, at 4:11 PM, Isabel Drost wrote:
2. Sect. 4.1, too.
"reduce phase can minimize communication by combining data as
it's
passed back; this accounts for the logP factor", Could you
help me
figure out how logP is calculated.
Anyone else who can help out here?
Isn't this just log(P) where P is the number of cores? The
version of
the paper I have says log(P) not logP, so maybe there is a typo?
From earlier in 4.1:
"We assume that the dimension of the inputs is n (i.e., x
∈R
n
), that we have m
training examples, and that there are P cores"
-Grant
