AuthorsO. Lysne, J. M. Montanana, J. Flich, J. Duato, T. M. Pinkston and T. Skeie
TitleAn Efficient and Deadlock-Free Network Reconfiguration Protocol
Afilliation, Communication Systems
StatusPublished
Publication TypeJournal Article
Year of Publication2008
JournalIEEE Transactions on Computers
Volume57
Number6
Pagination762-779
Date PublishedJune
Abstract

Component failures and planned component replacements cause changes in the topology and routing paths supplied by the interconnection network of a parallel processor system over time. Such changes may require the network to be reconfigured such that the existing routing function is replaced by one which enables packets to reach their intended destinations amid the changes. Efficient reconfiguration methods are desired that allow the network to function uninterruptedly over the course of the reconfiguration process while remaining free from deadlocking behavior. In this paper, we propose, evaluate, and prove deadlock freedom of a new network reconfiguration protocol that overlaps various phases of “static” reconfiguration processes traditionally used in commercial and research systems to provide performance efficiency on par with that of recently proposed “dynamic” reconfiguration processes, but without their complexity. Simulation results show that the proposed Overlapping Static Reconfiguration protocol can reduce reconfiguration time by up to 50%, reduce packet latency by several orders of magnitude, reduce packet dropping by an order of magnitude, and provide unhalted packet injection as compared to traditional static reconfiguration while allowing network throughput similar to dynamic reconfiguration.

Citation KeySimula.ND.22