Improving Performance of Deterministic Single-Path Routing on 2-Level Generalized Fat-Trees

Author

Nienaber, Wickus ; Mahapatra, Santosh ; Yuan, Xin

Author_Institution

Dept. of Comput. Sci., Florida State Univ., Tallahassee, FL, USA

fYear

2011

fDate

16-20 May 2011

Firstpage

718

Lastpage

722

Abstract

This paper focuses on deterministic single-path routing schemes on 2-level generalized fat-trees. We develop a routing algorithm that is optimal in terms of worst-case permutation performance. In comparison to existing routing schemes for such topologies, our algorithm also improves the average performance of common communication patterns including bisect patterns, full permutation patterns, and dissemination (Bruck) patterns on various 2-level generalized fat-trees as demonstrated in our evaluation results.

Keywords

multiprocessor interconnection networks; network routing; trees (mathematics); 2-level generalized fat-trees; bisect patterns; communication patterns; deterministic single-path routing schemes; dissemination patterns; fat-tree-based interconnects; full permutation patterns; performance improvement; worst-case permutation performance; Algorithm design and analysis; Bandwidth; Computer architecture; Computer science; Measurement; Routing; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on

Conference_Location

Shanghai

ISSN

1530-2075

Print_ISBN

978-1-61284-425-1

Electronic_ISBN

1530-2075

Type

conf

DOI

10.1109/IPDPS.2011.213

Filename

6008842