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
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/35141 |
| Date | 04 May 1995 |
| Creators | Larson, Shawn M. |
| Contributors | Cull, Paul |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0017 seconds