Optimal All-to-All Personalized Communication with Minimum Span on Boolean Cubes

DSpace/Manakin Repository

Optimal All-to-All Personalized Communication with Minimum Span on Boolean Cubes

Citable link to this page

 

 
Title: Optimal All-to-All Personalized Communication with Minimum Span on Boolean Cubes
Author: Johnsson, S. Lennart; Ho, Ching-Tien

Note: Order does not necessarily reflect citation order of authors.

Citation: Johnsson, S. Lennart and Ching-Tien Ho. 1991. Optimal All-to-All Personalized Communication with Minimum Span on Boolean Cubes. Harvard Computer Science Group Technical Report TR-18-91.
Full Text & Related Files:
Abstract: All-to-all personalized communication is a class of permutations in which each processor sends a unique message to every other processor. We present optimal algorithms for concurrent communication on all channels in Boolean cube networks, both for the case with a single permutation, and the case where multiple permutations shall be performed on the same local data set, but on different sets of processors. For K elements per processor our algorithms give the optimal number of elements transfer, K=2. For a succession of all-to-all personalized communications on disjoint subcubes of β dimensions each, our best algorithm yields (K/2)+σ-β element exchanges in sequence, where is the total number of processor dimensions in the permutation. An implementation on the Connection Machine of one of the algorithms offers a maximum speed-up of 50% compared to the previously best known algorithm.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:25680330
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters