A theory for total exchange in multidimensional interconnection networks
Loading...
Date
Authors
Dimakopoulos, V. V.
Dimopoulos, N. J.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Type
Type of the conference item
Journal type
peer reviewed
Educational material type
Conference Name
Journal name
IEEE Transactions on Parallel and Distributed Systems
Book name
Book series
Book edition
Alternative title / Subtitle
Description
Total exchange (or multiscattering) is one of the important collective communication problems in multiprocessor interconnection networks. It involves the dissemination of distinct messages from every node to every other node. We present a novel theory for solving the problem in any multidimensional (cartesian product) network. These networks have been adopted as cost-effective interconnection structures for distributed-memory multiprocessors. We construct a general algorithm for single-port networks and provide conditions under which it behaves optimally. It is seen that many of the popular topologies, including hypercubes, k-ary n-cubes, and general tori satisfy these conditions. The algorithm is also extended to homogeneous networks with 2(k) dimensions and with multiport capabilities. Optimality conditions are also given for this model. In the course of our analysis, we also derive a formula for the average distance of nodes in multidimensional networks; it can be used to obtain almost closed-form results for many interesting networks.
Description
Keywords
collective communications, interconnection networks, multidimensional networks, packet-switched networks, total exchange, communication algorithms, hypercubes
Subject classification
Citation
Link
Language
en
Publishing department/division
Advisor name
Examining committee
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής