run page rank with asynchronous execution engine

User 158 | 3/26/2014, 12:34:01 PM

Hello,

As the paper says, page rank can run faster with the asynchronous execution. I tried it, and found it ran faster with the synchronous execution. I'm just wondering if I did something wrong. ./pagerank --graph graphfile --format tsv --engine asynchronous For my graph (100M vertices and 2B edges), the synchronous execution took around 600 seconds and the asynchronous execution took around 900 seconds. I don't know if I should use a special scheduler, so I tried the priority scheduler with the asynchronous execution. It took hours and still couldn't terminate.

I guess my question is how to run page rank in order to get its maximal performance? I think the same question also goes to the implementation of weakly connected components. It doesn't converge very fast with the default setting. BTW, I ran the page rank on a single machine.

Thanks, Da

Comments

User 20 | 3/26/2014, 5:36:36 PM

Hi,

The Asynchronous Engine is fickle and difficult to tune, and can be highly graph dependent in practice. The reason is that: - while Asynchronous is pretty much guaranteed to converge faster in terms of total computation (if you see your outputs, async execution while taking longer should require much fewer updates) - Synchronous execution is substantially easier to implement and optimize

As a result we get this two conflicting forces: the async algorithm has faster convergence rates, but the implementation is harder to optimize and is thus slower.

The result is that you get something which sometimes converges faster, and sometimes not.

Furthermore, our regular synchronous execution is not purely "synchronous" either. It is strictly speaking, synchronous + adaptive: i.e. it will skip computation on vertices that have converged (you will see that later iterations run faster than earlier iterations)


User 158 | 3/26/2014, 6:23:42 PM

Hello,

Let's see if I understand the difference of the synchronous engine and the asynchronous engine correctly.

The synchronous engine maintains two copies of all data associated to vertices and edges. During the iteration, vertices can only access the data from the previous iteration and the engine swap the two copies of data at the end of iteration.

The asynchronous engine only needs to maintain one copy of data. All updates during the iteration write to the data immediately. In the asynchronous mode, there are no iterations. All activated vertices are added back to the queue immediately and waiting for execution.

Is it correct?

I also have some questions related to the scheduler: Does the scheduler work for both the synchronous engine and the asynchronous engine? What property is the scheduler based on for scheduling? For example, can I schedule the vertices so that I can process the vertices with the largest degree first?

Thanks, Da