论文部分内容阅读
由于二维网孔机器的结构简单、规整，易于ＶＬＳＩ实现，使得它不仅成为许多理论研究的基础模型，而且还是许多并行机所采用的互连结构．Ｗｏｒｍ ｈｏｌｅ 路由技术的采用改进了二维网孔机器的通信能力．该文在带有Ｗｏｒｍ ｈｏｌｅ 路由技术的ｎ×ｎ 二维网孔机器上提出了一个时间复杂度为Ｏ（ｌｏｇ２ｎｌｏｇｌｏｇｎ）的并行ｋ－选择算法，改进了该问题在Ｓｔｏｒｅ－ａｎｄ－Ｆｏｒｗ ａｒｄ 路由技术下的时间复杂度下界Ｏ（ｎ）．据已掌握的资料，该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的ｋ－选择算法．
Because of its simple structure, regular structure and easy VLSI implementation, 2D mesh machine not only becomes the basic model for many theoretical studies, but also is the interconnection structure adopted by many parallel machines. The adoption of Worm hole routing technology improves the communication capabilities of two-dimensional mesh machines. This paper proposes a parallel k-selection algorithm with time complexity O (log2nloglog) on an n × n two-dimensional mesh machine with Worm hole routing technology, and improves the problem in Store-and-Forw ard routing technology Under the time complexity of the lower bound O (n). According to the available information, the algorithm is the polynomial k-selection algorithm with logarithm of time complexity on the earliest, non-bus-connected two-dimensional mesh machine.