Deadlock Analysis in Minimal Adaptive Routing Algorithms using Petri Nets

TitleDeadlock Analysis in Minimal Adaptive Routing Algorithms using Petri Nets
Publication TypeConference Paper
Year of Publication2010
AuthorsRovetto, C, Cano E, Colom JM
Conference NameIEEE International Conference on Systems, Man, and Cybernetics (SMC’10)
Date Published10/2010
Conference LocationIstanbul, Turkey
ISBN Number978-1-4244-6587-3
KeywordsPetri nets Deadlock Analysis Resource Allocation Systems Minimal Adaptive Routing Algorithms
AbstractMulticomputer Interconnection Networks and the design of routing algorithms for these networks, is a very active research domain that in the last decade has given rise to technologically consolidated systems. Nevertheless, from the methodological point of view, the diverse approaches are very limited, moreover in many cases are not complete in order to cover the different phases of the design cycle. In this paper we present a complete design approach, supported by a methodology until to get a deadlock-free routing algorithm. The starting information is the topology of the interconnection network and the initial minimal routing algorithm elaborated by the designer. From this information we obtain a Petri Net model, allowing to characterize the deadlock situations, and, if necessary, to modify the algorithm in order to produce a deadlock-free minimal adaptive routing algorithm.