In this paper, 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 reordering 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(n/sup 3/) 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.

For distributed memory parallel computers, broadcast operations are widely used in a variety of applications. In this paper we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 2D torus with arbitrary size. The underlying network is assumed to support only the dimension-ordered unicast. By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can greatly reduce the number of message-passing steps. In addition, it can be proved to be depth contention-free. The performance study in this paper clearly shows the advantage of the proposed algorithm.

For distributed memory parallel computers, broadcast operations arc widely used in a variety of applications.In this paper, we propose an eflicicnt algorithm for broadcasting on an all-port wormhole-routed 2D torus.The underlying network is assumed to support only the dimensionordered unicast routing.By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can be proved to be depth contention-free, and needs only n steps for broadcasting on a 2d~2" torus.Furthermore, the software latency is also reduced by appropriately overlaying the messages sent out by the same node in each step.The timing analysis and the computer simulation conducted in this paper clearly show the performance im provement of the proposed algorithm.