Optimum Performance Standard Cell Array Multiplier

This invention relates to a cell array multiplier design which uses unique internal connections to increase the speed of the multiplier output by minimizing overall delay, given sum and carry delays for a full adder.

Traditionally, array multiplier performance was increased in one of three standard ways. First, recoding techniques, such as Booth's algorithm, have been used to reduce the number of partial products to be added within the multiplier. By using Booth's algorithm to reduce the partial products, the number of full adder (FA) columns was reduced, as shown by U.S. Pat. No. 4,168,530. Another example using Booth's algorithm is U.S. Pat. No. 4,575,812, which reduces the propagation delay by connecting each sum to a FA within the same column and two stages beyond that sum's stage. However, recoding techniques are not overly efficient when implementing both signed two's complement and unsigned multiplication, which the present invention does in fact implement. In order to provide signed and unsigned multiplication, the Baugh-Wooley multiplication algorithm was used as a design base.

The second area of potential performance enhancement involves variations in circuit design intended to speed up the longest signal path within the multiplier. The longest path is generally the carry path. However, multiplier arrays often do not have the freedom to use circuit design techniques, since they are implemented using a predetermined set of circuits, such as those used on the DCP-C CMPhilo chip. As a result, the logical operations available for design are limited to the specified chip's set, such as a CMPhilo bookset.

The third area of performance enhancement involves variations on the interconnection scheme, such as a Wallace tree or Binary tree, which are used to reduce the signal path lengths. The assumption made when using a Binary tree is that carry delays through the full adder are negligible. Unfortunately, this is rarely the case. As a result, the Binary tree algorithm produces a less than optimal interconnection strategy. The improvement provided by the present invention improves on the interconnection strategy.

Previous multipliers have used a very basic structure, as disclosed in U.S. Pat. No. 4,748,583, which shows sum and carry signals from each adder connected to adders within the next stage. Alternatively, VLSI circuits have been adapted to increase multiplier speed by reducing the number of stages and connecting carry signals to full adders beyond the next stage. For instance, U.S. Pat. No. 4,752,905 discusses connecting each carry signal to a FA two stages beyond that carry signal's stage, while U.S. Pat. No. 4,556,948 discloses connecting each carry signal to FA's up to six stages thereafter.

However, most custom designs are concerned with making interconnections regular or symmetrical in order to simplify the chip's layout, which in turn affects the chip density and performance. This symmetry of layout affects the choice of interconnection schemes and also determines whether more than one adder type will be used within the multiplier; for instance, whether to use a carry look-ahead (CLA) adder in some of the stages instead of a less complex ripple adder.

The present invention is not limited to the less complex ripple adders, since it utilizes a standard cell design system. The present invention also is not concerned with the effects of complex interconnection schemes upon the density of the chip, since the standard cell design system was a more limiting factor upon chip density. Moreover, the present invention is not concerned with using more complex CLA adders within the multiplier, since the performance improvement achieved by using these adders was considered to outweigh the increase in area. Because of the constraints imposed by the standard cell design system, the only area of improvement was in the interconnection of the full adders which sum the partial products, in conjunction with using a CLA adder for the last stage. Using a CLA adder for the last stage of a multiplier by itself would not create a significant improvement in performance, since a CLA adder achieves maximum performance when its inputs arrive simultaneously, whereas inputs to the last stage of the inventive multiplier arrive as nearly simultaneously as possible, because of the unique interconnection scheme.

An object of the present invention is to provide a standard cell array multiplier within which a unique interconnection scheme provides a high speed multiplier.

A second object of this invention is to provide an interconnection scheme which uses irregular or asymmetrical connection layouts within the multiplier to reduce the longest signal path through the multiplier.

Another object of this invention is to provide a method for determining the optimal interconnection scheme, whereby the connections are dependent upon each adder's sum delay and carry delay.

The present invention involves a new method of configuring the adder interconnects within a multiplier to obtain the best performance possible. This method depends upon the ratio of carry delay to sum delay for the adders. Therefore, an optimal design will be produced if the carry and sum delay estimates are reasonably accurate. By taking carry delay into account, the present invention uses a more realistic full adder model, which in turn leads to a better resultant configuration. The technique is recursive, and so builds the next column within the multiplier based upon the estimated carry delays of the columns built previously. Determining interconnections from the first few columns is quite simple; however, the problem grows more complex as the number of columns increases, for instance, such as for a 16.times.16 multiplier.

