• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Optimal Sorting Algorithms for a Simplified 2D Array with Reconfigurable Pipelined Bus System
【24h】

Optimal Sorting Algorithms for a Simplified 2D Array with Reconfigurable Pipelined Bus System

机译：具有可重构流水线总线系统的简化二维阵列的最佳排序算法

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

摘要

In recent years, many researchers have investigated optical interconnections as parallel computing. Optical interconnections are attractive due to their high bandwidth and concurrent access to the bus in a pipelined fashion. The Linear Array with Reconfigurable Pipelined Bus System (LARPBS) model is a powerful optical bus system that combines both the advantages of optical buses and reconfiguration. To increase the scalability of the LARPBS model, we propose a two-dimensional extension: a simplified two-dimensional Array with Reconfigurable Pipelined Bus System (2D ARPBS). While achieving better scalability, we show the effectiveness of this newly proposed model by designing two novel optimal sorting algorithms on this model. The first sorting algorithm is an extension of Leighton's seven-phase columnsort algorithm that eliminates the restriction of sorting only an r times s array, where r ge s^2 , and sorts an n times n array in O(log n) time. The second one is an optimal multiway mergesort algorithm that uses a novel processor efficient two-way mergesort algorithm and a novel multiway merge scheme to sort n^2 items in O(log n) time. Using an optimal sorting algorithm Pipelined Mergesort designed for the LARPBS model as a building block, we extend our research on parallel sorting on the LARPBS to a more scalable 2D ARPBS model and achieve optimality in both sorting algorithms.
机译：近年来，许多研究人员将光互连作为并行计算进行了研究。光互连因其高带宽和以流水线方式同时访问总线而具有吸引力。具有可重构流水线总线系统的线性阵列（LARPBS）模型是功能强大的光总线系统，结合了光总线和可重构的优点。为了增加LARPBS模型的可扩展性，我们提出了二维扩展：具有可重构流水线总线系统（2D ARPBS）的简化二维阵列。在实现更好的可伸缩性的同时，我们通过在该模型上设计两种新颖的最佳排序算法来展示此新提出的模型的有效性。第一种排序算法是Leighton的七阶段列排序算法的扩展，该算法消除了仅排序r次s数组（r ge s ^ 2）的限制，并以O（log n）时间对n次n数组进行了排序。第二种是一种最佳的多路合并排序算法，该算法使用一种新颖的处理器高效的两路合并排序算法和一种新颖的多路合并方案在O（log n）时间内对n ^ 2个项目进行排序。使用为LARPBS模型设计的最佳排序算法Pipelined Mergesort作为构建基块，我们将对LARPBS上的并行排序的研究扩展到更具可扩展性的2D ARPBS模型，并在两种排序算法中都实现了最优性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号