Parallel computers are classified into: Multiprocessors, and multicomputers. A
multiprocessor system usually has a shared memory through which its processors
can communicate. On the other hand, the processors of a multicomputer system
communicate by message passing through an interconnection network. A widely
used class of interconnection networks is the toroidal networks. Compared to a
hypercube, a torus has a larger diameter, but better tradeoffs, such as higher channel
bandwidth and lower node degree. Results on resource placements and fault-tolerant
broadcasting in toroidal networks are presented.
Given a limited number of resources, it is desirable to distribute these resources
over the interconnection network so that the distance between a non-resource and a
closest resource is minimized. This problem is known as distance-d placement. In
such a placement, each non-resource must be within a distance of d or less from at
least one resource, where the number of resources used is the least possible. Solutions
for distance-d placements in 2D and 3D tori are proposed. These solutions are
compared with placements used so far in practice. Simulation experiments show
that the proposed solutions are superior to the placements used in practice in terms of reducing average network latency.
The complexity of a multicomputer increases the chances of having processor failures. Therefore, designing fault-tolerant communication algorithms is quite necessary for a sufficient utilization of such a system. Broadcasting (single-node one-to-all) in a multicomputer is one of the important communication primitives. A non-redundant fault-tolerant broadcasting algorithm in a faulty toroidal network is designed. The algorithm can adapt up to (2n-2) processor failures. Compared to the optimal algorithm in a fault-free n-dimensional toroidal network, the proposed algorithm requires at most 3 extra communication steps using cut through packet routing, and (n + 1) extra steps using store-and-forward routing. / Graduation date: 1998
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/33680 |
| Date | 13 November 1997 |
| Creators | AlMohammad, Bader Fahed AlBedaiwi |
| Contributors | Bose, Bella |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0021 seconds