Parallelization and performance optimization of bioinformatics and biomedical applications targeted to advanced computer architectures

In this dissertation, we focus on three representative applications targeted to advanced computer architectures: parallel Hmmpfam (Hidden Markov Model for Protein FAMily database search) on cluster computing, parallel SPACE RIP (Sensitivity Profiles From an Array of Coils for Encoding and Reconstruction in Parallel) on Cyclops-64, a state-of-the-art multiprocessor-on-a-chip computer architecture, and halftoning-based tactile graphics.; Hmmpfam is one of the widely used bioinformatics tools for searching a single sequence against a protein family database. We analyzed the Hmmpfam program structure, proposed a new task decomposition scheme to reduce data communication and implemented a scalable and robust cluster-based parallel Hmmpfam using the EARTH (Efficient Architecture for Running Threads) model.; SPACE RIP, one of the parallel imaging techniques, utilizes a number of receiver coils to simultaneously acquire data, thus reducing the acquisition time. We implemented the parallelization and optimization of SPACE RIP at three levels. The top level is the loop level parallelization, which decomposes SPACE RIP into many tasks of a singular value decomposition (SVD) problem. The middle level parallelizes the SVD problem using the one-sided Jacobi algorithm and is implemented on Cyclops-64. At this level, an SVD problem is decomposed into many matrix column rotation routines. The bottom level further optimizes the matrix column rotation routine using several memory preloading or loop unrolling approaches. We developed a performance model for the dissection of total execution cycles into four parts and used this model to compare different memory access approaches.; We introduced halftoning algorithms into the field of tactile imaging and implemented four different multilevel halftoning algorithms in the TIGER (Tactile Graphics Embosser) printer, a widely used embossing printer designed to produce tactile text and graphics for visually impaired individuals. Digital halftoning creates the illusion of a continuous-tone image from the judicious arrangement of binary picture elements. We exploited the TIGER tactile printer's variable-height punching ability to convert graphics to multilevel halftoning tactile texture patterns. We conducted experiments to compare the halftoning-based approach with the simple, commonly utilized thresholding-based approach and observed that the halftoning-based approach achieves significant improvement in terms of its texture pattern discrimination ability.