Treffer: The power of list ranking on a reconfigurable array of processors with wider bus networks

Summary: This paper makes an efficient improvement of processor complexity for computing list ranking and some related problems on a reconfigurable array of processors with wider bus networks by increasing the bus width between processors. Usually, the bus width of the system bus requires log \(N\)-bit for a parallel processing system with \(N\) processors; instead of using log \(N\)-bit, the bus width of the system bus of a reconfigurable array of processors with wider bus networks is assumed to be \(O(N^{1/\zeta}\))-bit, where \(\zeta\) is a constant and \(\zeta\geq 1\). Based on such an architecture and a base-\(n\) \((n = N^{1/\zeta})\) number system technique, two constant time basic operations are first introduced for computing the prefix modular \(n\) and prefix division \(n\) of an \(N\)-bit binary sequence using \(N\) processors. Then, many fundamental algorithms can be solved in constant time on this newly created machine using \(N^{1+1/\zeta}\) processors. These algorithms include the prefix sum of \(N\) integers problem, the unweighted (or weighted) list ranking problem, the Euler tour related problems and tree recursion related problems, respectively. Note that the last two categories of problems can be reduced to the list ranking problem. If this problem can be solved efficiently, then both of the others can also be solved efficiently. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width of the system bus installed. That is, the wider the system bus installed, the faster the algorithm obtained.