부동소수점 나눗셈에서 많이 사용하는 골드스미트 부동소수점 나눗셈 알고리즘은 한 회 반복에 두 번의 곱셈을 수행한다. 본 논문에서는 한 회 반복에 K 번 곱셈을 수행하는 가칭 오차 교정 K차 골드스미트 부동소수점 나눗셈 알고리즘을 제안한다. 본 논문에서 제안한 알고리즘은 입력 값에 따라서 곱셈 횟수가 다르므로, 평균 곱셈 횟수를 계산하는 방식을 유도하고, 여러 크기의 근사 역수 테이블에서 단정도실수 및 배정도실수의 나눗셈 계산에 필요한 평균 곱셈 횟수를 계산한다. 또한 한 번의 곱셈과 판정으로 나눗셈 결과를 보정하는 알고리즘을 제안한다. 본 논문에서 제안한 알고리즘은 오차가 일정한 값보다 작아질 때까지만 반복 연산을 수행하므로 나눗셈 계산기의 성능을 높일 수 있다. 또한 최적의 근사 테이블을 구성할 수 있다.
The commonly used Goldschmidt's floating-point divider algorithm performs two multiplications in one iteration. In this paper, a tentative error corrected K'th Goldschmidt's floating-point number divider algorithm which performs K times multiplications in one iteration is proposed. Since the number of multiplications performed by the proposed algorithm is dependent on the input values, the average number of multiplications per an operation in single precision and double precision divider is derived from many reciprocal tables with varying sizes. In addition, an error correction algorithm, which consists of one multiplication and a decision, to get exact result in divider is proposed. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a divider unit. Also, it can be used to construct optimized approximate reciprocal tables.
부동소수점 계산은 과학 및 공학 기술 분야에서 많이 사용된다. 최근에는 음성 처리, 3차원 그래픽, 자동차등 실장제어 분야에도 폭넓게 사용되면서 CPU의 기본 기능으로 채택되고 있다[1]. 실장제어 분야에서 고성능의 부동소수점 연산이 요구되면서 실장제어용 마이크 로프로세서도 기본적으로 부동소수점 연산기능을 갖추게 되었다[2].
부동소수점 나눗셈은 덧셈, 뺄셈 및 곱셈보다 출현빈도가 낮지만, Oberman과 Flynn의 연구[3]는 나눗셈의 수행 시간이 덧셈이나 곱셈과 비슷하게 소요됨을 보이고 있다.
부동소수점 나눗셈은 뺄셈을 반복하는 SRT[4] 알고리즘과 곱셈을 이용한 알고리즘으로 뉴톤-랍손(Newton-Raphson) 역수 알고리즘[5] 및 골드스미트(Goldschmidt) 나눗셈 알고리즘이 있다. 곱셈을 이용하는 방식은 SRT와 비교하여 속도가 빠르고 추가적인 하드웨어가 크지 않다는 장점이 있으나 근사 값만을 얻는다.
Pineiro[6]는 작은 곱셈기를 직렬로 연결하여 골드스미트 방식으로 부동소수점의 나눗셈, 역수, 제곱근, 역 제곱근을 구하는 방식을 제안하였다. 곱셈을 이용한 알고리즘은 초기 근사 값을 이용하여 수렴 속도를 향상시키고 있다. 그러므로 초기 근사 값을 결정하는 알고리즘과 수렴 속도를 높이기 위한 방식에 대하여 연구가 진행되었다[7].
종래 연구는 초기 근사 값이 가지는 최대 오차를 계산하고, 오차를 부동소수점에서 표현 가능한 최소값보다 작게 될 때까지 반복 연산을 수행하였다. 이러한 종래 연구에서는 최대 오차만을 고려했기 때문에, 실제 구하고자 하는 결과 값에 도달했음에도 불구하고 가외의 연산을 수행하여 연산 속도를 저하시키는 단점이 있었다. 김성기는 가변 시간 알고리즘을 제안하여 이러한 문제를 개선했으나 한 회 반복에 항상 두 번의 곱셈을 사용했으므로 가외의 연산이 남아있으며 또한 근사 값만을 얻을 수 있었다[8].
조경연은 한 번 반복에 K번 곱셈을 수행하는 K차 뉴톤-랍손 역수 알고리즘을 제안하였다[9]. 뉴톤-랍손 알고리즘은 오류 예측이 용이하나 병렬 곱셈이 되지 않는다.
본 논문에서는 테일러급수 정리로부터 가칭 K차 골드스미트 부동소수점 역수 알고리즘을 유도한다. K차 골드스미트 부동소수점 역수 알고리즘은 한 번 반복에 K번 곱셈을 수행한다. 반복 과정의 오차를 예측하고, 예측한 오차가 정해진 값보다 작아지는 시점까지만 반복 수행하는 알고리즘을 제안한다. K차 골드스미트 알고리즘은 병렬 곱셈이 가능하다.
한편 골드스미트 알고리즘을 사용한 나눗셈은 근사 계산으로 정확한 결과를 얻기 위해서는 보정이 필요하다. Anderson[10]은 요구되는 정밀도보다 10비트를 더 계산하는 것을 제안했으나 항상 정확한 값을 보장하지는 못한다. Viitanen[11]과 Pasca[12]는 입력 값에 스케일링을 도입하여 오차를 보정하였다. Markstein[13]은 요구되는 정밀도의 2배 길이 계산을 제안했으나 이 또한 항상 정확한 값을 보장하지는 못한다. Schwarz[14]가 제안한 방식은 스티키 비트를 정확히 산출하지 못한다. Brisebarre[15]는 제수가 정해진 경우에 보정하는 알고리즘을 제안했다.
본 논문에서는 나눗셈 에서 제수 1.
본 논문에서 제안한 알고리즘은 C 언어로 프로그래밍하여 정확한 계산이 산출되는 것을 검증하였고, 또한 Verilog HDL로 코딩하고 로직 시물레이션하여 동작을 검증하였다.
본 논문의 구성은 다음과 같다. 2장에서는 테일러급수 정리로부터 가칭 K차 골드스미트 역수 알고리즘을 유도하고, 나눗셈 결과 보정 알고리즘을 제안하고, 오차를 예측하는 방법을 제안하고, 연산 자릿수 및 반복을 종료할 오차 한계를 계산한다. 3장에서는 제안한 알고리즘을 구현하는 하드웨어 알고리즘을 제시한다. 4장에서는 근사 테이블을 구성하고, 나눗셈 계산에 소요되는 평균 곱셈 횟수를 계산한다. 그리고 그 결과를 종래 골드스미트 나눗셈 알고리즘과 비교 분석한다. 5장에서 결론을 맺는다.
부동소수점 수 D의 역수
부동소수점 수 D의 가수부 1.
식 (1)에서 g와 h의 길이를 각각
근사 테이블은 ROM에 저장하거나 또는 별도의 회로를 사용해서 산출하기도 한다. T(g)는 의 근사계산이므로 ‘
a
식 (3)에서 이므로
이로부터
식 (2)부터 식 (5)까지를 정리하면 식 (6)이 된다.
식 (6)을 가칭 K차 골드스미스 역수 알고리즘이라고 한다. 식 (6)에서 k=2이면 골드스미트 역수 알고리즘이 된다.
정수 N을 부동소수점 수 1.d로 나누는 것은 ,
이를 연산하기 위하여 , 0.
식 (7)에서 ‘0.75 ≤
‘
식 (6)에서 ‘
식 (8)에서
식(7)에서
또한 은 식(11)이 된다.
식 (10) 및 식 (11)과 같이 연산을 반복하면 절삭 오차가 누적된다. 반복 연산에서 누적되는 최대 절삭 오차를 표 1에 보인다.
반복 연산에 따른 최대 누적 오차
표 1에서 를 4번 반복 연산하는 경우에 절삭에 따른 오차는 2-
IEEE-754 단정도실수와 배정도실수에서 가수부의 유효자릿수는 각각 24 비트와 53비트이다. 유효자릿수에 라운드 한 비트를 더하면 25 비트와 54비트이다. 2-
유효자릿수. 단위는 비트
표 2에서
하나의 곱셈기를 사용하여 하드웨어로 구현한 오차 교정 K차 골드스미트 나눗셈 알고리즘을 표 3에 보인다. 표 3에서 , 1 <
[표 3.] 오차 교정 K차 골드스미트 나눗셈 알고리즘. 하나의 곱셈기를 사용한 경우.
오차 교정 K차 골드스미트 나눗셈 알고리즘. 하나의 곱셈기를 사용한 경우.
표 3에서 상태-1부터 상태-5에서
레지스터 B가
상태-6에서는
또한 레지스터 T의 하위 2비트를 레지스터
IBM-PC의 window-7에서 Icarus Verilog version 0.9를 사용하여 HDL로 코딩하고 시물레이션하여 동작을 확인하였다. 두 개의 곱셈기를 사용하여 하드웨어로 구현한 오차 교정 K차 골드스미트 나눗셈 알고리즘을 표 4에 보인다.
[표 4.] 오차 교정 K차 골드스미트 나눗셈 알고리즘. 두 개의 곱셈기를 사용한 경우.
오차 교정 K차 골드스미트 나눗셈 알고리즘. 두 개의 곱셈기를 사용한 경우.
DasSarma[17]의 연구 결과 최적의 근사 역수는 식 (12)로 주어진다.
T(g)의 소수점 이하 길이를 t 비트라고 하면 ‘
식 (12)로부터
식 (10)에서 최대오차 이 2-
식 (14)에서
식 (11)의 최대오차 이 2-
그림-1에
본 논문에서 제안한 알고리즘에 의한 IEEE 단정도실수 및 배정도실수의 테이블 크기에 따른 나눗셈 계산에 필요한 곱셈 횟수를 표 5와 표 6에 보인다.
[표 5.] IEEE 단정도실수 나눗셈 계산에 필요한 곱셈 횟수
IEEE 단정도실수 나눗셈 계산에 필요한 곱셈 횟수
[표 6.] IEEE 배정도실수 나눗셈 계산에 필요한 곱셈 횟수
IEEE 배정도실수 나눗셈 계산에 필요한 곱셈 횟수
종래 골드스미스 알고리즘에서는 최대 오차를 고려해서 반복 횟수를 정했다. 표 5와 표 6에서 ‘GS No. of Multiply’는 종래 골드스미트 알고리즘에서의 곱셈 횟수이다. ‘1 mult’와 ‘2 mult’는 각각 곱셈기를 하나 사용한 경우와 두 개 사용한 경우이다.
하나의 곱셈기를 사용하는 경우에 종래 알고리즘에 의한 단정도실수 나눗셈은 ‘128x6’ 테이블을 사용하면 7회의 곱셈을 수행하였고, ‘256x8’ 테이블을 사용하면 5회의 곱셈을 수행하였음을 표 5로부터 알 수 있다. 그러나 본 논문에서 제안한 알고리즘에서는 ‘128x6’ 테이블에서 평균 4.70회의 곱셈, ‘256x7’ 테이블에서 평균 4.66 회의 곱셈으로 나눗셈을 할 수 있다.
평균 5회의 곱셈으로 나눗셈을 계산하려면 종래 알고리즘에서는 ‘256x7’ 테이블을 사용했지만, 본 논문에서 제안하는 알고리즘을 사용하면 ‘64x6’ 테이블을 사용해도 5회 곱셈으로 나눗셈을 계산할 수 있다. ‘64x6’테이블의 면적은 ‘256x7’ 테이블의 사분의 일에 불과하다.
이러한 결과는 배정도실수 연산에서도 동일하게 나타난다. 배정도실수 나눗셈 계산은 표 6으로부터 종래 알고리즘에서는 ‘128x6’ 테이블을 사용하면 9회의 곱셈, ‘256x7’ 테이블을 사용하면 7회의 곱셈을 수행하였다. 그러나 본 논문에서 제안한 알고리즘에서 는 ‘128x6’ 테이블을 사용하면 평균 6.81회의 곱셈, ‘256x7’ 테이블을 사용하면 평균 6.67회의 곱셈으로 나눗셈을 수행한다.
표 5와 표 6은 근사 나눗셈에 소요되는 곱셈 회수이며 정확한 결과를 구하기 위한 오차 보정에 한 번의 곱셈과 판정이 추가된다.
부동소수점 나눗셈은 뺄셈을 반복하는 SRT 알고리즘과 곱셈을 반복하는 뉴톤-랍손(Newton-Raphson) 역수 알고리즘 및 골드스미트(Goldschmidt) 나눗셈 알고리즘이 있다. 뉴톤-랍손 역수 알고리즘은 제수의 역수를 피제수에 곱해서 나눗셈을 계산한다. 역수 계산은 제수의 역수의 근사 값을 초기 값으로 해서 반복 연산으로 오차를 줄여나간다. 반복 연산을 수행할 때마다 상대 오차는 자승으로 줄어들며, 한 회의 반복 연산에 2회의 곱셈이 필요하다.
본 논문에서는 테일러 급수로부터 가칭 K차 골드스미트 역수 알고리즘을 유도하였다. K차 알고리즘에서는 한 회 반복에 K번의 곱셈을 수행한다. 또한 반복 연산 과정의 오차를 예측하고, 예측한 오차가 정해진 값보다 작아지는 시점까지만 반복 연산을 수행한다.
나눗셈 에서 1.
제안한 알고리즘을 verilog로 구현하고 시물레이션하여 동작을 검증하였으며, 다양한 근사테이블에서 기존의 골드스미트 알고리즘과 비교하여 계산속도가 개선되었음을 증명하였다.
본 논문에서 제안한 알고리즘은 평균 곱셈 횟수가 중요한 디지털 신호처리, 컴퓨터 그래픽, 멀티미디어, 과학 기술 연산 등에서 폭 넓게 사용될 수 있다. 또한 계산기 성능에 따른 최적의 근사 역수 테이블을 구성할 수 있으므로 하드웨어 사양에 제한적인 SOC(System On Chip)에 유용하게 적용될 수 있다.