Reciprocal ROM compression methods in high-speed dividers

Abstract

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 ...