Towards Concurrent Arithmetic: Residue Arithmetic and VLSI Citation Chiang, Chao-Lin (1984) Towards Concurrent Arithmetic: Residue Arithmetic and VLSI. Master's thesis, California Institute of Technology. doi:10.7907/mh9h-1v86. https://resolver.caltech.edu/CaltechTHESIS:04022012-150108167 Abstract No abstract. Item Type: Thesis (Master's thesis) Subject Keywords: (Computer Science) Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Johnsson, Lennart Group: Computer Science Technical Reports Thesis Committee: Unknown, Unknown Defense Date: 1 January 1984 Other Numbering System: Other Numbering System Name Other Numbering System ID Computer Science Technical Reports 1984:5135 Record Number: CaltechTHESIS:04022012-150108167 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:04022012-150108167 DOI: 10.7907/mh9h-1v86 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 6887 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 02 Apr 2012 22:27 Last Modified: 03 Nov 2025 20:24 Thesis Files Preview PDF - Final Version See Usage Policy. 3MB Repository Staff Only: item control page

Towards Concurrent Arithmetic: Residue Arithmetic and VLSI Chao-Lin Chiang . Computer Science Department California Institute of Technology 5135:TR:84 Towards Concurrent Arithmetic: Residue Arithmetic and VLSI by Chao-Lin Chiang 5135:TR:84 Department of Computer Science California Institute of Technology Pasadcna, California Submitted to the Computer Science Department in Partial Fulfillment of the Requirements for the Degree of Master of Science. The research was spousored iu part by the Defense Advanced Research Projects Agency (DARPA), and monitored by the Office of Naval Research (ONR) under contract N00014-79-C-0597. The research was also in part sponsored by the Office of Naval Research under contract N00014-84-K-00438. Acknowledgments Special thanks are due to my advisor, Lennart Johnsson, for his continued guidance and support on this research. I also wish to thank Tzu-mu Lin for his help and encouragement. Many thanks to everyone in the computer science department for their willing- ness to help and to be friendly. Table of Contents Introduction Part1. Residue Arithmetic and VLSI 1. Introduction e Weighted Number Systems e The Residue Number System 2. Residue Arithmetic and the Chinese Remainder Theercm e Congruence Relations, Modulo Operations and the Chinese Remainder Problem e Concurrent Computation in the Residue Number System ® Degree of Concurrency and Code Efficiency in the Residue Number System 3. Implementations of Residue Arithmetic e A Residue Adder e Residuc Multiplicrs e Pure Table Look-up Multiplier © A Quarter Square Residue Multiplier e An Index Transform Residue Multiplier e An Array Multiplier e Summary of Area Complexities of Difierent Multiplier Schemes 4. Residue Multipliers in nMOS e Delay and Arca Estimates e Performance Comparison between Residue Arithmetic and Binary Arithmetic « Chip Characteristics 5. Base Selection and Design Cost 6. Conclusion Part 2. Distributed RC Delay Line Model and MOS PLA Timing Estimation 1. Introduction 2. The Distributed RC Delay Line Model e A URC Element Driven by a Voltage Source with Source Resistance « A URC Element Driven by a Voltage Source with Source Resistance and Source Capacitance 3. MOS PLA Delay Estimation e The Worst Case Delay e Delay Estimates for Personalized PLAs e The Effect of Scaling e How to Improve the Performance 4. Conclusion References Introduction Arithmetic based on the residue number system is attractive because addition and multiplication are performed on each digit independently [Ga59]. It is a “concurrent” arithmetic. There are many important issues in residue arithmetic. Two such issues are the degree of concurrency and the code efficiency as functions of range requirements. From an implementation standpoint, it is important to find a good implementation of residue adders and multipliers for different ranges, and to select a basis for a residue number system satisfying the specific range requirement. Choosing a configuration that fully explores the potential of the residue number system at various stages of the technology is one of the major concerns of this paper. There are many alternatives for the implementation of a residue multiplier. Different designs are often evaluated in terms of two factors: cost and speed. Traditionally, the cost is evaluated by the number of IC components used. In VLSI, silicon area is more relevant. The signal delay in VLST cirenits is no longer determined by the number of gates in a path. Wire delays need to be included in realistic delay models. In [Ch&3a], a model is developed to estimate the delay of MOS storage structures such as PLA and ROM. The details of this model is contained in the second part of this report. This report is organized as follows: In part 1, the residue number system is introduced first. Then, several different designs of a multiplier based on the residue number system are presented and analyzed. Finally, base selection algorithms with respect to minimum delay or minimum area are presented. In part 2, “Distributed RC Delay Line Model and MOS PLA Timing Estimation”, a VLSI computation model for storage structures‘is developed in detail. -1- Part 1. Residue Arithmetic and VLSI 1. Introduction 1.1 Weighted Number Systems The decimal number system and the binary number system are weighted number systems. A number system is said to be weighted if there exists a seb of weights w,’s such that, for any number z, z can be expressed in the form z = >. GW, where the a,’s are a set of permissible digits. If the values for w,’s are successive powers of the same number, then the number system has a fixed base or fixed radiz, e.g., base 10 for the decimal number system, base 2 for the binary number system. The fixed base number system has the following important advantages: e Relative-magnitude comparison of two numbers can be mechanized easily. e The logic required for performing arithmetic is essentially identical for all digits. e Overflow detection is easily mechanized. The attributes which lead to these advantages impose a limitation on the speed with which many arithmetic operations can be performed. In both the binary and the decimal number system, truly parallel arithmetic operations, i.c., processing all digits concurrently, is not possible because of carry propagation. For all arithiuetic operabious in such oumber systems, each digit of the resull is a function of all digits of equal or lower significance. This characteristic imposes a fundamental limitation on the speed of arithmetic in weighted number systems. —~ 9 _ In order to achieve high-speed computation, other number system that allows concurrent arithmetic is needed. Such a number system is the residue number system. 1.2 The Residue Number System In the residue number system [Ga59], a number is represented by several residue digits. The arithmetic operations addition, subtraction and multiplication are inherently carry-free, i.e., each digit of the result is a function of only one digit from each of the operands. In particular, for the case of multiplication, the need for partial products is eliminated. This local property allows a high degree of concurrency. The residue number system is not a weighted number system, however, and does not have many of the advantages listed above for such systems. Operations such as division, magnitude comparison and overflow detection are difficult in a residue number system. Several attempts have been made to find efficient algorithms to solve these problems [Ba69], [Ki73], [Ba80]. However, due to the inherent non-local properties in these operations [$z67], no efficient algorithms with complexity comparable to addition and multiplication have been found. The complexity of these operations has prevented the residue number system from use in general purpose computers. However, there is a large class of digital signal processing and pattern recognition problems in which addition and multiplication dominates [Je77], [Je79], [Ts79], {Hu81], [Fv82]. Iu those applicatious, the residue arithmetic is competitive with binary arithmetic. In [Je77], a residue number system is used to implement a 64th order bandpass FIR filter. In [Ts79], a hardware implementation of a FFT ~g§- based on the residue number system is proposed. In [Fo82], a VLSI architecture for pattern recognition using residue arithmetic is described. Other applications can be found in [Je79] and [Hu81]. In these applications, the required range is typically small (10 to 24 bits) and the individual residue adders and multipliers are implemented by table look-up. The size of the tables ranges from 1K to 5K bits and commercial high-speed ROM’s are used to realize the tables. In the references above, the cost is measured in terms of IC components used and the performance comparisons are based on particular cases. In the era of VLSI technology, hundreds of thousands of devices can be integrated on one chip. Therefore, the need for a new criteria to evaluate different VLSI designs is evident. Area is a measurement that corresponds to counting IC components. In residue arithmetic, the table look-up scheme is one design alternative of many. Two factors make the table look-up scheme unfavorable. First, the table size grows exponentially with the number of inputs. For a large range requirement, the table size will soon become too large. Second, the MOS PLA or ROM that implements a table contains long poly wires. The wire delay does not scale well as feature sizes scale down. Hierarchically organized tables or storages as described in [Me80] can be used to reduce the delay to logarithmic in the table size, instead of proportional to its size. In this report, the effect of these two factors - increased range requirement and reduced feature size - on different design alternatives is analyzed in detail. In the next section, the Chinese Remainder Theorem and some basic concepts of a residue number system are introduced. Two important issues, the “degree of concurrency” and the “code efficiency,” are discussed. In section 3, several implementations of residue adders and multipliers are discussed. Based on -4- VLSI computation models, the cost functions with respect to time and area are calculated and the relative competent range of each implementation is analyzed in section 4. In section 5, optimal base selection algorithms with respect to time and area are presented. 2. Residue Arithmetic and the Chinese Remainder Theorem 2.1 Congruence relations, Medulo operations and the Chinsse Remainder Problem Consider three integers A, a and 6. If there exists another integer ¢ such that A=a+6bt, then A, a and 6 satisfy the congruence relation A= a(mod 8) which is read, A is congruent to a modulo b. a is called the restdue and 6 is the modulus of the number A. For convenience, A (mod 6) is sometimes abbreviated as |Als. The problem of computing solutions to systems of simultaneous congruence relations, such as Z=1mod5 z=Omod7 z=4mod8 was studied by Chinese mathematicians as far back as the first century A.D. In deference to this historical background, we call the problem of solving a system of n congruence relations & =r, mod mz (kK =0,...,%—1) the Chinese Remainder Problem. It is readily verified that z = 196 is a solution to the above problem. The general algorithm for computing solutions to Chinese Remainder Problems is based on the Chinese Remainder Theorem [$267], [Ah74]. 2.2 Concurrent Computations in the Residue Number System Let {m: | ged(m:,m;) = 1, fori?’ A 7, i,f = 1,.,p} be a set of pairwise relatively prime numbers and R = ][5_, mj be the range of the set. According to the Chinese Remainder Theorem, any number X in the range [0, R-1] can be represented uniquely by a set of residues (21,...,%,), where z; = X modm; is called the restdue digit with respect to modulus m; and the p-tuple (2),..., Zp) is a residue code of the number X. The sct {r1,..., mp} is called the base of the residue number system. Table 1 shows the residue number representation corresponding to the integers 0 to 29 with respect to moduli 2, 3, 5. A number represented in residue code can be converted to binary code according to the formula [S267] : P x= If hy- nj = mod R : i to=1 - R 1 = where m=-— and |-—|=ae (mj-a)=1modk mj; mj; Integers Residue Digits Integers Residue Digits Moduli Moduli 2 3 5 2 3 5 0 0 0 0 15 1 0 0 1 1 1 1 16 0 1 1 2 0 2 2 17 1 2 2 3 1 0 3 18 0 0 3 4 0 1 4 19 1 1 4 5 1 2 0 20 0 2 0 6 0 0 1 21 1 0 1 7 1 1 2 22 0 1 2 & 0 2 3 23 1 P4 3 9 1 0 4 24 0 0 4 10 0 1 0 25 1 1 0 11 1 2 1 26 0 2 1 13 0 0 2 27 1 0 2 13 1 1 3 28 0 1 3 14 0 2 4 29 1 2 4 Table 1. Residue representation of the numbers 0 to 29 for moduli 2, 3, 5 Example: Conversion of a residue number by use of the Chinese Remainder Theorem. For moduli my, = 18, mz = 11, mg = 7, and m4 = 9, find the number whose residue representation is {4, 2, 4,7}. Solution 4 R= || m;=13 x 11x 7x 9 = 9009 f=1 \malm, = [11 X 7 X 9|is = [693113 = 4 then |—-| =10 Ty tis |rte|me = [13 X 7X Bra = [81911 = 5 then |—| =—9 , 72 111 |7%3| m3 = [13 X 11 xX 9|7 = |1287|,; = 6 then |—|] =6 Tits \¢ [mu] mq = [13 X 11 X To = 1001]) = 2 then |—-| =5 Ma \g |%|so0e — [693 XK |10 X 4],, +819 x [9 X 2]11 + 1287 X [6 X 4|7 + 1001 X [5 X 7g] Gono = |693 X 1+ 819 X 7+ 1287 X 34+ 1001 X 8] gooo = |18295|9009 = 277 Let X and Y have residue codes (21,...,%p) and (y1,..., yp) respectively and X,Y,X+Y,X-¥ €[0, R-1]. Then [Ga59] |X +¥|m, = |tetyilm, and [X-¥|m; = |ti-yilm, It follows that (JX + Vrs ey |X + ¥ my ) = (]e1 + yalmgs-s lap + ¥p|mp) (1X . Yas sony LX . Yim, ) = (ler . Hil mas os [Yn . Unlme) Example: Addition in the residue number system For the moduli 4,3,5 and 11 add = 102 + {2,0,2,3} and y = 211 + {3, 1,1, 2}. Solution: Moduli: 4 35 102 <— *{2, 0, 2, 3) +211 <— — {3, I, ], 2} |313|sceo = 318<——— {1, 1, 3, 5] Example: Multiplication in the residue number system For the moduli 4,3,5 and 11 multiply z = 25 + {1,1,0,3} and y= 21 + {1, 10, 1, 10}. . Solution: . Moduli: 4 3 5 11 25 -—_———— {1, 1, 0, 3} X21 -———_+ {1, 4, .1, 10} {525[eso = 525+ [1, 0, 0, 8} The examples above show that addition and multiplication of two numbers can be carried out on each digit independently. When these operations are performed in each residue digit concurrently, the overall speed is often limited by the residue digit with respect to the largest modulus. For a given range R, if the moduli are properly chosen such that the maximum modulus is as small as possible then the maximum speed-up can be achieved. However, the maximum modulus for a given range can not be arbitrarily small since each pair of moduli must be relatively prime numbers. Indeed, there is an analytic relation between the —~10- required range and the maximum modulus. This relation indicates the inherent degree of concurrency in the residue number system. 2.8 Degree of Concurrency and Code Efficiency in the Residue Number System Consider a residue number system with base {7mi,...,mp} and range R = Ii ,™:. Each residue digit is typically encoded in the binary number system. Let M; be the number of bits required to encode the i-th residue digit and Nj, be the number of bits required for a direct binary encoding of the largest number in the range [0, R-1], ie., M; = [logm:], Np, = [logR], where log = logy. Denote M = max{M;} the number of bits required to encode the largest moduli and Ny = }o) Mj; the total number of bits required to encode the entire residue code, The quantity y = N}/M is the ratio between the number of bits needed in the hinary numher system and the number of bits for the largest: madulus in a binary encoded residue number system. We define it as the degree of concurrency of the residue number system. Another quantity 7 — Np/Nr is the ratio of the total number of bits required to encode numbers with equal range in a binary number system and a residue system. We define it as the code effictency of the residue number system. Table 2 lists several bases for some ranges and the accompanying values of M, Np, Nr, 7 and 7. Note that all moduli are of the form p*, where p is prime. Moduli are listed in order of increasing p. The reason for choosing these particular bases will be clear later. From table 2, it is easily seen that the degree of concurrency (7) is monotoni- on i moduli M | Np | Nr 7 log Np, /M n 8,3,5,7 3 | 10 | 12 | 3.33 1.11 0.91 16,9,5,7,11,13 4 | 20 | 22 | 5.00 1.08 0.91 32,27,25,7,11,13,17,19,23,29,31 | 5 | 48 | 51 | 9.60 1.12 0.94 64, 27,25,49,11,13, ... ,53,59,61 6 90 97 15.00 1.08 0.93 128,81,125,49, ... ,107,109,113 | 7 | 184 | 196 | 26.29 1.08 0.94 256,243,125,49, ... ,239,241,251 | 8 | 363 | 386 | 45.37 1.06 0.94 Table 2. Degree of concurrency (7) and code efficiency (n) cally increasing with the range. Indeed (log Np)/M approaches 1 as the range increases. This follows from the fundamental theorem of arithmetic. A proof is given below. The significance of this property is that instead of Np-bit arith- metic, log Np-bit binary arithmetic suffices. However, O(N, / log Np) such units are required instead of one Nj,-bit unit. Since each residue digit is binary encoded, only m; out of Mi available codes are used. There is some redundancy in the residue code. Therefore the code efficieucy is always less tlhau 1. However, table 2 shows that the code efficiency is greater than 0.9 for ranges of interest and it can further be proved that Np/Nr > 1 as Np — o. That the property O(M)=O(log Np) follows from the fundamental theorem of arithmetic will now be shown. Definition 1. {m,...,m,} is a feasible baze for a range R if any two elements in {mi,...,mp} are relatively prime and the product of all elements in {mi,..., mp} is greater or equal to R, ie., ged(mi,mj) = 1 for ¢ # j, i,f = 1,..,p and P f=1 the base. m; > R. Denote the largest modulus in {mi,...,mp} as the norm of — 12 — For example, {3,5,7,11} is a feasible base for the range R=1000, but not a feasible base for the range R=1200, since 3 X 5 X 7 X 11 = 1155 < 1200. The norm of this base is 11. {6,7,9,11} is not a feasible base for any range since 6 and 9 are not relative primes. Definition 2. Let z be the norm of a feasible base {m,,...,m,} . Then this base is also an optimal base if for any other set {71,...,nq | gcd(ni,nj) = 1, fori j, £7 =1,.,9, and ny < 2,Vi}, [7 ns < TPR, mi. Definition 2 means that if a base is constructed with the restriction that its norm is less than x, then the range has an upper bound R, which is achieved by the optimal base. The upper bound R is a function of z, ie., R—R(z). The following lemma gives the construction of an optimal base and the characteristic of R(x). Lemma 1. (Construction of an Optimal Base) For any x > 2, the set of moduli {pj | pi: ith prime, pi<a< pr't?} forms an optimal base with range R= R{z) = TIyptice Pi’ where ky = lioee |: Ii Proof: (1) {p**} is a feasible base since p;*’s are relatively prime for different i (2) Let {mi,...,mp} be the given base and {mi,...,m¢} be another feasible base. By the fundamental theorem of arithmetic [Ha79], there exist a unique prime expansion for the range of the base {m1,...,mp} , and for the range of the base {11,...,m} . i=] i=1 — 18 - and Lf = [2 (2) j=l i= where p; is the 7th prime number. Assume nj < max {m;} for all 1 <j < gq, then for every term pi! 1 in eq(2), pi’ < some n; < max {m;} < z. The first < holds because each pe divides exactly one n; (otherwise, elements in {m,...,n,} are not relatively prime.) The second and third < hold due to the assumptions. Compare eq(1) with eq(2) term by term. In eq(2} p;? < x, while in eq(1) pl? < 2 < phit! hence I; < &; for all i. Therefore We. ny < Te, log. « Lemma 2. log(R(z)) = log Ul pier! is of order =. vey! <a Proof: see [ITa79] pp. 341. Theorem Let Np be the number of bits required for a direct binary encoding of numbers in the range [0, R-1] and M be the number of bits required for binary encoding of the maximum possible digit in a residue representation of the same numbers. Then M= O(log Np) provided that the base is an optimal base with range > R. ~14- Proof: Let M = pz[R(z) > R] where yw is the minimalization operator. Then the optimal base with norm M achieves range > R. By the definition of M, R(M—1) < R < R(M), ie., log R(M —1) < logR < log R(M). By Lemmas 1 and 2, O(M)=O(logR). Since M=[log M] and Ny} = [logR], it follows that M=O(log Nj). ~ 15 — 3. Implementations of Residue Arithmetic The concurrent property of the residue number system provides a method to achieve high-speed computation. However, addition and multiplication of each digit is more complex than in the binary number system in that it is performed modulo the set. of integers, mi, -..,%%,. For moduli of the form 2", 2"+ 1 or 2"—1, the modulo operation is essentially for free and implementations of residue arithmetic is simple [Et82], [Ta82]. However, if the selection of moduli is limited to the form 2,2" +1 or 2" —1, (“easy” base) the degree of concurrency will be reduced since the available choices of moduli arc fewer and the maximum modulus is larger, see Table 3. In fact the code efficiency is slightly higher for the easy buse, bul the uuimber of bits uecded fur the waatuuin base rapidly becomes significantly larger. Performing the modulo operation by a restoring or nonrestoring division algo- rithm is very time consuming and should be avoided. Finding a good algorithm for the modulo operations therefore becomes an essential part of realizing an efficient residue arithmetic system. We will now discuss a few alternatives for the implementation of multiplication modulo arbitrary (but fixed) integers. Addition and multiplication modulo the integers m1, mo,.., Mp are traditionally implemented by table look-up [Je77], [Hu81], [Ba82], [Fo82]. The table look-up scheme provides many advantages: it is programmable and easy to design; it has a very regular structure and can be made very dense. Since the table size grows exponentially with the number of inputs, it is almost impossible to implement a 10-bit by 10-bit adder or multiplier in the binary number system (22° 1M bits!). However it is possible to decompose a large number, say 18 bits, into several 3 or 4-bit residue digits (see Table 2) so that the table size can be kept small when implementing residue adders or multipliers in each residue digit. ~ 16 — optimal base easy base Np | Norm; M|Nrji 4 n Np, | Norm ;|M/Nrj] 4 7 10 & 3,12 ) 3.33 | 0.91 9 8 3! 44 (3.00 | O81 20 16 4 | 22 | 5.00 | 0.91; 20 32 5 | 22 | 4.00 | 0.91 48 32 A | ORT 940 | 0.94; 64 1024 10; 56 |5.40 | 0.96 90 64 6 | 97 |15.50 0.98) 95 16384 | 15) 96 |6.33 | 0.99 184} 128 |7 | 196 | 26.29 0.94 | 180] 4194304 | 22/181] 8.18 | 0.99 Table 3. The norms, degree of concurrency, and code efficiency for an optimal base and an easy base With residue encoding of the operand, they can be decomposed into O(N, /log Np) residue digits. Each digit is encoded by at most O(log Np) bits. If the table look-up scheme is used to implement a two-operand adder or multiplier in the binary number system, the table size is O(N, » 9?Nb }=0(N, : 4Nb) bits. On the other hand, if the adder or multiplier is implemented for residue en- coded operands, then each table is of size O(log Ny - 2?!°€N*)=O(log Ny, - Np?) bits and the total size is O((Nb/logNb) - logN, - N,”)=O(N,*). The ad- vantage of the residue number system is clear since the table size in the bi- nary number system grows exponentially, while in the residue number sys- tem it grows at a polynomial (cubic) rate. The table look-up scheme without partitioning has some drawbacks, however. First, O(N»*) is still too big for a large range requirement. Second, a large storage contains long wircs unlcss hierarchically organized. The wire delay dves not decrease with reduced feature size and eventually becomes a performance limiting factor. A hierarchical storage as described In [Me80] has an access time that grows logarithmically with the storage size. A few alternatives to the ~11- table look-up method will be discussed in the following subsections. The time- space complexity of each design is analyzed. For the time complexity of storage structures the model derived in the second half of this report is used. 3.1 A Residue Adder Residue addition 2; = (t; + y:})mod m:, where 0 < 2;,y:; < mi—1, can be computed as (ere if situ < mi: a= "last y:—m if zat ys > mi One M;-bit adder can be used to compute 2; + y; while another computes Zitii—m;. The carry bit generated from the second adder indicates whether or . not a+; Is greater than m;. A multiplexor controlled by the carry bit selects the correct output, see Figure 1. In this implementation, 2M; 1-bit adders and M; multiplexors are needed. tity 9 vi Zit Ui —m: T7 U pn Zit yim-— mM; L J CARRY Figure 1. An implementation of residue addition - 18 - 3.2 Residue Multipliers Three different methods to implement multipliers for one residue digit have been evaluated: 1. pure table look-up 2. combinations of tables and adders 3. arrays of adders 3.2.1 Pure Table Look-up A table for a one-digit residue multiplier has two M;-bit inputs, z; and y;, and produces one Mj-bit output, 2; = (%:-yi) mod mz, see Figure 2. The total number of bits in one table is M,2?™i == M,4™). For o(N b/ log Np) digits, the total table size is ), Mi4™1 es Np® bits. : ay 4 vi TABLE per er eam) Figure 2. Table look-up residue multiplier —~ 19 - 3.2.2.2 A Quarter Square Residue Multiplier [Da65] Figure 3 shows another type of residue multiplier. It realizes the identity: t ifm; 4 4 ms i Im; The “modular quarter square” Ou is implemented by table look-up. There Mm; are two tables for each residue digit. Each table has Mj2™it+ — 9m,2™i bits. For O(Np/ log Ny) digits, the total table size = > 2-2Mi2™" e~ (Np/ log Ny) - (4log Ny) - 2°¢N® = QNF bits. Note that the table size is O(N,) compared to O(N, *) if a single table is used. On the other hand, one Mj-bit binary adder/subtractor and one M;,-bit residue subtractor are needed for each residue digit. The total number of 1-bit adder/subtractors is of order O(N;). 3.2.2.b An Index Transform Residue Multiplier One familiar method of multiplication is “ log transform — addition — antilog transform ” [Ki71]. Similarly, residue multiplication can be performed by “ index transform — residue addition — reverse index transform ”. The index transform 7ND, is defined by [Sz67]: IND,C =bmodP «+ 1r>=CmodP, P prime For m; a prime number, an implementation of a residue multiplier based on the cquation : IND,2zj+IND,y;)mod(m;—-1 les Bilmg = [rONDHEEHINDevd mod msm) | ~ 20 — I-l wn, 3. A quarter square residue multiplier IND;* Fo at yi 3 ey ADD/ SUB hi ci Vi m3 Figure | eT ——wm-) IND; aa |+| meg) a vi ——w1 IND, ~ 91 — Figure 4. An index transform residue multiplier ro} a is shown in Figure 4. The index and reverse index transform is implemented by tables. For each residue digit, there are two tables for the index transform and one for the reverse index transform. In each table, both the input and the output have Mj bits. The table size is 3M,2™i bits. For O(Ny/log Ny) digits, the total table size is FY (Np/ log Np): 3log Np2'°eN» = 3N,*. There are Mj 1-bit adder/subtractors in one digit. The total number of 1-bit adders is O(N;). 3.2.6 An Array Multiplier A residue array multiplier is composed of two parts: (1) a binary array multiplier and (2) a converter performing the modulo evaluation of the product. The binary multiplier has a delay of O(M) and an area of O(M:?). The complexity of the conversion part can be made equal to that of the binary multiplier by employing carry save adders [Hw79]. Let A be the 2M; bit product, m; be the M; bit modulus, and z; the M; bit output number, 2; = Amodm,;. To compute 2, the distributive property of the modulo operation over addition is used: (aem;—1 g?Mi-1 +... + an, 2! + OM,—1 gMi-t + veg 2°) mod 7; = = (ens (2?™i~? mod mi) + ... + anr,(2™ mod mi) + (amy—1 277 4+... + 292°) ) The M; highest order hits ag, 1, Gont,—2, ---; Gam, can be used to control whether or not the Mj-bit constants (2?™i—* mod mj), (22Mi-? mod mj), ..., (2Mi mod m;) shall be added to the M; lowest order bits, Figure 5. —~ 9D _ The conversion part consists of M; stages of M;-bit adders. Each adder stage needs o(M;) time with the carry propagating from one bit to the next. The total delay is o(M?). However, if the carry for each bit is fed into the next stage only O(Mi) time is needed. An additional stage is needed to convert Mj + 2 bit numbers into M; bit residue numbers. For one residue array multiplier, the area is O(M&”). The total area of O(N, /log Np) residue digits is -& O((Ni/ log Ny) : (log N,)”) =O(N, log N,). In the binary to residue conversion part, a Booth (or Booth-like) algorithm can be used to reduce the number of adder stages by pairing the high-order control bits. For instance, bit j, and j+1 as well as the carry bit generated from the last conversion stage can be used to decide which of the 8 constants to be added. j j+1 carry constant to be added 0 0 0 Omod m; 0 0 1 2Mi mod m; 0 1 0 2)+1 mod mi 0 1 1 2547 + 2) mod m; 1 0 0 2) mod m; 1 0 1 2) + 2Mi mod m; 1 1 0 23+ 2541 mod m; 1 1 1 2323+) 4 oMi mod m However, in each stage a few constants need to be stored. It is a trade-off as to how many bits should be grouped in one stage. As a rule of thumb, the number of constants in each level of the adder should not exceed 8, therefore no more than 2 bits are to be grouped in this scheme. — 93 _ BINARY MULTIPLIER j M; M;-1 0 { { MUX ADD slp MUX ZADD- carry MUX &ADD LAST STAGE CONVERSION bit number ab==00 —e +0 ab==01 —= +2/ mod m; ab=10 —— +2M: mod m; ab=11 —= +2/ + oM; mod m; Figure 5. A residue array multiplier - 4 - 3.3 Summary of Area Complexities of Different Multiplier Schemes Some features of the four residue multiplier designs discussed above are sum- marized in Table 4. From this table it is clear that the quarter square approach is of limited interest, and that each of the other approaches may be superior to the rest depending on the value of M;. To determine performance characteristics as well as more precise area requirements, and their dependence on feature sizes, some sample designs were made in nMOS. Table(bits) | 1-bit Bin. Adder | 1-bit Res. Adder TABLE Mi4™i 0 0 QUARTER SQUARE 4M;2™ M; Mi INDEX TRANSFORM | 3M,2™5 0 M; ARRAY 0 2M? | 0 Table(bits) | 1-bit Bin. Adder | 1-bit Res. Adder TABLE N.° 0 0 QUARTER SQUARE 4N,,? N; N; INDEX TRANSFORM | 3N,? 0 N; ARRAY 0 2Np» log Np 0 Table 4. Some features of residue multipliers for one residue digit (top) and the whole system (bottom) — 95 — 4. Residue Multipliers in nMOS 4.1 Delay and Area Estimates In the last section, different schemes for implementing residue multipliers and their relative complexities were discussed in terms of order statistics. For most applications, more accurate performance evaluations are necessary. Since different residue multipliers are composed of tables, adders, or a combination of both tables and adders, the total delay time and chip area can be calculated by adding the delay and area of the basic building components - tables and adders. In general, tables are implemented by PLAs. In [Tr83], an equation is derived to calculate the chip area of MOS PLAs in terms of the number of inputs, minterms and outputs. To estimate the delay of a MOS PLA, a model based on an extension of the r-model [Me80] is developed in the second part of this report. The worst case delay is expressed in terms of the number of inputs, minterms, and outputs (see eq. 12 in Part I). The delay time and the chip area of various adders may differ significantly due to the great diversity of designs. For a reasonable trade-off between delay time and chip area, most adders are in the area range 3000\? ~ 5000d? and with a delay of 407 ~ 607. To first order a one-bit adder has area = 4000)? and delay= 50r. We have derived a method to calculate the delay and area of tables and adders. Therefore the delay time aud chip area of diferent residue inultIpHers is easily obtained since the size of the basic building block in a residue multiplicr is known. Figure 6 and 7 contain delay estimates for residue multiplier designs in — 9§ -— 4pm and 0.5um nMOS. The delays are computed in a manner illustrated by the following examples taken from Figure 6. We calculate the delays in three different 5 X 5 residue multipliers as specified in the third row. 1. Table look-up multiplier: The table is implemented by a PLA with 10 inputs and 5 outputs. There are as many as 2° — 1024 product terms (rows) in the AND-plane. On the other hand, the OR-plane has only 5 columns. The large number of product terms implies a long wire delay. In order to minimize this delay, the bit pattern can be reorganized so that the PLA has relatively balanced AND- and OR-plane (see part 2, section 4, subsection “How to improve the performance” item 2). In this particular 10-input 5-output PLA, if 6 bits are used for the inputs to the AND-plane, then the number of product terms is reduced to 64. However, the OR-plane will generate 80 outputs. Only 5 out of these 80 outputs are selected in a multiplexor which uses the remaining 4 input bits as control bits (2* = 16 = 80/5). In this configuration, the actual number of inputs, product terms and outputs used in the delay equation (eq.12 part II) are I=6, P=64, O=80 respectively. Using the values of I, P, and O in the delay equation gives the delay = 923r 2. Index Transform Multiplier The delay in a 5 X 5 index transform residue multiplier is composed of the delays in the INDEX transform table, the mod (m; — 1) residue adder and the INVERSE transform table. The INDEX and INVERSE INDEX transform tables are implemented by PLA’s with 5 inputs and 5 outputs. To make the table _— oF — square like, the actual number of inputs is 4, the number of product terms is 16 and the number of outputs is 10. Using the values I=4, P=16 and O=10 in the delay equation gives a table delay of es 1597 The critical path in the 5-bit residue adder consists of 6 1-bit adders. This is a delay of = 6 X 507 = 300r. The total delay is 159 X 2+ 300 = 618r. 3. Array Multiplier The signal in a critical path propagates through 4 X 5 = 20 adders. Therefore the delay is es 20 k ANr = 1NNNr. As is apparent from the figures, table look-up does not scale well if the storage is unstructured. The delay decreases only slightly. When measured in ¢ it increases significantly. The index transform approach employs much smaller tables. The delay measured in r increases only slightly for M < 8 bits, ie., the delay is reduced almost to the same extent as the switching speed of the devices while the feature sizes are reduced. The areas, see Figure 8, expressed in terms of ? [Me80] is to first order independent of the feature size. —~ 93 — Delay(r) F eoo0t ! / 1800 t * / \ 1800 A / X% f ‘Array y ~ mA 1400r / a 7 / K a 1200/7 a ae ic 1000 a r 7 ~N Index Transform 4 ‘ ra , ¢ e * a x Sf eoor ~~ ae i v = a 400 fF aw L?. \_Table “ 200 -——*~ —> M;, (bits) 1 lt I L t t 4 _& 6 7 8 Number of bits Table Ind. tran. Array 3 173 331 606 4 396 454 800 5 923 618 1000 6 2220 858 1200 7 5724 1137 1400 8 16553 1602 1600 (unit: 7 Ir Fe 0.2ns) Figure 6. Delay in residue multipliers for 44m nMOS —~ 99 - 2000 -- 1800 F j ‘ 1600 f LAM f aN a Array 1400 . 1200/7 / a / / . A 1000 F 4! 7 a A KX 800 ae “ Index Transform a , a / 600F x f Poat — bo \ 4007 I af - wit _* —~—»»- M; (bits 200k 7 a _— Table Mi (bits) - ft h a | ! | n 3 4 5 6 7 8 Number of bits Table Ind. tran. Array 3 188 335 600 4 475 464 800 5 1327 646 1000 6 4270 922 1200 vé 159074 1277 1400 8 67015 1997 1600 (unit: 7 ire 0.025ns) Figure 7. Delay in residue multipliers for 0.52m nMOS - 80 - 600 600 400. 300 200 100 Area({1000)7) / i x | ‘ Array if QL Index Transform ao iy “O” cc _ Table ——-— M; (bits) 4 [ 1 I _ _t 3 4 5 6 vi 8 Number of bits Table Ind. tran. Array 3 45 95 115 4 147 168 207 5 524 282 297 6 1870 543 407 7 8000 1007 591 8 32000 2177 664 (unit : 1000\7) Figure 8. Chip area of residue multipliers - 81 - 4.2 Performance Comparison between Residue Arithmetic and Binary Arithmetic Figure 9 shows the relative speeds of multiplying two N,-bit numbers in the residue number system (delay=T,) and the binary number system (delay=Ty). T, is taken to be the minimum delay of the three alternative designs investigated, ie., table look-up, index transform, and array multiplier with conversion. The values for T, are obtained from Figure 6. T, is obtained by assuming that a binary array multiplier is used. An Np XNp array multiplier has a delay time T,==2N, X (1-bit adder delay). For M>7 the array scheme is the most effective way to implement a residue multiplier. The speed-up ratio T,/T, between residue arithmetic and binary arithmetic is of O(N,/logNy). In a rosiduc array multiplier, the binary to residue conversion part and the binary multiplication part have the same delay. Therefore, Tp/Tre 7/2 For a relatively small range R, the actual speed. up ratio is better than 7/2. The fact that the speed-up is better than the asymptotic ratio for a small range is due to the use of different implementation techniques. Table look-up is efficient for a small range. For a large range residue multiplication as well as binary multiplication make use of array multipliers. Roughly speaking, the speed for multiplication in the residue number system is about 5 to 10 times higher than the speed in the binary number system for a moderate range. ~ 82 — or wm Wh TM ONO OD Ny, (bits) = | J 30 60 90 120 150 180 210 © Np N; M 4 Ty Tp T,/T; 10. 12 3 3.3 173 1600 5.8 20 22 4 5.0 396 2000 Bl 48 51 5 9.0 618 4800 7.8 90 97 6 15.0 858 9000 10.4 184 196 7 26.3 1137 18400 16.2 (4um nMOS technology) Figure 9. Comparison between residue and binary arithmetic — 88 - 4.3 Chip Characteristics A parameterized residue array multiplier has been designed. The multiplier performs M; X M; bit residue multiplication with respect to modulus m;. The design is composed of two parts: a M; X M; binary multiplier that produces a 2M; bit result, and a binary to residue converter which converts a 2M, bit binary number to a M;j bit residue number (with respect to the modulus m;). Both parts are composed of arrays of adders. A Binary Multiplier with Carry Save Adders The binary multiplier is composed of arrays of carry save adders. In a multiplier which consists of carry save adders, there are two critical paths: the carry chain and the sum chain, Figure 10. The speed of generating the sum bit should be as fast as the speed of generating the carry bit. A Manchester carry chain as presented in [Me80] enhances the speed of carry bit generation at the expense of the speed of sum bit generation. Figure 11 shows the logic diagram of a nMOS carry save adder. The layout is in Figure 12. Circuit simulation results indicate that the delay for generating sum bits and the carry bit are about the same (8 & 10 ns for 4 wm technology), see Figure 13. — 84 - { J i [4 ty sum chain { { ii cs ] ] ! 7 ae | i] ! il { 4 { 17 4 carry chain Figure 10. Sum chain and carry chain — 85 - Cin L Ain = Carry ai - Bin I Sum It Figure 11. The logic diagram of the carry save adder _~ 86 — Figure 12. The layout of the carry save adder ~ 37 - a0+d000'9 00+0d009°S 00+a000°2 to-000°9 " F0-a899°% * JO-dE69'S * 40-d202°S * J0-d298'°% * TO-QLIt' ” TO0-d528° " OO+0PTT'T * O0+0ETE'S * 00+d809°) * 00+0496°% * 90+q000°9 * 00+0000°9 * 00+@000°3 " 00+0000°9 * 00+a000°9 * 06+0000°9 * 00+0000°9 * 00+0000'°9 * 090+9000°9 * 00+a000°9 * 00+a000'¢ * 00+dr00°9 * 00+dr00°9 * 00+dr00°2 " 00+d366') * 00+d566'P * 00+dL76'9 * 00+0322°9 * 00+0366' 8 * 00+0369°S * 00+0221°T * FO-GEeL's * 40-0529°2 * JO-€379'S * 70-G379'°S * 40-G879°S * FO-d399'°S " 70-379" 2 * 10-0379'S * T0-339°2 * 7O-G379'°S 00+000°t- -~---~---—— (= +0) X 80-a000°S 80-0096" F 80-4006'T 80-d098'F 80-008 't 80-a0ge't 80-a00zZ'S 80-a099'F 80-a009'F 80-a099'F 80-009 'F 80-d0SP'T 80-d00P 'T 80-aog¢ Tt 80-a00e'T 80-092 'T 80-€002 'T 80-d09T 'T 80-d00T T 80-d090'T 80-d000'T 60-009 °6 60-000 6 60-1009 8 66-000 '8 60-0032 60-a000'°L 60-a009'9 60-000 '9 60-0039 60-000 °9 60-d003 '¥ 60-d000'¥ 60-d009'¢ 60-4000 '¢ 60-4002 '°S 60-d000'2 60-d009 'T 60-4000'T at-a000'9 00+d000°0 lt of the carry save adder i0n resu + lat ircuit simu Figure 13. Thec — 98 _ Binary to Residue Conversion Using Multiplexed Adders The binary to residue conversion part is composed of M; stages of adders. In each stage, one of the four constants 0, 2) mod m, 2™! mod m;, 2) + 2™i mod m, is added to the partial sum, where j indicates the stage number from M; to 2M; — 1 (see figure 5). Which constant should be added is determined hy two control bits. One is the j-th bit of the number generated by the binary array multiplier. The other is the carry bit generated by the previous stage or adder. Notice that the constants and the partial sums (not including the carry bit} are all M,-bit numbers. The basic cell in the conversion part is a multiplexed adder. It has two inputs and four control signals: The two inputs, Sin and Cin, come from the adder in the previous stage. The two control signals that determines which one of the four constants should be added, are decoded into the control signals m1,m2,ms3 Lene RO ame a ee tenement anal re —EE | tee as pe , _— bteteeeneenemee onan rammeecresorenemrann RNR ~_ | ceentibheememeer aed Cf Ss OF Ss neo? teri a Reameaeneie aaatl me: parameterized| » ——— ae Ws ———-—-te| adder ee M4 ————we{ > fer Figure 14. The multiplexed adder ~ 39 — The multiplexed adder can also be considered as a 3-input full adder. Two of the inputs are Sin and C;,. The third input is a function of the control signals. If mz is 1 then the third input is always 0. If me is 1 then the third input may be either 0 or 1, depending on the constant 2) mod m;, as is the case when msg is 1 or mg is 1. Therefore there are 8 different combinations: control signal the third input bit my=1 00000000 M2=1 OO00011II ms=1 00110011 m4=1 01010101 The third input bit pattern can be used to parameterize the multiplexed adder cells. The parameterized adder cell is composed of two parts: a two-input half adder and a multiplexor. The half adder takes inputs S;, and Cin, and generates four outputs co, 80,¢1 and 81. Co and So are the carry bit and sum bit generated as if the third input is 0. cz and si are the carry bit and sum bit generated as if the third bit is 1. Cin Sin | Co So Cy S21 ae et OO 2 a) rece oe mi © a a a) HH © Of It can be easily verified that co=AND(Cin, Sin), cr = OR(Cin, Sin), So= KOR(Cin, Sin) and si=XNOR(Cin, Sin). The multiplexor takes co, &, ¢1, #1 a8 inputs and uses four control signals mi,Mme,ms3 and mg to determine whether the output is (co,s0) or (c1,81). — 40 - For example, if the third input bit pattern is (0101), then the multiplexor will perform the following function: if (mi,me,m3,m4)=(1,0,0,0) then Cous=MAI(Cin,Sin,0)=co Sout =XOR(Cin, Sin,0)=80 if (m1,m2,m3,m4)==(0,1,0,0) then Cous=MAJI(Cin,Sinyl)=e1 Sout = XOR(Cin, Sin, L)=81 if (mi,m2,m3,m4)=(0,0,1,0) then Cout= MAI (Cin, Sin, 0)=co Sout = XOR(Cin, Sin, 0)—=80 if (mi,mM2,m3,m4)=(0,0,0,1) then Cous=MAJI(Cin, Sin, LJ=c1 Sour XOR(Cin, Sin, l)—=31 (MAJ is the majority function and KOR is the exclusive-or function) Express Cout and Sout as boolean functions: , i f f i } i f i i S$ out =™1Me’m3’m4’so+m1’Mems’m4’s;+m1'Me’mM3m4'so+m1'Me'ms'm4S1 Cout==MiMo! ma’ma’co+mi’momes’ma’c1+ma/’me’msma'co+mi/me!'ms’m Cy Figure 15 shows the logic diagram of the (0101) multiplexed adder. The layout is in Figure 16. The multiplexor parts of the 8 different parameterized cells are shown in Figure 17. - Ai - Sout Cout’ | 4 1 4 H 1 1 Sy 80. C1 Co . I t+ - t— aH Cin’ Sia Figure 15. The logic diagram of a (0101) multiplexed adder — 42 - NZ z ZZ er ee pamint aiick Beate aA ses 43 i Ve Figure 16. The layout of a (010i) multiplexed adder — 43 - Sout Cout f f—- + f ms lia If jis } it My f TS i TL (0000) % (9100) Co. I I 1% aa! i FFL FP = F = (0001), (0101)! 7 7 TI 7 s iT t se f f f E f ‘in i Ir i its # a i f (00 1 0) (0110) rl F r 3 It T ff tf i tf i lia i lm i ic ’ ir 4 4 ‘ (001 1) (0111) Figure 17. The multiplexor part of 8 different parameterized adder cells ~ 4d - The layout of the whole chip is generated by a program written in Earl code [Ki82]. The cells are parameterized so that the program can generate the layout for different moduli. Figure 18 shows the metal layer of the layout of an 8-bit residue array multiplier. A 4-bit version of the multiplier requires an area of 300 X 700d”, and an 8-bit version 540 X 12007. Simulations indicate that carry and sum bit generation requires 8ns~-10ns. The critical path in each M;-bit residue multiplier goes through 4M; adders. Therefore, the total delay is 32M; to 40M; ns, and hence about 250--320 ns for an 8- bit multiplier. The performance of the design can be improved iu several ways. For instance, the sample design does not have any form of pipelining. Optimizing the residue afray multiplier design should make it competitive for smaller values of Mj. — 45 - cree ena 2 eel peel = fr, aa 9 Reka] Sauna Rather anger et t residue multiplier i The metal layer of an 8-b 18 Figure ~ 46 - 5. Base Selection and Design Cost The cost of a VLSI design is affected by many factors such as chip area, speed, layout regularity and ease of design. There are some trade-offs between these factors to minimize the design cost. In residue arithmetic, total design cost depends on the individual cost of each digit. Therefore base selection is impor- tant for the total cost. This section contains two heuristic algorithms for base selection with respect to minimum delay, or minimum area. - Problem 1: Given a cost function T(m) (delay) and range requirement R ([logR] = Ny, bits), find a base S={7mj,..., mp} such that log( TT, mi)> Np and max{‘l'(77)} is minimized. . Algorithm 1: 1. BEGIN 2. find n, such that T(n,) is minimum, set § + {ny} 3. WHILE (range ofS)<N, DO 4 BEGIN { add/substitute the next modulus 1 5. For all & not examined, 6 S, —SU{k}—{n, | 25 €S, gcd(k, nj) 4 1} 7 AR, =(range of S,)— (range of S), 8 Select $, such that AR > 0 and T(é) minimum. If there are more than one such Sx, select the one whose AR, is maximum. 9. Set § — Sx 10. BND 11. END 12. S is the base wanted — An - In algorithm 1, the base 5 starts with a modulus with overall minimum cost (line 2) and then searches for the next larger modulus until the range requirement is met (line 3 to line 10). The next modulus selected must (1) be relatively prime with respect to other moduli already in S$ (line 5), and (2) have the smallest cost among all possible candidates (line 8). Problem 2: Given the cost function A(n) (area) and the range requirement R (Nj, = [logR] bit), find a base 8 ={mj,..., mp} such that log([]?_, mi)> Ny, and >, A(mi) is minimized. Algorithm 2: 1. BEGIN 2. find n, such that A(n) is minimum at nm, set 8 ~ {ni} 3. WHILE (rangeofS)<R DO 4. BEGIN { add/substitute the next modulus } 5. for all & not examined 6. Sx — SU{k} — {5 | nj € 8, ged(h, nj) A 1} 7. AR, =(range of §,)— (range of S), 8. AA; =(total area of §,) — (total area of 8) 9. select 5, such that she is minimum and set S — S, 10. END 11. END 12. S is the base wanted — 48 — In algorithm 2, as in algorithm 1, the base selection starts with finding a modulus with overall minimum cost (linc 2) and then searches for the next modulus until the range requirement is met (line 3 to line 10). The requirements for the next modulus selected are somewhat different from those in algorithm 1. The relatively prime requirement is still the same. The second requirement is sharply different, it becomes: a selected number should have minimum ane among all candidates. The reason for this criterion is due to the fact that the chip area is additive. To make a minimal total area, the area incremental] rate should be kept as small as possible. The purpose of the following examples are to illustrate the construction of an optimal hase with respect to minimnm delay and minimum area respectively. The cost functions for delay and area used in these examples are obtained from Figure 6 and Figure 8. It should be noted that a modulo of the form 2* has lower time and area cost than other moduli for every implementation scheme studied. In an array implementation no conversion is necessary. In a table implementation the PLA will have fewer product terms after a Boolean function minimization {is carried out. A modulo 2* —1 or 2* +1 multiplier has lower time and area cost when implemented by arrays. The modulo computation does not require a large conversion section. However, in a table look-up scheme no reduction in table size is possible. It should be noticed though, that a modulo of the form 2* — 1 makes more efficient use of the storage, since a k-bit wide table suffice, whereas modulo 2* + 1 requires k+1 bits. In the example of the base selection algorithm that follows it should be noticed that the range is small enough that table look-up is the optimum way of im- plementing the residue multiplier. The moduli réquire less than 6-bits for their ~ 49 - binary encoding. Hence, moduli in the interval between moduli of the form 2* require about equal time and area. However, a modulo 257(2° + 1) residue multiplier require less area than a modulo 259 residue multiplier, since such a multiplier would be implemented as an array multiplier and the latter modulus would require a conversion stage. EXAMPLE 1. Assume that the required range R=3 x 10!° (Nj, = 34.8 bits). The goal is to find a base with range >R and the smallest delay time. Assume the delay time function T(n) of the first few numbers have the values listed below. n T(n) 2 20 3 63 4 50 57 173 8 90 9~15 396 16 185 1T~31 618 32 330 33-~63 858 84 570 —~ 50 — Algorithm 1 gives the fulluwing result: Action Basco (S) Rangoe(bit) Cost (Time) (1) S+ {2} {2} 1 20 (2) 8-SU{4} — {2} {4} : 2 50 (3) SS J{3} {4,3} 3.58 63 (4) 8<-S|J{3} — {4} {8,3} 4.58 90 (5) SSL {7} {8,3, 7} 7.39 173 (6) SSL) {5} {8,3,7, 5} 9.71 173 (7) S+-SLJ{16} — {8} {16, 3,7, 5} 10.71 185 (8) S+-SL {32} — {16} {82, 3,7, 5} 11.71 330 (9) s—sLJ{13} {32, 2,7, 5,12} 15.41 296 (10) S+-S|J{11} {32, 3,7, 5,13, 11} 18.87 396 (12) SSLJ{9} — {3} {32, 9, 7,5, 13, 11} 20.46 396 (13) S+-S|){64}— {32} | {64,9,7, 5,13, 11} 21.46 570 (14) S+S| {31} {64, 9,7, 5,13, 11,31} 26.41 618 (15) SSL{29} {64, 9,7, 5,13, 11,31, 29} - 31.27 618 (16) S+-S|J{27} — {9} {64, 27, 7,5, 13,11, 31, 29} 32.85 618 (17) SS|J{25} — {5} {64, 27,7, 25, 13,11, 31, 28} 35.18 618 Let us consider action (7). The base $ after action (6) is {8, 3, 7,5}. The numbers already considered are 2,3,4,5,7,8. So,the next candidates are 6,9,10,11,12,13,- 14,15,16,17....... Composite numbers such as 6,10,12,14,15 are of little interest because once these numbers are selected the resulting range will decrease, i.e, AR < 0. The possible candidates left are 9,11,13,16,17, ... . According to the delay function given, T(16)< T(9)— T(11)— T(12)< ... . Henec, T(18) is the smallest among all candidates. Therefore the next action is $+-S| J{16} — {8}. In action (5), T(5)=T(7) but 7 has larger AR. Therefore 7 is selected. In action (9), 18 is selected instead of 11 for the same reason. — 54 -— EXAMPLE 2. Assume that the required range R=6 X 107° (N}, = 35.8 bits). The goal is to find a base with range >R and the smallest total area. Assume the area function A(n) of the first few numbers have the values listed below. n A{n) 2 10 3 26 4 20 5~7 45 8 35 9~15 147 16 80 17~31 282 32 160 33-63 407 64 320 Algorithm 2 gives the following result: Action Base (S) AA/AR | Range(bit) | Area (1) Sx {2} {2} 10.0 1.0 10 (2) S-SUJ{4}—{2} | {4} 10.0 2.0 20 (3) SSL J{8} — {4} | {8} 15.0 3.0 35 (4) S—SLJ{3} {8,3} 15.8 4.6 60 (5) S+-SU{7} {8,7,3} 16.0 6.7 105 (6) SS {5} {8, 7,3, 5} 19.4 9.7 150 (7) S+S {13} {8,7,3, 5,13} 39.7 13.4 297 (8) SSL {11} {8, 7,3, 5, 13, 11} 42.5 16.9 444 (9) S+S|LJ{16} {16, 7,3, 5,13, 11} 45.0 17.9 489 (10) $—S| {31} {16, 7, 3,5, 13, 11, 31} 56.9 22.8 771 (11) SSL J{29} {16, 7, 3,5, 13, 11, 31, 29} 58.0 27.7 1053 (12) S-S|J{23} {16, 7,3, 5, 13, 11, 31, 29, 23} 62.3 32.2 1335 (13) S~sU{19} 66.4 36.5 1617 {16, 7,3, 5, 13, 11, 31, 29, 23, 19} — 52 — As is shown in the above examples, both algorithms (1) and (2) are very efficient since only a small number of next candidates need to be tested. Indeed, it is only necessary to test numbers of the form p* (p: prime) provided that the functions A(n) and T(7) satisfy the following relations: T(nine) > max{T(ni), T(me)}} and Alnine) > A(ni)+Alne) The relations above imply that the cost of an arithmetic unit for a residue digit with a composite modulus ning is greater than the total cost of an arithmetic unit with moduli n, and ny, respectively. Since the cost functions A(n) and T(n) derived in section 4.1 satisfy the above relations, it is only necessary to search the numbers 2, 3, 4(27), 5, 7, 8(2*), 9(37), 11, 18, 16(2*), 17, 19, ... (not necessarily in this sequence) until the range requirement is met. © Area and time are certainly not the only two factors that affect the design cost. Sometimes several moduli requiring the same number of bits are selected such that a regular layout for each digit can be made. For example: (16,15,13,11) for a 15 bit range and (32,31,29,27,25) for a 24 bit range. On the other hand, some designers choose moduli of the forms 2" —1, 2", 2° +1 [Tagg] for simple implementation schemes and ease of binary & residue conversions. — 58 - 6. Conclusion The residue arithmetic is a “concurrent” arithmetic. Two important indices “the degree of concurrency” and “the code efficiency”: have been defined and analyzed. The analysis shows that the degree of concurrency in a residue number system is of order O(N, /log Ns), where N, is the number of bits required for binary encoding. The code efficiencies in most application ranges are between 0.91 and 0.94. Al the current state of the technology, implementations based on table look-up are preferred with respect to both performance and area for a range that can be encoded with 18 bits. If a larger range is needed, both index transform designs and array designs have smaller area requirements and delays. The array design is preferable with respect to area, and also with respect to delay if the range requires a large number of bits. However, if the array design is optimized it can be operated at a clock rate that is comparable to or less than that of the index transform approach. At feature sizes of 0.5um , table look-up designs are preferred only for ranges of up to 9 bits. In comparing with computer arithmetic based on the binary number system it shall be noticed that our residue array multiplier is of the same complexity as a binary array multiplier. The estimated speed-up ratio is about 7 to 10 for a large application range (ranges from 2'° to 2'°°). For the range greater than 21° the speed-up ratio is asymptotically proportional to Np/ log Np. - - 5h - Part 2. A Distributed RC Delay Line Model and MOS PLA Timing Estimation 1. Introduction The resistance and capacitance of wires in MOS technology affect the propaga- tion delay of signals along wires. The wire delay in state-of-the-art MOS circuits is often of the same order of magnitude as the charge transit time of transistors. The wire delay does not scale well with the technology |[Me80]. Uniform scaling of circuit geometry without any change in doping levels results in constant delay for wires whose length is reduced by the scaling factor. For a wire of constant length the delay increases [Bi81]. If the wire is very long, the increase is proportional to the square of the scaling factor /Se79]. In table 1, some typical nMOS circuit paraineters are listed and the effect of these parameters on the delays in a nMOS circuit is shown. To estimate the delay in digital MOS circuits, transient analysis of a circuit that contains distributed RC lines is important. In [Pe81], a computationally simple ‘method to estimate the delay of nodes in an RC tree network is presented. This paper develops a delay model for wires with uniformly distributed resistance and capacitance. The delay estimates are more accurate than those obtained in [Pe81] and can be applied to estimate the delay of MOS storage circuits such as PLA or ROM. In the next section, 2 MOS wire is modeled as a two-port network. The dis- tributed resistance and capacitance are approximated by lumped resistors and eapacitors. A simple equation for estimating the delay of a wire with uniformly distributed resistance and capacitance is derived. The wire is assumed to be — 55 — A = 2um \ = 0.52m Resistance |Relative length} Resistance |Relative length {2/o) of equal R (42/0) of equal K Transistor 10* 1 10* 1 Diffusion 100 100 600 12.6 Poly 25 400 200 50 Metal 0.03 3 x 10° 0.24 4x 10+ Capacitance | Relative area | Capacitance | Relative area (10-4 pF/#m?)| of equal C |(107* pF /ym’”)| of equal C Gate 5.0 1 40 1 Diffusion 1.2 4 10 4 Poly 0.5 10 4 10 Metal 0.33 15 2.7 15 Table 1. The parasitic parameters as feature size scales down driven by a voltage source having an internal resistance. The delay in a static nMOS PLA is estimated in section 3. The effect of reduced feature sizes is also analyzed. — 56 — 2. The Distributed RC Delay Line Model Wires in MOS circuits are often modeled as transmission lines as shown in Figure 1 [Se79], [Bi81]. Signal propagation across the wire is described by the one- dimensional diffusion equation: OV(z,t) | 6°V(z,t) Stn? (1) where V(z, ¢) is the voltage along the wire, (t) time, (z) the spatial coordinate, and r, c the resistance and the capacitance per unit length, respectively. te My Ae Ae —-— Me 0 ¥(z,t) — == edz = = = bd -—- © Figure 1. A wire modeled as a transmission line The solution of this diffusion equation is complex and it is unreasonable to solve it for every element in a VLSI circuit. However, with uniformly dis- tributed resistance and capacitance along the wire, simple approximate solutions of good accuracy can be found. In the following such a wire is referred to as a URC element [Gh68], [Pen81]. It is represented by the symbol “ “ee ” and has total resistance R and total capacitance C, R = rL and C = cl, where L is the wire length. Equation (1) is the classical equation for an induc- _~ BY — tance free transmission line with no conductance to ground. Its transmission . an - coshr 4 sinht matrix (T-matrix) in the Laplace domain is: , Where Z1sinhl coshr T=vsRC, and Z= \/ = I'/ZL is often referred to as the wave propaga- tion constant and Z as the wave impedance [De72],/Gh68]. Let V;(s),Vo(s),J:(6),fo.{s) be the Laplace transforms of the input voltage, output voltage, input current and output current respectively, Figure 2. Then m ‘ _ | coshT Zsinh " nn (2) Fi{s) Z~ sinhT ~— cosh’ IL Joa) Ii(s) R I.(6) WWW Vila) Cc Vals) ) r | Figure 2. A URC element modeled as a twe-port network The first order [l-equivalent circuit of a URC element has a transmission im- pedance of H and shunt elements equal to C/z. This is easily realized by a Taylor series expansion of eq(2) ~ 58 — + high order terms (3) cosh Z sinh 1 " +0.58RC R Z sinhl cosh’ 8C 1+ 0.58RC The corresponding IT network is shown in Figure 3. R oo _ [1 +0.58RC R o/2 ienemmated c/2 T - Matrix — | aC 1+0.5sRC | Figure 3. A lumped approximation of a URC element A URC Element Driven by a Voltage Source with Internal Resistance In VLSI circuit wires are driven by transistors that often may have significant internal resistance (Rs) compared to the wire resistance (#2). It is clear that the accuracy of the first order approximation increases with the ratio Rs/R. We will now study the accuracy of the first order approximation in some detail. A URC element with total resistance R and total capacitance C driven by a voltage source having source resistance As is shown in Figure 4. The source resistance can be considered as the equivalent channel resistance of the driving transistor. — 59 — et oad ‘ ——e f= Hs) R Tol) =0 Rs Vile) = 4 V2(8) Q Figure 4, A URC element driven by a voltage source with source resistance Rs The two-port network equation is rio) | coshT Zamarvse) 4) Hs)! lo aliz-sinhr cosh |Lyo(s) With open output and the input driven by a unit step voltage, fe, Io{s) = 0 and YV;,{s) = 1/2, Ll a(coshl’ + Z—1 Fg sinhT) Vo(s) = (5) The time domain representation of the step response can be obtained by an inverse Laplace transform: 1 (coshT + Z-1 Rg sinhT) (6) _— ¢—i V(t) = L ; However, there is no simple closed form for this transform. Using the first order approximation of the URC element, from {3} and (4) — 60 — ~l 1 Vo{t) = £ Fr + 6(Rs + 0.5R)C) | This is the familiar response of a first order ordinary differential equation with time constant r = (Rs 1-0.6R)C. The accuracy of this firet order approximation by comparing with a numerical inverse of eq(6) is now evaluated. Some results - [Imsz] for different ratios of Rs /F are plobled in Figure 5. The time-axis is normalized by (Rs +0.5R)C, ie, a = t/(Rs + 0.5R)C 1.0 v(t) | 0.8 LL 0.6 | 0.47 02 fF Rs/R +0 \— t= (Rs + 0.5R)C { — 02 O4 O06 O8 40 22 14 16 18 2.0 Figure 5. The unit step voltage response of the circuit in Figure 4 —~ @1 — Rs/{R Vola =1) oo 0.63213 10 0.63210 0.63180 1 0.63127 0.5 0.63044 0.1 0.62930 0 0.62922 Table 2. Unit step responses of the circuit in Figure 4 For R = 0, ie., Rg /R = oo, the URC element is simply a pure capacitor and the lumped model is an accurate model of the URC element. The unit step response is an exponential function with time constant r= RsC. For Rs = 0, the response is that of the URC element alone. The accuracy of the first order approximation decreases monotonically as Rs /R — 0. Let Va(t) be the output voltage response of the circuit for a given ratio of Rs /R and V;(t) the response for a smaller ratio. In the beginning (¢ = 0*), V;(t) is rising slower than V.(t) and Va(é) > Vi(é). As time proceeds, the rising rate of V;(t) is approaching the rising rate of V,{t) and eventually exceeds that rate. From Figure 5 and Table 2, it is observed that the curves for different ratios Rs /F cross at about (1, 0.63). The curves indeed intersect each other within a very small neighborhood of (1+0.01, 0.63). Hence we conclude that the time constant of the first order approximation is a very accurate approximation of the time a URC element driven by a voltage source with internal resistance reaches level 1— + of its final level. For all values of Rs /R the relative error is less than 1%. The curves in Figure 4 are bounded by the two extreme cases: Rs /R — co and Rs/R— 0. The unit step responses of these two cases are given in (7) and (8) — 62 — respectively, [Ka62]. v@(t)=1-—e/" (7) 4m exp (Qn—1)? 5? 9 —_. * _1\ 4r ; Ve=1+ 5 de 1 (8) i= While t < 0.997 the upper bound is V(t) and the lower bound is V°(t) and for £ > LOlr the upper bound is V°(¢) and the lower bound is V°(£). The bounds given by (7) and (8) are considerably tighter than those given in [Pe81] as is indicated in Figure 6, 1.0 v() 0.8 T | 0.6 F (7) bounds in [pe81] 0.4 7 oe L (8) t= (Rs + 0.5R)C / —~— a 0.0 a en 0.2 0.4 06 08 10 412 14 #16 18 20 Figure 6. Bounds (7), (8) and by [Pe81] for unit step responses of the circuit in Figure 4 (Rs /R = 1) — 63 — A URC Element Driven by a Voltage Source with Source Resistance and Source Capacitance A URC element with total resistance R and total capacitance C driven by a voltage source with source resistance Rg and source capacitance Cs is shown in Figure 7. mA Rg R Ia(s) = QO ww Wih—@ “ vete) — ae | = ol & Vs Vils) = 3 Cs ; @ Figure 7. A URC element driven by a voltage source with source resistance As and source capacitance Cs An approximation of the output voltages can again be obtained from a first order approximation of the URC element. The unit step responses depend only on two parameters: ky = Rs/R and k. = Cs/C. However, over a large range of resistance and capacitance values, the unit step responses are bounded in a way similar to those shown in Figure 5 and Figure 6. Table 3 gives the unit step responses at time t = RsCs + (Rs + 0.5R)C, the time constant of the first order approximation, for different ratios k, and k,. Again, we conclude that the time constant of the first order approximation is a very accurate approximation of the time constant of the circuit in Figure 7 — 64 - reaches 1— + of its final value. Hence, as is the case for a one-dimensional array of lumped circuits, the time constant for a composite circuit is to first order equal to the sum of the time constants of the circuit constituting the array. Next, a delay model for a nMOS PLA will be doveloped. ier} 0.1 0.2 0.5 i 2 5 10 0.1 0.629 0.629 0.627 0.623 0.615 0.607 0.615 02 | 0.629 | 0.629 | 0.626 | 0.621 | 0.616 | 0.620 | 0.630 0.5 | 0.630 | 0.630 | 0.628 | 0.623 | 0.626 | 0.630 | 0.631 1.0 | 0.631 | 0.631 | 0.630 | 0.630 | 0.631 | 0.632 | 0.632 2.0 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 5.0 0.632 0.632 0.632 0.632 0.632 | 0.632 0.632 10 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 | 0.632 Table 3. Unit step responses of the circuit in Figure 7 at t= RsCs + (Rs + 0.5R)C —~ 65 —- 3. MOS PLA Delay Estimation Cherry, [Ch79$] has given a formula for the delay of a nMOS PLA. However, the wire delay is ignored in Cherry’s model. A formula that takes the wire delay into account is developed below. The wires in the PLA are modeled as URC elements. Consider a typical nMOS PLA as shown in Figure 8. The path that passes the points a,b,c,d,f,g is a critical path. Its equivalent circuit is also shown in Figure 8. The poly wire starting at point 6 that runs in parallel with the wire cd has resistance Ry and capacitance Cy. The poly wire between point c and d has resistance Re and capacitance Cy. The metal wire connecting d and e has capacitance C3. Its resistance can be ignored. The poly wire between d and f has resistance R, and capacitance Cy. The metal wire connecting f and g has capacitance Cs. The output loading capacitance is Cour. Let Ry be the channel resistance of a pull-down transistor. The pull-up to pull-down transistor ratio is denoted k, and it is assumed to be 4 in the following calculations. ‘Using first order approximation of the URC elements, the signal delay from the input @ to the output h for 0 + 1 and 1 — 0 transitions are given in Table 4. Wire resistances and capacitances are assumed to be uniformly distributed. The magnitudes of To.., and T, ,9 depend on the values of (1,Co,C2,C1,Cs and Cout. As a rule of thumb, if the number of minterms is greater than twice the number of outputs {i.c., the AND-planc dominates the OR planc), then To+1>Ti40. Otherwise, T1409 >To~1. -— 66 - i Cc : | IER Ch i ne d a - Gest isi ES ah eS Bla) 7 te ge = mort mig is) ah) Te et pt i TU; amped Hein sg SBSESREECES SRDESRS SBnEZBSUCRDNGapAZATECRTASE 0 Tee 3 = a Z a S = gS SH IG ch St oe te) i 2G. ih i is Sr ie) iS ie ia ee i a¢ =I i wt sp ay mt — y aa .. a mu —— at és oy io (ey fot tet (al io} fea et tat fel Te fe age ot tc} fal fol fol fel tot fe el ie} (ol fal fe To tee! ix = oa) E=} Sy tS) tS) SS) ey hr Sh dee ty) ay Sy tea et tt ish fot fy do fet fet fet fe [ol ie : aa ee = — i =a] cH i Pte To) Tol (ey fe? fol fel fof Tat ol tol ol tel fet toh ete) fol oh fol tel fet of erie tel isl To} fe i =; = = aie a | Ele t el. iar tal to) el ie (oy oy a Stay felts el eerie! eer arto ter er a fer] 7 far io) ay i et ia ih ist o ‘ Pa 2 ble i) it Jee es etre gl ole rie @ i tlie = : se —— = =. =: 5 aa amisl ep = fa} NE + me 7 ni £ : o cl a fet SS SiS ot elie ie = ; a == = S fz} { rier fal tot Tol fick to fol tel [et fs! fs = : j = a i ——| ist = oy ay = i=} = Sa aa : y ot tet teh eee cy int ¥ — a rept retry Pret Pert een ime attest tee © : 7 i r ; i ate Tobe Epemnts) opm t) oris: = Eon o. fa) fehemed tote eo * fat r y — ia} ta} cajm je) (ms hay fa} a, (a3 (a) fa) orig [ay {=} apa ee EReenn t=) erat) =) “7 arto ya) cere a) a a : ate 1 i f c T & as e @) Ini) ) 5 op ors =) =) f=) aoe o =) ee = shen Giamats one te oitttot tomet tett tet ten tonn’ he to a BSS ie (=) mera} m=) = (J =) fms) fz) c epuemntere| [syamende) t 7 Ral “ Sa =. ons, & fa} 5 foam ix) £. fa} fa) [aja ia} 2g a, Giese = 3 t cic (3 ria} i=} i [=¥ f=} 9 et ay a a Se es pep ias eee = at aie alleen iv ie sence arbi — i fas Hail isi9 jE TEL bel icy ict jel. al ftait {iat aL am Figure 8. A critical path in a typical nMOS PLA and its equivalent circuit - 61 - Path Section Transition 0 +1 Transition 1 — 0 a—-+b RieCy ERC, bd (KR: + 0.5R2)C2 (Ri: + 0.5R2)C1 d—f KR:C3 + (kRe + 0.6Rs)C4 RriC3 + (Re + 0.5Rg C's f —> g ER:Cs RiCs Table 4. Delays for the PLA path shown in Figure 8 The delay from a to h for a0 to 1 transition at point « is estimated as follows: To+wit RiCi t+kR:Co —— input buffer delay + 0.5ReCe —— AND-plane wire delay + kRi(C3+Cs) | —— AND-plane switching delay (9) + 0.5F4C, ———— OR-plane wire delay + RiGs —— OR-plane switching delay + KR: Count —— output buffer delay T-.9 can be computed in a similar way. Note that 0.6R2Ce2 and 0.5R.C.4 are wire delays due to the resistance of the poly wires. Figure 9 shows the layout of a basic PLA cell. It is 7 x 7®. The gates are minimum. size (2\ X 2d) and separated by 5X poly wires. The width is 2X for both poly and diffusion wires. Metal wires are 3\ wide. The pull-up to pull-down transistor ratio (x) is 4. Let rp denote the sheet resistance of a poly wire {2/C) and C, denote the capacitance of a minimum gate (pF /(2))*). The poly wire capacitance is about 1, /(2d), and the metal wire capacitance is about 4C,/(2d)?. — 68 — Y) POLY WINIREMIAAS NINN: WN 5A V/ 4 y LTE \ pacia Z } C Za Z Z U Y L DIFFUSION Figure 9. The layout of a basic PLA cell The Worst Case Delay Let P = number of minterms I = number of inputs O = number of outputs four= Cour/Cy = fan-out factor Then the maximum value of C;’s and R,’s can be obtained under the assumption that in every cell there is a gate present. 5 1 7X3 1 C =( 1 =) C,)O = oO 2=((1+2-5) co) 0 = (.250,) 7X3 1 (10) 7 7 Substituting these values into (9) yields the longest delay, t The value of R;C, is the time constant for a minimum size transistor driving a minimum gate. It is equal to the charge transit time (T) of a minimum size - transistor [Me80]. The values of rp and R; depend on the IC process technology. At 4pm feature size, R; is of the order 10/0 and ry is in the range from 10 to 100 0/O. Substituting r,=25N/O and R:=10*2/c into (11) yields To-+1 FS (o.00ss (P? + 07)+6.6P+28I+5.00+4 Jout)T (12) Equation (12) gives the worst case delay of a static nMOS PLA in terms of the number of inputs 7, outputs O and minterms P. For a particular design, the number of gates in each column and row is known. ~ 10 — Deley Estimates for Personalized PLAs Let _ uiax{the wuuiber of gales each puly wire drives in tue AND plane} Pi P p max{the number of gales each poly wire drives in the OR plane } 2 = 2-0 (13) Then the relations between the actual wire capacitance (C;') and resistance (R;') | and the maximum wire capacitance and resistance are: Cy (1.259) P + 0.035(1 — pi) P) Cy = (0.28 + 0.72p1)C1 Co! <(1.25p1 P + 0.035(1 — pi) P) Cy = (0.28 + 0.7291) Ce C;' =Cs C4! <(1.25p2 O+ 0.035(1 — pz) O) C, = (0.28 + 0.72p0)Cy (14) Cs! =Cs Ro! =Re Ra’ =Ry where C, C2, Cs, Ca, C's, Re, Rs are the maximum wire resistances and capaci- tances given in (10). The approximated delay is Toi! (o.0056((0.28 + 0.72p1)P? + (0.28 + 0.72p2)0”) + 6.6(0.28 + 0.72p1)P + 2.81 + 5.0(0.28 + 0.72p2)O + sions) (15) —~ 1 - The Effect of Sealing The coefficients in (12) and {15) are based on the resistance and capacitance values typical at the current state of the technology (\ = 2pm ée., rp=250/o0 and A,=10*0/c). As feature sizes are reduced by a, the wire resistances/O increase by a, while the channel resistance of a transistor essentially remains constant, The capacitances/ym? increase by a [Me80], [Sa82]. To summarize: z—>sfa Ri > R: Cy, 7 C,/a T3T/a (16) tp Tpa za) ~ Ga) (3 ARDS Equation (12) and (15) become - To1 (o.00ssa(r* + 0°)+6.6P+28I+500+4 fous) (17) and To+1' (o.00560((0.2 + 0.72p1)P? + (0.28 + 0.72p2)0") +6.0(028-40.79p,)P +2874 50098 407% p9}0 4 Ayan)! (18) where T’ = T/a — 42 - The wire delay is comparable with the switching delay when 0.00550 P?66P —- Pr i181/a 0.0055a 075.00 4 OF 909/a (19) At 0.5ym feature size a 8 and equality holds at about 150 X 110 bits. Hence, unless, ¢g., the shect resistance is reduccd, the delay of large nMOS storage structures (>10K bit) will essentially be proportional to the storage size (bits). Eiow to Improve the Performance By inspecting the delay equations (17), (18), the delay introduced by a PLA can be reduced in several ways : 1. 4. Ge Use super buffers or.a sequence of exponential horn-type drivers [Me80] to reduce the switching delay 6.6P + 2.87 + 5.00. Reorganize the bit patterns in order to minimize P? +O? such that the wire delay is equally divided between the AND-plane and the OR-plane. Improve the process technology to reduce r,, and therefore the wire delay. (for example, the sheet resistance of silicide has only one tenth of that of polysilicon.) Limit. the driving needs on each clock phase by pipelining the operations (e.g., input buffer, AND-plane, OR-plane, output buffer). Use hierarchical storage architectures as suggested in [Me80] Chapter 8. — (3 — 4, Conclusion A first order linear approximation of the one dimensional diffusion equation used to model wires in MOS technology is shown to render very accurate estimates of the time constant for wires driven by a source having internal resistance and capacitance. The first order approximation is used to derive estimates of delays in a MOS PLA. The delay is computed in terms of inputs, outputs, and minterms. The data used in section 3 is based on nMOS technology. However, the method is general and can be applied to estimate the delays of other classes of MOS storage circuits in different technologies such as CMOS or different design strategies such ' as precharging. The effect of scaling technologies preserving aspect ratios and doping levels, as suggested in [Me80Q], is calculated. The delay equation can be used not only to estimate the speed of MOS PLA circuits but also to provide the proper VLSI computation models for storage structures. In [Bi81], it is concluded that “the current MOS VLSI technology falls in the domain of either the synchronous or the capacitive model and for projected future technology may reach the boundary of the capacitive model region.” In that work, propagation time is defined as the time required to transfer a bit along a wire of length L. The conclusion is based on the assumption that information change is transferred on metal wires. However, for information storing and extraction, the signal is not only propagating along metal wires, but also along poly wires because of layout considerations. For a large MOS storage with flat structure {no hierarchy), the delay is essentially proportional to the storage size (i.e. the square of the chip dimension). Hence, the diffusion model is indeed the proper one in this case. References [Ah74] [Ba69] [Bas0] A.V. Aho, J.E. Hopcroft, J.D. Ullman, “The Design and Analysis of Computer Algorithms”, 1974. D. Banerji and J. A. Brzozowski, “Sign Detection in Residue Number Systems”, IEEE, Transaction on Computers, Vol. C-18, Apr. 1969. D. Banerji, T.Y. Cheung and V. Ganesan, “A High-Speed Division _ Method in Residue Arithmetic”, 5th symposium on computer arith- [Ba82] [Bis] [Ch79] [Ch83a} [Ch83b} [Da65] [De72] metic. May 1980. M.A. Bayoumi, G.A. Jullien and M.A. Sid-Ahmed, “VLSI implementa- tion of Memory Intensive Residue Number System Architertnre”, Pro- ceedings, 20th annual Allerton Conference on Communication, Control, and Computcr. Oct 1982. Jim Bilardi, M. Pracchi and F. P. Preparata, “A Critique and an Appraisal of VLSI Models of Computation”, VLSI Systems and Compu- tations, Computer Science Press, 1981, pp. 81 - 88. Jim Cherry, “PLA Speed Calculations”, 1979 © C. Chiang, “Distributed RC Delay Line Model and MOS PLA Timing Estimation”, DF:5110:83, Department of Computer Science, California Institute of Technology, 1983. C. Chiang, L. Johnsson, “Residue Arithmetic and VLSI”, International Conference on Computer Design (ICCD), Nov. 1983. L. Dadda, “Some schemes for parallel multipliers”, Alta. Freq. Vol.19 May 1965. Charles A. Desoer and Ernest §. Kuh, Basic Circuit Theory, Chapter 17, McGraw - Hill, 1969 ~ 5 — [Ets2] [Fos] [Gag] [Gh68] [Ha79] [Hw79]} [Im82] [Je77| [ Je79] [Ka62] [Ki7]] M. H. Etzel and W. K. Jenkins, “The Design of Specialized Residue Classes for Efficient Recursive Digital Filter Realization”, IEEE, Transactions on Acoustic, Speech, and Signal Processing, Vol. ASSP-30, June 1982. 8. D. Fouse, G. R. Nudd and A.D Cumming, “A VLSI Architecture for Pattern Recognition Using Residue Arithmetic”, IEEE, Proceeding of the 6th International Conference on Pattern Recognition, Oct 1982. H. Garner, “The Residue Number System”, IRE Transaction on Electronic Computers, June 1959. Mohammed 8. Ghausi and John J. Kelly, Introduction to Distributed- Parameter Networks: with Application to Integrated Circuits, Chapter 1,2,3, Holt,Rinehart and Winston Inc., 1968 G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th edition, Oxford Science Publications, 1979. K. Hwang, Computer Arithmetic, Wiley 1979. The IMSL Library Reference Manual, vol 2, International Mathematical &Statistical Libraries Inc., 1982. W. Jenkins, “The Use of Residue Number Systems in the Design of Finite Impulse Response Digital Filters”, IEEE, Transaction on Circuits and Systems, Vol. CAS-24, Apr. 1977. W. K. Jenkins, “Recent Advances in Residue Number Techniques for Recursive Digital Filtering”, IEEE, Transaction on Acoustics, Speech, and Signal Processing, Vol. ASSP-27, Feb. 1079. W. M. Kaufman and S. J. Garrett, “Tapered Distributed Filters”, IRE Tran. Circuit Theory, CT-9, pp. 329 - 336 Dec. 1962. N.G. Kingsburg and P.J. Rayner, “Digital Filtering Using Logarithmic — 16 - [Ki73] [Kisg| [Ku78] [Me80] [Pe8I] [Sa82] [Se79| [St8g| {Sz67] {Ta82] {Ts79] Arithmetic”, Electron. Lett., vol.7, Jan., 1971. E. Kinoshita, H. Kosako and Y Kojima, “General Division in Symmetric Residue Number Systems”, IEEE, Transaction on Computers, Vol. C- 22, Feb. 1973. C. Kingsley, “Earl: An Integrated Circuit Design Language” TM:4710:82, Department of Computer Science, California Institute of Technology, 1982, D. J. Kuck, “The Structure of Computers and Computations”, , 1978. Carver A. Mead and Lynn Conway, Introduction to VLSI System, Addison Wesley, 1980 Paul Penfield Jr. and Jorge Rubinstein, “Signal Delay in RC Tree Network”, Proceedings of the Second Caltech Conference on VLSI, California Institute of Technology, 1981. Krishna C. Saraswar and Farrokh Mohammadi, “Effect of Scaling of Interconnections on the Time Delay of VLSI Circuits”, IEEE, Journal of Solid State Circuit, SC-17, pp. 275 -280, April 1982. Charles L. Seitu, “SelfTinied VLSE System”, Proceedings of the First Caltech Conference on VLSI, California Institute of Technology, 1979. §. Trimberger, “A Comparison of MOS PLAs”, TM:5059:82, Department of Computer Science, California Institute of Technology, 1982. N.S. Szabo and R.I. Tanaka, Residue Arithmetic and its Applications ~ to Computer ‘Yechnology, New York, McGraw-Hill, 1967. F, J. Taylor, “A VLSI Residue Arithmetic Multiplier”, IEEE, Transactions on Computers. Vol. C-31, June 1982. B. D. Tseng and G. A. Huliien “Implementation of FFT Structures ~~ Using the Residue Number System”, IEEE, Transaction on Circuits and Systems, Vol. CAS-24, Apr. 1977. ~ 4 —