PROGRAMMABLE TECHNOLOGIES WEB SITE
A scientific study of the problems of
digital engineering for space flight systems,
with a view to their practical solution.
Hardware Divider For Leon Processor
A European Space Agency have developed a processor named Leon. Synthesizable VHDL model
of the processor is also made available. The project involves design and implementation of
one of the following arithmetic units in two technologies; FPGA and Synopsys standard
library.
Note: From http://www.cse.iitd.ernet.in/~vls00021/semester1/project/leon/algo.htm
Requirements
- Hardware divider. An iterative 1 bit/cycle signed and unsigned
divider.
- The divider should do the following:
- Division performs integer division (signed & unsigned)
- Division by zero issues a warning (assertion)
Algorithm
The simplest form of algorithm for division is:
- A = B*Q + R
- Sign(R) = sign(A)
- Abs(R) < Abs(B)
This is called the Euclidian Division.
Various Algorithms For Division
The two main categories are
- The subtractive method:
- Subtractive algorithms are the most popular.
- They calculate the square root and quotient directly
- They can achieve low latencies with a relatively small amount of hardware
- Various algorithms for this method are:
- restoring
- non-restoring with non-redundant digit set and
- non-restoring with redundant digit set.
These methods are widely used in modern microprocessors and co-processors
- The multiplicative methods.
- Multiplicative algorithms do not calculate quotients and square roots directly but they
use iterations to refine an approximation to the desired result. Moreover, they imply the
use of a fast multiplier, generally very expensive in terms of silicon area.
The SRT non-restoring division algorithm
This algorithm corresponds to a recurrence where each iteration produces one redundant
digit of the result.
The choice of the SRT algorithm is due to the following considerations:
- Many recent microprocessors use its implementations for both division and square root
- The architecture is sufficiently simple to be placed in a low cost programmable chip
The SRT method was discovered independently, at about the same time by Sweeny,
Robertson and Tocher. Its digit-serial implementation represents a good compromise between
computational speed and cost in term of silicon area. It is used in many floating-point
arithmetic units of recent microprocessors. In the SRT algorithm, the quotient is computed
as with the pencil and paper procedure. Thus, the following recurrence is used at every
iteration:
W[j+1] = r*W[j] - d*q[j+1]
Where W[j] is the partial remainder at iteration j, q[j+1] is the (j+1)-th digit of the
quotient, r is the radix, r*W[0]=x is the dividend and d is the divisor.
The flowgraph
The control Machine operation:
- The division block is in WAIT state to start with i.e. on processor reset. It comes out
of the WAIT state on receiving the START signal from the control machine
- On receiving the START signal the division block starts the operation only if the
previous division operation is over i.e. only if it is in WAIT state. If the division
block is busy then it indicates the same to the control machine & the control machine
then keeps issuing the signal till the request is operated.
- The dividend register is loaded with the dividend at the start of the first iteration.
For the rest iterations it is loaded with the partial remainder/residual. The control
machine issues signals to the operating machine to achieve this.
Project Team
Home
Last Revised: February 03, 2010
Digital Engineering Institute
Web Grunt: Richard Katz