Browse Prior Art Database

Efficient Communication Primitives on Hypercubes

IP.com Disclosure Number: IPCOM000122656D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 67K

Publishing Venue

IBM

Related People

Ho, CT: AUTHOR [+1]

Abstract

Disclosed are some practical algorithms, complexity analysis and implementation for one-to-all broadcasting, all-to-all personalized communication, and matrix transpose (with two-dimensional partitioning of the matrix) on hypercubes. The following communication characteristics assume circuit-switched routing, oblivious path selection (in ascending order of dimensions), and a one-port communication model.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient Communication Primitives on Hypercubes

      Disclosed are some practical algorithms, complexity
analysis and implementation for one-to-all broadcasting, all-to-all
personalized communication, and matrix transpose (with
two-dimensional partitioning of the matrix) on hypercubes. The
following communication characteristics assume circuit-switched
routing, oblivious path selection (in ascending order of dimensions),
and a one-port communication model.

      For one-to-all broadcasting, an algorithm is given that
combines the well-known recursive doubling algorithm (1) and the
algorithm based on edge-disjoint spanning trees (2). The measured
times of the combined algorithm are always superior to the
edge-disjoint spanning tree algorithm and out performs the recursive
doubling algorithm.

      For all-to-all personalized communication, a hybrid algorithm
is proposed that combines the well-known recursive doubling algorithm
(3,4) and the recently proposed direct route algorithm (5,6).  The
hybrid algorithm balances between data transfer time and start-up
time of these two algorithms, and its communication complexity is
estimated to be better than the two previous algorithms for a range
of machine parameters.  For matrix transpose with two-dimensional
partitioning of the matrix, the algorithm is measured to be better
than the recursive transpose algorithm (7) by n nearest-neighbor
communications (3).  The algorithm takes advantage of
circuit-switched rou...