The bottleneck was not only computation

An algorithm can remain unchanged while the system around it crosses a resource boundary and becomes a different performance problem.

BLAST compares nucleotide or protein queries with databases of known sequences. In the memory-limited environment studied in 2002, performance was strong while the database could remain in physical memory. Once it grew beyond that boundary, the operating system repeatedly moved pages between memory and disk. CPU time was no longer the complete story; disk waiting and page replacement had entered the critical path.

The MSc insight

Do not partition only because processors are available. Partition so that each processor receives a working set its memory can hold.

A memory-aware parallel architecture

The database was divided into partitions sized for the memory available at each processing node. Every node searched its partition concurrently, after which the partial matches were gathered into a complete result. This produced two gains at once: comparison work was distributed, and the working set on each node could remain resident in memory.

Correctness still required complete coverage, meaningful global ranking, balanced work, memory-aware partition sizing and a merge step that did not discard significant matches. Parallelism was useful only if the scientific meaning of the original search survived.

Why speedup could become superlinear

With p processors, linear speedup is approximately p. Superlinear speedup means the measured ratio S(p) = T(1)/T(p) is greater than p. That sounds paradoxical only if we assume the parallel run is merely the serial run divided into equal CPU work.

Single memory-limited nodeT(1) ≈ compute + heavy swapping
p memory-aware nodesT(p) ≈ compute/p + communication + merge

In the single-node baseline, the database exceeded physical memory and incurred substantial swapping. After partitioning, each node operated on a smaller resident working set. The parallel system therefore removed a cost that existed disproportionately in the baseline. It did not create computation from nothing; it changed the machine's operating regime.

S(p) = T(1) / T(p) > p

This can occur when the swapping eliminated from the baseline is larger than the communication, coordination and merge overhead introduced by parallel execution.

What the claim does—and does not—mean

The reported result belongs to the implemented 2002 memory-limited environment. Superlinear speedup is not guaranteed for every database, machine or node count. A reproducible comparison must state memory capacity, database and partition sizes, timing boundary, storage behaviour, communication cost and equivalence of returned results.

The enduring lesson is broader than BLAST: when a system crosses the memory hierarchy, performance engineering must reason about data placement as carefully as it reasons about the algorithm.

MSc research record

  • Title: A Parallel Processing System for a BLAST Program
  • Author: Warin Wattanapornprom
  • Degree: M.Sc. in Computer Science
  • Institution: Chulalongkorn University
  • Academic year: 2002
  • Advisor: Assoc. Prof. Prabhas Chongstitvatana
  • Co-advisor: Dr. Natawut Nupairoj
  • ISBN: 974-17-1195-6

Download the archived MSc thesis PDF

Return to warin.me