Message latency in hypercubes in the presence of matrix-transpose traffic

Several analytical models of adaptive routing in wormhole-routed networks, including hypercubes, under the uniform traffic pattern have recently been proposed in the literature. However, there has been hardly any model report ed yet that deals with other important non-uniform traffic patterns exhibit ed by many parallel applications. As a result, most existing studies have r esorted to simulation when evaluating the performance merits of adaptive ro uting under non-uniform traffic conditions. This paper describes a new anal ytical model of adaptive routing in the hypercube in the presence of non-un iform traffic generated by matrix-transpose permutations, which is used in many matrix computation problems. Results obtained through simulation exper iments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.