Title

Stirling Networks - A Versatile Combinatorial Topology For Multiprocessor Systems

Authors

Authors

S. K. Das; J. Ghosh;N. Deo

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Discret Appl. Math.

Keywords

STRUCTURED PARALLEL COMPUTER; INTERCONNECTION NETWORKS; HYPERCUBE; COMPUTERS; GRAPH ALGORITHMS; TREE; PERFORMANCE; DIAMETER; CYCLES; MODEL; VLSI; Mathematics, Applied

Abstract

We derive a family of labeled, undirected graphs from the Stirling table of the first kind and investigate properties of these graphs as a basis for multiprocessor interconnection networks. The diameter of a Stirling network with n nodes is [log2 (n+1)]-1, the average distance is less than 10/3, and the number of links is O(n1.59). Stirling networks can be inductively specified with incrementability of one, and adjacencies can be determined solely by the node addresses. Many standard networks including full-ringed binary trees, tree machines, meshes and half mesh of trees are shown to be embedded in these combinatorial networks. Properties of Stirling networks are analyzed and related to the underlying mathematical structure. We present a routing scheme that is deadlock free, avoids congestions, and can be executed on the fly by bit manipulation of node labels. A methodology for modular construction of these networks yields estimates for the VLSI area required for their layout. Fault-tolerance properties are analyzed, a vulnerability of 1 is proved, and fault-handling abilities in presence of faulty nodes or links are demonstrated. We also show how several classes of parallel algorithms can be efficiently implemented using these networks.

Journal Title

Discrete Applied Mathematics

Volume

37-8

Publication Date

1-1-1992

Document Type

Article

Language

English

First Page

119

Last Page

146

WOS Identifier

WOS:A1992JH95000010

ISSN

0166-218X

Share

COinS