## 3 Parallel Algorithm Design
```
1 threadedMaxClique :: (Graph \(G\)) \(\rightarrow\) Set of Integer begin
2 shared\(C_{max}\leftarrow\emptyset\)
3 shared\(q\leftarrow\) an empty Queue of (Set, Set)
4 permute\(G\) so that the vertices are in non-increasing degree order
5 launch the populating thread do
6 expand\((G,q,\emptyset,\mathrm{V}(G),C_{max})\)
7 launch multiple worker threads do
8 while there is work left do
9\((C,P)\leftarrow\)dequeue\((q)\)
10 expand\((G,q,C,P,C_{max})\)
11
12 join all threads
13 return\(C_{max}\) (unpermuted)
```  
**Algorithm 3**A threaded algorithm to deliver a maximum clique  
```
1 expand :: (Graph \(G\), Queue of (Set, Set) \(q\), Set \(C\), Set \(P\), Set \(C_{max}\))
2 begin
3\(populate\leftarrow\)true if we are the populating thread, and \(|C|=1\), otherwise false
4\((colour,order)\leftarrow\)colourOrder\((G,P)\)
5 for\(i\gets|P|\) downto\(1\)do
6 if\(|C|+colour[i]>|C_{max}|\)then
7\(v\gets order[i]\)
8\(C\gets C\cup\{v\}\)
9\(P^{\prime}\gets P\cap\mathrm{N}(G,v)\)
10 if\(P^{\prime}=\emptyset\)then
11 if\(|C|>|C_{max}|\)then\(C_{max}\gets C\)
12 else
13 if the populating thread is done, and \(q\) is empty, and there are idle workers then
14\(populate\leftarrow\)true
15 ifpopulatethen\(\texttt{enqueue}(q,(C,P^{\prime}))\)
16 elseexpand\((G,q,C,P^{\prime},C_{max})\)
17\(C\gets C\setminus\{v\}\)
18\(P\gets P\setminus\{v\}\)
19

### Goals of Parallelism

We define the _speedup_ obtained from a parallel algorithm to be the runtime for a good sequential implementation divided by parallel runtime. We call a speedup of \(n\) from \(n\) cores _linear_ and a speedup of greater than \(n\)_superlinear_. Intuitively, we may expect that doubling the number of cores available could at best halve the runtime of the algorithm--that is, the speedup we obtain could at best be linear. However, for branch and bound algorithms, this is not the case, and superlinear speedup is possible [19; 20; 21; 22]. This is because we are not simply dividing up a fixed amount of work: if an additional thread finds a better incumbent quickly, we will have less overall work to do. On the flip side, we cannot guarantee that we will produce a speedup at all: it may be that some threads spend all their time exploring parts of the tree, which would have been eliminated in a sequential run, and, so, contribute nothing to the solution. A parallel algorithm is _work efficient_ if it does \"the same amount of work\" as a sequential algorithm. We ignore implementation overheads and focus upon a \"representative operation\", as is done when considering complexity; here, we count the number of recursive calls to expand. If an algorithm is not work efficient, we define its _efficiency_ to be the ratio of work done by the sequential algorithm to work done by the parallel algorithm, expressed as a percentage. If the time taken to execute each \"unit of work\" is roughly equivalent, we would expect an efficiency of greater than 100% to be a necessary, but not sufficient, condition for obtaining a superlinear speedup (This is not entirely true, due to cache effects: it could be that the working memory will fit entirely in cache when using multiple cores, but not when using a single core. However, for our purposes, this effect is negligible.). The goal of parallelisation is not necessarily to produce a speedup. We are also interested in being able to tackle larger problems within a reasonable amount of time [6]. For this work, we consider it more

Figure 2: Work splitting and queueing mechanism for our parallel algorithm. Nodes correspond to a call to expand. Work donation occurs once when the donating worker’s position is at the node marked \(\star\). important to be able to reduce a runtime from, say, days to hours, rather than from one second to one tenth of a second. We must also be careful not to introduce the possibility of a slowdown. Ignoring overheads, this may be done by ensuring that one worker follows \"the same path\" (or a subset thereof) as the sequential version of the algorithm [23], which our queueing mechanism provides.