The present invention is a method of full adder column generation, which consists of initially listing all the inputs to the column as elements of a list, sorting list elements based on their estimated delay values, and then assigning the element's inputs to adders. Beginning with the first adder, each adder of the column is assigned three inputs from this list during each iteration of the method. Each adder assignment results in new carry and sum signals; thus, the sum has to be added to the input list, while the three assigned inputs are deleted from the list. The carry signal is retained as an input for the next column. The input list of the present column is gradually reduced by assigning inputs to full adders until the list has only one element: the sum from the last adder in the column. At this point, the column is complete. This method is repeated for every adder of every column, thereby generating the most time efficient adder connection scheme.

The performance of the standard cell multiplier has been shown to be comparable to a custom 16.times.16 multiplier array designed in the same technology. The worst case performance based on actual wiring capacitance is 63 ns.

FIG. 1 is a block circuit diagram of a conventional cell-structured 5.times.5 digital multiplier.

FIG. 2 is a block circuit diagram of a section of a 16.times.16 conventional multiplier.

FIG. 3 is a block circuit diagram of a section of the present invention within a 16.times.16 multiplier.

FIG. 4(a) is a block circuit diagram of column 1 of the multiplier of the preferred embodiment of the present invention.

FIG. 4(b) is a block circuit diagram of column 2 of the multiplier of the preferred embodiment of the present invention.

FIG. 5 is a flowchart representing the method of the present invention.

FIG. 6. is a block diagram representing a partial product of the present invention.

FIG. 7 represents a block diagram of the apparatus of the present invention .

In the following description of the preferred embodiment of the present invention, it is assumed that all partial products are available at the same time which is designated as time 0. Also, the carry delay for each full adder is assumed to be 3 ns, and the sum delay is assumed to be 4 ns. For the purposes of describing the algorithm, it is assumed that the multiplier performs unsigned multiplication.

The following notation will be used to describe the present invention: the multiplier inputs are designated by a(0...15) and b(0...15), which are sixteen bit signals. The partial products are designated by p(X,Y), wherein X and Y denote the inputs from which the partial products are derived. For example, p(14, 15) is equal to a(14) ANDED with b(15), as shown in FIG. 6. The multiplier output is designated by r(0...31), which is a thirty-two bit signal. Intermediate adder carry signals are denoted by c(X,Y) where X is the column number from which the carry is generated, and Y is the full adder within the column. Intermediate sums are denoted in a similar manner by s(X,Y).

The method of the present invention is most clearly understood by reference to an example, as set forth in FIG. 4(a), which shows the generation of the output S(1,0) of column 1, which requires one half adder. The carry signal C(1,0) of this adder becomes an input for column 2. To generate the optimum column 2 connections, first a list of column 2 inputs must be generated. The inputs to each column come from one of two sources; either the partial products of the corresponding inputs or the carry signals from the previous column.

The partial products of corresponding inputs for each column are determined by the two following ;) series:

where y equals the column, P(15-n,15+n-y) equals the partial product of inputs a(15-n) and b(15+n-y), and P(30-y-n, n) equals the partial product of a(30-y-n) and b(n).

Each partial product and carry signal included on the list represents elements of the list. Each list element specifies the output signal name (i.e. C(x,y) or S(x,y)) and that signal's accumulated delay. The accumulated delay represents the interval between the time the inputs a(x) and b(y) are available, and time the output signal is available. Each partial product has no delay, since partial products are immediately available, while each carry has at least a 3 ns delay.

Referring to FIG. 4(b), the initial list of column 2 is as follows:

The three partial products, which were generated from series (1) above, have a 0ns delay, and the carry C(1,0) from column 1 has a delay of 3 ns. These time delays are used to order the list elements in ascending delay order. Thereafter, the present invention groups the first three elements of the list as one set of full adder inputs to the first adder in column 2 (Fig. 4(b)). This adder generates a sum S(2,0), which is added to the list as a new element, wherein a 4 ns time delay is associated therewith. The partial products connected to this adder are removed from the list, since they are no longer available inputs for this column. Next, the list is resorted by delay, thereby rendering the elements of the list ordered by ascending time delays, as follows:

