Efficient Communication in Folded Petersen Networks
| Autor: | Dirk H. Hohndel, Sabine R. Öhring, Maximilian Ibel, Sajal K. Das |
|---|---|
| Rok vydání: | 1997 |
| Předmět: | |
| Zdroj: | International Journal of Foundations of Computer Science. :163-185 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054197000136 |
| Popis: | Fast and efficient communication is one of the most important requirements in today's multicomputers. When reaching a larger scale of processors, the probability of faults in the network increases, hence communication must be robust and fault tolerant. The recently introduced family of folded Petersen networks, constructed by iteratively applying the cartesian product operation on the well-known Petersen graph, provides a regular, node– and edge-symmetric architecture with optimal connectivity (hence maximal fault-tolerance), and logarithmic diameter. Compared to the closest sized hypercube, the folded petersen network has a smaller diameter, lower node degree and higher packing density. In this paper, we study fundamental communication primitives like single routing, permutation routing, one-to-all broadcasting, multinode-broadcasting (gossiping), personalized communications like scattering, and total exchange on the folded Petersen networks, considering two communication models, namely single link availability (SLA) and multiple link availability (MLA). We derive lower bounds for these problems and design optimal algorithms in terms of both time and the number of message transmissions. The results are based on the construction of minimal height spanning trees in the fault-free folded Petersen network. We further analyze these communication primitives in faulty networks, where processing nodes and transmission links cease working. This analysis is based on multiple arc-disjoint spanning trees, a construct also useful for analyzing other families of multicomputer networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|