Parallel (threaded) implementation of curveball (sone threads) and cooccurrence (separate threads)
Use case: Generate g
random graphs and compute the cooccurrence matrix for each graph G_k
.
The optimization idea is to separate the execution of the Global Curveball algorithm from the computation of the Cooccurrence matrix.
In a sequential manner you would:
- run the Global Curveball algorithm for a certain number of steps in order to generate the first Graph
G_1
, - run the cooccurrence computation for
G_1
, - run the Global Curveball for generating the 2nd graph,
- run the cooccurrence computation for
G_2
, etc.
----- TIME ----->
| Curveball G_1 | Cooccurrence G_1 | Curveball G_2 | Cooccurrence G_2 | Curveball G_3 | Cooccurrence G_3 |...
The total amount of time spend by this sequential approach is the sum of the time spent by the Global Curveball + the Cooccurrence computation.
Let t_{cu}
be the average time taken to run one step of the Global Curveball.
Let t_{co}
be the average time taken to run the cooccurrence computation.
Then the time taken by the sequential approach is simply T=\sum_{i=1}^{g} t_{cu} + t_{co}
In a parallel version, one would let a thread compute the Global Curveball and another thread (or more if needed) would compute the Cooccurrence.
Example with 2 threads:
----- TIME ----->
THREAD 1 | Curveball G_1 | Curveball G_2 | Curveball G_3 | Curveball G_4 | ...
THREAD 2 ................| Cooccurrence G_1 | Cooccurrence G_2 | Cooccurrence G_3 | ...
One can already see that, one thread for the Global Curveball and one thread for the Cooccurrence computation is OK if t_{cu} \geq t_{co}
----- TIME ----->
THREAD 1 | Curveball G_1 | Curveball G_2 | Curveball G_3 | Curveball G_4 | ...
THREAD 2 ................| Coocc G_1 |...| Coocc G_2 |...| Coocc G_3 |...| Coocc G_4 |
If t_{cu} < t_{co} \leq 2 t_{cu}
, the optimal time is acchieved with one thread for the Global Curveball and two threads for the cooccurrence computation. (For now, let's assume the cost of switching context and copying data between threads is negligible).
----- TIME ----->
THREAD 1 | Curveball G_1 | Curveball G_2 | Curveball G_3 | Curveball G_4 | ...
THREAD 2 ................| Cooccurrence G_1 |........... | Cooccurrence G_3 | ...
THREAD 3 ................................| Cooccurrence G_2 |............| Cooccurrence G_4 | ...
etc.
The best scheme will depends upon the two values of t_{cu}
and t_{co}
.