A performance study of wormhole routed networks through analytical modeling and experimentation
Frank Hady · 1993
The individual processors of a parallel computer cooperate by exchanging information over an interconnection network. This dissertation studies the performance of such multicomputer interconnection networks. Here an analytical model that uses a new concept called the distributed queue is presented. This model is used to predict both the latency and maximum possible throughput of wormhole routed k-ary n-cube networks. Comparisons with experiments on a parallel computer called the High-speed Network Evaluation Testbed (Hnet) prove the model's accuracy. Using this model the performance of networks for different worm sizes, node topologies and length to width ratios (for the 2-dimensional mesh) are compared. The model is also used to compare the performance of different topologies within the k-ary n-cube family subject to equal cost constraints. A combined cost constraint which includes both node cost and network packaging cost is presented. Next this dissertation evaluates interconnection network performance in an experimental manner, with parallel applications generating Hnet network traffic. Both a latency-tolerant parallel sorting algorithm and a latency-sensitive parallel sparse matrix multiply algorithm are used to compare the performance of different networks. The effect on performance of variations in network topology, routing algorithm and application algorithm are explored.