Neighbourhood reserve-a measure of locality of the direct interconnection networks

This paper addresses the problem of the design/evaluation of direct interconnection networks by introducing the neighbourhood reserve criterion. The criterion shows how the interconnection structural potential of an interconnection network fits the communication requirements of a parallel process and vice versa. The approach is based on the ideas that any communication model can be well characterised by locality properties and, on the other side, any topology has its intrinsic, structural, locality characteristics. The measure, essentially the difference of the structural neighbourhood and functional neighbourhood, could be used to look for the most suitable structures for a given routing distribution or, inversely, to suggest the most appropriate routing distributions for a given topology. The criterion is illustrated for some known interconnection networks, generalised hypercubes, hypertori and hypergrids, emphasising the locality as one of the main principles of the topological design