search

ciaranm / glasgow-subgraph-solver

A solver for subgraph isomorphism problems, based upon a series of papers by subsets of McCreesh, Prosser, and Trimble.
MIT License
62 stars 23 forks source link

Why parallel version is slower ? #12

Open Weissle opened 2 years ago

Weissle commented 2 years ago

When I use glasgow-subgraph-solver, I find that the parallel version is slower than sequential version in most cases. I wonder if I am using it wrong. My script is:

# sequential version
./glasgow_subgraph_solver --induced --format labelledlad --count-solution query.llad target.llad
# parallel version
./glasgow_subgraph_solver --induced --parallel --format labelledlad --count-solution query.txt target.txt
# I have tried different thread number and restarts policy.
./glasgow_subgraph_solver --induced --threads 8 --restarts timed  --format labelledlad --count-solution query.llad target.llad

This two file is a small example. I get them from Benchmarks and convert them from LAD to Labelled LAD. pattern.txt target.txt Looking forward to your reply.

ciaranm commented 2 years ago

Parallel is only faster on relatively hard instances that have a large search tree: if it's taking milliseconds or only a few nodes to solve, the overheads of doing parallel search will outweigh any gains.

Another possible problem is, if there are lots of solutions, the threads have to synchronise every time a solution is found, which can also lead to no speedups.

Are you seeing any large, hard problem instances where parallel isn't helping?