Lossless static vs. dynamic reconfiguration of interconnection networks in parallel and distributed computer systems

ABSTRACT

Advances in the technology of dynamic reconfigurable hardware allow enhanced architectures of interconnection networks for large scale down to on-chip parallel and distributed systems. To archive a higher communication performance the topology of the interconnection network can be reconfigured at runtime to support the particular communication profile of the active applications. One important issue concerning the reconfiguration of the network is the prevention of packet losses. Altering the network topology leads to a new routing situation for the remaining packets. Two approaches are possible: emptying all buffers of the network before reconfiguration, called static reconfiguration, or rerouting of remaining packets after reconfiguration, referred to as dynamic reconfiguration. For the latter approach, a reconfiguration-aware routing scheme is required, which is presented in this paper. In addition, the static and dynamic approaches are discussed and compared concerning complexity and performance. It is shown that the increased efficiency of the dynamic approach becomes negligible, if current available technology is regarded.

References

1. Benini, L.; De Micheli, G. 2002, "Networks on Chips: A New SoC Paradigm." Computer, 35, no. 1: 70--78.
2. Guerrier, P.; Greiner, A. 2000, "A Generic Architecture for On-Chip Packet-Switched Interconnections." In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE 2000), Paris, France, 250--256.
3. Pande, P. P.; Grecu, C.; Ivanov, A.; Saleh, R. 2003, "Switch-Based Interconnect Architecture for Future Systems on Chip." In J. F. Lopez; J. A. Montiel-Nelson; D. Pavlidis, eds., Proceedings of SPIE, VLSI Circuits and Systems, SPIE--The International Society for Optical Engineering, Maspalomas, Gran Canaria, Spain, vol. 5117, 228--237.
4. Bertozzi, D.; Jalabert, A.; Murali, S.; Tamhankar, R.; Stergiou, S.; Benini, L.; De Micheli, G. 2005, "NoC Synthesis Flow for Customized Domain Specific Multiprocessor Systems-on-Chip." IEEE Transactions on Parallel and Distributed Systems, 16, no. 2: 113--129.
5. Sánchez, J. L.; García, J. M. 2000, "Dynamic reconfiguration of node location in wormhole networks." Journal of Systems Architecture, 46, no. 10: 873--888.
6. Majer, M.; Bobda, C.; Ahmadinia, A.; Teich, J. 2005, "Packet Routing in Dynamically Changing Networks on Chip." In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05)--Workshop 3, IEEE Computer Society, Washington, DC, USA, vol. 4, 154.2.
7. Casado, R.; Bermúdez, A.; Quiles, F. J.; Sánchez, J. L.; Duato, J. 2000, "Performance Evaluation of Dynamic Reconfiguration in High-Speed Local Area Networks." In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, IEEE Computer Society, Los Alamitos, CA, USA, 85--96.
8. Ni, L. M.; Gui, Y.; Moore, S. 1997, "Performance Evaluation of Switch-Based Wormhole Networks." IEEE Transactions on Parallel and Distributed Systems, 8, no. 5: 462--474.
9. Lüdtke, D.; Tutsch, D.; Walter, A.; Hommel, G. 2005, "Improved Performance of Bidirectional Multistage Interconnection Networks by Reconfiguration." In Proceedings of 2005 Design, Analysis, and Simulation of Distributed Systems (DASD 2005), SCS, San Diego, CA, USA, 21--27.
10. Duato, J. 1993, "A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks." IEEE Transactions on Parallel and Distributed Systems, 04, no. 12: 1320--1331.
11. V., A. K.; Pinkston, T. M. 1995, "An Efficient, Fully Adaptive Deadlock Recovery Scheme: DISHA." ACM SIGARCH Computer Architecture News, 23, no. 2: 201--210.
12. Zimmermann, C. 2006, "Simulative Leistungsbewertung und Entwicklung "rekonfigurationsfester" Rout-ingverfahren für mehrstufige Verbindungsnetzwerke (in German)." Diplomarbeit, Technische Universität Berlin, Fakultät für Elektrotechnik und Informatik.
13. Tutsch, D.; Lüdtke, D.; Kühm, M. 2006, "Investigating Dynamic Reconfiguration of Network Architectures with CINSim." In Proceedings of the 13th Conference on Measurement, Modeling, and Evaluation of Computer and Communication Systems 2006 (MMB 2006); Nürnberg, VDE, 445--448.
14. Heine, H. 2007, "Entwurf und Synthese eines generischen Network-on-Chip Modells in VHDL (in German)." Diplomarbeit, Technische Universität Berlin, Fakultät für Elektrotechnik und Informatik.
15. Sedcole, P.; Blodget, B.; Becker, T.; Anderson, J.; Lysaght, P. 2006, "Modular dynamic reconfiguration in Virtex FPGAs." IEE Proceedings--Computers and Digital Techniques, 153, no. 3: 157--164.
16. Lüdtke, D.; Tutsch, D.; Hommel, G. 2006, "An Analyzable On-Chip Network Architecture for Embedded Systems." In Hommel; Sheng, eds., Proceedings of the 7th International Workshop on Embedded Systems-Modeling, Technology, and Applications, Springer, 63--72.

• Computer systems organization

• General and reference

  • Cross-computing tools and techniques

• Networks

  • Network properties