http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Boyer-Moore 알고리즘을 위한 GPU상에서의 병렬 최적화
정요상(Yosang Jeong),쟌 느앗-프엉(Nhat-Phuong Tran),이명호(Myungho Lee),남덕윤(Dukyun Nam),김직수(Jik-Soo Kim),황순욱(Soonwook Hwang) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.2
Boyer-Moore 알고리즘은 컴퓨터 및 인터넷 보안, 바이오 인포매틱스 등의 응용프로그램에서 널리 활용되는 패턴매칭 알고리즘이다. 이 알고리즘은 방대한 양의 입력 데이터에 존재하는 특정한 하나의 패턴을 실시간에 검색해야하는 높은 계산 요구량으로 인하여 병렬 처리 및 성능 최적화가 필수적이다. 본 논문에서는 GPU를 활용하여 BM 알고리즘을 병렬 최적화하는 방법론을 제안한다. 방법론에 따라 알고리즘 cascading 기법을 적용하여 실행시간에 소요되는 매핑 오버헤드를 최소화하고, 멀티스레딩 효과를 극대화하여 스레드들간의 부하 부산을 향상시킴으로써 순차실행 대비 최대 45배의 성능향상을 얻었다. The Boyer-Moore algorithm is a single pattern string matching algorithm that is widely used in various applications such as computer and internet security, and bioinformatics. This algorithm is computationally demanding and requires high-performance parallel processing. In this paper, we propose a parallelization and performance optimization methodology for the BM algorithm on a GPU. Our methodology adopts an algorithmic cascading technique. This results in significant reductions in the mapping overheads for the threads participating in the parallel string matching. It also results in the efficient utilization of the multithreading capability of the GPU which improves the load balancing among threads. Our experimental results show that this approach achieves a 45-times speedup at maximum, in comparison with a serial execution.
Intel Xeon Phi 에서의 Aho-Corasick 알고리즘을 위한 메모리 친화적인 고성능 병렬화
쟌느앗프엉 ( Nhat-phuong Tran ),정요상 ( Yosang Jeong ),이명호 ( Myungho Lee ) 한국정보처리학회 2014 한국정보처리학회 학술대회논문집 Vol.21 No.1
Aho-Corasick (AC) algorithm is a multiple patterns string matching algorithm commonly used in many applications with real-time performance requirements. In this paper, we parallelize the AC algorithm on the Intel’s Many Integrated Core (MIC) Architecture, Xeon Phi Coprocessor. We propose a new technique to compress the Deterministic Finite Automaton structure which represents the set of pattern strings again which the input data is inspected for possible matches. The new technique reduces the cache misses and leads to significantly improved performance on Xeon Phi.