摘要
主要研究蜂窝环上的全广播路由算法。第一个全广播算法的设计思路是找到一条通过所有节点的路径,关键是确定边界上的一些特殊节点;第二个全广播算法应用了蜂窝环的哈密尔顿性质。假设一个有n个处理机的蜂窝环,前者每个节点有自己专用的路由策略,时间复杂度为3n,因为计算时间往往比数据传送时间低得多,所以总的通信时间可以降低到n;后者是基于哈密尔顿圈的,需要n时间复杂度。到目前为止,这是第一次给出蜂窝环上全广播算法。
This paper addressed all-to-all broadcasting algorithms on honeycomb tori.The design of the first all-to-all broadcasting algorithm was to find a path going through all the nodes,and the main task was to determine some special nodes on the border.The second one used the fact that honeycomb tori was Hamiltonian.Considering a network with n processors,the former had personalized routing strategy at each node and it required a 3n communication time complexity.This communication time could be reduced to n because the computation time was always assumed to be much lower than the communication time.The latter was based on a Hamiltonian cycle and had an n communication time complexity.These all-to-all broadcasting algorithms are the only ones so far exhibited on a honeycomb torus.
出处
《计算机应用研究》
CSCD
北大核心
2011年第7期2492-2493,2496,共3页
Application Research of Computers
基金
贺州学院2010年度院级科研立项资助项目(2010ZRKY14)
关键词
并行计算机
互连网络
蜂窝环
全广播
parallel computers
interconnection networks
honeycomb tori
all-to-all broadcasting