Improving Cytogenetic Search with GPUs Using Different String Matching Schemes

Cytogenetic data involves analysis of chromosomes structure using karyotyping. Current cytogenetic data of patients in a hospital are very large. A physician needs to search and analyses these data for typical aberration. This paper presents the approach to speedup large cytogenetic data search with GPUs. It utilizes the parallel threads in GPUs which concurrently look for a typical string. The two search schemes are parallelized and their performances are compared. Different search scheme can be parallelized in the same manner. The experimental results show that the speedup up to 15 times can be achieved compared to the sequential version even for large number of strings searched. With the help of shared memory, parallel string search can be improved further by 8 %. However, the shared memory has the limited size which cannot hold large number of strings. The percentage of data transfer time can be reduced if more strings are searched; i.e. more work load per thread. Using a more optimized string matching scheme leads to lower speedup due to the overhead of precomputing of state tables and occupies more GPU memory due to these tables. Thus, due to the nature of GPUs that have many concurrent threads, separate and smaller memory, the simple algorithm for a thread may be good enough. The optimization may be focused on the GPU-related issues such as memory coalesce, thread divergence etc. to improve the speedup further. We also present the application of the GPU string search for finding typical aberrations, and extracting the relevant data from patients’ record for further analysis.