Method and apparatus for performing fast division
AssigneeDigital Equipment Corporation
InventorsWilliam R. Wheeler, Matthew J. Adiletta
Life of this patent
Estimating the term…
Abstract
A method and apparatus for performing division in accordance with certain bandwidth requirements particular to an implementation is described. A pseudo pipelined approach for performing division using the SRT non-restoring division algorithm is described which uses a minor clock and a major clock cycle time. The number of stages in the division pipeline is a function of the parameters bandwidth requirements of the system. The pseudo pipeline division technique iterates for several minor cycles rather than having individual hardware associated with each minor cycle in the division pipeline. High division bandwidth requirements are provided while minimizing the amount of hardware and the area occupied by the associated hardware.
Claims21
A circuit for performing a process on a data stream comprising:
- a plurality of pipeline stages, each one of said pipeline stages operating on a portion of said data stream to produce an output from each of said stages to be fed as an input to a succeeding one of said stages;
- with at least one of said pipeline stages further comprising:
- means for recirculating an output from said one pipeline stage to an input of said one pipeline stage for a predetermined number of times before the output of said one pipeline stage is provided as an input to a succeeding one of said pipeline stages, said predetermined number of times representing a clock period comprising a plurality of assertions of a clock signal.
A divider circuit for producing a quotient by dividing a dividend by a divisor, the divider circuit comprising:
- a plurality of divider stages, each of said plurality of divider stages further comprising:
- means for retiring at least one bit of a dividend to produce an partial remainder using the dividend, prior partial remainders, and the divisor with said retiring means further including:
- means for iteratively executing said retiring means for a predetermined number of times to retire an associated number of bits of the dividend;
- means for passing said partial remainder to a succeeding stage after said means for iteratively executing has iteratively executed for said predetermined number of times;
- and
- means, responsive to said retiring means, for gathering data used to produce the quotient.
Dependencies are inferred from the claim text.