Integer summing algorithms on reconfigurable meshes
Koji Nakano, K. Wada · 2002
This paper presents the following algorithms to compute the sum of n d-bit integers on reconfigurable parallel machine models: i) a constant-time algorithm on a reconfigurable mesh of the bit model of size d/spl radic/n log/sup (O(1/)) n/spl times//spl radic/n, ii) an O(log* n)-time algorithm on a reconfigurable mesh of the bit model of size d/spl radic/(n/log* n)/spl times//spl radic/(n/log* n), iii) an O(log d+log* n)-time algorithm on a reconfigurable mesh of the word model of size /spl radic/(n/(log d+log* n))/spl times//spl radic/(n/(log d+log* n)), and iv) an O(log* n)-time algorithm on a VLSI reconfigurable circuit of area O(dn/log* n).>