COMP 322 Homework 3: Pairwise Sequence Alignment

Part 1: Written Questions (30 points)

1.1 Amdahl's Law Generalization (15 points)

Consider a generalization of Amdahl's Law:

• q1 = fraction of WORK that must be sequential (1 processor only)
• q2 = fraction that can use at most 2 processors
• (1 - q1 - q2) = fraction that can use unbounded processors

---

1.1.1 Speedup Upper Bound (10 points)

> Provide the best possible upper bound on Speedup as a function of q1 and q2.

Your Answer:

Let W be the total work. With P processors (P → ∞):

1. Time for each component: - q1 fraction: must run on 1 processor → time = q1 * W - q2 fraction: can use at most 2 processors → best time = q2 * W / 2 - (1 - q1 - q2) fraction: unbounded processors → time → 0 as P → ∞

2. Total parallel time as P → ∞: T_par = q1·W + (q2/2)·W + 0 = W·(q1 + q2/2)

3. Speedup formula: Speedup = T_seq / T_par = W / [W·(q1 + q2/2)]

Best upper bound: Speedup ≤ 1 / (q1 + q2/2)

---

1.1.2 Justification with Special Cases (5 points)

> Justify your answer using cases when q1=0, q2=0, q1=1, or q2=1.

Your Answer:

Justification:

• q1=1, q2=0: Speedup ≤ 1. Correct — the entire program must run on 1 processor.
• q1=0, q2=1: Speedup ≤ 2. Correct — even with infinite processors, the 2-processor constraint limits us to 2x.
• q2=0: Speedup ≤ 1/q1. This is exactly standard Amdahl's Law.
• q1=0, q2=0: Speedup → ∞. Correct — perfectly parallel, all processors can be used.

The bound is tight because it is achievable: assign 1 processor to the q1 work, 2 processors to the q2 work (getting q2·W/2 time), and P processors to the rest (getting near-zero time). The fractions are disjoint so there is no overlap, and the total parallel time equals W·(q1 + q2/2).

---

1.2 Finish Accumulators (15 points)

Analyze the following Parallel Search algorithm:

count0 = 0;
accumulator a = new accumulator(SUM, int.class);
finish (a) {
    for (int i = 0; i <= N - M; i++)
    async {
        int j;
        for (j = 0; j < M; j++) if (text[i+j] != pattern[j]) break;
        if (j == M) { count0++; a.put(1); }
        count1 = a.get();
    }
}
count2 = a.get();

Where:

• N = length of text
• M = length of pattern
• Q = number of times pattern occurs in text

> What possible values can count0, count1, and count2 contain? Write answers in terms of M, N, and Q.

Your Answer:

count0:

• Possible values: Any integer from 0 to Q (i.e., {0, 1, 2, ..., Q})
• Explanation: count0++ is a non-atomic read-modify-write on a shared variable executed by multiple async tasks concurrently. This is a data race: two tasks can both read the same value of count0, both increment it, and write back the same incremented value — effectively losing an update. In the worst case, all Q increments are lost (count0 = 0). In the best case (unlikely sequential execution), all succeed (count0 = Q). Any value from 0 to Q is possible.

count1:

• Possible values: Any integer from 0 to Q (i.e., {0, 1, 2, ..., Q})
• Explanation: a.get() inside the finish block returns the current partial sum of accumulator a at that moment. Since async tasks run concurrently, when any given task calls a.get(), anywhere from 0 to Q of the a.put(1) calls may have already been committed. Multiple async tasks also write to count1 (itself a data race on a shared variable), so count1 holds the last value that was written. The last-writing task could have observed any partial sum from 0 to Q. Therefore count1 can be any value in {0, 1, ..., Q}.

count2:

• Possible values: Exactly Q
• Explanation: count2 = a.get() is called after the finish (a) block. The finish-with-accumulator guarantees: (1) all N-M+1 async tasks have fully completed, and (2) all values placed into accumulator a via a.put(1) have been summed into the accumulator. Exactly Q of the async tasks found the pattern and called a.put(1). Since the accumulator is a SUM type and all puts are fully committed before the finish returns, count2 = Q always.

