Calculating Optimal Flit Size and Upper Limit on the Performance of Wormhole Routing

Anthony Symons and V. Lakshmi Narasimhan 1

The emergence of large scale distributed memory computers has brought with it a variety of interconnection networks. As it is not feasible to fully interconnect the processors with a diameter of one, routing of messages is necessary. Wormhole routing is an efficient method of routing and in this paper, we derive a model for wormhole routing. Using this model, we determine the optimal buffer size, and hence show that for medium to large messages, the communication time using wormhole routing is dependent on the square root of the network diameter.

Parallel Distributed Computing, Hypercube, Mesh, Performance Parameters, Wormhole routing

The paper was presented to the ICA 3 PP-97 conference, Melbourne, December 1997 and appeared in the proceedings.

1. Head, Information Management Group, Information Technology Division, DSTO, SA 5108, Australia