Parallel Force Atlas

[pbittner]

Thank you very much for trying Clement.

I observe the same behavior (nodes converging to the center) on the oldest graphic card I have tried. It is due to the CUDA kernel failing to launch when there are not enough resources available (memory, registers...). However, your graphic card is very recent and I am surprised that it does not work on your machine.

Could you make sure that you have the latest driver installed (275.33 in your case). You can get it there: http://www.nvidia.com/Download/index.aspx?lang=en-us

I'll do more testing tomorrow when I have access to the machine on which the GPU implementation is not working either.

Thanks,
Paul

[Neo---]

Hey,

can you (or had you already and I need a new pair glasses) also published the source code of the plugin (CPU version)? I'm currently working on GraphGL and I would like to check parallel FA algorithm since it (theoretically at least) should be possible to implement it with Web Workers. While I can only dream of speedups due to SSE or Fortran's number crunching capabilities, I hope it can provide inspiration for nice speedups nonetheless.

Cheers,
Urban

[pbittner]

Hi Urban,

The source code of the CPU implementation of Parallel Force Atlas is in the following file: http://bazaar.launchpad.net/~pbittner/g ... tUtils.f90

The repulsion stage of the force atlas algorithm is made of two nested loops that calculate the force between each pair of nodes. Since there are no dependencies between the calculations of individual pairs, it is possible to distribute the outer loop among the different threads.

Code: Select all

for (int i1=0;i1<nbNodes;i1++) {
    for (int i2=0;i2<nbNodes;i2++) {
        // calculation on the pair of nodes <i1,i2>
    }
}

Let me know if you have any other question.

Paul

[seinecle]

Thanks for the answer!

Indeed my current driver is not up to date, but the new one suggested by Nvidia does not install . I contacted my laptop provider and Nvidia to check the issue.

I'll keep you posted,

Best,

Clement

[seinecle]

Ok, it is Monday morming but the firm that built my laptop already reacted and sent me the patch (to give them credit for this fantastic response time: they are http://www.malibal.com)

Parallel Force Atlas now works fine with the settings set to "GPU", and the eyeball test (^^) says that it runs significantly quicker than with the CPU settings.

For anybody reading this, please realize: I run a (parallel) Force Atlas layout on the Powergrid dataset (4941 nodes, 6594 edges), and it moves from this (screenshot 1) to that (screenshot 2) in 60 seconds.

Really as easily as if it was a 100 nodes, 50 edges graph.

**Thanks** Paul!

[martin.pernollet]

Hi Paul,

I have not been has lucky as Clément, here's my experience:
1) I added the Parallel FA plugin the 10th september to Gephi 0.8, and tried to run it on a 1600 nodes & 17000 edges graph.
2) FA1 and your version run at the same visual speed: roughly 1 iteration per second
3) When checking "run the layout in parallel" and then clicking "run", the checkbox unchecks itself Do you think that this GUI error prevent from really running forces in parallel?
4) Running with OpenMP and Cuda gives the same speed. Using 1, 10 or 100 threads for OpenMP visually gives the same computation speed.

Then I noticed my GPU driver was desactivated by Windows, so I update the drivers and now the systems says the GeForce is activated, but nothing change for Parallel FA1.

I don't have much time to dive in your plugin sources and build your work by myself, but if there are log files I can send you, just ask me.

Remark: FA2 is really really faster than FA1 and Parallel FA1

Regards,
Martin

------------------------------
Sys: Windows 7 64 bits
CPU: Intel Core I3 CPU M350 @ 2.27Ghz, 64bit
RAM: 4go
GPU: 1) Intel HD Graphics 2) NVIDIA GeForce 310M (don't really understand why there are two chips on my laptop :s)

[jacomyma]

Dear all,

The performance gain for the ForceAtlas2 comes a little from its automatic "speed vs. precision" optimization, but it is in majority due to the implementation of a Barnes Hut optimization. If you disable "Approximate Repulsion", ForceAtlas2 will be very close to ForceAtlas. I guess it would be useful to have Parallel + Barnes Hut.

I tried a simple (and naïve) implementation of multi-threading in ForceAtlas2 and it works well (x2.5 performance on my old quad-core laptop). I hope it will be available in the next release of Gephi (I pushed it on my ForceAtlas2 branch on launchpad).

The really amazing innovation will be the usage of the GPU to compute the layout. I guess Barnes Hut + Multithreading + GPGPU = Huge perf boost...

[olive22]

First, thanks for this great layout plugin.

Do you intend to release a 32bit OpenMP version ? Unfortunately, one of the systems I use frequently cannot (for policy reasons...) receive a 64bit OS, and doesn't have a CUDA GPU.

OpenOrd runs fine with 3 threads, but I prefer PFA's layout.

[jeffg]

I haven't tested out any of the CUDA stuff, but I've been working to optimize Force Atlas 2 as is and have gotten significant performance improvements, in addition to adding 3D to the layout. However, I haven't had time to port it back to the Gephi code and I don't know how to determine in Gephi which to use 2D or 3D.

[pbittner]

Hi guys,

Sorry Martin for not responding earlier, I recently moved to the UK for a new job and I haven't had much time to check the forum. The checkbox unchecks itself when the plug-in is unable to load the libraries used for computation. I have done some testing and it appears that you don't only need a 64bit OS but also a 64bit version of Java. I am going to add that to the plug-in page.

Regarding Force Atlas 2, I have implemented a prototype of the layout using CUDA. It is only a little faster (up to 2x) than Force Atlas 2 for graphs with less than 50,000 nodes but gives a significant speedup for large graphs (10x faster for graphs with more than 500,000 nodes). I plan on releasing a new version of the plug-in with parallel versions of Force Atlas 1 and 2 layouts in about a month.

When the implementation is completed (I am also rewriting the Fortran source code of PFA in C++), I will be looking for someone able to compile the plug-in on Mac (requires to have g++ and the CUDA toolkit installed) so that it can be used on that platform.

For Olive, I should be able to release a 32bit OpenMP version. I put that on my TODO list.

And finally for Jeff, I am very interesting in the optimizations that you’ve done on Force Atlas 2. Can you tell us more about what you’ve done? Is it implemented in Java? The current FA2 implementation used a 2D implementation of the Barnes-Hut algorithm.

Regards,
Paul