[Networkit] NetworkIt and Xeon Phi

Wang, Zhijie ZHW47 at pitt.edu
Sat Mar 12 00:49:17 CET 2016


I am aware the work by Dennis is on graph generation. Just curious if the additional core with OpenMP support is going to faster.

Currently running the approx with default parameters.
The professor is from business school with little technical knowledge. She requested to calculate the betweeness centrality, so that is my work.  I already know the graph is highly centralized on 50 some nodes. (the graph was converted from a social network graph by pulling 40 brands followers' id). Desired accuracy level is low, so any suggested epsilon level or sample size?

Thank you,

Bill Wang

From: networkit-bounces at ira.uni-karlsruhe.de <networkit-bounces at ira.uni-karlsruhe.de> on behalf of Christian Staudt <christian.staudt at kit.edu>
Sent: Friday, March 11, 2016 5:26 PM
To: NetworKit: a toolkit for high-performance network analysis
Subject: Re: [Networkit] NetworkIt and Xeon Phi

Hi Bill

Then networkit, using ApproxBetweenness. -- still running on my workstation, 4 days already

Which parameters did you use? Do we agree that calculating exact betweenness for 5 million nodes is impractical, no matter if with or without Xeon Phi? For ApproxBetweenness, the running time depends on the desired accuracy via the number of searches performed. (Also check out ApproxBetweenness2 which gives more intuitive control over the number of searches.) A handful of searches should take minutes, more searches will take you hours, days, weeks, and so on. Which brings us to the next question: Why do you want to calculate betweenness? Clarify how much accuracy you need, especially before you turn lots of electricity into hot air using supercomputer time. Yes, that is a tricky conceptual problem, but my guess is that doing just tens of searches lets you effectively discriminate between high- and low-betweenness nodes, which should be enough for many applications, and should be doable on your workstation.


On 11 Mar 2016, at 22:27, Wang, Zhijie <ZHW47 at pitt.edu<mailto:ZHW47 at pitt.edu>> wrote:

Hi all,

I am very new to NetworkIt.

I am working as a research assistant for a professor at Katz Graduate School of Business. She is interested in calculating the centrality of a graph ( 5 million nodes). For previous network related calculation, using python Networkx, my workstation is able to handle in a reasonable time. However, the betweeness centrality is too much for it.

Workstation: 32GB RAM, i7-4790k (quad core)

So I first tried to use Networkx, failed -- too slow
Then networkit, using ApproxBetweenness. -- still running on my workstation, 4 days already

I actually happen to have access a Xeon Phi 5110p (a CS professor) and I saw a paper "Parallel Graph Algorithms on the Xeon Phi Coprocessor<http://felsin9.de/nnis/phi/thesis/thesis.pdf>" by Dennis Felsing.

Will using a Xeon Phi improve performance of centrality calculation? And what are the necessary steps I need to perform? (Explicit Offload? Automatic Offload?)
My workstation supports 64 bit bar decoding, so Xeon Phi is compatible.

Also, requesting an allocation on Pittsburgh Super Computer is an option.

Due to certain requirements and future maintainability of this code base, I prefer not to write a hardware specific optimized C/C++ code.

Any suggestion is appreciated.

Thank you,
Bill Wang
NetworKit mailing list
NetworKit at ira.uni-karlsruhe.de<mailto:NetworKit at ira.uni-karlsruhe.de>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160311/0fb3ce85/attachment.html>

More information about the NetworKit mailing list