## Abstract

A major component of a large-scale parallel computer is the interconnection network that connects processors to memories in a shared-memory machine, or processors to processors in a multicomputer. This paper formally studies the relationship between network topology and network performance. Rectangular banyan networks are shown to provide maximum bandwidth/cost ratio for symmetric traffic. For their cost, contracting banyan networks are shown to provide maximum bandwidth up to a constant factor for semisymmetric traffic. For a restricted class of networks, contracting banyan networks are shown to provide exactly maximum bandwidth for semisymmetric traffic. Rectangular banyan networks are shown to provide optimal delay-to-cost tradeoffs for symmetric traffic. It is shown that, in many situations, optimal bandwidth is achieved by using a unique path to route information between each input-output pair.

Original language | English (US) |
---|---|

Pages (from-to) | 359-385 |

Number of pages | 27 |

Journal | Discrete Applied Mathematics |

Volume | 37-38 |

Issue number | C |

DOIs | |

State | Published - Jul 15 1992 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics