Bit-level array design

As argued in section 1, the throughput of word-level arrays is in several cases not sufficient. Therefore, the bit-level parallelism should also be exploited. Assume that a PE of an array processor has W words as inputs, each denoted Bi = 0,1. IF — 1, and are defined by  

By substituting equations (13) and (15) into equation (14), the following is obtained  

Due to the carries produced by the nested summations of equation (16), it holds that p n. As can be seen from equation (16), a (6o,vo,6i,vi, , iVfc-i,VNfc-i) contributes to = 0,1. p - 1 if and only if qk,i,v = 1- Therefore, the number of input bits that contribute to gi is specified by  

By definition, the dimension of the DG of an algorithm is identical to the index space dimension. In particular, the bit-level algorithm of equation (14) should be described by a W-D DG. However, the construction of the multidimensional DG is avoided by using combinatorial logic to compute the values of Zk -)j thus reducing the problem to multiple-operand binary addition, which can be represented by a 2-D DG. Moreover, in this DG, the properties of the target architecture may be embodied. 

The DG will be completely specified when the exact position of the nodes and the interconnecting edges are determined. The number of the nodes of the DG should be specified first. Let Ai be the number of nodes contributing to the computation of the tth output bit, ft. Also, let 0i be the number of bits that should be added by the Ai nodes. The Pi bits include the bits specified by equation (17), and the carry bits that result from the computation of the (i — l)th output bit. It can be noticed that the number of carry bits coincides with the number Ai i. Hence  

---