Re: [igraph] Running Igraph in parallel

[Tamas Nepusz]

Hi Chris,

The OpenMP direction is indeed interesting and it would definitely be  
of use to some of the algorithms implemented by igraph (e.g., diameter  
or betweenness calculations). The main problem at the moment is that  
igraph is not thread-safe. There is at least a single global data  
structures we use that will surely cause problems: a stack of  
protected pointers. Whenever an igraph function allocates memory for a  
given purpose, it pushes the pointer to the stack along with a  
corresponding destructor function. If an error happens anywhere inside  
an igraph call, a macro called IGRAPH_ERROR is invoked which takes  
care of unwinding the stack and freeing everything using its  
corresponding destructor function.

Now, if one of the threads launched by OpenMP encounters an error, we  
will have to find a way to inform all the other threads that 1) there  
was an error, so there's no need to continue the calculations, 2) the  
stack was already unwound by the thread that had run into an error.  
(Even more complications will arise if the OS switches threads while  
the stack is only partially unwound). I'm sure that OpenMP has tools  
for coordinating the behaviour of independent threads, but we will  
have to dig deeper into OpenMP's internals and make igraph thread-safe.

--
Tamas

On 2009.01.25., at 15:31, Chris Wj wrote:

> I have been doing some OpenMP research recently and I really think  
> it would help igraph to use it. OpenMP allows you to ensure that  
> variables are thread safe so you don't have to worry much about  
> igraph's existing implementation.
>
> After reading some tutorials and writing a few examples, I have  
> found it very easy to use and almost a no-brainer in many situations  
> because of its simplicity. Also, all the major compilers support it.  
> It is as simple as a header file and a compiler flag.
>
>
> I found a few open source implementations of OpenMP graph  
> calculations:
> Python with C++ back-end: https://projects.forked.de/graph-tool/
> C and OpenMP: https://sourceforge.net/projects/snap-graph/
>
>
> Check the pubs here: http://www.graphanalysis.org/publications.html
> Kamesh Madduri, and David A. Bader seem to have the most pubs on  
> this topic.
>
>
> The future of computing is MP and igraph is too good to not follow  
> suit!
>
> I'll help in any way I can. I just have to learn a lot more about  
> igraph's internals to do anything and on first glance that looks  
> like it will take a short while.
>
>
> -Chris
>
> True, this is also an option, just like many similar libraries,
>
> eg. MPI implementations if you want to distribute jobs to
> many machines. But it is still true that a single igraph
> function will not run any faster.
> Another issue might be if you go with openmp, that we never checked
> that igraph is thread-safe. I think it is, most of the time,
> but would not be 100% sure, e.g. the error handling might cause
> problems.
>
> Gabor
>
> ps. please consider joining the list, otherwise i have to acknowledge
> your mails by hand and this can cause delay. Thanks.
>
> On Thu, May 29, 2008 at 11:07:11PM +0200, Walter de Back wrote:
> > Hi,,
> >
> > If you're implementing in C/C++, you could use openMP to exploit
> > multithreading
> > (on a multi-core machine) to do various analysis tasks on your  
> huge graph in
> > parallel.
> >
> > I've made some simple openMP examples showing how to:
> >
> > - generate and analyse multiple graphs in parallel
> > http://walter.deback.net/media/c/igraph_openmp1.c
> >
> > - do different analysis tasks on the same graph in parallel
> > http://walter.deback.net/media/c/igraph_openmp2.c
> >
> > More on openMP:
> > http://openmp.org
> > https://computing.llnl.gov/tutorials/openMP/
> > http://en.wikipedia.org/wiki/OpenMP
> >
> > Best,
> > Walter
> [...]
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help