## 3 Pms6 mc
### Inner-Level Parallelization
#### 3.3.1 Finding Equivalence Classes in Parallel:
## 5 Results and Discussion

### PMS6 and PMS6 MC

We compare the run times of PMS6 and PMS6 MC on an Intel 6-core system with each core running at 3.3 GHz. PMS6 takes 22 s on an average to solve (15,5) instances and 19 h on an average to solve (23,9) instances. PMS6 MC, on the other hand, takes 8 s on an average to solve (15,5) instances and 3.5 h on an average to solve (23,9) instances. The speedup achieved by PMS6 MC over PMS6 varies from a low of 2.75 for (13,4) instances to a high of 6.62 for (17,6) instances. For (17,6) instance we can use many threads while staying within memory constraints and hence we get a larger speedup. For (19,7) and larger instances PMS6 MC achieves a speedup of over 5 as we can't go beyond a certain number of threads due to memory limitations. The run times for various challenging instances are given in Table 2. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Challenging instances** & **Outer-level blocks** & **Threads per block** & **Total threads** \\ \hline (13,4) & 2 & 6 & 12 \\ (15,5) & 2 & 6 & 12 \\ (17,6) & 8 & 6 & 48 \\ (19,7) & 4 & 12 & 48 \\ (21,8) & 2 & 12 & 24 \\ (23,9) & 2 & 12 & 24 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Degree of inner and outer level parallelism for PMS6 MC. ### PMS6 MC and Other Parallel Algorithms

[PERSON], [PERSON] and [PERSON] proposed a voting based parallel algorithm for multi-core architectures using bit arrays [24]. They followed up with an improved algorithm based on suffix trees for GPUs and multi-core CPUs from intel [25]. We estimate the relative performance of PMS6 MC and these parallel algorithms using published run times and performance ratios. Table 3 and the first 4 rows of Table 4 give the performance of PMS5 and PMSPrune as reported in [22] and that of PMS6 and PMS5 as reported in [23], respectively. We divide the ratio \(PMS5/PMSPrune\) by \(PMS5/PMS6\) to estimate the ratio \(PMS6/PMSPrune\) (5 th row of Table 4). Next, we divide the ratio \(PMS6/PMS6 MC\) (row 4 of Table 2) by our estimate of \(PMS6/PMSPrune\) to get an estimate of \(PMSPrune/PMS6 MC\) (6 th row of Table 4). The first 4 rows of Table 5 give the run times of gSPELLER-x, mSPELLER-x, and PMSPrune as reported in [25]. The \"x\" indicates the number of CPU cores for mSPELLER and the number of GPU devices in the case of gSPELLER. We report the times for mSPELLER-16 and gSPELLER-4 as these were the fastest reported in [25]. From this data and that of Table 4 we can estimate the speedups shown in rows 5 through 8 of Table 4. We estimate that the speed up of PMS6 MC using 6 cores compared to \begin{table}
\begin{tabular}{c c c c c c c} \hline Algorithm & (13,4) & (15,5) & (17,6) & (19,7) & (21,8) & (23,9) \\ \hline PMS5 & 39 s & 130 s & 11.35 min & 40.38 min & 4.96 h & 40.99 h \\ PMS6 & 22 s & 75 s & 6.72 min & 22.75 min & 2.25 h & 19.19 h \\ PMS5/PMS6 & 1.77 & 1.73 & 1.69 & 1.77 & 2.20 & 2.14 \\ PMS6/PMSPrune & 1.46 & 0.27 & 0.17 & 0.06 & - & - \\ PMSPrune/PMS6 MC & 1.88 & 13.04 & 38.94 & 85.17 & - & - \\ \hline \end{tabular}
\end{table} 
Table 4: Total run time of different PMS algorithms. \begin{table}
\begin{tabular}{c c c c c c} \hline Algorithm & (13,4) & (15,5) & (17,6) & (19,7) & (21,8) & (23,9) \\ \hline PMS6 & 22 s & 74 s & 6.82 min & 22.75 min & 2.25 h & 19.19 h \\ PMS6 MC & 8 s & 21 s & 1.03 min & 4.45 min & 25.5 min & 3.57 h \\ PMS6/PMS6 MC & 2.75 & 3.52 & 6.62 & 5.11 & 5.29 & 5.38 \\ \hline \end{tabular}
\end{table} 
Table 2: Run times for PMS6 and PMS6 MC. \begin{table}
\begin{tabular}{c c c c c} \hline Algorithm & (13,4) & (15,5) & (17,6) & (19,7) \\ \hline PMS5 & 117 s & 4.8 min & 21.7 min & 1.7 h \\ PMSPrune & 45 s & 10.2 min & 78.7 min & 15.2 h \\ PMS5/PMSPrune & 2.6 & 0.47 & 0.28 & 0.11 \\ \hline \end{tabular}
\end{table} 
Table 3: Run times for PMS5 and PMSPrune [22].