Embedding complete k-ary trees into k-square 2-D meshes with optimal edge congestion

Wormhole switching is distance insensitive but suffers from blocking in the case of communication conflicts. Embeddings of process graphs into interconnection networks of parallel machines with wormhole switching can ignore dilation, but should minimize edge congestion for a given load or expansion....

Full description

Saved in:
Bibliographic Details
Published in:Parallel computing 2000-05, Vol.26 (6), p.783-790
Main Authors: Trdlicka, Jan, Tvrdik, Pavel
Format: Article
Language:English
Subjects:
2-D mesh
Complete tree
Divide & conquer computation
Edge congestion
Embedding problem
Expansion
Load
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Wormhole switching is distance insensitive but suffers from blocking in the case of communication conflicts. Embeddings of process graphs into interconnection networks of parallel machines with wormhole switching can ignore dilation, but should minimize edge congestion for a given load or expansion. In this paper, we present an algorithm for embedding complete k-ary trees into k-square 2-D meshes with load 1, asymptotically optimal expansion, and nearly optimal edge congestion.
ISSN:0167-8191
1872-7336
DOI:10.1016/S0167-8191(00)00009-0