hama-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Martella <claudio.marte...@tis.bz.it>
Subject Re: Pregel article
Date Fri, 02 Jul 2010 16:08:12 GMT
I'll try to make things clear.

The end of a superstep is obtained by the un-activation of all the
vertices. In pregel the superstep is over when all the vertices call
VoteToHalt() (in hama it's done by the sync() method). This happens at
the end of each computation by each vertex. Each vertex is activated by
the arrival of a message directed to that vertex. This means that each
superstep computation is atomic and it should be considered in the
design of the algorithm. That's a change of paradigm and that's what
pregel author's call the "vertex's perspective programming".

So no, there's no assumption about all the vertices to be active at the
beginning of each superstep.

About Felix's argument: yes, fewer supersteps mean less communication
and synchronization overhead. At the same time, having longer supersteps
will mean that it's more probable that certain vertices end their
computation earlier than others, making them idle for a long time
(waiting for the others to finish), and loosing computational time. So
ideally it should be a good balance between long computational
supersteps (decreasing communication overhead) and short computational
supersteps (decreasing idle time).
This is an intrinsical problem of BSP models because of the barrier. On
the contrary DataFlow models don't have barriers and each computation is
more independent, therefore more similar to the model you have in mind.

Hope this helps.

I attach the text from my blog post (roughly obtained with html2text) as
requested.

Cheers,

Claudio


zercal wrote:
> The paper I found about pregel are not very detailed, 
> is it "http://portal.acm.org/citation.cfm?id=1582716.1582723"?
> I guess, in this paper, vertices are assumed to be all actived at every superstep. simply
random
> access will reduce some communication cost but take more superstep.
> However, is there any way of vertice selection method can be performed
> that at every super step, each vertex knows whether to active according to 
> information it kept and received from other vertex? 
> But I can't found more detail from that paper...
> Becides, I can not access your blogs. Would you please send me your article?
>
> Thank you very much!
> from Xiong Chenyan
>
> ÔÚ2010-07-02 20:04:40£¬"Felix Halim" <felix.halim@gmail.com> дµÀ£º
>   
>> Exactly how to activate a particular vertex is not clear from the
>> paper (is it random access?) and this feature is probably not as good
>> as it sounds for complex graph algorithms. It might be better off to
>> assume all vertices are active (to reduce the overhead of the flag
>> needed and the space to make it randomly accessible, by storing it in
>> blocks or whatever).
>>
>> Here is my argument:
>>
>> The way Pregel (and existing MR) works is iterative, where each
>> iteration is separated by a super-step barrier where all messages have
>> to arrive. Algorithms that have fewer super-steps are preferable than
>> those that have large number of super-steps. In fact, we should
>> measure Algorithms in terms of the number of super-steps required. To
>> minimize the number of super-steps, likely we need to activate as much
>> vertices as possible to do all the work in current super-step, rather
>> than spill-over to the next super-step. In this case, the feature to
>> "turn off" vertices is useless, since most of the time all vertices
>> will be active to effectively reduce the number of super-steps.
>>
>> Unfortunately, I don't have experiments to backup my argument... I
>> don't have Pregel...
>>
>> Felix Halim
>>
>>
>> On Fri, Jul 2, 2010 at 7:37 PM, Claudio Martella
>> <claudio.martella@tis.bz.it> wrote:
>>     
>>> I did too. See:
>>>
>>> http://blog.acaro.org/entry/pregel-is-out-but-what-is-pregel
>>>
>>>
>>> Felix Halim wrote:
>>>       
>>>> I have. See my comment in this blog:
>>>>
>>>> http://blog.udanax.org/2010/06/summary-of-google-pregel.html
>>>>
>>>> Felix Halim
>>>>
>>>>
>>>> On Tue, Jun 8, 2010 at 4:00 AM, Mark Kerzner <markkerzner@gmail.com>
wrote:
>>>>
>>>>         
>>>>> Hi,
>>>>>
>>>>> anybody has read it?
>>>>>
>>>>> Thank you,
>>>>> Mark
>>>>>
>>>>>
>>>>>           
>>>>         
>>> --
>>> Claudio Martella
>>> Digital Technologies
>>> Unit Research & Development - Analyst
>>>
>>> TIS innovation park
>>> Via Siemens 19 | Siemensstr. 19
>>> 39100 Bolzano | 39100 Bozen
>>> Tel. +39 0471 068 123
>>> Fax  +39 0471 068 129
>>> claudio.martella@tis.bz.it http://www.tis.bz.it
>>>
>>> Short information regarding use of personal data. According to Section 13 of
Italian Legislative Decree no. 196 of 30 June 2003, we inform you that we process your personal
data in order to fulfil contractual and fiscal obligations and also to send you information
regarding our services and events. Your personal data are processed with and without electronic
means and by respecting data subjects' rights, fundamental freedoms and dignity, particularly
with regard to confidentiality, personal identity and the right to personal data protection.
At any time and without formalities you can write an e-mail to privacy@tis.bz.it in order
to object the processing of your personal data for the purpose of sending advertising materials
and also to exercise the right to access personal data and other rights referred to in Section
7 of Decree 196/2003. The data controller is TIS Techno Innovation Alto Adige, Siemens Street
n. 19, Bolzano. You can find the complete information on the web site www.tis.bz.it.
>>>
>>>
>>>
>>>       


-- 
Claudio Martella
Digital Technologies
Unit Research & Development - Analyst

TIS innovation park
Via Siemens 19 | Siemensstr. 19
39100 Bolzano | 39100 Bozen
Tel. +39 0471 068 123
Fax  +39 0471 068 129
claudio.martella@tis.bz.it http://www.tis.bz.it

Short information regarding use of personal data. According to Section 13 of Italian Legislative
Decree no. 196 of 30 June 2003, we inform you that we process your personal data in order
to fulfil contractual and fiscal obligations and also to send you information regarding our
services and events. Your personal data are processed with and without electronic means and
by respecting data subjects' rights, fundamental freedoms and dignity, particularly with regard
to confidentiality, personal identity and the right to personal data protection. At any time
and without formalities you can write an e-mail to privacy@tis.bz.it in order to object the
processing of your personal data for the purpose of sending advertising materials and also
to exercise the right to access personal data and other rights referred to in Section 7 of
Decree 196/2003. The data controller is TIS Techno Innovation Alto Adige, Siemens Street n.
19, Bolzano. You can find the complete information on the web site www.tis.bz.it.


Mime
View raw message