## 3 Pms6 mc
### Inner-Level Parallelization
#### 3.3.1 Finding Equivalence Classes in Parallel:
Although there might be a write conflict while setting the bit in the \(markBuffer[]\), all threads can carry this step in parallel as threads that write to the same mark bit write the same value. Algorithm 6 gives the steps used to compute and process \(B_{d}(C)\). ```
ProcessBd(\(B_{d}(C)\), \(Q\), \(k\), \(i\), \(j\)) if\(k=1\) { foreach\(l\)-mer\(w\in B_{d}(C)\)\(counter[j][w[0]]++\); Copy\(l\)-mers in\(B_{d}(C)\) to\(strs1[]\) from theoffset for this class; } if\(k\geq 2\) { For all\(l\)-mer\(w\in B_{d}(C)\), set\(markBuffer[]\) if\(w\) is present in\(Q\); }
```
**Algorithm 6**Compute and process \(B_{d}(C)\). #### 3.3.3 Processing \(Q\) in Parallel

The processing of \(Q\) depends on the iteration number. When \(k=1\), we sort \(strs1[]\), then remove the duplicates and set the bucket pointers. For the remaining iterations, we need to remove all unmarked \(l\)-mers from \(strs1[]\) and update the bucket pointers. The \(k=1\) sort is done by first computing the prefix sum of \(counters[][]\) so that the counter for a particular thread and a particular character equals the total number of \(l\)-mers processed that have either smaller first character or equal first character but processed by threads with a smaller index. Since the number of counters is small (256 different counters for 8-bit characters) we compute the prefix sums using a single thread. The pseudocode is given in Algorithm 7. Next, each thread in the threadblock scans through the \(l\)-mers in \(strs1[]\) that it had stored while generating \(B_{d}(C)\). Depending on the first character of the \(l\)-mer, the \(l\)-mer is moved to \(strs2[]\) starting from the offset indicated by prefix sum counter. This movement of \(l\)-mers is done by the threads in a thread block in parallel. Once the movement is complete, \(strs2[]\) is divided into segments such that the first characters of all \(l\)-mers within a segment are the same. Following this segmenting, the threads sort the segments of \(strs2[]\) in parallel using radix sort. Each thread works on a different segment. Since the first character of the \(l\)-mers in a segment are the same, the radix sort starts from the second character. Once the segments are sorted, we proceed to eliminate duplicates and set the bucket pointers. First the threads count the number of unique \(l\)-mers in each segment in parallel by checking adjacent \(l\)-mers. Again, each thread works on a different segment. The determined counts of unique \(l\)-mers are prefixed summed by a single thread to get the offsets required for moving the unique \(l\)-mers to their final positions. Using these offsets, the threads move unique \(l\)-mers with each thread moving the unique \(l\)-mers of a different segment from \(strs2[]\) to \(strs1[]\) in parallel. While moving an \(l\)-mer, the threads also check to see if first \(p\) characters of the current \(l\)-mer are the same as those of the previous \(l\)-mer; if not, the appropriate pointer in \(bucketPointers[]\) is set. ```
PrefixCounters(\(\textit{counters}[][]\)) sum = 0; for i = 0 to 255 // There are 256 possibilities for the first character { \(\textit{counters}[0][i]=\textit{counters}[0][i]+\textit{sum}\);  for j = 1 to threads { \(\textit{counters}[j][i]=\textit{counters}[j][i]+\textit{counters}[j][i-1]\); }  sum = counters[threads - 1][i]; }
```
**Algorithm 7**Prefix sum of counters. When \(k\geq 2\), we need to remove from \(Q\) all the \(l\)-mers that are not marked in \(markBuffer\). This is done in two steps. First, the \(markBuffer\) is divided into segments and each thread does a prefix sum on different segments in parallel. This gives the number of marked \(l\)-mers in each segment. Next, we move the marked \(l\)-mers in each segment from \(strs1[]\) to \(strs2[]\). For this, a prefix sum is performed by a single thread on the counters having the number of marked \(l\)-mers in different segments to get the offset in \(strs2[]\) for moving the \(l\)-mers. With these offsets, the threads then move the marked \(l\)-mers from different segments in parallel.