The input list now has only two elements, which are grouped as a set of half adder inputs to produce the final list or final output:

The final list shows that the sum for column 2 has an estimated delay of 8 ns. This delay is cumulative, reflecting the delay of S (2,0) plus the delay caused by the second FA of column 2.

As inputs are assigned, each full adder also generates a carry signal for the next column, which is added to the carry list. The final carry list of column 2 is as follows:

It should be noted that the carry C(2,0) from the first adder has a 3 ns delay, while the second carry has a 7 ns delay. The 7 ns delay is an representative of the delays from the sum S(2,0) and the carry delay within the second FA of column 2. This will be used as a part of the input list when generating column 3.

This process seems relatively straightforward for simple designs as described above. However, when considering a larger column, such as column 14, the possible inputs grow complex and computer assistance becomes helpful.

Before describing column 14 of the multiplier of the present invention, it will be useful to show a corresponding layout for a known multiplier.

The block diagram illustrated in FIG. 1 corresponds to a conventional 5.times.5 multiplier. FIG. 2 corresponds to a section of a known 16.times.16 multiplier; namely columns 13-16 and rows 4-12. Full adder (FA) 1, which corresponds to the 9th stage (row) in column 14, accepts as inputs the sum from FA 13, the carry from FA 4 and the partial product of p(7,9). Similarly, FA 2 connects with the sum of FA 1, the carry of FA 5, and the partial product p(6,10), and FA 3 connects with the sum of FA 2, the carry of FA 6, and the partial product of p(5,11). Thus, the symmetrical connection layout of the known multiplier is very apparent.

This circuit's negative effects on multiplier speed are also very apparent. In reference to FIG. 2,

FA 4 has a 4 ns delay between its input and sum output, which connects with FA 1. The sum of FA 1 adds 4 ns to the column's delay, and FA 2's sum adds another 4 ns delay. Therefore, the delay between the input to FA 4 and the sum output from FA 3 is 16 ns. Extrapolating this delay to the beginning of column 14, there will be a 44 ns delay from the time the inputs a and b are available until FA 3 outputs its sum, whereas the present invention only has a 15 ns delay from the time the inputs are available until the output of an adder 103 of the present invention which corresponds to FA 3 is available, as described hereafter.

FIG. 3 shows full adder connections of the present invention, corresponding to the full adder rows and columns shown in FIG. 2. More specifically, FIG. 3 shows some connections within columns 13-16 between FA 101-118. FA 101 obtains its inputs from the carry signals of FA 108, 109, and 110, while FA 102 gains as its inputs, the sum outputs of FA 111, 112, and 113, and FA 103 secures its inputs from the carry signals of FA 104 and 105, and the sum output from FA 101.

The connections of column 14 will be described hereafter. As described for columns 1 and 2 above, the present invention begins with creating a list of available inputs for column 14, which includes any partial products, generated by equation (1) above (with y=14), and the carry signals retained from column 13. It should be noted that every carry signal has a delay greater than 0, since these carries have accumulated delays from their corresponding FA carry paths, while every partial product has a 0 time delay.

The initial list (ordered in ascending order) for column 14 is shown in Table 1), from which the first three elements 18, 19, and 20 are used as inputs for the first adder of the column (not shown). This initial list is generated by the series of equation 1 for Y=14. This adder generates a sum S(14,0), which is placed on the list as element 21 (element (b) of Table 1) while elements 18, 19 and 20 are deleted. Note this sum has a 4 ns delay. This process of ordering, assigning and replacing elements is repeated throughout the column. Elements (i), (j), and (k) of Table 1 show the available input list for adders 101, 102, and 103 of FIG. 3, respectively. The first three elements (22, 23, and 24) of the list of element (i) of Table 1 act as inputs for FA 101. These elements correspond to the carry of FA 108, C(l3,4), the carry of FA 109, C(13,5), and the carry of FA 110, C(13,6). These signals combine to form the sum output of FA 101, S(14,8), which is placed back onto the available input list as element 25 in element (j) of Table 1. Element 25 is given an 11 ns delay, which corresponds to the 7 ns delay of the slowest input to FA 101 (element 24) plus the 4 ns delay within FA 101. This process is reiterated for the available input list in element (j) of Table 1, from which elements 26, 27, and 28 are chosen as inputs for FA 102. As a result, the following inputs for FA 102 are generated: the sum output of FA 111, S(14,5), the sum output of FA 112, S(14,6), and the sum output of FA 113, S(14,7). Accordingly, these sums are deleted from the available input list, and the sum of FA 102 is added as element 29, element (k) of Table 1.

