## 3 Pms6 mc
### Inner-Level Parallelization
#### 3.3.1 Finding Equivalence Classes in Parallel:
As before, when moving an \(l\)-mer, the thread checks to see if the first \(p\) characters of the current \(l\)-mer differs from the previous one and update the appropriate pointer in \(bucketPointers\). There might be a problem in updating the bucket pointers in the boundary region of the segments as one bucket can extend across the boundary of two segments and hence two threads might update that bucket pointer. These boundary bucket pointers are fixed by a single thread after all \(l\)-mers are moved. Note that there can only be as many boundary buckets as there are segments which are very few in number. The pseudocode for the processing \(Q\) for different values of \(k\) is given in Algorithm 8. #### 3.3.4. \(outputMotifs\)

Once the size of \(Q\) drops below a certain threshold, we break out of the loop and call \(outputMotifs(Q)\) to determine the set of valid motifs in \(Q\). This step can be done in parallel as checking the validity of \(l\)-mers to be motifs can be done independent of one another. So, each thread examines a disjoint set of \(l\)-mers from \(Q\) exhaustively checking if it is a motif as is done in PMS6; the threads operate in parallel. ```
ProcessQ((Q,k,T[i]) if\(k=1\) { prefixCounters(counters);  Move\(l\)-mers from\(\mathit{strs}\)[] to\(\mathit{strs}\)2[] by threads T[i][j] in parallel;  syncthreads(T[i]);  Sort segments in\(\mathit{strs}\)2[] in parallel by threads T[i][j];  syncthreads(T[i]);  Count unique \(l\)-mers in each segment in parallel by threads T[i][j];  syncthreads(T[i]);  Move unique \(l\)-mers to\(\mathit{strs}\)1[] and update bucket pointers in parallel by T[i]j[j];  }  if\(k\geq 2\){  Divide\(\mathit{markBuffer}\) into segments;  Prefix sum\(\mathit{markBuffer}\) by threads T[i][j] in parallel;  syncthreads(T[i]);  Move marked \(l\)-mers from segments in\(\mathit{strs}\)1[] to\(\mathit{strs}\)2[] in parallel by Threads T[i][j];  Update the bucket pointers while moving \(l\)-mers;  syncthreads(T[i]);  Fix the boundary buckets if necessary;  }
```

**Algorithm 8**Processing \(Q\). ## 4 Experimental Section

We evaluated the performance of PMS6 MC on the challenging instances described in [22] as they are representatives of harder to solve instances and provide a uniform way to compare results from previous algorithms. For each \((l,d)\) that characterizes a challenging instance, we generated 20 random strings of length 600 each. Next, a random motif of length \(l\) was generated and planted at random positions in each of the 20 strings. The planted motif was then randomly mutated in exactly \(d\) randomly chosen positions. For each \((l,d)\) value up to (19,7), we generated 20 instances and for larger \((l,d)\) values, we generated 5 instances. The average run times for each \((l,d)\) value are reported in this section. Since the variation in run times across instances was rather small, we do not report the standard deviation. Even though wetest our algorithm using only synthetic data sets, several authors (e.g., [22]) have shown that PMS codes that work well on the kind of synthetic data used by us also work well on real data. ### PMS6 MC Implementation

PMS6 MC is implemented using the pthreads (POSIX Threads) library under Linux on an Intel 6-core system with each core running at 3.3 GHz. We experimented with different degrees of outer-level (number of thread blocks) and inner-level (number of threads in a thread block) parallelism for different challenging instances. For smaller instances (e.g., (13,4) and (15,5)), the performance is limited by the memory bandwidth of the system. Hence, increasing the degree of inner or outer level parallelism does not have much effect on the run time as most of the threads stall for memory access. For larger instances, the number of thread blocks is limited by the available memory of the system. Table 1 gives the number of thread blocks and the number of threads in a thread block for different challenging instances which produces the optimum performance.