A new methodology for design and analysis of interprocessor communication networks.
Item
-
Title
-
A new methodology for design and analysis of interprocessor communication networks.
-
Identifier
-
AAI9432333
-
identifier
-
9432333
-
Creator
-
Chen, Fu-Wei.
-
Contributor
-
Adviser: Seyed-Ali Ghozati
-
Date
-
1994
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
It is well known that the performance of a parallel computer is often limited by the time spent communicating data from one processor to another. The problem of design, analysis, and control of interprocessor communication networks is considered in this thesis. A novel approach based on a formal modeling of communication network by an algebraic structure, called Communication-Algebra (C-Algebra), is proposed. C-Algebra is used to investigate properties of networks and link them to their control structures. Two classes of communication networks, (N,K) cube and (N,K) PM2I, are modeled by the proposed algebra.;The following are the list of original contributions made in this thesis: (1) Systematic enhancement of network's performance and its fault-tolerance, (2) A new approach to establish parallel paths in the network, (3) Proving that the (N,K) cube is maximally fault tolerant, i.e., the maximum number of parallel paths between any pair of nodes equal to the degree of each node and the length of each parallel path is at most equal to the Hamming distance between source-destination nodes plus 2, (4) Developing an adaptive distributed routing scheme which will successfully route messages between any pair of functional nodes in an (N,K) cube as long as these two nodes are connected, (5) Establishing a lower bound on the number of parallel paths in the class of (N,K) PM2I networks, (6) Developing several node-independent algorithms for embedding other topologies, such as rings, linear arrays, meshes and standard spanning trees in an (N,K) cube, (7) Using Gray control sequences to establish Hamiltonian cycles in an (N,K) cube, and investigating properties of control vector space to numerate the number of distinct Gray control sequences in an (N,K) cube, (8) Graph theoretical characterization of the class of (N,K) cubes to determine whether or not a gi ven graph is isomorphic image of an (N,K) cube.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