---

Part 2: Report (10 points)

A. Design Summary

IdealParScoring:

The Smith-Waterman recurrence has a wavefront dependence structure: S[i,j] depends on S[i-1,j-1], S[i-1,j], and S[i,j-1]. All cells on the same anti-diagonal (where i+j = constant) are mutually independent and can be computed in parallel.

Implementation: process anti-diagonals d = 2 to xLength+yLength sequentially. For each diagonal, use a finish block containing one async task per cell. Each task calls doWork(1) (before computing the cell value) to register one unit of abstract work. This achieves exactly Work = xLength × yLength and CPL = xLength + yLength - 1 as required. No phasers are used (as required for Checkpoint 1).

UsefulParScoring:

Creating one async task per cell (as in IdealParScoring) has too much overhead for n=10,000. We use a block-based wavefront: partition the matrix into BLOCK_SIZE×BLOCK_SIZE (128×128) blocks. Blocks on the same block anti-diagonal are independent and each assigned one async task inside a finish block. Each task processes its block sequentially (good cache locality). Character indices are precomputed into int arrays to avoid repeated charMap() calls. This gives real speedup on 16 cores with minimal synchronization overhead.

SparseParScoring:

For n=10^5, storing the full n×m matrix requires ~40GB — impossible. We use three rotating anti-diagonal buffers of size O(n):

• diag2[i] = S[i][d-2-i] (two diagonals back, for diagonal term)
• diag1[i] = S[i][d-1-i] (one diagonal back, for top and left terms)
• diagCurr[i] = S[i][d-i] (being computed)

The recurrence becomes: diagCurr[i] = max(diag2[i-1] + M[xI][yJ], diag1[i-1] + M[xI][0], diag1[i] + M[0][yJ]).

For large diagonals (>= MIN_CHUNK_SIZE = 1000 cells), the work is split into multiple equal-sized chunks computed in parallel via async/finish. After each diagonal, the three buffers rotate. This achieves O(n) memory while maintaining useful parallelism across large diagonals.

---

B. Performance Measurements

Machine Specifications:

• CPU: Docker container (comp322-runner image)
• Cores: Available via numWorkerThreads()
• Memory: 8GB heap (set in pom.xml)

Ideal Parallelism Metrics (xLength=100, yLength=120):

Work = 100×120 = 12,000; CPL = 100+120-1 = 219; Parallelism = Work/CPL ≈ 54.8

Useful Parallel Speedup (string length = 10,000):

Sparse Parallel Speedup (string length = 100,000):

---

C. Discussion

UsefulParScoring: The block-based approach achieves good speedup by balancing parallelism with overhead. For n=10,000 with BLOCK_SIZE=128, the matrix has ~78×78 blocks. The peak block anti-diagonal contains ~78 parallel blocks, providing enough work for 16 cores. The sequential within-block computation ensures cache efficiency. The 8x speedup target is achievable because the computation is compute-bound and the block granularity is well-matched to 16 cores.

SparseParScoring: The memory constraint forces O(n) storage, enabling n=100,000 sequences. The tradeoff is that block-level parallelism (which exploits independence across multiple rows and columns simultaneously) is no longer available. Instead, we parallelize within each anti-diagonal by splitting it into chunks. For the largest diagonals (~100,000 cells), splitting into chunks of 1,000 gives up to 100 parallel tasks. On 16 cores, the 3x speedup target should be achievable since large diagonals dominate the runtime and have ample parallelism.

Wavefront parallelism: The anti-diagonal wavefront is the key structure for Smith-Waterman parallelization. The critical path length is O(n+m), giving theoretical parallelism = nm/(n+m) ≈ n/2 for square matrices. This means the algorithm is highly parallel in theory, but practical speedup is bounded by cores, memory bandwidth, and task-creation overhead. The block approach in UsefulParScoring most effectively exploits available parallelism in practice.