• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Algorithms and average time bounds of sorting on a mesh-connected computer
【24h】

Algorithms and average time bounds of sorting on a mesh-connected computer

机译：网格连接计算机上的排序算法和平均时限

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We give three new parallel sorting algorithms on a mesh-connected computer with wraparound connections (i.e. a torus). These three algorithms, with the minimum queue size of 1, sort n/sup 2/ random input data items into a blocked snakelike row major order, a row major order, and a snakelike row major order, in 1.5n+o(n), 2n+o(n), and 2n+o(n) average steps, respectively. These results improve the previous results of 2n+o(n), 2.5n+o(n), and 2.5n+o(n), respectively. In addition, we prove that the distance bound n on a torus is an average-time lower bound independent of indexing schemes of sorting random input data items on it.
机译：我们在具有环绕连接（即圆环）的网状连接计算机上给出了三种新的并行排序算法。这三种算法的最小队列大小为1，将n / sup 2 /随机输入数据项按1.5n + o（n）分成阻塞的蛇状行主顺序，行主顺序和蛇状行主顺序。 ，2n + o（n）和2n + o（n）个平均步长。这些结果分别改善了先前的2n + o（n），2.5n + o（n）和2.5n + o（n）的结果。此外，我们证明了圆环上的距离限制n是平均时间下限，与对随机输入数据项进行排序的索引方案无关。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号