Title

Stirling Networks: A Versatile Combinatorial Topology For Multiprocessor Systems

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 vulner-ability 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. © 1992.

Publication Date

7-15-1992

Publication Title

Discrete Applied Mathematics

Volume

37-38

Issue

C

Number of Pages

119-146

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0166-218X(92)90128-W

Socpus ID

44049118969 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/44049118969

This document is currently not available here.

Share

COinS