Z. El Jamous, L.B. Levitin, and M. Mustafa (USA)
interconnection networks, wormhole routing, deadlock prevention, routing algorithms
A new algorithm for deadlock prevention in interconnec tion networks by prohibition of certain turns, called Edge Deletion Algorithm (EDA), is suggested. We proved that EDA breaks all cycles and preserves connectivity. Com putation complexity of EDA is estimated. This algorithm is compared with the well-known Up-and-Down algorithm (UDA). Simulation results show that EDA dramatically outperforms UDA in three important characteristics. It yields 30% reduction of the average fraction of prohibited turns. It cuts by more than 40% the increase of the aver age distance in the network; and it increases by 45% the saturation load (maximum message generation rate)
Important Links:
Go Back
