Stirling Networks - A Versatile Combinatorial Topology For Multiprocessor Systems

    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