선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 8-bit ATmega128 프로세서 환 경에서 효율적인 GF(2271), GF(2193)의 감산 알고리즘을 제안하였다. Fast reduction 알고리즘에서 반복적으로 일어나는 메모리의 호출과 저장으로 인한 비효율성을 개선하기 위해 [3]의 감산 알고리즘을 변형하여 사용하였다.
제안 방법
- 또한, ATmega128에서 제공하는 rotate right, rotate left 연산을 적극 활용하였다. Fast reduction 반복문에서의 1-bit shift와 7-bit shift를 한번의 rotate연산으로 처리함으로써 연산의 효율성을 높였다.
- )의 감산 알고리즘을 제안하였다. Fast reduction 알고리즘에서 반복적으로 일어나는 메모리의 호출과 저장으로 인한 비효율성을 개선하기 위해 [3]의 감산 알고리즘을 변형하여 사용하였다. 그러나 [3]의 감산 알고리즘과는 달리 감산 처리해야 될 상위 워드들을 미리 계산해서 중첩되는 워드들을 제거하였다.
- 레지스터 내부의 데이터에 대하여 수행되는 연산에는 1클럭 사이클만이 소요되는데 반하여, 메모리에 저장된 데이터를 레지스터로 로드하거나 연산의 결과값을 다시 메모리에 저장하는 데는 2클럭 사이클이 소모된다. 따라서 감산 알고리즘에 메모리 로드와 저장을 최소한으로 설계하여 어셈블리 언어로 구현하였다.
- 이를 통해 기존의 7-bit right shift(>>7)연산의 효과를 볼 수가 있다. 따라서 필요한 rotate 연산은 34번이지만 중간 값을 저장할 레지스터 개수가 제한적이라 여러 개의 블록으로 나누어 처리하여 총 41번의 rotate 연산으로 구현하였다. GF(2193)에서는 반대로 1-bit right shift를 최상위 워드부터 0번째까지 순차적으로 rotate right shift 명령어로 처리한다.
- 또한, ATmega128에서 제공하는 rotate right, rotate left 연산을 적극 활용하였다. Fast reduction 반복문에서의 1-bit shift와 7-bit shift를 한번의 rotate연산으로 처리함으로써 연산의 효율성을 높였다.
- 메모리로 저장하는 연산은 ‘C[0]’부터 ‘C[24]’까지 1회만 수행하여 감산 연산을 종료하였다.
- 본 논문에서 사용한 GF(2271), GF(2193)에서의 감산 연산은 삼항 혹은 오항 기약다항식을 이용하여 시프트 연산과 XOR(Exclusive -OR) 연산으로 구현 가능하다. 본 논문에서는 8-bit 프로세서 환경에서의 감산 연산 최적화를 위해 GF(2271) 상의 기약 다항식 f(x)=x271+x207+x175+x111+1과 GF(2193) 상에서의 기약다항식 f(x)=x193+x145+x129+x113+1을 선택하였다.
- 본 논문에서는 기존 감산 알고리즘의 반복문 사용 방식과는 달리 사전 연산을 통해 중복되어 사라지는 연산들을 제외하여 최종적인 감산 연산 결과 값을 해당 기약 다항식에 대해서 감산 알고리즘 테이블로 각각 Table 2, Table 4로 나타내었다. 각 Table에는 중복되는 워드들의 조합이 많이 발생한다는 사실을 발견할 수 있다.
- 제한된 환경에서의 감산 연산을 구현하기 위해 어셈블러 언어로 설계하여 26개의 레지스터를 적극적으로 활용하였고, 기본적으로 제공하는 ATmega12-8의 rotate shift 연산을 효율적으로 사용하여 감산 연산의 최적화를 이루었다. 결과적으로 최종적인 감산 결과 값에 나타난 중첩되는 워드 조합과 이를 이용한 레지스터의 효율적인 스케줄링, rotate 연산의 적극적인 활용 등을 통해 메모리 접근 연산의 최소화를 가능하게 하였다.
대상 데이터
- 이는 한번 계산으로 두 번 혹은 세 번씩 재사용을 한 감산 알고리즘 테이블의 중복 워드 조합들이 많다는 사실을 나타낸다. 기본적으로 25번째 레지스터(r25)는 다른 레지스터들(r0~r24)에서 이미 만들어진 워드들의 블록들을 이용하여 최종적인 결과값을 만들고 저장하는 공간으로 사용하였다.
이론/모형
- 이진체상에서 곱셈 연산과 제곱 연산의 결과는 입력 값의 두 배 워드 크기를 가지며 이 값을 기준으로 감산 연산이 이루어진다. 본 논문에서 사용한 GF(2271), GF(2193)에서의 감산 연산은 삼항 혹은 오항 기약다항식을 이용하여 시프트 연산과 XOR(Exclusive -OR) 연산으로 구현 가능하다. 본 논문에서는 8-bit 프로세서 환경에서의 감산 연산 최적화를 위해 GF(2271) 상의 기약 다항식 f(x)=x271+x207+x175+x111+1과 GF(2193) 상에서의 기약다항식 f(x)=x193+x145+x129+x113+1을 선택하였다.
성능/효과
- GF(2271)에서 기약다항식 f(x)=x271+x207+x175+x111+1에 대한 Fast reductio-n을 구현 시 1,084 클럭 사이클이 소모되었고, 제안하는 감산 연산 알고리즘을 사용하여 구현 시 482 클럭 사이클이 소모되어 약 56% 정도 속도가 향상되었다. GF(2193)에서 기약다항식 f(x)=x193+x145+x129+x113+1에 대한 Fast reduction은 769 클럭 사이클이 소모되었고, 제안하는 감산 연산구현 시 326 클럭 사이클로 약 58% 가량 속도가 향상되었다. 단, 이 수치들은 오직 알고리즘 자체에 대한 향상율이다.
- Table 6는 기존의 Fast reduction과 본 논문에서 제안한 감산 연산 알고리즘을 각각 어셈블리 언어로 구현하였을 때의 성능을 클럭 사이클 단위로 비교 한 것이다. GF(2271)에서 기약다항식 f(x)=x271+x207+x175+x111+1에 대한 Fast reductio-n을 구현 시 1,084 클럭 사이클이 소모되었고, 제안하는 감산 연산 알고리즘을 사용하여 구현 시 482 클럭 사이클이 소모되어 약 56% 정도 속도가 향상되었다. GF(2193)에서 기약다항식 f(x)=x193+x145+x129+x113+1에 대한 Fast reduction은 769 클럭 사이클이 소모되었고, 제안하는 감산 연산구현 시 326 클럭 사이클로 약 58% 가량 속도가 향상되었다.
- GF(2271)에서 메모리로부터 레지스터로 로드하는 연산은 Fast reduction 알고리즘이 208회가 필요하나 제안하는 감산 알고리즘은 94회로 약 2배 정도 차이가 났다. 메모리로 저장하는 연산은 각각 Fast reduction 174회, 제안하는 감산 알고리즘 34회로 약 5배 차이가 발생했다.
- 제한된 환경에서의 감산 연산을 구현하기 위해 어셈블러 언어로 설계하여 26개의 레지스터를 적극적으로 활용하였고, 기본적으로 제공하는 ATmega12-8의 rotate shift 연산을 효율적으로 사용하여 감산 연산의 최적화를 이루었다. 결과적으로 최종적인 감산 결과 값에 나타난 중첩되는 워드 조합과 이를 이용한 레지스터의 효율적인 스케줄링, rotate 연산의 적극적인 활용 등을 통해 메모리 접근 연산의 최소화를 가능하게 하였다.
- 최적화 구현에서 사용된 로드 연산은 ‘C[0]’부터 ‘C[41]’까지 1회, ‘C[42]’부터 ‘C[67]’까지는 2회가 필요하며 연산이 끝난 후 메모리로 저장하는 연산은 각 워드의 연산이 종료된 후에만 저장하기 때문에 ‘C[0]’부터 ‘C[33]’까지 1회만 사용하게 된다. 동일한 이유로 GF(2193)에서 메모리로부터 레지스터로 로드는 Fast reduction 알고리즘은 146회가 발생하나 제안하는 알고리즘은 50회로 약 3배 차이가 났다. 레지스터에서 메모리로 저장은 122회에서 24회로 약 5배 차이가 났다.
- 미리 계산된 감산 연산 알고리즘 구성표를 통해서 레지스터 사용을 효율적인 설계가 가능하였다. 따라서 기존의 Fast reduction을 적용하였을 때 생겨나는 중복되는 메모리 접근을 효과적으로 줄일 수 있었다. 위와 같은 최적화 기법을 다른 기약다항식을 사용하는 이진체에서도 유도가 가능하다.
- 추가된 클럭 사이클은 전체적인 향상율을 저하시키게 된다. 따라서 실질적인 감산 연산 향상율은 각각 약 53%, 55%로 나타났다.
- 그러나 이진체 제곱 연산에서 감산 연산은 약 50% 정도로 차지하는 비중이 크다. 따라서 제안하는 감산 연산 알고리즘은 이진체 제곱 연산에서 큰 효율성을 얻을 수 있다.
- )에서 메모리로부터 레지스터로 로드하는 연산은 Fast reduction 알고리즘이 208회가 필요하나 제안하는 감산 알고리즘은 94회로 약 2배 정도 차이가 났다. 메모리로 저장하는 연산은 각각 Fast reduction 174회, 제안하는 감산 알고리즘 34회로 약 5배 차이가 발생했다. 이는 Fast reduction의 루프 내에서 발생하는 메모리 중복 접근 때문이다.
- 자원이 제한된 환경에서는 중복되는 메모리 접근에 대한 부하가 상대적으로 크다. 미리 계산된 감산 연산 알고리즘 구성표를 통해서 레지스터 사용을 효율적인 설계가 가능하였다. 따라서 기존의 Fast reduction을 적용하였을 때 생겨나는 중복되는 메모리 접근을 효과적으로 줄일 수 있었다.
- 따라서 최대한으로 Table에 나타난 중복 조합들을 사용할 수 있도록 스케줄링 하는 것이 구현에서의 관건이다. 본 논문에서는 제한된 환경에서 레지스터를 적극적으로 사용하기 위해 중복 조합들을 워드 2개 단위까지 재사용하여 GF(2271), GF(2193)에서 각각 53%, 55%의 효율성을 개선 시켰다.
- 각 Table에는 중복되는 워드들의 조합이 많이 발생한다는 사실을 발견할 수 있다. 실제 구현에서 중복 조합들을 한번 계산으로 2번 이상 재사용하는 방식으로 스케줄링하여 최종적인 연산량과 레지스터 사용을 효율적으로 줄일 수 있었다.
- Shift 연산은 GF(2271)에서 68회에서 41회로,GF(2193)에서는 48회에서 25회로 줄었다. 제안하는 감산 알고리즘은 미리 구해놓은 감산 알고리즘 테이블의 결과 값에 대해 순차적으로 Shift 연산을 진행 할 수 있으므로 Shift 연산의 연속성을 유지할 수 있다. 예를 들어, GF(2271)에서 Fast reduction은 하나의 워드 감산을 위해 7-bit right shift(>>7)와 1-bit left shift(<<1)가 필요하다.
- Table 5는 Fast reduction 알고리즘과 제안하는 알고리즘에서 필요한 주요 연산의 횟수를 비교한 표이다. 제안하는 감산 알고리즘의 연산량 측정을 위해 불필요한 연산과 레지스터 사용을 최대한으로 줄여서 최적화된 구현을 하였다. 따라서 Table 5에 나타난 연산량은 최적화를 했을 때의 값이다.
후속연구
- 중간항들의 지수의 차이가 작고 8이나 16의 배수인 기약다항식이라면 더 좋은 향상율을 기대 할 수 있다. 또한 중간항들의 지수의 차가 16의 배수인 기약다항식에 대해서는 16-bit 프로세서 환경에서도 본 논문에서 제시한 감산 연산 알고리즘을 적용 할 수 있다. 이를 반영하여 다양한 이진체와 기약다항식의 특성을 고려한 효율적인 감산 알고리즘에 대한 연구를 진행 중이다.
- 또한 중간항들의 지수의 차가 16의 배수인 기약다항식에 대해서는 16-bit 프로세서 환경에서도 본 논문에서 제시한 감산 연산 알고리즘을 적용 할 수 있다. 이를 반영하여 다양한 이진체와 기약다항식의 특성을 고려한 효율적인 감산 알고리즘에 대한 연구를 진행 중이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.