Abstract:
A fast, scalable, systolic modular multiplier based on projection onto planar ring structures is presented. Systolic paradigms of limited fan-out on all signal paths and nearest neighbor interconnections guarantee optimally fast clock rates. Linear throughput scalability with respect to consumed hardware resources is achieved through simultaneous parallel processing of multiple independent data streams. Signal sharing among input and output busses and a common control interface for all independent data streams is made possible, thus benefiting integrated circuit implementations.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   Not applicable. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to the processing of digital signals to render modular multiplication. 
   2. Description of Related Art 
   Modular multiplication, which is the computation of A·B modulo M where A, B, and M are integer values, is a fundamental mathematical operation in applications based on number-theoretic arithmetic. A central application area is cryptography, where techniques such as the popular RSA and DSS methods utilize modular multiplication as the elemental computation. Since large word lengths on the order of thousands of bits are typically processed, hardware approaches to modular multiplication are typically very slow. Existing art attempts to address this deficiency through a handful of approaches. 
   Linear systolic array approaches dominate the art, with the article C. Walter, “Systolic modular multiplication,” IEEE Transactions on Computers, v. 42, no. 3, pp. 376–378, 1993, being representative. In such an approach, a linear array of processing elements is connected so that all signal paths are formed between adjoining elements only. Thus, signal path lengths are minimized. Accordingly, all signal paths only connect two adjoining elements, guaranteeing unit fan out. The forgoing properties of systolic arrays ensure that the clock rate is determined solely by the processing element delay. However, efforts to scale the performance beyond the level offered by a single linear array have encountered very limited success. Cell optimization is the commonly applied technique to gain performance. However, performance scales only logarithmically with respect to consumed integrated circuit area. 
   Another method which attempts to provide a performance-area tradeoff is the digit-serial array. In the paper, J. Guo and C. Wang, “A novel digit-serial systolic array for modular multiplication,” in Proc. of the 1998 IEEE International Symposium on Circuits and Systems, v. 2, pp. 177–180, 1998, a digit-serial modular multiplier methodology was presented. However, the arrays were not pipelined, and thus the clock period of the digit-serial cells grows proportionally with digit size. Therefore, performance scaling occurs in a sub-linear fashion for small digit sizes and quickly saturates to yield negligible performance gains for large digit sizes. A non-systolic array was presented in the article H. Orup, “Simplifying quotient digit determination in high-radix modular multiplication,” in Proc. of the 12th Symposium on Computer Arithmetic, pp. 193–199, 1995. A roughly linear performance-area tradeoff was achieved through retiming of the modular correction loop within the modular multiplication algorithm. However, the clock rate is severely limited by the required full-word-length signal broadcasts of the modular correction selection bit. Thus, the fan out of the aforementioned signal is the complete word length. Implementational efforts to increase the signal drive through transistor sizing destroys the linear performance-area trade off and only provide minor mitigation of the slow-clock-rate obstacle plaguing this methodology. 
   SUMMARY OF THE INVENTION 
   The present invention describes a method for parallel modular multiplication capable of processing multiple independent data streams simultaneously. 
   An implementation realizing this method consists of a multi-column array of processing elements having a row count equivalent to the number of iterations necessary to process a modular multiplication of a target word length. Each processing element accepts and generates bit-level data and performs partial product formation, modular correction formation, and summation of these generated bits with the right-single-bit-shifted result of the previous algorithmic iteration. The number of columns of the array is determined in accordance with the available integrated circuit implementation area and the desired throughput performance, which scales linearly with column count. 
   The data stream capacity and operational throughput are directly scalable with the available integrated circuit implementation area. This performance scalability is accomplished while maintaining a systolic paradigm, such that all interconnection paths are locally connected to neighboring processing elements and entail minimal fan out. Thus, the achievable clock rate is maximized and is dictated by the processing element delay rather than by long interconnect paths or loading due to multiple-gate fan out. Moreover, in contrast to isolated parallel modular multiplication arrays, the unified array structure of the present invention incorporates single input and output data buses, thereby reducing global integrated circuit wiring overhead. Additionally, the unified array permits a single controller to be utilized when the modular multiplier is utilized as a component in a higher-level functional unit such as a modular exponentiator. 
   OBJECTS AND ADVANTAGES OF THE INVENTION 
   The primary object of this invention is fast parallel processing of modular multiplication. 
   It is an advantage of this invention that multiple independent data streams may be simultaneously processed. The number of data streams is arbitrary, limited only by implementation area. 
   It is a primary advantage of this method that throughput performance scales linearly with the area of the integrated circuit implementation while maintaining the optimal systolic clock rate. The latter is attained through guaranteeing properties of purely nearest neighbor interconnections between processing elements and unit signal fan out. 
   It is an advantage of this invention that input and output data share signal lines such that the number of internal signal buses in an integrated circuit implementation are reduced. 
   It is an advantage of this invention that a unified control unit may be utilized when the modular multiplier unit is used in a modular exponentiator. 
   It is an advantage of this invention that regularity of the architecture is two-dimensional rather than uni-dimensional. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  illustrates the modular multiplier with its connections 
   

   DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
   The preferred embodiment is an array consisting of N rows of K bit-wise processing elements arranged in a planar ring structure, where N represents the number of iterations in the modular multiplication algorithm and K is an integer parameter with value greater than one. The value of K directly relates to the amount of parallelism implemented in the array and should be chosen in accordance with the amount of integrated circuit area available for the implementation. 
   Each cell,  1 , possesses a set of bit-wise inputs corresponding to the multiplicand, multiplier, modular correction, modular selection, partial sum, and two previous carry signals. Each cell also possesses a set of bit-wise outputs corresponding to the multiplicand, multiplier, modular correction, modular selection, generated partial sum, and two generated carry signals. Let each ring be numbered in ascending order from top to bottom and let each cell within a particular ring be numbered with an index such that the upper-rightmost cell is designated zero and the index is incremented by one for each cell traversed in the counterclockwise direction. Each cell of ring I and position J is interconnected within the structure in the following manner: the multiplicand and modular correction outputs are each delayed by three clock cycles and are input to cell J+1 mod K of the ring of row I+1. The multiplier, modular selection, and two carry outputs are each delayed by one clock cycle and are input to cell J+1 mod K of the ring of row I. Finally, the generated partial sum output is delayed by two clock cycles and is input to cell J of the ring of row I+1. 
   The modular correction, multiplier, and carry inputs of each cell of index  0 ,  2 , are modified from the above description in that these inputs are each multiplexed by two levels. The modular correction multiplexer,  3 , for an index  0  cell in ring I accepts the modular correction output of the cell K in ring I at the PRI multiplexer input. The SEC input of the same multiplexer is connected to the partial sum output of cell K−1 of ring I−1. The multiplier signal multiplexer,  4 , for an index  0  cell in ring I accepts the multiplier output signal from cell K−1 of I−1 at input PRI. The SEC input of the same multiplexer is connected externally for the provision of an initialization value. 
   Each of the aforementioned multiplexers takes in two data inputs, labeled PRI and SEC. An additional input SEL is used to multiplex data at the PRI and SEC inputs to the multiplexer output. De-assertion of the SEL input selects the PRI input, while assertion selects the SEC input. 
   Delay elements,  5 , have a single input and a single output. Data presented at the input is delayed by a specified number of clock cycles and is then delivered to the output. 
   A counter,  6 , asserts the signal PASS_DATA for one clock cycle every N+2K clock cycles. The signal PASS_DATA is connected to the SEL input of each of the multiplexers associated with cells of index  0  within each ring wherein I mod K=0. De-assertion of the PASS_DATA signal selects the PRI input to the multiplexer, whereas assertion selects the SEC input. The PASS_DATA signal is delayed by two clock cycles and is passed to the SEL input of the associated multiplexers of the cell of index  0  in the next ring wherein I mod K=1. Once again, this signal is delayed by two clock cycles and passed to the multiplexers associated with cell index  0  of the subsequent ring. This procedure is repeated for rings having indexes numbered up to and including I mod K=K−1. Thus, for each ring, the SEL inputs of each multiplexer associated with the cell of index  0  are asserted every N+2K+2*(I mod K) clock cycles. 
   Each cell performs a computation which, for the purposes of illustration, may be decomposed into the following sequence of bit-wise operations. The multiplicand input bit is ANDed with the multiplier input bit. Similarly, the modular correction input bit is ANDed with the modular selection input bit. The outputs of the two aforementioned computations are added with the partial sum input and the two carry inputs. The least significant bit of the latter sum is connected to the cell&#39;s partial sum output, while the two bits generated in the most significant position are connected to the two carry outputs. The multiplicand, modular correction, multiplier, and modular selection inputs are also passed to the multiplicand, modular correction, multiplier, and modular selection outputs, respectively. 
   Initial data is supplied externally to the unit such that K new independent data sets commence processing in sequence every N+2K−1 clock cycles. Multiplicand and modular correction data bits are entered into the cells of the topmost ring in the following manner. The cell of index  0  receives the least significant modular correction, multiplicand and multiplier bits associated with the first of the K data streams upon the first clock cycle wherein PASS_DATA is asserted. Upon the next clock cycle, the least significant modular correction, multiplicand and multiplier bits associated with the second of K currently entering data streams are received. In each of the subsequent K−2 cycles, the index  0  cell successively receives the remaining K−2 least significant bits of each input type. An identical process commences for the next-to-least significant modular correction and multiplicand inputs in the cell of index  1  in the second clock cycle after PASS_DATA is asserted. Similarly, the delivery of the first of K bits corresponding to significance J is provided J cycles after the initial assertion of PASS_DATA in the cell of index J mod K. After K clock cycles, the bit position  2  of the multiplier input data begins to arrive and is received for the remaining data streams for the next K cycles. This process continues for subsequent clock cycles. 
   An illustration of the modular multiplier array for the K=8, N=2 case is shown in  FIG. 1 . Arrays for other parameterizations should be evident to an individual in the field with a grasp of the above description.