giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Eli Reisman (JIRA)" <>
Subject [jira] [Updated] (GIRAPH-314) Implement better message grouping to improve performance in SimpleTriangleClosingVertex
Date Tue, 04 Sep 2012 20:14:07 GMT


Eli Reisman updated GIRAPH-314:

    Attachment: GIRAPH-314-2.patch

This patch represents a blatant tradeoff of compute time for space (in the form of memory,
networking resources/buffers etc.)

It adds a user-configurable option that allows you to amortize the overwhelming load of degree(V)^2
messages in a triangle closing operation over as many super steps as you can stomach, which
in practice has turned out to be surprisingly effective, and still reasonably quick given
there is little work for most vertices to do in such super steps when only 1/N of them on
any given superstep will do any sending, and many will similarly not receive anything.

This has been tested on the cluster (even under surprisingly high load) and passes mvn verify

It will be part of a 2-pronged strategy to get triangle closing to work at a useful scale,
the other half of which will be posted in a separate JIRA. But this part is good to go.

> Implement better message grouping to improve performance in SimpleTriangleClosingVertex
> ---------------------------------------------------------------------------------------
>                 Key: GIRAPH-314
>                 URL:
>             Project: Giraph
>          Issue Type: Improvement
>          Components: examples
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Trivial
>             Fix For: 0.2.0
>         Attachments: GIRAPH-314-1.patch, GIRAPH-314-2.patch
> After running SimpleTriangleClosingVertex at scale I'm thinking the sendMessageToAllEdges()
is pretty in the code, but its not a good idea in practice since each vertex V sends degree(V)^2
messages right in the first superset in this algorithm. Could do something with a combiner
etc. but just grouping messages by hand at the application level by using IntArrayListWritable
again does the trick fine.
> Probably should have just done it this way before, but sendMessageToAllEdges() looked
so nice. Sigh. Changed unit tests to reflect this new approach, passes mvn verify and cluster,

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see:

View raw message