The most important part of parallel computation is communication. Except in the most embarassingly parallel examples, processors cannot work cooperatively to solve a problem unless they can communicate. One way to solve the problem of communication is to use an interconnection network. Processors are located at nodes of the network, which are joined by communication channels. Desirable aspects of an interconnection network include low maximum and average routing distances (as measured in the number of communication channels crossed), a large number of processors, and low number of communication channels per processor. A number of published networks are created from the hypercube by rearranging the hypercube's communication links in a systematic way [23] [28] [30] [33] [50]. These networks maintain the same number of processors, communication links, and links per processor as the hypercube, but have dramatically smaller maximum and average routing distances. This thesis derives one formal mathematical description for this family of networks. This formal description is used to derive graph-theoretic properties of existing networks, and to design new networks. The description is also used to design generalized routing and other communications algorithms for these networks, and to show that these networks can embed and simulate other standard networks, for instance, ring and mesh networks. A network simulator is used to model the dynamic behavior of this family of networks under both store-and-forward and wormhole routing strategies for message-passing. The simulation results are used to study and compare the networks' behavior under various message-passing loads, and to determine what properties are desirable in a network that exists in this model. / Graduation date: 1995

As the size of networks increases continuously, dealing with networks with faulty nodes becomes unavoidable. In this dissertation, we introduce a new measure for network fault tolerance, the strong fault tolerance (or strong Menger-connectivity)in multicomputer networks, and study the strong fault tolerance for popular multicomputer network structures. Let G be a network in which all nodes have degree d. We say that G is strongly fault tolerant if it has the following property: Let Gf be a copy of G with at most d - 2 faulty nodes. Then for any pair of non-faulty nodes u and v in Gf , there are min{degf (u), degf (v)} node-disjoint paths in Gf from u to v, where degf (u) and degf (v) are the degrees of the nodes u and v in Gf, respectively. First we study the strong fault tolerance for the popular network structures such as star networks and hypercube networks. We show that the star networks and the hypercube networks are strongly fault tolerant and develop efficient algorithms that construct the maximum number of node-disjoint paths of nearly optimal or optimal length in these networks when they contain faulty nodes. Our algorithms are optimal in terms of their time complexity. In addition to studying the strong fault tolerance, we also investigate a more realistic concept to describe the ability of networks for tolerating faults. The traditional definition of fault tolerance, sustaining at most d - 1faulty nodes for a regular graph G of degree d, reflects a very rare situation. In many cases, there is a chance that a routing path between two given nodes can be constructed though the network may have more faulty nodes than its degree. In this dissertation, we study the fault tolerance of hypercube networks under a probability model. When each node of the n-dimensional hypercube network has an independent failure probability p, we develop algorithms that, with very high probability, can construct a fault-free path when the hypercube network can sustain up to 2np faulty nodes.

published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (M. Phil.)--University of Hong Kong, 1991.

The study of multicomputer interconnection networks is an important area of research in parallel processing. We introduce vertex-symmetric Hamming-group graphs as a model to design a wide variety of network topologies including the hypercube network.

Graduation date: 1993

Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1994. / Vita. Abstract. Includes bibliographical references (leaves 90-92). Also available via the Internet.

Thesis (M.A.) -- Central Connecticut State University, 2008. / Thesis advisor: Nelson Castañeda. "... in partial fulfillment of the requirements for the degree of Master of Arts in Mathematical Sciences." Includes bibliographical references (leaf 32). Also available via the World Wide Web.

Graduation date: 1991

Recent studies have shown an increased interest and research in the area of parallel computing. Graphs offer ' an excellent means for the modelling of parallel computers. The hypercube graph is emerging as the preferred topology for parallel processing. It is a subject of intense research and study by both graph theorists and computer scientists.This thesis is intended to investigate several graph theoretic properties of hypercubes and one of its subgraphs (middle graph of the cube). These include edgedensity, diameter, connectivity, Hamiltonian property, Eulerian property, cycle structure, and crossing number.. Theproblem of routing using parallel algorithms for implementing partial permutation is also described. We also discuss the problem of multiplying matrices on hypercube, which is helpful in solving graph theoretic problems like shortest paths and transitive closure. The problem of graph embeddings is also discussed pertaining to hypercube graph. Lastly, several important applications of hypercubes are discussed. / Department of Computer Science