Accelerating Sequence Calculations on Parallel GPU Architecture
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis, I have implemented a GPU (graphics processor unit) based sequencing algorithm that finds a sequence or order among data points to optimize a given objective. I have studied the sequencing algorithm as a path planner for an unmanned aerial vehicle (UAV) and also, a basecaller for a miniature DNA sequencer. Parallel implementation utilizing GPU enables faster processing and decision making that are important when data is quite large and a real-time response is critical e.g., in UAV based transportation. The goal of using UAV in my thesis is to construct a wireless sensor network in a remote location by deploying wireless sensor nodes. The proposed path planner, also known as a sequencer, is designed to find the shortest path that is also a safe path using travelling salesman problem. A path is considered safe when the vehicle would not collide with any obstacle. Two sets of heuristic algorithms, one for generating a sequence of waypoints (sequence generator) and another one for constructing a path between two waypoints (path explorer), are used to find the near optimal solution. The highly-parallel multicore GPU is used for the real-time implementation that offloads compute-intensive portions from the traditional CPU to the GPU to make the decision-making process faster. In this thesis, the parallel execution of the sequence generator and the path explorer achieved a 4.82x and 164x speed-up compared to the CPU-only approach respectively. The second sequencer is a palm-sized miniature DNA sequencer, the so-called MinION device. In the case of the MinION, a vast multitude of DNA strands are introduced into the device and converted into noisy electronic time-series signals; these measurements are essentially physical signatures related to the molecular make-up of the sensed DNA. Among a long "pipeline" of analysis steps to be performed on such measurement sequences, the first, and arguably most intensive, is the so-called basecalling step which analyzes the time-series and converts it into the equivalent monomeric base of the DNA under test using the Viterbi algorithm.