Quasi-perfect resource placements for two-dimensional toroidal networks

This work addresses the problem of having a limited number of resources in a multicomputer system that each processing element needs to access. Placing these resources in the system so that all processing elements can access them in a comparable manner is called the “resource placement problem”. In this paper, we present resource placement methods for two-dimensional toroidal networks. These methods assure uniformity such that the resources are distributed uniformly over the network where each resource is assigned an equivalent number of non-resource nodes. Hence, the resources' related traffic would have a balanced distribution over the network. This increases the overall network utilization rather than having parts of the network congested while others are barely utilized. Furthermore, the presented methods minimize the maximum distance between a non-resource node and its closest resource. There are many messages in a multi-computer system competing for its communication channels. The longer the path, traversed by a message, the higher the probability becomes that the message blocks or is blocked by other messages. Indeed, reducing the distance between a resource and a non-resource decreases the average network latency and increases the traffic volume a network could handle before it saturates. Analytical and simulation results show that the presented methods are superior to some existing methods in terms of reducing the average network latency.