星形图上无死锁的路径算法

摘要：

星形图具有许多良好的拓扑性质,是一种有可能替代传统的超立方体的并行计算互联网络的模型.在本文中,作者针对在星形图这样一种高度规则的网络中,可能产生死锁的问题,对星形图上无死锁的路径算法进行了研究.首先利用星形图中匹配基的性质,给出了从Sn(B)到Sk的正规映射的定义,然后提出了星形图上的两个无死锁受限条件,最后证明了一个满足无死锁受限条件的路径算法.作者还提出了星形图上路径算法的最小无死锁受限条件等,有待于进一步研究.

关键词：星形图、死锁、置换圈、匹配基

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金

在线出版日期：2005-08-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：946-951