2007 | OriginalPaper | Buchkapitel
Address-Free All-to-All Routing in Sparse Torus
verfasst von : Risto Honkanen, Ville Leppänen, Martti Penttonen
Erschienen in: Parallel Computing Technologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this work we present a simple network design for all-to-all routing and study deflection routing on it. We present a time-scheduled routing algorithm where packets are routed address-free. We show that a total exchange relation, where every processor has a packet to route to every other processor, can be routed with routing cost of 1/2 +
o
(1) time units per packet.
The network consists of an
n
-sided
d
-dimensional torus, where the
n
d
− 1
processor (or input/output) nodes are sparsely but regularly situated among
n
d
−
n
d
− 1
deflection routing nodes, having
d
input and
d
output links. The finite-state routing nodes change their states by a fixed, preprogrammed pattern.