Basic Local Alignment Search Tool (BLAST) is an important similarity search tool in bioinformatics. It is used to find biologically similar sequences to the given query sequence from the database of the annotated sequences. For high throughput processing of huge number of query sequences, which are generated by automatic DNA sequencing machines, there have been many studies on parallel batch processing of sequence similarity search using BLAST. As the number of sequences in the database increases at an exponential rate, the search speed of BLAST becomes the most critical performance parameter.
Although a parallel version of BLAST, which exploits intra-search level parallelism, has been developed by National Center for Biotechnology Information (NCBI) at National Institute of Health (NIH) and Washington University, it is targeted only on symmetric multiprocessors (SMP) machines. Since SMP machine has a limitation on the number of processors due to its architecture, the speedup of BLAST that can be achieved solely on one SMP machine also faces inevitable performance limitation. Hence, the speedup improvement of BLAST on the SMP machine is not sufficient to cope with processing a large amount of sequences that are newly added into the database at an exponential rate. In order to use more processors for more speedup of BLAST, we consider PC cluster system as an alternative to SMP machine.
This dissertation presents $\emph{Hyper-BLAST}$, a parallelized BLAST on cluster system, which can provides scalable speedup in terms of response time. $\emph{Hyper-BLAST}$ adds inter-node parallel execution techniques to the intra-search level parallelism that is used by NCBI BLAST. Logical partitioning of database is used to prepare and enable the inter-node parallel execution of intra-search level parallelism. In our parallelized BLAST on cluster system, the master node drives remote nodes to search similar sequence from logically partitioned database and collects minimal but complete data set for reporting the search results. The extension of intra-search parallelism enables us to use more processors for similarity search using BLAST and gives more speedup of individual query sequence search. Compared to the cost of SMP machines, cluster system with same computation capability can be built with fewer budgets and \emph{Hyper-BLAST} on cluster system provides fast similarity search with moderate cost.
From the comprehensive performance evaluation with different configurations of cluster systems, we observed scalable speedup on various configuration of cluster systems. From the experimental data, we also devise speedup function model that can describe speedup function of \emph{Hyper-BLAST} on cluster system. We expect \emph{Hyper-BLAST} can accelerate the biological studies that include sequence similarity analysis as an intermediate step.
BLAST (Basic Local Alignment Search Tool)는 서열간의 유사성을 평가하여 주어진 서열과 유사성을 가진 서열을 데이타베이스상에서 찾아주는 프로그램이다. 유사성을 가진 서열을 검색하는 작업을 통하여 미지의 서열에 대한 생물학적인 기능을 예측하거나, 서열 데이타 베이스에 등록되어 있지 않은 새로운 서열의 발견을 확인할 수 있으므로, BLAST를 사용한 서열 유사성 검색은 많은 유전 관련 연구에서 기초가 된다.
미국 국립보건원의 NCBI에서 배포하는 BLAST프로그램은 대칭형 다중 프로세서 (SMP: Symmetric MultiProcessor)상에서 유사성 검색을 병렬로 수행할 수 있도록 설계되어 있다. 따라서 클러스터 시스템과 같은 분산 메모리 기반의 다중 프로세서 시스템에서는 시스템내의 모든 프로세서 자원을 충분히 활용할 수 없는 문제점을 가지고 있다.
본 연구에서는 NCBI에서 배포하는 BLAST프로그램을 클러스터 시스템의 모든 프로세서 자원을 사용하여 보다 높은 정도의 속도 향상을 얻을 수 있는 클러스터 시스템에서 병렬화된 BLAST를 설계및 개발하였다.
클러스터 시스템상에서 병렬화된 BLAST프로그램 개발을 위하여 먼저 대칭형 다중 프로세서 시스템상에서 리눅스및 솔라리스 두가지 운영체제상에서의 성능을 측정한 결과 리눅스 운영체제가 좀 더 좋은 반응시간을 제공함을 확인하였다. 클러스터 시스템은 분산형 메모리에 기반하고 있으므로 효과적인 병렬화를 위해서는 클러스터 노드간의 데이타 통신량을 최소화하여야 한다. 이를 위하여 BLAST에서 사용하는 내부 자료구조및 알고리즘을 분석하여 노드간 통신을 위한 통신규약및 메시지 포맷을 설계하였다. 클러스터 시스템상의 각각의 노드는 서열 데이타베이스를 자신의 컴퓨팅 능력에 따라 논리적으로 분할된 서브 데이타베이스내에서 주어진 입릭 서열과 유사한 서열들을 검색한 후 마스터 노드에 전송하고 마스터 노드는 슬레이브 노드및 자신이 검색한 결과를 취합하여 유사성 검색 결과 보고서를 출력한다.
클러스터 시스템상에서 병렬화된 BLAST의 성능 평가를 위하여 8-way 4-노드 클러스터 시스템, 2-way 8-노드 클러스터 시스템과 1-way 64노드 클러스터 시스템상에서 실행시간, 속도 향상 및 병렬화에 따른 효율성을 측정한 결과, 만족스러운 성능 향상 결과를 확인할 수 있었다. 또한 속도 향상 측정 결과를 이용하여 클러스터 시스템용 병렬 BLAST의 속도 향상 모델을 개발하여 속도 향상 정도를 좀더 정확하게 예측할 수 있도록 하였다.
본 연구를 통하여 개발된 클러스터 시스템용 병렬 BLAST는 가격대비 성능면에서 대칭형 다중 프로세서 시스템상의 NCBI BLAST보다 우수할 뿐만 아니라 더 많은 속도 향상을 제공함으로써 BLAST를 사용하는 여타 유전자 분석 과정에 도움을 줄 수 있을 것으로 기대된다.
