Technique for placement of pipelining stages in multi-stage datapath elements with an automated circuit design system

Claim 3

The method of claim 1, including the additional step of comparing the estimated delay associated with each stage of said multi-stage datapath element with the desired cycle time and, if the estimated delay associated with any individual stage exceeds the desired cycle time, resetting said desired cycle time equal to the estimated delay of the individual stage which exceeds the desired cycle time, and repeating steps a through g.

Claim 4

The method of claim 2, wherein said multi-stage datapath element is a carry-save array multiplier including a plurality of stages consisting of carry-save adder stages followed by a ripple-carry adder stage.

Claim 5

The method of claim 3, wherein at least one of said stage delay estimating steps estimates the delay associated with an individual stage in accordance with the equation: D.sub.s =D.sub.b N.sub.b +C where D s is the estimated stage delay, D b is a delay associated with communication between bits in a considered stage, Nb is the number of bits in the datapath element, and C is a constant.

Claim 6

The method of claim 1, wherein said multi-stage datapath element is a carry-save array multiplier including a plurality of stages consisting of carry-save adder stages followed by a ripple carry adder stage.

Claim 7

The method of claim 5, wherein at least one of said stage delay estimating steps estimates the delay associated with an individual stage in accordance with the equation: D.sub.s =D.sub.b N.sub.b +C where D s is the estimated stage delay, D b is a delay associated with communication between bits in a considered stage, N b is the number of bits in the datapath element, and C is a constant.

Claim 8

The method of claim 1, wherein at least one of said stage delay estimating steps estimates the delay associated with an individual stage in accordance with the equation: D.sub.s =D.sub.b N.sub.b +C where D s is the estimated stage delay, D b is a delay associated with communication between bits in a considered stage, N b is the number of bits in the datapath element, and C is a constant.

Claim 9

The method of claim 1 wherein the delay associated with the initially-designated stage includes the delay of an independent element.

Claim 10

The method of claim 8 wherein the initially designated stage of the element is the last stage in terms of data flow

Claim 11

The method of claim 9 wherein the independent element follows the multi-stage element in terms of data flow.

Claim 12

The method of claim 1 wherein the delay associated with the initially-designated stage includes the delay of an independent which precedes the multi-stage element in terms of data flow.

Claim 13

A multi-stage datapath element having a preselected operating cycle time, which multi-stage element is produced with an automated circuit design system as a combination of functional stages and pipelining stages combined according to a method implemented on a computer of: a) obtaining a desired operating cycle time for a datapath element; b) estimating a delay associated with an initially-designated stage of said multi-stage element; c) setting an accumulated delay value which reflects estimated delay associated with the initially-designated stage; d) estimating a delay associated with a consecutively adjacent stage of said multi-stage element; e) incrementing said accumulated delay value by the estimated delay associated with said consecutively adjacent stage; f) comparing the accumulated delay value with the desired operating cycle time and, when the magnitude of the accumulated delay exceeds the desired cycle time, designating insertion of a pipelining stage prior to the consecutively adjacent stage and setting said accumulated delay value equal to the estimated delay associated with the consecutively adjacent stage; and g) repeating steps d through f with said automated circuit design system until all stages of the multi-stage datapath element have been analyzed.

Claim 14

A multi-stage datapath element having a preselected operating cycle time, which multi-stage element is produced with an automated circuit design system as a combination of functional stages and pipelining stages combined according to a method implemented on a computer of: a) obtaining a desired operating cycle time for a datapath element; b) estimating a delay associated with an initially-designated stage of said multi-stage element; c) setting an accumulated delay value which reflects estimated delay associated with the initially-designated stage; d) estimating a delay associated with a consecutively adjacent stage of said multi-stage element; e) incrementing said accumulated delay value by the estimated delay associated with said consecutively adjacent stage; f) comparing the accumulated delay value with the desired operating cycle time and, when the magnitude of the accumulated delay exceeds the desired cycle time, designating insertion of a pipelining stage prior to the consecutively adjacent stage and setting said accumulated delay value equal to the estimated delay associated with the consecutively adjacent stage; and g) repeating steps d through f with said automated circuit design system until all stages of the multi-stage datapath element have been analyzed.

Claim 15

The multi-stage element of claim 12 wherein the delay associated with the initially-designated stage includes the delay of an independent element.

Claim 16

The element of claim 13 wherein the initially-designated stage of the multi-stage element is the last stage in terms of data flow.

Claim 17

The multi-stage element of claim 14 wherein the independent element follows the multi-stage element in terms of data flow.

Claim 18

The method of claim 12 wherein the delay associated with the initially-designated stage includes the delay of an independent element which precedes the multi-stage element in terms of data flow.

Claim 19

The multi-stage element of claim 12, including the additional step of comparing the estimated delay associated with each stage of said multi-stage datapath element with the desired cycle time and, if the estimated delay associated with any individual stage exceeds the desired cycle time, resetting said desired cycle time equal to the estimated delay of the individual stage which exceeds the desired cycle time and repeating steps a through g.

Claim 20

The multi-stage element of claim 16 wherein said multi-stage datapath element is a carry-save array multiplier including a plurality of stages consisting of carry-save adder stages followed by a ripple-carry adder stage.

Claim 21

The multi-stage element of claim 17 wherein at least one of said stage delay estimating steps estimates the delay associated with an individual stage in accordance with the equation: D.sub.s =D.sub.b N.sub.b +C where D s is the estimated stages delay, D b is a delay associated with communication between bits in a considered stage, Nb is the number of bits in the datapath element, and C is a constant.

Claim 22

The multi-stage element of claim 12 wherein said multi-stage datapath element is a carry-save array multiplier including a plurality of stages consisting of carry-save adder stages followed by a ripple-carry adder stage.