## 3 Parallel Algorithm Design
For larger problems, we do not see any signs of scalability problems when using all of the cores available to us. \begin{table}
\begin{tabular}{l c c c} \hline
**Problem** & **Our runtime (s)** & **BBMCI (s)** & **BBMC1 (s)** \\ \hline brock400\_1 & 198 & 341 & 507 \\ brock400\_2 & 144 & 144 & 371 \\ brock400\_3 & 114 & 229 & 294 \\ brock400\_4 & 56 & 133 & 146 \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison of runtimes (in seconds) for our sequential implementation with [PERSON]’s published results for BBMCI [11] (which differs slightly from our algorithm) and with runtimes using [PERSON]’s BBMC1 [12] (which is the same as our algorithm, but in Java). The system used to produce these results has the same model CPU as was used by [PERSON]. \begin{table}
\begin{tabular}{l c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Problem**} & \(\omega\) & \multicolumn{3}{c}{**Sequential Runtimes**} & \multicolumn{6}{c}{**Threaded Runtimes, Speedups and Efficiency**} \\  & & & **and Search Nodes** & \multicolumn{3}{c}{**4**} & \multicolumn{3}{c}{**8**} & \multicolumn{3}{c}{**12**} & \multicolumn{3}{c}{**24**} \\ \hline p\_batt1000-2 & 46 & 159.2 s & \(3.4\times 10^{7}\) & 40.5 s & 3.9 & 98\% & 20.4 s & 7.8 & 97\% & 14.3 s & 11.1 & 96\% & 11.7 s & 13.7 & 92\% \\ p\_batt1000-3 & 68 & 804,28.9 s & \(1.3\times 10^{11}\) & 200,83.7 s & **4.0** & **101\%** & 101,30.7 s & 7.9 & 100\% & 67,695.5 s & 11.9 & 100\% & 53,242.6 s & 15.1 & 98\% \\ p\_batt500-1 & 12 & 32.8 s & \(1.2\times 10^{6}\) & 821 ms & 3.9 & **100\%** & 433 ms & 7.4 & 100\% & 341 ms & 9.4 & **100\%** & 259 ms & 12.4 & **100\%** \\ p\_batt500-2 & 65 & 24,338.5 s & \(2.0\times 10^{9}\) & 6,117.3 s & 4.0 & 99\% & 3,089.0 s & 7.9 & 98\% & 2,094.6 s & 11.6 & 96\% & 1,789.1 s & 13.6 & 91\% \\ p\_batt1500-3 & 94 & & & & & & & & & & & & & \\ s\_batt200-3 & 44 & 8.5 s & \(6.8\times 10^{6}\) & 439 ms & **19.5** & **955\%** & 319 ms & **26.8** & **417\%** & 177 ms & **48.3** & **734\%** & 271 ms & **31.5** & **567\%** \\ s\_att000.7-2 & 30 & 2.0 s & \(8.9\times 10^{5}\) & 590 ms & 3.4 & **106\%** & 298 ms & 6.7 & 90\% & 176 ms & 11.4 & **116\%** & 76 ms & **26.3** & **216\%** \\ s\_att000.7-3 & 22 & 13.3 s & \(5.2\times 10^{5}\) & 548 ms & **15.0** & **529\%** & 62 ms & **20.3** & **475\%** & 54 ms & **23.4** & **396\%** & 58 ms & 21.7 & **253\%** \\ s\_att000.9-1 & 100 & 25.5 s & \(4.5\times 10^{6}\) & 5.3 s & **44** & **133\%** & 312 ms & **75.3** & **13.7**\% & 203 ms & **102.2** & **1,383\%** & 191 ms & **123.0** & **1,217\%** \\ s\_att1000 & 15 & 1.9 s & \(1.5\times 10^{5}\) & 488 ms & 3.9 & 10\% & 281 ms & 6.8 & **107\%** & 173 ms & 11.1 & **108\%** & 108 ms & 17.7 & **139\%** \\ s\_att200.0-9 & 42 & 19.4 s & \(1.5\times 10^{7}\) & 5.3 s & 3.7 & 92\% & 2.8 s & 6.8 & 89\% & 2.2 s & 9.0 & 85\% & 3.0 s & 6.4 & 66\% \\ s\_att000.7-2 & 21 & 72.1 s & \(6.4\times 10^{7}\) & 181 s & 4.0 & **100\%** & 9.1 s & 7.9 & 100\% & 6.2 s & 11.7 & 100\% & 4.6 s & 15.7 & 100\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Problem**} & \(\omega\) & \multicolumn{3}{c}{**Sequential Runtimes**} & \multicolumn{6}{c}{**Threaded Runtimes, Speedups and Efficiency**} \\  & & & **and Search Nodes** & \multicolumn{3}{c}{**4**} & \multicolumn{3}{c}{**8**} & \multicolumn{3}{c}{**12**} & \multicolumn{3}{c}{**24**} \\ \hline fr830-15-1 & 30 & 657.1 s & \(2.9\times 10^{8}\) & 160.2 s & **4.1** & **102\%** & 76.6 s & **8.6** & **107\%** & 43.9 s & **15.0** & **130\%** & 35.5 s & 18.5 & **127\%** \\ fr830-15-2 & 30 &



When using 24 threads, we must worry about hyper-threading; nonetheless, our speedups typically (but not always) improve over those for 12 threads, and even when they do not, a speedup is still obtained. The \"gen400_p0.9_75\" graph benefits strongly from hyper-threading: with 24 threads, a maximum clique is found (but not proven) after 3,757 s by taking the 17 th, 8 th, 3 rd and 4 th choices given by the heuristic, followed by the first choice thereafter.