| 한글제목(Korean Title) |
CUDA 환경에서 임의 편위 검증의 병렬 구현 |
| 영문제목(English Title) |
Parallel Implementation of Random Excursions Test in CUDA Environment |
| 저자(Author) |
손창환
박우열
김형균
한경숙
표창우
Changhwan Son
Wooyeol Park
HyeongGyun Kim
KyungSook Han
Changwoo Pyo
|
| 원문수록처(Citation) |
VOL 41 NO. 02 PP. 0057 ~ 0066 (2014. 04) |
한글내용
(Korean Abstract) |
본 논문은 NIST 통계적 난수 검증 모음에 속하는 임의 편위(偏位, random excursions) 검증 프로그램을 CUDA 환경에서 병렬화 하고, 성능 향상을 측정한 결과를 보이고 있다. 문제의 추상적 수준에서는 데이터-병렬성이 존재하나, NIST의 구현에서는 사용되는 희소 행렬 구조가 의존 관계를 유발시켜 활용되지 못한다. 자료 구조 변환을 통해 반복문 수준으로 병렬성을 노출시켜 병렬 스캔과 스캐터 기법 적용이 가능하게 하였다. 또한, 전역 메모리 접근을 최적화하여 병렬화된 부분이 추가적인 성능 향상을 보일 수 있게 하였다. 병렬화된 임의 편위 검증은 순차적인 구현과 비교할 때 약 44배의 향상된 실행 성능을 보였다. 이진 난수의 검증 속도가 증가하여 수분 내에 가능하게 되면 대규모 이진 난수 발생 때 임의성 검증을 동시에 진행할 수 있어 암호 키 보안 향상에 기여할 것으로 예상된다.
|
영문내용
(English Abstract) |
This paper presents parallelization of the random excursions test, which is one of the NIST’s statistical test suite for random bit sequences, and experimental results of measured speedup. Data-parallel property underlies the random excursions test at abstract level of the problem, but the potential cannot be utilized because of the data dependence imposed by the sparse matrix structure adopted by the NIST’s original program. We have exposed data parallelism by transforming the sparse matrix structure. This makes it possible to apply parallel scan and scatter techniques. The parallelized random excursions test shows performance improved by 44 times over the sequential version. If the speed of randomness test would improve to the order of minutes, we can test random bit sequences on the fly when the sequences are generated on a huge scale. This would contribute to level up security of encryption keys.
|
| 키워드(Keyword) |
임의 편위 검증
병렬 구현
난수 검증
희소행렬
random excursions test
parallel implementation
randomness test
sparse matrix
|
| 파일첨부 |
PDF 다운로드
|
