High-Speed Multiplication Device
Abstract Generated abstract
This paper describes the design of a hardware multiplier for specialized high-speed computing machines, intended for numbers in semilogarithmic form with an 11-bit normalized mantissa and a 4-bit exponent. It compares sequential, tabular, and matrix multiplication approaches, then develops a matrix multiplier using 3-input AND-NOT integrated circuits and optimized partial-product adders. The proposed design improves speed by forming inverted sum and carry signals in a small number of logic stages, avoiding group carry hardware while reducing delay. The resulting device is reported to achieve about 500,000 multiplications per second, with multiplication time estimated as twice the product of word length plus one and the average element switching time.
Full Text
HIGH-SPEED MULTIPLICATION DEVICE
Yu. M. Achkasov, N. F. Kucher, Yu. A. Savel’ev, L. I. Ukhanov
(Presented by the Scientific-Technical Seminar of the Scientific Research Institute of Automatic Electronic Machines)
In specialized automatic computing machines that perform the operation of convolution of two functions, one of the main units is the multiplication device. The multiplication operation is one of the most labor-intensive; therefore, in high-speed specialized machines it is expedient to carry it out not by software but by hardware.
Multiplication methods that use a series of successive additions with shifting are unacceptable, despite their economy in components, because of their low speed, which even in principle cannot be higher than \((n-1)t_{\Sigma_n}\), where \(n\) is the number of digits of the numbers; \(t_{\Sigma_n}\) is the time for adding two \(n\)-digit numbers.
It is obvious that tabular methods are the most promising in terms of speed, but their application is limited by the growth of the equipment, the amount of which increases proportionally to \(2^{2n}\), since the number of digits of the product is equal to the sum of the digits of the multiplied numbers. Such devices provide a multiplication speed approximately equal to the speed of selecting a number from a table. The speed is limited only by the time for address decoding and for remagnetizing the cores. A compromise is the use of tables of squares, logarithms, or trigonometric functions, which makes it possible to reduce the size of the storage device, but lowers the speed, since the product is obtained as the result of a series of additional arithmetic operations. Despite their high speed, tabular multiplication devices have a number of shortcomings: low reliability, poor manufacturability, and a large number of different elements.
In the present work, the construction of a device for multiplying numbers represented in semilogarithmic form with an 11-digit normalized mantissa and a 4-digit exponent is considered. The speed of the device is 500 thousand multiplications per second.
Only one element is used in the device—a 3-input integrated “AND—NOT” microcircuit. The problem of constructing the multiplier is formulated as follows: to synthesize a logical switching circuit with 22 inputs and 22 outputs, realizing the function
\[ A(a_1,a_2,\ldots,a_m)=B(b_1,b_2,\ldots,b_n)\cdot D(d_1,d_2,\ldots,d_n), \]
where \(a\), \(b\), and \(d\) take the values “1” or “0”. Physically, the circuit must be implemented using 3-input Sheffer elements in accordance with
by the following optimality criterion: with a minimum of equipment—maximum speed. Obviously, in such a circuit the chain of consecutively connected elements must not exceed the value
\[ K=\frac{t_y}{(1.1\div 1.2)t_{\mathrm{sr}}}, \]
where
\[ \begin{aligned} t_y&\text{ is the multiplication time,}\\ t_{\mathrm{sr}}&\text{ is the operating time of one element,}\\ 1.1\div 1.2&\text{ is the safety factor.} \end{aligned} \]
For our function
\[ \begin{aligned} a_1&=F(b_1,c_1),\\ a_2&=F(b_1,c_1,b_2,c_2),\\ &\ldots\\ a_m&=F(b_1,c_1,b_2,c_2,\ldots,b_n,c_n). \end{aligned} \]
This function can be implemented by a “parallel” method and a multiplication time \(t_y\approx(2\div3)t_{\mathrm{sr}}\) can be obtained.
Such a circuit has the form of a pyramid and is too bulky; moreover, it requires excessively large fan-out and fan-in coefficients from the logic elements. Another implementation variant is simultaneous summation of partial products with the organization of group parallel carries in all digits. This method is also uneconomical.
Matrix multipliers, which form all partial products simultaneously by means of AND and OR elements, turn out to be more economical in terms of the number of elements used. Since the time required for forming the matrix of partial products is approximately equal to the operating time of an AND element, the multiplication time is determined mainly by the time of their summation (Fig. 1). The matrix
Fig. 1
is constructed so that its upper left corner forms the higher-order digits of the product, and its lower right corner the lower-order digits. This corresponds to multiplication starting with the higher-order digits in sequential multiplication. The wave of signal setting begins at the right side of the rhombus and moves to the left. Obviously, in its upper part it advances faster, since the input signals for the lower rows are the output signals of the upper ones. Obviously, the multiplication time here is equal to
\[ t_y = n(t_n + t_c), \]
where \(t_n\) is the time for forming a carry unit,
\(t_c\) is the time for forming the sum.
The speed of the matrix can be increased by dividing the multiplier into groups of two digits and, by decoding the resulting pairs of codes, controlling passage through the “0” stages of the multiplicand, the doubled multiplicand, or the tripled multiplicand, i.e., processing simultaneously the product of the multiplicand by a pair of multiplier digits (Fig. 2). The number of rows of parallel adders here is equal to \(\frac{n}{2}\). The speed of the device is
\[ t_y = n \cdot t_n + \frac{n}{2} t_c . \]
Fig. 2
For a further increase in speed it is necessary to reduce the times for forming the carry and the sum. In the best case they should be equal to the switching time of one logic element. The main delay is introduced by the time required to generate the carry signal. Usually, to reduce this delay, one proceeds by organizing group carry, but this requires additional hardware costs and a large input fan-in factor. The organization of group carry can be avoided. Let us consider the logic for forming the sum signals \((C)\) and carry signals \((\Pi)\).
\[ \begin{aligned} C_i &= X_iY_i\Pi_{i-1} + X_i\overline{Y_i}\,\overline{\Pi}_{i-1} + \overline{X_i}Y_i\overline{\Pi}_{i-1} + \overline{X_i}\,\overline{Y_i}\Pi_{i-1},\\ \Pi_i &= X_iY_i\Pi_{i-1} + X_iY_i\overline{\Pi}_{i-1} + X_i\overline{Y_i}\Pi_{i-1} + \overline{X_i}Y_i\Pi_{i-1}, \end{aligned} \tag{1} \]
where \(X\) and \(Y\) are addends.
To implement the adder in the “AND–NOT” basis, we minimize equation (1). The resulting expression for the carry has the form
\[ \Pi_i = X_iY_i + X_i\Pi_{i-1} + Y_i\Pi_{i-1}. \tag{2} \]
Let us find the inversion of expression (2):
\[ \overline{\Pi_i} = \overline{X_iY_i + X_i\Pi_{i-1} + Y_i\Pi_{i-1}} . \]
Obviously, this function is implemented by three Sheffer elements whose outputs are connected by a common wire. The inversion of the signal
the carry is obtained here in only one stage. Similarly, for the inversion of the sum signal we have
\[ \overline{C_i}=\overline{X_i \Pi_i \Pi_{i-1}+X_i \Pi_i+Y_i \Pi_i+\Pi_i \Pi_{i-1}}. \]
The inversion of the sum signal is implemented by four Sheffer elements whose outputs are combined. The formation time of the signal “\(C\)” is \(t_c=2t_{\mathrm{av}}\). The self-duality property of both functions of a binary adder makes it possible, by inverting the input variables, to obtain inversions of the sum and carry at the output. Using trigger registers for the first row of adders, we can feed the variables themselves to the odd adders, and their inversions to the even adders. In the next row of adders, the odd adders will receive inversions at the input, will generate carries, and will feed them to the input of neighboring even adders, which received the variables at the input. The variables are fed to the output trigger register in such a way that the direct product functions appear at the register output. Through the use of the functions “\(C\)” and “\(\Pi\),” obtained in one stage, the multiplication time for this construction is
\[ t_y=2(n+1)t_{\mathrm{av}}. \]
To obtain a speed of two microseconds when multiplying 11-bit numbers, it is necessary to have elements with an operating time of no more than 80 nanoseconds. For the elements participating in the formation of the sign and order of the product, the speed requirement is significantly lower.
Conclusions
-
When multiplying numbers of comparatively small word length, it is advisable to use matrix multipliers.
-
The amount of equipment in such multipliers grows in proportion to the square of the word length of the numbers being multiplied.
-
To increase the speed of such multipliers and to reduce the amount of equipment, it makes sense to complicate the logic of the circuits.
-
As adders of partial products, it is better to use circuits that form not the actual values of the sum and carry, but their inversions.
References
-
L. K. Golyshev. Structural Theory of Digital Machines. “Energiya,” 1971.
-
M. A. Kartsev. Arithmetic of Digital Machines. “Nauka,” 1969.
-
A. D. Shitin. Digital Computing Machines. “Energiya,” 1971.