| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于Wormhole路由的二维Mesh上的并行 k -选择 |
| 作者 | 许胤龙 王 洵 万颖瑜 陈国良 |
| 作者单位 | (中国科学技术大学计算机科学与技术系国家高性能计算中心 合肥 230027) |
| 发表年份 | 1999 |
| 发表月份 | 12期 （页码：1309—1313) |
| 文章摘要 | 由于二维网孔机器的结构简单、规整,易于VLSI实现,使得它不仅成为许多理论研究的基础模型,而且还是许多并行机所采用的互连结构.Wormhole路由技术的采用改进了二维网孔机器的通信能力.该文在带有Wormhole路由技术的n×n二维网孔机器上提出了一个时间复杂度为O(log2nloglogn)的并行 k -选择算法,改进了该问题在Store-and-Forward路由技术下的时间复杂度下界 O(n) .据已掌握的资料,该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的k-选择算法. 关键词 k-选择,网孔机器,Wormhole路由. |