Integer summing algorithms on reconfigurable meshes
Integer summing algorithms on reconfigurable meshes
复制标题
可重构网格上的整数求和算法
DOI：
10.1109/icapp.1995.472185
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
K. Wada
中科院分区：
文献类型：
--
作者：
K. Nakano;K. Wada
本文介绍了以下算法，以计算可重新配置的并行机器模型上的n d-bit整数之和：i）在大小d/spl radic/n log/sup的位模型的可重新配置网格上的恒定时间算法（o） （1/））N/SPL时间// spl radic/n，ii）a（log* n） - 位可重新配置网格上的a（log* n） - 时间算法大小d/spl radic/（n/log* n）/spl times // spl radic/（n/log* n），iii）o（log d+log* n） - 可重新配置网格上的时算法的模型大小/spl radic/（n/（log d+log* n）的单词模型）/spl times // spl radic/（n/（log d+log* n））和iv）o（log） * n） - vlsi可重构电路O（dn/log* n）的时间算法。<< etx >>
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).<<ETX>>