search

ETOgaosion / Multiplier_Divider

Other
0 stars 0 forks source link

Divider algoritm #1

Open ismailtufan123 opened 1 year ago

ismailtufan123 commented 1 year ago

What algorithm did you use for the division, can you please provide a source?

ETOgaosion commented 1 year ago

This project is for UCAS architecture course, we use an optimized try-quotient iterative divider. This algorithm is out-of-date to be used in commercial chip design.

Iterative part algorithm:

  1. Add 32 zeros before the 32-bit dividend, record it as A [63:0], and record the divisor as B [31:0], the quotient obtained as S [31:0], and the remainder as R [31:0].
  2. In the first iteration, take the high 33 bits of A, that is, A [63:31], and subtract the result {1b0, B [31:0]} of filling 0 with the high bit of B: if the result is negative, then the corresponding bit of the quotient (S [31]) is 0, and the dividend remains unchanged; If the result is a positive number, the corresponding bit of the quotient is marked as 1, and the corresponding bit of the dividend (A [63:31]) is updated to the result of subtraction.
  3. Perform the second iteration, where A [62:30] and {1'b0, B [31:0]} need to be subtracted, and S [30] and A [62:30] need to be updated based on the results.
  4. And so on until the 0th position is calculated.

Our optimization is accelerating try-quotient process by ignore the 0s prefix.

You can search for SRT algorithm, which is commonly used by commercial processor. More specifically, SRT 16 is more mature, SRT 64 is currently used on ARM platform.