Embedding torus in hexagonal honeycomb torus

Abstract

A number of parallel algorithms admit a static torus-structured task graph. Hexagonal honeycomb torus (HHT) networks are regarded as promising candidates for interconnection networks. In order to efficiently execute a torus-structured parallel algorithm on an HHT, it is essential to map the tasks to processors so that the communication overhead is minimised. The study proves that a (3n, 2n) torus can be embedded into an nth-order HHT with dilation 3, congestion 4, expansion 1 and load factor 1. Consequently, a parallel algorithm with a (3n, 2n) torus task graph can be executed on an nth-order HHT efficiently.