All-port total exchange in cartesian product networks (EN)

Dimakopoulos, V. V. (EN)

Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής (EL)

Dimakopoulos, V. V. (EN)

We present a general solution to the total exchange (TE) communication problem for any homogeneous multidimensional network under the all-port assumption. More specifically, we consider cartesian product networks where every dimension is the same graph (e.g. hypercubes, square meshes, n-ary d-cubes) and where each node is able to communicate simultaneously with all its neighbors. We show that if we are given an algorithm for a single n-node dimension which requires T steps, we can construct an algorithm for d-dimensions and running time of n(d-1)T steps, which is provably optimal for many popular topologies. Our scheme, in effect, generalizes the TE algorithm given by Bertsekas et al. (J. Parallel Distrib. Comput. 11 (1991) 263-275) for the hypercubes and complements our theory (IEEE Trans. Parallel Distrib. Systems 9(7) (1998) 639) for the single-port model. (C) 2004 Elsevier Inc. All rights reserved. (EN)

collective communications (EN)

Πανεπιστήμιο Ιωαννίνων

Ιδρυματικό Αποθετήριο Ολυμπιάς

Σχολή Θετικών Επιστημών

ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"

Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Journal of Parallel and Distributed Computing (EN)

Αγγλική γλώσσα

2004

http://olympias.lib.uoi.gr/jspui/handle/123456789/10793