# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 2 Materials and Methods
### Parallelization  
Recursive bisection is straightforward to parallelize by computing orders on the separated blocks independently, using task-based parallelism. This only employs parallelism after the first separators have been found.  
Therefore, we additionally parallelize InertialFlowCutter. The implementation of FlowCutter [22] contains a simple parallelization. In a round, all cutters with the currently smallest cut are advanced to their next cut in parallel. Before the next round, all threads synchronize. This approach exhibits poor core utilization since only a few cutters may have the smallest cut in a round and threads perform different amounts of work, leading to skewed load distribution.  
Instead, we employ a simple wait-free task-based parallelization scheme, which guarantees that the cutters with the \(t\) currently smallest flow values are making progress, for \(t\) threads executing in parallel. Algorithm 2 illustrates this scheme in pseudocode. For every cutter, we store two atomic flags: a _free_ flag, which indicates that currently no task holds this cutter, and an _active_ flag, which indicates that this cutter can still yield a cut with better expansion than previously found cuts. In the beginning, every cutter is active and free.  
Recall that \(q\) is the number of cutters. We create \(q\) tasks, and the task scheduler launches \(t\leq q\) parallel tasks, potentially adding more when resources from other parts of the recursive bisection become available. A task executes a loop in which it first acquires a cutter with the currently smallest flow out of the free and active cutters, then performs a _chunk of work_ on it and releases the cutter again. A chunk of work consists of deactivating the cutter, if it can not improve expansion and otherwise running one Pseudo-Depth-First-Search, which either pushes one unit of flow or derives a cut. If the cut has at least 20% of the nodes on the smaller side and improves expansion, we acquire a lock and store the cut. A task terminates once it fails to acquire a free and active cutter, as there are now more tasks than active cutters.  
If less than \(q\) tasks are running simultaneously, the tasks switch between cutters. If all cutters are acquired and the task's currently acquired cutter remains active, we continue working on it, to avoid the overhead of releasing and immediately re-acquiring the same cutter. Note that, due to the parallelization, cuts are not necessarily enumerated in the order of increasing cut size, and dominated cuts may also be reported.  
```
1 active(\(c\)) \(\leftarrow\)\(\mathit{true}\) for \(c\in\{1,\dots,q\}\)
2 free(\(c\)) \(\leftarrow\)\(\mathit{true}\) for \(c\in\{1,\dots,q\}\)
3 Launch \(q\) parallel tasks executing Worker
4 FunctionWorker:whiletruedo
5\(c\leftarrow-1\)
6 for\(i\in\{1,\dots,q\}\)do
7 if\(\mathit{active}(i)\) is truethen
8 atomically test and set free(\(i\)) to false
9 ifold value was true and \(\mathit{active}(i)\) is still truethen
10\(c\gets i\)
11 break
12
13 if\(c=-1\)then
14 return
15
16 do
17 ifcutter \(c\) can improve the expansionthen
18 augment flow or calculate cut on cutter \(c\)
19 else
20\(\mathit{active}(c)\leftarrow\) false
21 ifcutter \(c\) has a cut that improves the expansionthen
22 acquire lock and report cut
23 while\(\mathit{active}(c)\) is true and no cutter is free
24\(\mathit{free}(c)\leftarrow\) true
```  
**Algorithm 2**Parallel InertialFlowCutter