I. INTRODUCTION
The topmost machines of the top 500 supercomputer list
[18] are composed of hundreds of thousands of processing
nodes. The performance of the machine is strongly impacted
by the interconnection network among the processing nodes.
The main design challenges of interconnection networks
are to provide low latency and a high network throughput
while providing a simple implementation at a reduced
hardware cost. Two of the most important design issues of
interconnection networks are topology and routing algorithm
[3], [5]. Topology defines how the processing nodes are
connected, and the routing algorithm determines the path
followed by packets from their source to their destination
node. The topology of a network also impacts to a large
extent its cost. Topologies usually adopt a regular structure to
simplify the routing algorithm, their implementation and the
possibility of expanding the network. The most commonlyused
taxonomy classifies topologies in direct and indirect
networks [3], [5].
Direct topologies adopt an orthogonal structure where
nodes are organized in an n–dimensional space. The nodes
are connected in each dimension in a ring or array fashion.
2D or 3D direct topologies are relatively easy to build as
each topology dimension is mapped to a physical dimension.
Direct topologies with more than three dimensions imply not
only increasing its wiring complexity but also the length of
This work was supported by the Spanish Ministerio de Ciencia e
Innovacion (MICINN), and jointly financed with Plan E funds, under Grant ´
TIN2009-14475-C04 as well as by Consolider-Ingenio 2010 under Grant
CSD2006-00046, and by Ayudas para Primeros Proyectos de Investigacion´
from Universitat Politecnica de Val ` encia under grant ref. 2370.