## 3 Parallel Algorithm Design
Also plotted is the total runtime taken to find a maximum clique, but not proven is its optimality (we rerun the algorithm, telling it to exit as soon as it finds a clique of a size equal to what we now know the maximum to be). We see that with eight threads, a maximum clique is found almost instantly. This is because a maximum clique is located in the part of the search tree given by taking the eighth heuristic choice at the top of search, followed by the first choice at every subsequent depth. The work remaining once such a clique has been found is fixed and consists of exploring every node that cannot be eliminated by the bound regardless of the current incumbent--this explains the linear-like behaviour at over eight threads. The same behaviour is observed with other \"san\" graphs and members of the \"brock\" and \"gen\" families. The plot of \"brock400_4\" is similar to that of \"san400_0.9_1\", with a drop in work when going to nine threads and, then, a level graph afterwards. Here, a maximum clique is found by taking the ninth heuristic choice, then the third, fourth and third. For \"brock400_1\", we do not see a drop in work done, but we do see an unusually high improvement when going from 12 to 24 threads, despite hyper-threading. Further experiments show that with 20 or more threads, a maximum clique would be found very quickly, and we would get strongly superlinear

\begin{table}
\begin{tabular}{l r r r r r r r r} \hline
**Problem** & **Sequential** & \multicolumn{6}{c}{**Average Threaded Runtimes and Speedups**} \\  & **Runtimes** & **4** & & **8** & & **12** & **24** & \\ \hline \(G(1,000,0.1)\) & 18 ms & 18 ms & 1.0 & 23 ms & 0.8 & 26 ms & 0.7 & 33 ms & 0.5 \\ \(G(1,000,0.2)\) & 65 ms & 30 ms & 2.2 & 30 ms & 2.2 & 32 ms & 2.0 & 36 ms & 1.8 \\ \(G(1,000,0.3)\) & 532 ms & 151 ms & 3.5 & 100 ms & 5.3 & 83 ms & 6.4 & 76 ms & 7.0 \\ \(G(1,000,0.4)\) & 6.1 s & 1.6 s & 3.9 & 860 ms & 7.1 & 585 ms & 10.5 & 439 ms & 13.9 \\ \(G(1,000,0.5)\) & 138.6 s & 34.9 s & 4.0 & 17.6 s & 7.9 & 12.2 s & 11.3 & 8.9 s & 15.6 \\ \(G(3,000,0.1)\) & 640 ms & 220 ms & 2.9 & 171 ms & 3.7 & 156 ms & 4.1 & 168 ms & 3.8 \\ \(G(3,000,0.2)\) & 11.9 s & 3.1 s & 3.9 & 1.7 s & 7.0 & 1.2 s & 10.1 & 900 ms & 13.3 \\ \(G(3,000,0.3)\) & 358.5 s & 90.3 s & 4.0 & 45.6 s & 7.9 & 30.7 s & 11.7 & 23.2 s & 15.4 \\ \(G



speedups here, too (One may ask why we do not then use more threads than we have cores, to make this more likely to happen. Such an approach would sometimes be of benefit, but only if we are prepared to accept the possibility of a considerable slowdown in other cases.). ## 5 Conclusion and Future Work

Despite some of the more pessimistic claims that have been made in the literature regarding the suitability of sequential maximum clique algorithms for parallelisation, we have shown that making use of multi-core parallelism for hard clique problems is possible and worthwhile. This is important for two reasons. Firstly, existing work on local parallelism using bitset encodings has produced a speedup of between two and twenty over the basic algorithm [10; 12]. We have shown that a further speedup of around the same magnitude is possible by making use of the resources offered by today's multi-core processors. Secondly, we have shown that superlinearity can happen in practice and not just as a rare event. Furthermore, when it does happen, the effects can be extremely significant--we are able to make some

Figure 3: Total CPU time spent (_i.e._, runtimes multiplied by the number of threads) for “san400_0.9_1” from DIMACS with varying numbers of threads. Also shown is the total CPU time taken to find a maximum clique, but not to prove its optimality. A linear speedup would give a horizontal line, and downwards sloping lines are superlinear. \"hard\" instances \"easy\". We conjecture that this is due to the method used to split the work, where we use parallelism to avoid an overly strong commitment to an early heuristic.