선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이에 본 논문에서는 CPU와 GPU 환경에서 HIGHT의 소프트웨어 구현을 고속화하기 위한 다양한 방법을 시도하고 성능을 평가한다. 본 논문은 HIGHT의 GPU 구현을 시도한 최초 결과이다.
- 이 절에서는 본 논문에서 구현 및 실험에 사용한 NVIDIA의 GTX470 모델을 기준으로 GPU의 구조에 대해 살펴본다.
- HIGHT가 비록 저전력, 경량화를 요구하는 컴퓨팅 환경을 위한 암호 알고리즘이지만 암호분석관점에서 또는 HIGHT를 사용하는 센서의 데이터를 다량으로 처리하는 중앙 서버 등에서는 HIGHT의 소프트웨어 최적화 기술이 반드시 필요하다. 이에 본 논문에서는 CPU와 GPU 환경에서 HIGHT의 소프트웨어 구현을 고속화하기 위한 다양한 방법을 시도하고 성능을 평가한다. 본 논문은 HIGHT의 GPU 구현을 시도한 최초 결과이다.
제안 방법
- GPU상의 HIGHT 구현은 KISA에서 제공해주는 소스코드와 앞 장에서 다뤘던 바이트 슬라이싱 코드를 CUDA 라이브러리를 이용하여 GPU 프로그램으로 포팅하는 방식으로 구현하였다.
- 본 장에서는 GPU 환경에서의 HIGHT 고속화 구현에 대해 다룬다. KISA에서 제공해주는 소스코드와 앞 장에서 다뤘던 바이트 슬라이싱 구현을 NVIDIA의 CUDA 라이브러리[14]를 이용해 GPU 프로그램으로 포팅하는 방법으로 구현하였다. GPU는 레지스터의 크기가 32비트로 크지 않고, 개수도 제한적이어서 비트 슬라이싱 구현에 적합하지 않으므로 비트 슬라이싱 기법의 GPU 구현은 고려하지 않는다.
- 한편 GPU에서는 복잡한 쓰레드 및 메모리 계층구조로 인해 최적화에 고려할 요소가 더 많은데, 본 논문에서는 통합 접근(coalesced access) 기법을 이용하여 캐시 히트 비율을 높이고 각종 참조 테이블과 서브키 등 자주 활용되는 데이터는 가능하면 온 칩 메모리를 사용하도록 하여 데이터 접근 시간을 최소화하였다. 또한 여러 쓰레드에서 공통적으로 사용되는 데이터를 전역 메모리에서 공유 메모리로 복사할 때 각 쓰레드가 오버헤드를 병렬적으로 분담할 수 있도록 멀티 프로세서당 쓰레드 개수를 최적화하였다. 구현기법 측면에서는 GPU는 레지스터 크기가 32비트로 작고 개수도 제한적이어서 비트 슬라이싱 구현에 적합하지 않으므로 GPU 상에서는 바이트 슬라이싱 기법만을 고려하였다.
- HIGHT는 XOR, 덧셈, 순환 이동 등의 간단한 연산들로 이루어져 있기 때문에 비트 슬라이싱을 적용하면 효율적으로 구현이 가능하다. 본 논문에서는 32비트 OS 환경의 CPU와 64비트 OS 환경의 CPU로 나눠 비트 슬라이싱 기반으로 HIGHT를 구현하였다. 32비트 OS 환경의 CPU에서는 사용하는 레지스터의 크기가 32비트 이고, 64비트 OS 환경의 CPU에서는 레지스터의 크기가 64비트이다.
- 바이트 슬라이싱은 같은 순서의 바이트들을 묶어서 한 번의 수행으로 여러 블록이 동시에 수행되는 것과 같은 효과를 보여주는 기법이며, HIGHT와 같이 바이트 단위로 연산되는 알고리즘에 적합하다. 본 논문에서는 CPU 상에서 비트 슬라이싱 및 바이트 슬라이싱 기법을 모두 구현하여 기존 구현과 비교하였다.
- 본 논문에서는 HIGHT의 바이트 슬라이싱을 비트슬라이싱과 마찬가지로 32비트 OS 환경과 64비트 OS 환경에서 구현하였다. 32비트 환경의 경우 하나의 레지스터에 네 개의 바이트를 담을 수 있으나, 실제로는 덧셈 연산에서 캐리가 발생하여 다른 블록의 바이트 값에 영향을 끼칠 수 있으므로 각 바이트 사이에 최소 1비트의 여유 공간이 주어져야 한다.
- 본 논문에서는 비트 슬라이싱 및 바이트 슬라이싱 기법을 적용하여 CPU와 GPU 환경에서 각각 HIGHT 알고리즘을 최적화 구현하였다. 비트 슬라이싱 및 바이트 슬라이싱 기법을 CPU에서 구현한 결과기존 구현보다 최대 2.
- HIGHT는 128비트 키, 64비트 평문으로부터 64비트 암호문을 출력한다. 제한적 자원을 갖는 환경에서 구현될 수 있도록 8비트 단위의 기본적인 산술 연산들인 XOR, 덧셈, 순환 이동만으로 설계되었다. HIGHT는 128비트 키를 입력으로 받아 8바이트의 화이트닝키와 128바이트의 서브키를 생성하여 초기변환과 각 라운드 연산에 사용한다.
- 한편 GPU에서는 복잡한 쓰레드 및 메모리 계층구조로 인해 최적화에 고려할 요소가 더 많은데, 본 논문에서는 통합 접근(coalesced access) 기법을 이용하여 캐시 히트 비율을 높이고 각종 참조 테이블과 서브키 등 자주 활용되는 데이터는 가능하면 온 칩 메모리를 사용하도록 하여 데이터 접근 시간을 최소화하였다. 또한 여러 쓰레드에서 공통적으로 사용되는 데이터를 전역 메모리에서 공유 메모리로 복사할 때 각 쓰레드가 오버헤드를 병렬적으로 분담할 수 있도록 멀티 프로세서당 쓰레드 개수를 최적화하였다.
대상 데이터
- 256개 이상의 쓰레드를 사용하면 각 테이블을 복사하기 위해 한 쓰레드가 한 개의데이터만 복사하면 된다. 256보다 작은 192를 제외하고 최적의 성능을 발휘할 수 있는 256, 512, 768의 값을 실험적으로 적용하여 쓰레드의 개수를 결정하였다. 실험 결과 기존 구현과 바이트 슬라이싱 기법을 적용한 구현 모두 768의 쓰레드 개수를 선언했을 때 더 좋은 성능을 보여주어 이 결과를 이용하였다.
- 실험은 2.67GHz의 클럭을 지원하는 Intel core i7 920 CPU와 607MHz 클럭 및 1280MB 메모리를 지원하는 NVIDIA GeForce GTX 470 GPU 환경에서 수행하였다. 수행한 결과는 키 스케줄링을 포함하지 않는 순수 암호화 연산에 대한 속도이다.
- 이 연산이 자칫 오버헤드로 작용할 수도 있지만 공유 메모리에서 사용되는 데이터는 주로 같은 블록 내에 속한 모든 쓰레드들이 함께 공유하므로 복사할 때 각 쓰레드 별로 복사할 데이터를 나눠 할당해 주면 쓰레드 당 한 번 또는 두 번 정도의 데이터 복사만 하면 된다. 평문 데이터를 읽어와 연산을 할 때 빠른 연산을 하기위해 레지스터를 활용하는데, HIGHT는 64비트의 데이터가 바이트 단위로 연산되므로 이를 위해 8개의 레지스터를 사용한다.
이론/모형
- 본장에서는 CPU 환경에서의 HIGHT 고속화 구현에 대해서 다룬다. 본 논문에서는 비트 슬라이싱 기법과 바이트 슬라이싱 기법을 적용하여 구현하였으며, 아래에서는 이들에 대해 각각 설명한다.
- 본 논문에서는 우선 비트 슬라이싱(bit-slicing)및 바이트 슬라이싱(byte-slicing) 기법을 이용하였다. 비트 슬라이싱 기법은 Eli Biham에 의해 소개되었으며[12], DES, AES 등의 주요 암호 알고리즘 구현에 적용된 바 있다[12][13].
- 이 연산 후 상위 5비트에 대한 데이터만 얻게 되므로, 하위 3비트의 값을 얻기 위해 오른쪽으로 5비트 쉬프트하고 마스크 연산을 준다. 순환 이동 연산이 사용되는 F0, F1함수는 기존 구현에서 table lookup 방식을 이용하여 구현되었다. 32비트 환경에서의 바이트 슬라이싱 구현 역시 순환 이동 연산을 통한 on-the-fly 계산보다 table lookup 방식을 이용하는 것이 더 효율적이다.
- 입력으로 들어오는 평문과 최종 출력으로 나오게 되는 암호문은 처음과 마지막 한 번씩만 메모리에 접근하게 되므로 전역 메모리를 이용한다. 전역 메모리에서 데이터를 읽어올 때 캐시 히트(cache hit) 효과를 최대화하기 위하여 통합 접근(coalesced access)기법을 적용하여 구현하였다.
성능/효과
- CPU 환경에서의 실험 결과는 [표 1]과 같다. 32비트 환경과 64비트 환경에서 모두 기존 구현보다 비트 슬라이싱, 바이트 슬라이싱 구현이 더 좋은 성능을 보여주는 것을 볼 수 있다. 또한 이 결과를 통해 레지스터의 크기가 클수록 더 좋은 성능을 얻을 수 있음을 확인할 수 있으며, 특히 64비트 환경에서는 바이트 슬라이싱보다 비트 슬라이싱이 월등한 성능을 보임을 확인할 수 있다.
- 기존 구현도 덧셈과 마스크 연산으로 이뤄져 있기 때문에 연산량의 차이가 없으나, 바이트 슬라이싱 구현에서는 여러 블록이 동시에 연산되므로 더 빠르다. 3개의 블록이 동시에 연산되는 32비트 환경에서는 블록 당 연산 횟수가 약 0.67번이고, 7개 블록이 동시에 연산되는 64비트 환경에서는 블록 당 연산횟수가 약 0.29번이다. 기존 구현에서 블록 당 2번의 연산을 하는 것과 비교하면 속도 개선 효과가 큰 것을 쉽게 확인할 수 있다.
- 따라서 64비트 바이트 슬라이싱 구현에서는 순환 이동 연산을 이용해 직접 F0, F1 함수의 값을 계산한다. 64비트환경의 구현에서는 묶어놓은 7개의 블록 데이터들 사이에 1비트의 여유 공간이 있으므로 1비트 차이의 쉬프트 연산들을 묶어서 처리하면 마스크 연산의 횟수를 줄일 수 있으며, 결과적으로 64비트 환경에서 F0, F1의 값을 얻기 위해 15번의 연산이 필요하다.
- 4배의 성능을 얻을 수 있었다. CPU 구현은 32비트 OS 환경과 64비트 OS 환경으로 나눠서 구현 및 실험하였으며, 이들에 대한 결과비교를 통해 레지스터의 크기가 클수록 더 좋은 성능을 보여주는 것 또한 확인할 수 있었다. GPU 구현의 경우 레지스터 크기가 32비트로 비교적 크지 않고 레지스터의 개수 또한 제한적이므로 비트 슬라이싱 기법의 적용이 적합하지 않으며, 비교적 적은 양의 레지스터만으로 구현이 가능한 바이트 슬라이싱을 이용할 경우 KISA 소스코드를 단순히 포팅한 것에 비해 약 1.
- CPU 구현은 32비트 OS 환경과 64비트 OS 환경으로 나눠서 구현 및 실험하였으며, 이들에 대한 결과비교를 통해 레지스터의 크기가 클수록 더 좋은 성능을 보여주는 것 또한 확인할 수 있었다. GPU 구현의 경우 레지스터 크기가 32비트로 비교적 크지 않고 레지스터의 개수 또한 제한적이므로 비트 슬라이싱 기법의 적용이 적합하지 않으며, 비교적 적은 양의 레지스터만으로 구현이 가능한 바이트 슬라이싱을 이용할 경우 KISA 소스코드를 단순히 포팅한 것에 비해 약 1.2배 빠름을 확인할 수 있었다.
- 62Gbps보다 높은 성능을 얻을 수 있었다. GPU에서는 NVIDIA사에서 제공해주는 CUDA 라이브러리[14]를 이용하여 구현하였는데, KISA에서 제공하는 CPU용 소스코드를 NVIDIA GeForce GTX 470 GPU에 포팅했을 때 38Gbps의 성능을 보인 데 비해, 바이트 슬라이싱을 추가로 적용할 경우 46Gbps로 더 좋은 성능을 얻을 수 있었다. CPU와 GPU 간의 성능을 비교하면 약 31배 빠름을 확인할 수 있다.
- 또한 이 결과를 통해 레지스터의 크기가 클수록 더 좋은 성능을 얻을 수 있음을 확인할 수 있으며, 특히 64비트 환경에서는 바이트 슬라이싱보다 비트 슬라이싱이 월등한 성능을 보임을 확인할 수 있다. 결과적으로 비트 슬라이싱을 이용한 구현은 KISA의 소스코드와 비교하여 32비트 환경에서는 약 1.7배, 64비트 환경에서는 약 2.4배의 성능을 보여준다.
- GTX470의 경우는 비교적 최신모델로 자원이 여유롭기 때문에 HIGHT 구현 시 어떤 조합을 사용하더라도 필요한 자원이 모두 지원되는 것을 확인할 수 있다. 다만, 한 개의 멀티프로세서가 최대 1536개의 쓰레드를 사용할 수 있으므로, 쓰레드의 개수를 192,256, 512, 768 등의 크기로 선언하여 구현해야 모든 쓰레드를 사용할 수 있어 최적의 성능을 보여준다. 한편 F0, F1 함수를 공유 메모리에 복사할 때 오버헤드를 최소로 하기 위해 256개 이상의 쓰레드를 선언하여 사용하는 것이 좋다.
- 레지스터의 크기에 따라 동시에 수행할 수 있는 블록의 개수가 결정되므로 레지스터의 크기가 클수록 유리하고, 레지스터 수가 적으면 일부 데이터를 메모리에 저장하는 오버헤드가 발생하므로 레지스터의 개수가 많을수록 유리하다. 또한 비트 슬라이싱 구현은 하드웨어 구현과 구조가 유사하므로 대상 알고리즘을 하드웨어로 작게 구현 가능할수록 이 방법을 이용하여 효율적인 구현을 할 수 있다.
- 32비트 환경과 64비트 환경에서 모두 기존 구현보다 비트 슬라이싱, 바이트 슬라이싱 구현이 더 좋은 성능을 보여주는 것을 볼 수 있다. 또한 이 결과를 통해 레지스터의 크기가 클수록 더 좋은 성능을 얻을 수 있음을 확인할 수 있으며, 특히 64비트 환경에서는 바이트 슬라이싱보다 비트 슬라이싱이 월등한 성능을 보임을 확인할 수 있다. 결과적으로 비트 슬라이싱을 이용한 구현은 KISA의 소스코드와 비교하여 32비트 환경에서는 약 1.
- 라운드 함수 단위로 살펴보면 기존 구현은 한 라운드 당 연산 횟수가 28번이고, 32비트 구현은 약 18.67번, 64비트 구현은 약 10.29번으로 기존 구현보다 더 적은 연산량을 보여준다. 이는 F0, F1의 값을 얻기 위해 연산의 횟수가 많이 늘어났지만 덧셈과 XOR 연산에서 연산의 횟수가 많이 줄어들기 때문이다.
- 통합접근 방식을 적용해 수행한 결과가 비통합 접근 방식으로 수행한 결과보다 더 향상된 결과를 얻을 수 있음을 확인할 수 있으며, 바이트 슬라이싱 기법을 적용한 구현이 KISA 소스코드를 포팅한 방법보다 더 빠른 결과를 보여주는 것을 확인할 수 있다. 바이트 슬라이싱 기법과 통합 접근 기법을 함께 적용한 구현이 가장 빠른 결과를 보여주며, 통합 접근 기법을 적용하여 KISA 소스코드를 포팅한 구현보다 약 1.2배 더 빠른 결과를 보여주는 것을 볼 수 있다. 한편, [표 1]과 [표2]의 결과를 비교해보면 GPU의 성능이 CPU에 비해 약 31배 가량으로 월등히 높은 것을 볼 수 있다.
- 본 논문의 구현 및 실험 결과, 64비트 CPU인 Intel core i7 920에서 비트 슬라이싱은 1.48Gbps, 바이트 슬라이싱은 0.98Gbps의 속도로, 한국인터넷진흥원(Korea Internet & Security Agency; 이하 KISA)에서 제공해주는 소스코드1)를 그대로 실행했을 때의 결과인 0.62Gbps보다 높은 성능을 얻을 수 있었다.
- 본 논문에서는 비트 슬라이싱 및 바이트 슬라이싱 기법을 적용하여 CPU와 GPU 환경에서 각각 HIGHT 알고리즘을 최적화 구현하였다. 비트 슬라이싱 및 바이트 슬라이싱 기법을 CPU에서 구현한 결과기존 구현보다 최대 2.4배의 성능을 얻을 수 있었다. CPU 구현은 32비트 OS 환경과 64비트 OS 환경으로 나눠서 구현 및 실험하였으며, 이들에 대한 결과비교를 통해 레지스터의 크기가 클수록 더 좋은 성능을 보여주는 것 또한 확인할 수 있었다.
- 256보다 작은 192를 제외하고 최적의 성능을 발휘할 수 있는 256, 512, 768의 값을 실험적으로 적용하여 쓰레드의 개수를 결정하였다. 실험 결과 기존 구현과 바이트 슬라이싱 기법을 적용한 구현 모두 768의 쓰레드 개수를 선언했을 때 더 좋은 성능을 보여주어 이 결과를 이용하였다.
- GPU 환경에서의 실험 결과는 [표 2]와 같다. 통합접근 방식을 적용해 수행한 결과가 비통합 접근 방식으로 수행한 결과보다 더 향상된 결과를 얻을 수 있음을 확인할 수 있으며, 바이트 슬라이싱 기법을 적용한 구현이 KISA 소스코드를 포팅한 방법보다 더 빠른 결과를 보여주는 것을 확인할 수 있다. 바이트 슬라이싱 기법과 통합 접근 기법을 함께 적용한 구현이 가장 빠른 결과를 보여주며, 통합 접근 기법을 적용하여 KISA 소스코드를 포팅한 구현보다 약 1.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.