Optimal algorithms for the channel-assignment problem on a reconfigurable array of processors with wider bus networks

The computation model on which the algorithms are developed is the reconfigurable array of processors with wider bus networks (abbreviated to RAPWBN). The main difference between the RAPWBN model and other existing reconfigurable parallel processing systems is that the bus width of each network is bounded within the range [2,[√(N)]]. Such a strategy not only saves the silicon area of the chip as well as increases the computational power enormously, but the strategy also allows the execution speed of the proposed algorithms to be tuned by the bus bandwidth. To demonstrate the computational power of the RAPWBN, the channel-assignment problem is derived in this paper. For the channel-assignment problem with N pairs of components, we first design an O(T + [N/ω]) time parallel algorithm using 2N processors with a 2N-row by 2N-column bus network, where the bus width of each bus network is ω-bit for 2 ≤ ω ≤ [√N] and T = [log_ωN] + 1. By tuning the bus bandwidth to the natural log N-bit and the extended N¹c/-bit (N¹c/ > log N) for any constant c and c ≥ 1, two more results which run in O(log N/log log N) and O(1) time, respectively, are also derived. When compared to the algorithms proposed by Olariu et al. [17] and Lin [14], it is shown that our algorithm runs in the equivalent time complexity while significantly reducing the number of processors to O(N).