首页> 外文期刊>Parallel Computing >On variable blocking factor in a parallel dynamic block―Jacobi SVD algorithm
【24h】

On variable blocking factor in a parallel dynamic block―Jacobi SVD algorithm

机译:并行动态块中的可变块因子Jacobi SVD算法

获取原文
获取原文并翻译 | 示例

摘要

The parallel two-sided block-Jacobi singular value decomposition (SVD) algorithm with dynamic ordering, originally proposed in [Parallel Comput. 28 (2002) 243-262], has been extended with respect to the blocking factor l. Unlike the unique blocking factor l = 2p in the original algorithm running on p processors, the current blocking factor is a variable parameter that covers the values in two different regions―namely, l = p/k and l = 2kp for some integer k. Two new parallel two-sided block-Jacobi SVD algorithms with dynamic ordering are described in detail. They arise in those two regions and differ in the logical data arrangement and communication complexity of the reordering step. For the case of l = 2kp, it is proved that a designed point-to-point communication algorithm is optimal with respect to the amount of communication required per processor as well as to the amount of overall communication. Using the message passing programming model for distributed memory machines, new parallel block-Jacobi SVD algorithms were implemented on an SGI-Cray Origin 2000 parallel computer. Numerical experiments were performed on p = 12 and 24 processors using a set of six matrices of order 4000 and blocking factors l, 2≤l≤192. To achieve the minimal total parallel execution time, the use of a blocking factor l∈{2, p, 2p} can be recommended for matrices with distinct singular values. However, for matrices with a multiple minimal singular value, the total parallel execution time may monotonically increase with l. In this case, the recommended Jacobi method with l = 2 is just the ScaLAPACK routine with some additional matrix multiplications, and it computes the SVD in one parallel iteration step.
机译:具有动态排序的并行两面块雅各比奇异值分解(SVD)算法,最初在[Parallel Comput。参见图28(2002)243-262],关于阻挡因子l已经扩展。与在p个处理器上运行的原始算法中唯一的阻塞因子l = 2p不同,当前阻塞因子是一个可变参数,它覆盖两个不同区域中的值,即对于某些整数k,l = p / k和l = 2kp。详细介绍了两种新的具有动态排序的并行双面块-Jacobi SVD算法。它们出现在这两个区域中,并且在逻辑数据排列和重新排序步骤的通信复杂性方面有所不同。对于l = 2kp的情况,证明了设计的点对点通信算法在每个处理器所需的通信量以及整体通信量方面都是最佳的。使用分布式内存机器的消息传递编程模型,在SGI-Cray Origin 2000并行计算机上实现了新的并行块-Jacobi SVD算法。使用一组6个阶数为4000且阻塞因子为1、2≤l≤192的矩阵在p = 12和24个处理器上进行了数值实验。为了达到最小的总并行执行时间,对于具有不同奇异值的矩阵,建议使用阻塞因子l∈{2,p,2p}。但是,对于具有多个最小奇异值的矩阵,总并行执行时间可能单调增加l。在这种情况下,推荐的l = 2的Jacobi方法只是带有一些附加矩阵乘法的ScaLAPACK例程,并且它在一个并行迭代步骤中计算SVD。

著录项

  • 来源
    《Parallel Computing》 |2003年第9期|p.1153-1174|共22页
  • 作者

    Martin Becka; Gabriel Oksa;

  • 作者单位

    Department of Informatics, Institute of Mathematics, Slovak Academy of Sciences, Dubravska cesta 9, 841 04 Bratislava, Slovak Republic;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号