To appear in Mathematical and Computational Modeling.

Shift-Product Networks

Marilynn Livingston
Dept. of Computer Science, Southern Illinois University at Edwardsville

Quentin F. Stout
EECS Department, University of Michigan

Abstract: Economics is the principle driver of current trends to use commodity components in the construction of parallel systems for a range of sizes. One objective is to enable the user to purchase a small system initially, and then extend it through a range of sizes as needs dictate. A desirable feature is to have good system performance through the range of sizes; an undesirable feature is to require the user to purchase excess hardware that will not be used until the system is grown to its maximum allowable size. In this paper, we give a new construction which reconciles these two conflicting factors by introducing a way to interconnect several components of a given small network using only the routers for the small network, with one additional port per router. This construction, which we call a shift-product, does not unduly raise the communication diameter of the resulting large network.

Keywords: interconnection networks, parallel computer, scalable networks, shuffle-exchange networks, Cayley graphs, product graphs, de Bruijn network, commodity components, computer architecture, computer science

Full paper (Postscript)
Full paper (PDF)

Links to Related Work
Parallel Computing: overview of my work papers
Graph Theory: overview of my work papers

Quentin's Home Copyright © 2005-2017 Quentin F. Stout