Julien Boucaron's Page

I wrote a simple library to simulate quickly Marked Graph, Synchronous Data Flow (under ASAP firing rule) in C++ while also having some fun with Intel’s Threading Building Blocks library to check how it works.

I enjoy very much this raising of abstraction for threads, however, my parallel code performs not well (too thin grain) but I did not build too big examples, and not enough testing. Nevertheless, this small code is memory-leak free and very fast. Moreover, it is also “data race” free, I will explain quickly the sketch of the algorithm and its threaded variations.

Basic sequential algorithm:

1. Mark all nodes that can fire.
2. Fire those nodes.
   • Update input arcs
   • Update output arcs
3. Unmark all nodes.

Where there is parallelism here ?

1. Mark all nodes that can fire.
   • Data parallelism, we can check each node in parallel
2. Fire those nodes. Data parallelism, we can fire each node in parallel
   • Update input arcs
     • Data parallelism, we can do this for each node in parallel
   • Update output arcs
     • Data parallelism, we can do this for each node in parallel
3. Unmark all nodes.
   • Data parallelism, we can do this for each node in parallel

The green one, is useful when there is a lot of nodes. The red one, when a node is having a lot of arcs (not really helpful in general, in my case).

Code source is available here and release under LGPL: http://julien.boucaron.free.fr/download/ (check tbb_simu*.tgz)

There is different Makefiles (.Java building JNI Wrapper using SWIG; .graph just build JNI Wrapper for my dummy graph lib)

There is also a JNI wrapper made with SWIG, which works has long has you do not call too much “get” method in vector*.java; each time there is a “get” there is a call to the constructor… (be careful, it does not scale). I will fix this when I will have enough time.