Home > Research > Publications & Outputs > BDG-torus union graph-an efficient algorithmica...


Text available via DOI:

View graph of relations

BDG-torus union graph-an efficient algorithmically specialized parallel interconnect

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Publication date2/12/1991
Host publicationProceedings of the Third IEEE Symposium on Parallel and Distributed Processing
Number of pages8
ISBN (print)0818623101
<mark>Original language</mark>English


The binary de Bruijn graph (BDG) is a realizable alternative to the hypercube. An extension of the BDG by the edge set union with a torus is shown-union-graph (UG). This achieves graph capabilities/versatility comparable to the product shuffle (PS) graph and the hypercube within a fixed degree graph. The UG improves upon both in implementing pipelined and multi-phase algorithms. More importantly, the purpose being to design an algorithmically specialized interconnect, with the algorithmic features of a wide range of algorithms as well as direct architectural support for them, instead of simple providing for a set of graph embeddings in the interconnect. A set of examples demonstrate the UG's versatility in this aspect of algorithmic support.