It is important to note that the carry output list of column 14 has been continually updated as described above with reference to column 2. In other words, each time a FA's sum output is placed on the available input list, that FA's carry output is placed on a carry list. The carry list is used to retain the accumulated delay of each carry output. Once column 14 is configured (i.e. the FA connections are generated) these carries are used as inputs for the next column generation. After the output for FA 102 is generated, the carry list includes the following signals and delays:

FIG. 3 also shows an example carry path derived by the present invention.

FA 101 receives the carrys from FA's 108, 109, and 110, as determined by the example described above. The largest delay is 7 ns from FA 110, therefore the carry output of FA 101 is 10 ns. This carry is therefore connected to FA 118 in column 15, when repeating the column generation method. FA 118 outputs its carry signal with a delay of 13 ns, which is connected to FA 19 of column 16. This description of the connections between FA 101, 118, and 119, shows an example carry path determined by same method used to generate column 14. Therefore, the details of how to generate columns 15 and 16 were omitted.

FIG. 5 shows a flowchart for the method of the present invention. This method begins by initializing the FA sum and carry delays (step 501), and setting the output for column 1 (step 502). Next the column counter is incremented (step 503), and the column's initial list is generated (step 504). This list includes partial products and the carrys from the previous column (step 505). Thereafter, the first three elements on the list are chosen as inputs for an adder (step 506), and the adder's sum (step 507) and carry (step 508) are added to the corresponding lists. If the list is determined to include a single element (i.e. the column's output) (step 509), then the method moves to the next column (step 510). However, if the list contains more than one element, the method repeats steps 506-509. At step 511, if the column counter is not at the last column, the method repeats steps 503-511 for the next column. After every column has been generated (step 511), the method ends (step 512).

Table 2 shows all of the FA connections for columns 2-30 of the present embodiment of the invention. For instance, element (m) of Table 2 shows the input set 60 corresponding to FA 101, element (n) of Table 2 shows the input set 61 corresponding to FA 118, and element (o) of Table 2 shows the input set 62 corresponding to FA 119. Columns 1 and 31 do not use full adders since there are only two inputs for each.

Table 3 shows the program used to implement the method of the present invention, in accordance with the flow chart of FIG. 5.

FIG. 7 illustrates the apparatus by which the above method is performed. The apparatus 70 accepts includes input and output time pulse measuring modules 71 and 72. The input time pulse measuring module 71 measures the time value of each input pulse applied to each of said adder circuits in each row of said array to provide a plurality of input time pulses. The output time pulse measuring module 72 measures the time value of each output pulse of each of said adder circuits in each row of said array to provide a plurality of output time pulses. The list of output time pulses from module 72 is input to ordering module 73 arranging these output pulses in order. Thereafter, the ordered output pulses and the input pulses are transferred to the directing module 74 which directs the adder circuit outputs to inputs of other adder circuits based on the order in which the adder outputs are arranged. More specifically, directing module 74 directs each adder circuit output (along line A), being directed serially to another adder circuit in the same column, to one of the inputs of an adder circuit in the same column whose other inputs have time value equal to the selected outputs time value pulse or equal to the next greatest available time value. The directing module similarly directs each adder circuit output (along line B), being directed to an additional column, to an adder circuit whose other inputs have a time value equal to a time value of the selected output or equal to the next greatest available time value.

Although the invention has been described with respect to a preferred embodiment, it is not to be so limited as changes and modifications can be made which are within the full intended scope of the invention as defined by the appended claims.