Embedding Tree Structures in VLSI Hexagonal Arrays

Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1984-01, Vol.C-33 (1), p.104-107
Main Authors: Gordon, Dan, Koren, Israel, Silberman, Gabriel M.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Binary trees
Computer science
control theory
systems
Computers
Distributed configuration algorithm
Exact sciences and technology
hexagonal multiprocessor array
mapping scheme
Mirrors
Program processors
Propagation delay
Theoretical computing
tree structures
VLSI
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:Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology. Such an implementation requires an area-economical mapping of a tree on a plane. Novel mapping schemes for trees onto hexagonal arrays (or grids) and appropriate algorithms are proposed here and shown to be superior over known mappings on square arrays (or grids).
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.1984.5009319