A MODEL FOR ANALYZING INTERACTIONS IN 2-D MESH WORMHOLE-ROUTED MULTICOMPUTERS

This paper describes a general contention model called the heterogeneo us multipath contention model. The model is a representation of arbitr arily overlapped communication paths of jobs that have different messa ge injection rates. Based on this model, we analyze the degradation of communication performance due to multiple interacting jobs in a 2-D m esh wormhole-routed multicomputer system. We compute the contention de lay seen by a message on a path in the heterogeneous multipath content ion model. A divide-and-conquer strategy divides the problem into seve ral manageable problems of computing the contention delay for the hete rogeneous 2-path contention model. In order to verify the analysis of our heterogeneous multipath contention model, we compare our analytic results with a simulation model. In addition, we analyze a contention model in which two jobs have complex internal communication patterns t hat overlap.