• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications(ICCSA 2006) pt.5; 20060508-11; Glasgow(GB) >Efficient Longest Common Subsequence Computation Using Bulk-Synchronous Parallelism
【24h】

Efficient Longest Common Subsequence Computation Using Bulk-Synchronous Parallelism

机译：使用批量同步并行的有效最长公共子序列计算

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

摘要

This paper presents performance results for parallel algorithms that compute the longest common subsequence of two strings. This algorithm is a representative of a class of algorithms that compute string to string distances and has computational complexity O(n~2). The parallel algorithm uses a variable grid size, runs in O(p) supersteps (synchronization phases) and has linear communication costs. We study this algorithm in BSP context, give runtime estimations and compare the predictions to experimental values measured on three different parallel architectures, using different BSP programming libraries and an efficient implementation for sequential computation. We find that using the BSP model and the appropriate optimized BSP library improves the performance over plain MPI, and that scalability can be improved by using a tuned grid size parameter.
机译：本文介绍了并行算法的性能结果，该算法计算两个字符串的最长公共子序列。该算法是计算字符串到字符串距离的一类算法的代表，并且具有计算复杂度O（n〜2）。并行算法使用可变的网格大小，以O（p）个超步（同步阶段）运行，并且具有线性通信成本。我们在BSP上下文中研究此算法，给出运行时估计，并将预测与在三种不同并行体系结构上测得的实验值进行比较，使用不同的BSP编程库和有效的顺序计算实现。我们发现使用BSP模型和适当的优化BSP库可以提高纯MPI之上的性能，并且可以通过使用调整后的网格大小参数来提高可伸缩性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号