|dc.contributor.author||Aji, Ashwin Mandayam||en_US
|dc.description.abstract||With the emerging hybrid multi-core and many-core compute platforms delivering
unprecedented high performance within a single chip, and making rapid strides toward the
commodity processor market, they are widely expected to replace the
multi-core processors in the existing High-Performance Computing (HPC)
infrastructures, such as large scale clusters, grids and supercomputers.
On the other hand in the realm of bioinformatics, the size of genomic
databases is doubling every 12 months, and hence the need for novel approaches
to parallelize sequence search algorithms has become increasingly important.
This thesis puts a significant step forward in bridging the gap between
software and hardware by presenting an efficient and scalable model to
accelerate one of the popular sequence alignment algorithms by exploiting
multigrain parallelism that is exposed by the emerging multiprocessor architectures.
Specifically, we parallelize a
dynamic programming algorithm called Smith-Waterman both within and across multiple
Cell Broadband Engines and within an nVIDIA GeForce General Purpose Graphics
Processing Unit (GPGPU).
Cell Broadband Engine: We parallelize the Smith-Waterman algorithm
within a Cell node by performing a blocked data decomposition of the
dynamic programming matrix followed by pipelined execution of the blocks across the synergistic
processing elements (SPEs) of the Cell.
We also introduce
novel optimization methods that completely utilize the vector
processing power of the SPE. As a result, we achieve near-linear scalability
or near-constant efficiency for up to 16 SPEs on the dual-Cell QS20 blades, and
our design is highly scalable to more cores, if available.
We further extend this design to accelerate the Smith-Waterman algorithm
across nodes on both the IBM QS20 and the
PlayStation3 Cell cluster platforms and achieve a maximum speedup of 44,
when compared to the execution times on a single Cell node.
introduce an analytical model to accurately estimate the execution times of
parallel sequence alignments and wavefront algorithms in
general on the Cell cluster platforms.
Lastly, we contribute and evaluate TOSS -- a Throughput-Oriented Sequence
Scheduler, which leverages the performance prediction model and
dynamically partitions the available processing elements to
simultaneously align multiple sequences. This scheme succeeds in aligning more sequences per unit
time with an improvement of 33.5% over the
naive first-come, first-serve (FCFS) scheduler.
nVIDIA GPGPU: We parallelize the Smith-Waterman algorithm on the GPGPU
by optimizing the code in stages, which include optimal data
layout strategies, coalesced memory accesses and blocked data decomposition techniques.
Results show that our methods provide a maximum speedup of 3.6 on
the nVIDIA GPGPU when compared to the performance of the naive
implementation of Smith-Waterman.||en_US
|dc.rights||I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee.
I hereby grant to Virginia Tech or its agents the non-exclusive
license to archive and make accessible, under the conditions specified below,
my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.||en_US
|dc.subject||Cell Broadband Engine||en_US
|dc.title||Exploiting Multigrain Parallelism in Pairwise Sequence Search on Emergent CMP Architectures||en_US
|dc.description.degree||Master of Science||en_US
|thesis.degree.name||Master of Science||en_US
|thesis.degree.grantor||Virginia Polytechnic Institute and State University||en_US
|dc.contributor.committeemember||Cameron, Kirk W.||en_US
|dc.contributor.committeemember||Nikolopoulos, Dimitrios S.||en_US