1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)
Summation Algorithms on Constrained Reconfigurable Meshes
Fremantle, Australia
June 23-June 25
ISBN: 0-7695-0231-8
Constrained reconfigurable meshes are one type of parallel computing model taking the reconfigurability of hardware into account and also employing a practical assumption on the communication power. This assumption is such that a signal is propagated through a constant number of processing elements (PEs), say (k) PEs, at one unit of time. In this paper, we present algorithms for the fundamental problem of computing the sum of multiple integers. For the problem of summing (n) binary values, we show an optimal \math-time algorithm on a constrained reconfigurable mesh of size \math, where \math. For the problem of summing n d-bit integers, we present an \math-time algorithm on a constrained reconfigurable mesh of size \math, where m is the above value.
Index Terms:
reconfigurable mesh, constrained reconfigurable mesh, parallel algorithm, Bit summation
Citation:
Akihiro Matsuura, Akira Nagoya, "Summation Algorithms on Constrained Reconfigurable Meshes," ispan, pp.400, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999