If the cost is at each level, you are right. Maybe this is the exact answer. But I am still not clear how to implement it. Could anyone provide a more detailed description?
2008/3/28 Niranjan Balasubramanian <[EMAIL PROTECTED]>: > 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 > >>>> > >>>> > >>>> > >> > >> > >
