Embedded SoPC Design with Nios II Processor and Verilog Examples

CHAPTER 21

GCD ACCELERATOR

The GCD (greatest common divisor) of two non-zero integers is the largest positive integer that divides the numbers without a remainder. The binary GCD algorithm is a method to obtain the GCD. In this chapter, we implement the algorithm using a software routine and a hardware accelerator and compare their performances.

21.1 INTRODUCTION

The gcd(a, b) function returns the GCD of two positive integers, a and b. It is the largest positive integer that divides the numbers without a remainder. For example, gcd(l, 12) is 1 and gcd(24, 15) is 3. The gcd() function has the following property:

We can apply this equation repetitively to reduce the values of two operands and eventually obtain the GCD. However, the convergence rate of this scheme can be really slow when one of the numbers is small. For an N-bit input, computing gcd(l, 2^N − 1) requires 2^N − 1 iterations. One way to improve the algorithm is to take advantage of the binary number system. For a binary number, we can tell whether it is odd or even by checking the LSB. Based on the LSBs of two inputs, several simplification rules can be applied in the derivation of the gcd() function:

• If both a and b are even,
• If a is odd and b is even,
• If a is even and b is odd, .

The previous equation can be extended: ...