지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 지도교수
- 심정섭
- 발행연도
- 2013
- 저작권
- 인하대학교 논문은 저작권에 의해 보호받습니다.
이용수2
이 논문의 연구 히스토리 (4)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
근사문자열매칭 문제는 다양한 분야에서 연구되어 왔다. 최근에는 차세대염기서열분석의 비용과 시간을 줄이기 위해 빠른 근사문자열매칭 알고리즘들이 이용되고 있다. 근사문자열매칭은 문자열들의 오차를 측정하기 위해 편집거리와 같은 거리함수를 이용한다. 알파벳 ∑에 대한 길이가 각각 m, n인 두 문자열 X와 Y의 편집거리는 X를 Y로 변환하기 위해 필요한 최소 편집연산의 수로 정의된다. 두 문자열의 편집거리는 잘 알려진 동적프로그래밍을 이용하여 O(mn) 시간과 공간에 계산할 수 있으며, 4-러시안 알고리즘을 이용해서도 계산할 수 있다. 4-러시안 알고리즘은 블록 크기를 t라 할 때, 전처리 단계에서 O((3|∑|)^(2t)*t²) 시간과 O((3|∑|)^(2t)*t) 공간이 필요하며, 계산 단계에서 O(mn/t) 시간과 O(mn) 공간을 이용하여 편집거리를 계산하는 알고리즘이다. 본 논문에서는 4-러시안 알고리즘의 계산 단계를 병렬화하고 실험을 통해 CPU 기반의 순차적 알고리즘과 CUDA로 구현한 GPU 기반의 병렬 알고리즘의 수행시간을 비교한다. 본 논문에서 제시하는 4-러시안 알고리즘의 계산단계는 m/t개의 쓰레드를 사용하여 O(m+n) 시간에 편집거리를 계산한다. GPU 기반의 알고리즘이 CPU 기반의 알고리즘 보다 t=1일 때 약 10배 빠르고, t=2일 때 약 3배 빠른 결과를 보였다.
목차
제1장 서론 1제2장 편집거리 32.1. 용어정리 32.2. 문제정의 32.3. D-테이블 42.4. 4-러시안 알고리즘 6제3장 GPGPU 113.1. GPGPU의 개요 113.2. CUDA의 구조 133.3. CUDA 프로그래밍 모델 153.4. CUDA 프로그래밍 18제4장 4-러시안 알고리즘의 병렬계산 214.1. 데이터 종속성 214.2. 병렬 알고리즘 23제5장 실험 결과 및 분석 275.1 전처리 단계의 수행 결과 285.2 계산 단계의 수행 결과 29제6장 결론 31참고 문헌 32그림 목차[그림 2-1] 편집연산 4[그림 2-2] X = ababca와 Y = abcacdcac에 대한 D-테이블 5[그림 2-3] t = 3일 때, 4-러시안 알고리즘으로 계산한 편집거리 6[그림 2-4] 전처리된 룩업테이블을 사용한 4-러시안 계산 7[그림 2-5] 편집거리 값의 변환 8[그림 2-6] 룩업테이블 생성 ( = {a,b,.,z}, t = 4) 9[그림 3-1] CPU와 GPU에 대한 부동소수점 연산 12[그림 3-2] CPU와 GPU에 대한 메모리 대역폭 12[그림 3-3] 다양한 언어와 응용프로그램 프로그래밍 인터페이스를 지원하도록 설계된 CUDA 13[그림 3-4] 페르미 스트리밍 멀티프로세서 구조 14[그림 3-5] 듀얼 워프 스케줄러 구조 15[그림 3-6] CUDA의 쓰레드 계층구조 16[그림 3-7] CUDA의 메모리 계층구조 17[그림 4-1] D-테이블의 데이터 종속성 21[그림 4-2] 4-러시안 알고리즘의 데이터 종속성 22[그림 4-3] 4-러시안 알고리즘의 병렬화 방법 22[그림 4-4] 4-러시안 병렬 알고리즘을 이용한 편집거리 계산 23[그림 5-1] 블록 크기에 따른 수행시간 28[그림 5-2] C4R과 G4R의 성능 비교 (t=1, 1,000 <= m,n <= 10,000) 29[그림 5-3] C4R과 G4R의 성능 비교 (t=2, 1,000 <= m,n <= 10,000) 30표 목차[표 5-1] 실험 환경 27[표 5-2] t에 따른 룩업테이블의 메모리 크기 28
최근 본 자료
댓글(0)
0