In this technical report, we address the problem of minimizing channel contention of

linear-complement communication on wormhole-routed hypercubes. Our research reveals

that, for traditional routing algorithms, the degree of channel contention of a linear-

complement communication can be quite large. To solve this problem, we propose an

alternative approach, which applies processor mapping at compile time. In this compiler

approach, processors are logically reordered according to the given communication(s) so

that the new communication(s) can be efficiently realized on the hypercube network. It is

proved that, for any linear-complement communication, there exists a reordering mapping

such that the new communication has minimum channel contention. An O(n3) algorithm is

proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on

dynamic programming is also proposed to find an optimal reordering mapping for a set of

linear-complement communications. Several computer simulations have been conducted, and

the results clearly show the advantage of the proposed approach.

Keyword: Hypercubes, linear-complement communication, channel contention,

                 processor mapping, wormhole routing.