On the Characterization of Interconnection Networks with Irregular Topology : A New Model of Communication Cost



Abstract 


Networks of Workstations (NOWs) have become a cost-effective alternative to
parallel computers. Switch-based interconnects with irregular topologies
provide the wiring flexibility required in these environments. The
characterization of these networks results quite difficult, since the
traditional parameters used for regular topologies (node degree, diameter,
average distance, etc.) do not provide information about the arrangement of
the links. In this paper, we propose a new model of communication cost between
network nodes. This model takes into account both the network topology and the
routing algorithm, but it does not depend on the traffic pattern generated by
the application running on the machine. The evaluation results show that our
communication cost model is highly correlated with network performance. Since
it provides a metric based on internode distance, our model can be used as the
basis for both an efficient characterization of networks as well as an
efficient mapping of processes to processors.

Supported by the Spanish CICYT under Grant TIC97--0897--C04--01