지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 지도교수
- 심정섭
- 발행연도
- 2017
- 저작권
- 인하대학교 논문은 저작권에 의해 보호받습니다.
이용수2
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
대표문자열 문제는 다중 서열 배치를 위해 사용될 수 있는 방법 중 하나로, 주어진 문자열 집합 S를 대표하는 한 문자열을 찾는 문제이다. 환형문자열은 마지막 글자와 첫 글자가 연결되어 원 모양을 이루는 특수한 형태의 문자열이다. 본 논문에서는 O(n)개의 쓰레드를 사용하여 환형문자열과 관련된 두 개의 문제를 병렬적으로 해결하는 알고리즘을 제시한다. 첫 번째 문제는 길이 n인 환형문자열 3개로 구성된 S에 대한 거리합 및 거리반경을 모두 최적화하는 대표문자열 문제(CSR3 문제)이다. 본 논문에서 제시하는 첫 번째 병렬 알고리즘은 CSR3 문제를 O(|Σ|nlogn) 시간에 해결한다. 이 때, Σ는 S에 포함된 문자열들을 구성하는 문자들의 집합이다. 두 번째 문제는 길이 n인 환형문자열 4개로 구성된 S에 대한 거리합만을 최적화하는 대표문자열 문제(CS4 문제)이다. 본 논문에서 제시하는 두 번째 병렬 알고리즘은 CS4 문제를 O(n^2 log n)시간에 해결한다. 또한 본 논문에서는 엔비디아의 CUDA 플랫폼을 이용해 병렬 알고리즘을 구현하고, 순차 알고리즘과 수행 시간을 비교하였다. 그 결과, 병렬 알고리즘은 순차 알고리즘에 비해 최대 24.5배 빠르게 수행되었다.
목차
요약 - ivAbstract - v제1장 서론 - 1제2장 관련 연구 - 52.1. 선형문자열 집합에 대한 거리합 및 거리반경의 계산 - 52.2. CSR3 알고리즘 및 CS4 알고리즘 - 6제3장 병렬화 전략 및 구현 - 10제4장 실험 결과 및 분석 - 13제5장 결론 - 16참고 문헌 - 17
최근 본 자료
댓글(0)
0