Deadlock analysis in minimal adaptive routing algorithms using Petri Nets

Multicomputer 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.