基于Wormhole路由的二维Mesh上的并行k-选择

PARALLEL k-SELECTION ON WORMHOLE ROUTED 2D MESHES

由于二维网孔机器的结构简单、规整，易于ＶＬＳＩ实现，使得它不仅成为许多理论研究的基础模型，而且还是许多并行机所采用的互连结构．Ｗｏｒｍ ｈｏｌｅ 路由技术的采用改进了二维网孔机器的通信能力．该文在带有Ｗｏｒｍ ｈｏｌｅ 路由技术的ｎ×ｎ 二维网孔机器上提出了一个时间复杂度为Ｏ（ｌｏｇ２ｎｌｏｇｌｏｇｎ）的并行ｋ－选择算法，改进了该问题在Ｓｔｏｒｅ－ａｎｄ－Ｆｏｒｗ ａｒｄ 路由技术下的时间复杂度下界Ｏ（ｎ）．据已掌握的资料，该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的ｋ－选择算法．

Due to the simplicity of the interconnection pattern and regularity, a 2D mesh connected computer lends itself well to VLSI implementation. A mesh connected computer has become an important computation model in parallel algorithm study and many mesh connected computers have been developed. Wormhole routing improves the communication ability of mesh connected computers. This paper presents a parallel k- selection algorithm with time complexity O(log 2nloglogn) on n×n wormhole routed 2D meshes. It improves the time lower bound O(n) on the n×n Store and Forward routed 2D meshes.