Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-17
2001-11-20
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S650000
Reexamination Certificate
active
06321245
ABSTRACT:
TECHNICAL FIELD
The present invention relates to traffic management in communication networks, and more particularly to a method and system for performing fast division in the computation of the delay between data to be transmitted.
BACKGROUND ART
The function of traffic management is to control the use of network resources, optimizing network utilization and avoiding bottlenecks in the network. Various devices interfacing a network send and receive data on link connections. One important function in the high speed networks is to control the rate at which the data are delivered over the links.
In the so-called Asynchronous Transfer Mode (ATM) Networks the data are called ATM cells and transit over physical links in the network from endpoints to endpoints through internal nodes (also called switches) which route the cells to their destination endpoint. The cells within either a endpoint or a node are temporarily stored before being admitted on a link. Among the different parameters determining which one and the moment at which a new cell is to be output, the current cell rate (CCR) is mandatory. The computation of this parameter which is also expressed as a delay (the inter-cell delay) includes the step of performing a division.
Since the division belongs to an interactive process, the duration of this operation must be minimized. There are several families of dividers: dividers using iterations, dividers using logarithms and fully combinatorial dividers.
The dividers using iteration perform the operation thanks to a succession of subtractions and shift operations. These circuits generate the exact value of the division but they require several cycles to compute the result. The number of steps necessary to compute the result equals the number of bits of the divisor operand. These circuits are too slow for high speed network applications.
The dividers using logarithms require very large memory tables. This type of circuits are resources consuming.
The fully combinatorial dividers circuits require expensive circuitry. Moreover this type of circuits is not adapted to the high speed networks because they are not fast enough.
Another known combinational approach is based on a process using the so-called non restoring array divider as defined by H. H. Guild in “Some Cellular Logic Arrays for Non restoring Binary Division” the Radio and Elect. Engr., Vol. 39 June 1970, using controlled Adder/Subtracter cells. Such technique is hardware consuming and is sized to a precise shape of dividend/divisor, say a 32 bits/16 bits or any combination of (2 n bits
bits).
The general state of the prior art with respect to solving the aforementioned division problem may be best illustrated and understood with reference to the several patents to be described immediately hereinafter.
U.S. Pat. No. 4,228,518 from Chamberlin discloses a microprocessor having the capability of performing either a multiply or divide operation from a single instruction for each operation. Standard circuitry of a microprocessor is used along with a multiply/divide cycle counter, logic circuitry, and a shift network separate from the arithmetic logic unit. The microprocessor has the capability of performing unsigned integer multiplication and division. A shift and add algorithm is used for multiplication while for division a non-restoring divide algorithm is used. While this circuit does not occupy a great amount of additional circuitry on the microprocessor, several cycles of operation are needed to complete the division.
U.S. Pat. No. 4,707,798 from Nakano discloses a divide method and a divide apparatus for use in a data processing system by employing interpolation approximation. The divisor and the dividend are normalized in a normalization circuit. A table unit stores a plurality of approximate reciprocal divisors and differences between adjacent approximate reciprocal divisors and is addressed by the high-order bits of the normalized divisor. The approximate reciprocal divisor read out from the table unit is, in an interpolation approximation circuit, changed into an interpolation approximated approximate reciprocal divisor in accordance with a plurality of bits following the high-order bits and the difference. A multiplication unit multiplies the interpolation approximated approximate reciprocal divisor by the normalized dividend to obtain through successive iterations a quotient.
U.S. Pat. No. 5,068,816 from Noetzel discloses a function evaluator which uses an interpolating memory for evaluating functions. An argument is expressed in digital bits. High order bits are used to address a memory for selecting coefficients. Low order bits are used in combinational logic to supply powers which multiply the coefficients. An adder sums the products of the multipliers, and the summation is the function evaluation. This solution is hardware consuming because the apparatus is not limited to the division. The correction factor value is important due to the fact that the segments have all the same size, as will be explained later in the description.
The main characteristics of the prior art solutions are that a precise result of the division is sought which need several cycles of operations in order to apply corrections to an estimated result.
Therefore the circuits of these references are not acceptable for the present applications of very high speed networks in which the main constraint is the delay and not the accuracy.
Accordingly, it would be desirable to be able to provide a new method and system to evaluate an approximation of a division which eliminates the aforementioned constraint of delay and complexity of present solutions.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a low cost high speed divider for achieving fast divisions performed in one clock cycle.
In a preferred embodiment such an apparatus uses an approximation method based on a non linear interpolation technique. An hyperbola curve in the form of
Y
=
N
X
where N is a constant and X is the divisor operand, is parted into unequal segments and stored in a table. The value of each segment (&Dgr;X, &Dgr;Y)is not equal. The segments are smaller in the region of the hyperbola where the variation of Y is important, while the segments are longer in the region where the variation of Y is less. Moreover the sizes of the segments are predefined to always be an integer power of 2.
Another object of the invention is an adaptable fast divider wherein the number of interpolation points is fixed in order to provide the lower hardware cost for a required admissible error.
The system of this invention is particularly directed to a fast division circuit without great accuracy, which is acceptable in adaptive processes. The present invention provides a dividing apparatus for use in a high speed ATM network in order to compute the delay between ATM cells.
In a preferred embodiment, the dividing apparatus comprises means for storing x-axis and y-axis coordinates (X
0
, Y
0
) of a plurality of non uniform interpolation points, and x-axis and y-axis coordinates (&Dgr;X, &Dgr;Y) representing the differences between two successive points of the plurality of non uniform interpolation points. As stated above, the plurality of non uniform interpolation points are selected such that the value of the x-axis differences (&Dgr;X) is a power n of 2 in the form of (&Dgr;X=2
n
)with n being an integer. Upon reception of an operand value X input to the storing means, a set of coordinates (X
0
, &Dgr;Y, &Dgr;X, Y
0
) representing one of the plurality of the non uniform interpolation points is selected to be associated to the input value, and is output from the storing means. A correction factor
(
X
-
X0
)
×
Δ
Y
Δ
X
is computed from a first part of the set of coordinates, and is added to the y-axis coordinate (Y
0
) of the set of coordinates to achieve the division. The dividing apparatus further comprises means for determining the plurality of non uniform interpolation points to be stored in preferably a Progr
Caillet Bernard
Cukier Maurice
Cockburn Joscelyn G.
Frisone John B.
International Business Machines - Corporation
Mai Tan V.
LandOfFree
Method and system for performing fast division using non... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing fast division using non..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing fast division using non... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611573