• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >On Necessary and Sufficient Conditions for Deadlock-Free Routing in Wormhole Networks
【24h】

On Necessary and Sufficient Conditions for Deadlock-Free Routing in Wormhole Networks

机译：蠕虫网络中无死锁路由的充要条件

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Wormhole switching is a popular switching technique in interconnection networks. This technique is also prone to deadlocks. Adaptive routing algorithms provide alternative paths that can be used to escape congested areas and prevent some deadlocks to occur. If not designed carefully, these new paths may as well introduce deadlocks. A successful solution to deadlock prevention is to constrain the routing function such that it does not introduce any deadlock. Many necessary and sufficient conditions for deadlock-free routing have been proposed. The definition and the proof of these conditions are complex and error-prone. These conditions are often counterintuitive and difficult to understand. Moreover, they are not static, as they all require the analysis of configurations, i.e., the network state. The contribution of this paper is twofold. We present the first static necessary and sufficient condition for deadlock-free routing in wormhole networks. Our condition is much simpler and requires less assumptions than all previous ones. It is formally proven correct using an automated proof assistant. In particular, our condition applies to incoherent routing functions which was considered an open problem. Second, we prove the deadlock decision problem co-NP-complete for wormhole networks.
机译：虫孔交换是互连网络中流行的交换技术。此技术也容易出现死锁。自适应路由算法提供了可用于逃避拥挤区域并防止某些死锁发生的替代路径。如果设计不当，这些新路径也可能会导致死锁。一个成功的防止死锁的解决方案是限制路由功能，使其不引入任何死锁。已经提出了许多无死锁路由的必要条件和充分条件。这些条件的定义和证明很复杂且容易出错。这些条件通常是违反直觉的并且难以理解。而且，它们不是静态的，因为它们都需要分析配置，即网络状态。本文的贡献是双重的。我们提出了蠕虫网络中无死锁路由的第一个静态必要条件和充分条件。我们的条件比以前的条件都简单得多，所需的假设也更少。使用自动校对助手已正式证明它是正确的。特别地，我们的条件适用于被认为是开放问题的不连贯路由功能。其次，我们证明了虫洞网络的死锁决策问题co-NP-complete。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号