Abstract-A dödlägesfri routing algoritm kan genereras för godtyckliga sammankopplingsnätverk med hjälp av begreppet virtuella kanaler. Ett nödvändigt och tillräckligt villkor för dödlägesfri routing är frånvaron av cykler i ett kanalberoende diagram. Med tanke på ett godtyckligt nätverk och en routing funktion, cyklerna i kanalen beroende grafen kan tas bort genom att dela fysiska kanaler i grupper av virtuella kanaler. Denna metod används för att utveckla dödlås-fri routing algoritmer för k-ary n-cubes, för kub-anslutna cykler, och för shuffle-utbyte nätverk.
Dally och Seitz REF presenterade det nödvändiga och tillräckliga villkoret för dödstoppsfri routing i ett multidatornätverk.
Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
{'venue': 'IEEE Transactions on Computers', 'journal': 'IEEE Transactions on Computers', 'mag_field_of_study': ['Computer Science']}