## 3 Parallel Algorithm Design
We must also ensure that newly discovered incumbents are immediately visible to every worker. ### Complications from Hyper-Threading

Hyper-threading \"makes a single physical processor appear as two logical processors; the physical execution resources are shared, and the architecture state is duplicated for the two logical processors\" [24]. The system we will be using for experimental evaluations is hyper-threaded; this causes complications. Firstly, this means that when going from using one thread per physical processor to one thread per logical processor, we should not expect to be able to double our speedup. The cited Intel literature suggests a performance increase of \"up to 30%\"--this figure is derived from benchmarks (which show performance increases of \"21%\" and \"16 to 28%\"), not theory. Taken at face value, this means that a speedup of around 15.6 on the 12-core, hyper-threaded system that we describe later should be considered \"linear\". Secondly, and more problematically, this means that if two (software) threads are running on the same physical processing core, each will run more slowly than if it had the core to itself [25]. Because we are not executing a fixed amount of work on each thread, this can lead to a slowdown anomaly--this is a variation of what [PERSON] _et. al_. describe as the \"[danger of increasing] the processing power of a system by adding a less powerful processing element\" [23]. We will assume that so long as the number of threads we use is no greater than the number of physical processing cores, the operating system scheduler will be smart enough to allow us to ignore this issue. For larger numbers of threads, we proceed with the understanding that this could possibly make matters worse, not better (The same problem arises if we use more worker threads than can be executed simultaneously. This, however, is directly under our control.). ## 4 Experimental Evaluation

### Implementation

We implemented the sequential and threaded algorithms in C++, using C++11 threads [26]. Since we are using shared memory parallelism and since the graph data structure is not modified during execution, we may share the graph between threads to save memory (and improve cache performance). C++ provides us with strong enough guarantees to do this without locking. Sharing the incumbent requires more attention. To avoid the possibility of a slowdown, improved incumbents must be made visible to every worker. To simplify this problem, we note that we only need to share the size of the incumbent, not what its members are. Thus, we need only share a single integer and can retrieve the actual maximum clique when joining threads. We make use of an atomic to do this. The number of worker threads to use is left as a configuration parameter--this allows experiments to be performed evaluating scalability. We do not count the initial populating thread towards the thread count, as it is expected that the amount of work performed for the population will be a very small part of the overall work. We also do not count the main program thread, which just spawns, then joins, child threads. No attempt was made to parallelise the initial preprocessing and sorting of the graph. ### Experimental Data and Methodology

We work with three sets of experimental data. The first set, from the DIMACS Implementation Challenges [27], contains a smorgasbord of random and real-world problems of varying difficulty--some can be solved in a few milliseconds, whilst others have not been solved at all. The second set consists of \"Benchmarks with Hidden Optimum Solutions for Graph Problems\" [28]. Each of these contains a maximum clique of a known size that has been hidden in a way intended to make it exceptionally hard to find. Finally, we consider random graphs. For timing results, following standard practice, we exclude the time taken to read the graph from the file. We include the time to do preprocessing on the graph (this is not entirely standard, but we consider it the more realistic approach).