Á¤º¸°úÇÐȸ ³í¹®Áö A : ½Ã½ºÅÛ ¹× ÀÌ·Ð
ÇѱÛÁ¦¸ñ(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 ´Ù¿î·Îµå
|