(A) new mapping function for wormhole routing multicomputers

Abstract

Interconnection networks equipped with wormhole switching have been widely used for contemporary multicomputers/parallel machines because of its various advantageous features and good performance. The communication performance in wormhole routing networks is no longer sensitive to path lengths and minimizing the lengths is no longer a major concern. However, in wormhole routing, messages must compete for channels, and the resultant contention affects communication times. Thus, a random mapping is still not enough. In this thesis, we deal with the mapping problem on wormhole routing networks. Not only abstracted and stochastic task models but also more realistic parallel applications are considered. It is difficult to define and evaluate a meaningful performance metric when many messages are generated and exchanged concurrently in large wormhole routing networks. We analyze extensively the blocking characteristics of packets in wormhole routing network based on queuing system model. As a result of the analysis, we formulate a new cost function to evaluate how a mapping have good performance. The cost function reflect the contention property more exactly than others which have been suggested by a lot of researchers. The new cost function helps us to select more accurate and stable mapping with respect to the parameters of parallel tasks and multicomputers such as packet-length and operating network load. It is known that there is no polynomial time algorithm to find optimal mapping with a given objective function, in general case of mapping. We devise heuristic algorithms to find a near-optimal mapping with respect to the proposed cost function. The algorithms include a greedy algorithm and a heuristic optimization algorithm. The greedy mapping algorithm shows significant performance improvements over random mappings, and it is useful to use as an initial mapping algorithm for a heuristic optimization algorithm. The proposed heuristic optimization algorithm whi...