As logic density increase, more complex computational unit is merged into an integrated circuit. Nowadays, more and more applications include dividers within their central processing units. Regardless of its frequent usage, divider remains one of the slowest arithmetic units due to its iterative nature. The data hazards problem due to division operations become serious as clock speed becomes faster and a number of pipeline stage increase. Therefore, it is an important issue for digital hardware designers to improve the performance of dividers. As application like graphics rendering pipelines have been widespread, the importance of high performance dividers has been grown even higher.
Two approaches have been introduced to develop of algorithms for high-speed division. The first approach uses addition, subtraction, and shift operation, while the second approach relies on multiplication operation. For high-performance dividers, the multiplicative division algorithm is more suitable than the other. To speed up the operation time in a multiplicative divider, a large look-up table storing initial approximations is required. For 16-bit initial approximation ROM, only 3 steps are required to get the 64-bit result. However, a ROM with nearly 1 Mega bit storage capacity is required. A size of 1M bit ROM occupies most of the divider area and increase the total dedicated area. Therefore, ROM compression methods are needed to get the optimal performance at lower area cost.
In this paper, four compression methods area introduced. First, data transform is proposed to make the reciprocal data into a data format which various ROM compression techniques can be easily adaptable. Second, compression by vertical symmetry and compression by linear line subtractions are adapted to reduce the magnitude of data. Finally, the address bit reduction is proposed to compress the reciprocal ROM effectively.
Combining four different methods indicated above, the ROM size is reduced to nearly 1/7 for a ROM storing 16-bit initial approximation.
그래픽스 어플리케이션이 발전함에 따라서 전체 프로세서의 성능을 저하시키는 나눗셈기의 성능향상은 상당히 중요한 문제로 떠올랐다. 마이크로 프로세서들의 클락 주파수가 빨라지고 파이프라인 구조가 세분화 됨에 따라서 고성능 나눗셈기의 설계의 중요성은 더욱 증대되고 있다.
고성능 나눗셈을 구현하는 방법으로는 크게 감산기를 이용하는 알고리즘과 곱셈기를 이용한 알고리즘 두 가지로 나뉠 수가 있다. 비트수가 큰 고성능 연산에서는 감산기를 이용한 나눗셈기는 보다 곱셈기를 이용한 나눗셈기가 더 좋은 성능을 내기 때문에 이 논문에서는 곱셈기를 이용한 나눗셈기에 대하여 적은 면적으로도 성능을 최대화할 수 있는 방법을 제시하였다.
곱셈기를 이용한 나눗셈기의 성능을 최대화하기 위해서는 ROM에다가 처음 추정 값을 저장한다. ROM이 16비트 추정 값을 저장하고 있으면 64비트 나눗셈을 하기 위해서 단지 3단만이 필요하게 된다. 나눗셈기에서는 현재 8비트(7비트)와 16비트(14비트) 추정 값이 가장 많이 쓰이고 있다. 16비트 추정 값을 저장하기 위해서는 약 1 Mega 비트라는 큰 ROM이 필요하다. 1 Mega 비트 ROM은 디바이더 면적의 대부분을 차지하기 때문에 ROM의 압축방법이 필요하다.
이 논문에서는 ROM의 면적을 줄이기 위해서 4가지 압축방법이 제시되었다. 첫 번째로 다른 분야에서 사용되는 ROM 압축 방법들을 나눗셈기에 쉽게 적용하기 위하여 ROM에 저장되는 값의 축을 변형하였다. 두 번째로는 데이터의 비트를 줄이기 위하여 대칭되는 데이터의 값을 하나에 저장하여 ROM 크기를 줄이는 방법을 제안하였다. 세 번째로는 ROM을 액세스하는 동시에 1차 방정식을 구하여 ROM에 더해주어 ROM의 크기를 줄이는 방법을 제안하였고 마지막으로는 앞의 세가지 방법을 통해서 크기가 줄어든 데이터의 어드레스비트를 줄여 ROM을 줄이는 방법을 제안하였다.
네 가지 방법을 다 이용할 때 16비트의 추정 값을 저장하는 ROM은 액세스 성능이 저하되지 않으면서 크기가 약 1/7로 줄어들게 되었다.
