Parallel Force Atlas

[pbittner]

Hi everybody!

As mentioned in a previous post, I have been working on a parallel implementation of the Force Atlas layout recently and a first version is ready for release. I published it earlier today and it will hopefully be available quite soon. I attached the plugin NBM if anybody wants to try it now.

The plugin uses a dynamic library written in Fortran and parallelized with OpenMP. Because of that, it is only available on Windows 64bit for now as the library must be recompiled for each platform. The only part of the algorithm that is parallelized is the O(n2) repulsion as it is by far the most costly.

In term of performance, I have done some benchmarking on a recent i7 quad-core laptop and it is more than 50 times faster than the standard Force Atlas layout in some cases. On that machine, one iteration of the layout takes about 30ms with 5,000 nodes, 0.8s with 20,000 nodes and 3s with 50,000 nodes.

For the next version, I'll try to make it available on Linux and Mac. I also plan on implementing a version of the layout with CUDA to make it even faster.

Let me know what you think,
Paul

[admin]

That's amazing! Can't wait to see the ForceAtlas 2 improved!

[PMR3349]

I will definitely be trying this out today. Nice work

[seinecle]

I just tried it on the Power grid.gml (example of a network available on the welcome screen of Gephi): that's ***crazy*** fast.

Thanks a lot!

Clement

[pbittner]

I'm glad that you like it

Over the week-end, I wrote a prototype of Force Atlas using CUDA that is even faster (~10x). On my laptop with a mid-range GPU card, one iteration of the layout is taking 0.1s with 20,000 nodes and 2s with 100,000 nodes. I will include it in the next version of the plugin.

Regarding Force Atlas 2, things are a little more complicated. I have made a parallel version using OpenMP but it is at best 2.5 times faster than the Java implementation. I don't have much hope for a parallel version running on CPUs. However, I found a paper presenting the implementation of the Barnes-Hut method using CUDA and the performance is crazy: they manage to run one iteration of Barnes-Hut with 5,000,000 bodies in about 5s! (using a high-end desktop GPU card)

I'll definitely look into that when I have some time.

[admin]

Even if the performance is increase by 2.5, this would be still a great improvement for the users, and keeping the same quality of layout!

[seinecle]

If I may repeat the obvious and cheer again:

the work you do is very, very important! Good layouts are an essential for dataviz, and unfortunately there are very few if any very fast performing, good quality layouts.

ForceAtlas stands out for the very intuitive interpretation it affords, but so far it was still much too slow past a certain number of nodes. In practice, this means that good visualizations were simply not available for, say, a 100,000 nodes network. Your work is literally exploding this limit, and this opens new horizons for dataviz.

To illustrate, I just compared the layout of a 9,000 nodes + 15,000 edges network with OpenOrd and Parallel Force Atlas. it took me 20 seconds with each algo to get the final result. See snapshots attached. Main differences in favor of Parallel Force Atlas are:

- quality of the dispersal of nodes: communities appear more clearly
- no overlap of nodes
- possibility to modify the parameters for gravity, etc. while the layout is still running. OpenOrd makes one treatment without possibility to intervene while it runs.
- possibility to explain the mechanism of the layout to the audience. ForceAtlas = expansion + attraction + gravity. OpenOrd = much more difficult to explain in 1 minute.

So... continue the good work if you can, it benefits the community in a huge way!

[eduramiba]

Wow, this works really great!!
Keep the good work

[pbittner]

The plug-in has just been updated and includes a CUDA implementation of the layout running on GPUs.

If some of you have Windows 64 bit and a CUDA compatible Nvidia graphic card, I would appreciate some feedback since portability between different generations of Nvidia cards is a bit tricky. I have successfully tested the plug-in with a Quadro 2000 and a Geforce GT 540m but I wasn't able to use it with an older Quadro FX 1700.

The performance of the GPU implementation depends on the specification of the graphic card (number of CUDA cores) and on the number of nodes in the graph. With the Quadro 2000 card, the plug-in needs 0.5s per iteration on a graph of 100,000 nodes. This is about 1,000 times faster than the standard Force Atlas and 20 times faster than the parallel CPU implementation. Because the overhead of CUDA is quite high, the GPU implementation does not perform as well as the CPU implementation under 1,000 nodes.

Otherwise, I have been struggling a bit with making a parallel version of Force Atlas 2. The current prototype runs about 4 times faster but crashes above 100,000 nodes with a stack overflow. With OpenMP, the data private to each thread is allocated on the stack and I am not sure whether it is possible to increase the stack size when using a library through JNI. I'll try to make a non-recursive implementation and see how it performs.

[seinecle]

Hi,

I tested this new version of Parallel ForceAtlas on the Powergrid dataset.

I use Win7 64bits and the graphic card is GeForce GTX 560M (CUDA cores: 192 according to the specs)

Results:
GPU (CUDA)
- after a few seconds, the layout starts running. All nodes converge to the center until the graph is a single dot on the screen. Changing the parameters does nothing to that.

CPU (OpenMP)
- the layout works.

Hope it helps!

Best,

Clement