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