Scalable parallel matrix multiplication on distributed memory parallel computers

被引:8
|
作者
Li, KQ [1 ]
机构
[1] SUNY Albany, Dept Comp Sci, New Paltz, NY 12561 USA
基金
美国国家航空航天局;
关键词
cost optimality; distributed memory parallel computer; linear array with reconfigurable pipelined bus system; matrix multiplication; module parallel computer; optical model of computation; scalability; speedup;
D O I
10.1006/jpdc.2001.1768
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Consider any known sequential algorithm for matrix multiplication over an arbitrary ring with time complexity O(N(alpha)), where 2 < alpha less than or equal to 3. We show that such an algorithm can be parallelized on a distributed memory parallel computer (DMPC) in O(log N) time by using N(alpha)/log N processors. Such a parallel computation is cost optimal and matches the performance of PRAM. Furthermore, our parallelization on a DMPC can be made fully scalable, that is, for all 1 less than or equal to p less than or equal to N(alpha)/log N, multiplying two N x N matrices can be performed by a DMPC with p processors in O(N(alpha)/p) time, i.e., linear speedup and cost optimality can be achieved in the range [ 1..N(alpha)/log N]. This unifies all known algorithms for matrix multiplication on DMPC, standard or nonstandard, sequential or parallel. Extensions of our methods and results to other parallel systems are also presented. For instance, for all 1 less than or equal to p less than or equal to N(alpha)/log N, multiplying two N x N matrices can be performed by p processors connected by a hypercubic network in O(N(alpha)/p + (N(2)/p(2/alpha)) (log p)(2(alpha-1)/alpha)) time, which implies that if p = O(N(alpha)/(log N)(2(alpha-1)/(alpha-2))), linear speedup can be achieved. Such a parallelization is highly scalable. The above claims result in significant progress in scalable parallel matrix multiplication (as well as solving many other important problems) on distributed memory systems, both theoretically and practically. (C) 2001 Academic Press.
引用
收藏
页码:1709 / 1731
页数:23
相关论文
共 50 条
  • [21] Parallel MSC/NASTRAN on distributed memory computers
    Mayer, S
    Poschmann, P
    Shamsian, S
    Komzsik, L
    Boston, I
    Surridge, M
    HIGH-PERFORMANCE COMPUTING AND NETWORKING, 1995, 919 : 850 - 855
  • [22] An improved parallel algorithm for delaunay triangulation on distributed memory parallel computers
    Lee, SY
    Park, CI
    Park, CM
    ADVANCES IN PARALLEL AND DISTRIBUTED COMPUTING - PROCEEDINGS, 1997, : 131 - 138
  • [23] Parallel implementation of a ray tracing algorithm for distributed memory parallel computers
    Lee, TY
    Raghavendra, CS
    Nicholas, JB
    CONCURRENCY-PRACTICE AND EXPERIENCE, 1997, 9 (10): : 947 - 965
  • [24] MATRIX VECTOR MULTIPLICATION FOR SYMMETRICAL MATRICES ON PARALLEL COMPUTERS AND APPLICATIONS
    LANG, B
    ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1991, 71 (06): : T807 - T808
  • [25] A PARALLEL SOLVER FOR TRIDIAGONAL LINEAR-SYSTEMS FOR DISTRIBUTED MEMORY PARALLEL COMPUTERS
    BRUGNANO, L
    PARALLEL COMPUTING, 1991, 17 (09) : 1017 - 1023
  • [26] Parallel operation of CartaBlanca on shared and distributed memory computers
    Padial-Collins, NT
    VanderHeyden, WB
    Zhang, DZ
    Dendy, ED
    Livescu, D
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2004, 16 (01): : 61 - 77
  • [27] LOCALITY ESTIMATION OF PARALLEL ALGORITHM FOR DISTRIBUTED MEMORY COMPUTERS
    Likhoded, Nikolai A.
    Tolstsikau, Aliaksei A.
    DOKLADY NATSIONALNOI AKADEMII NAUK BELARUSI, 2020, 64 (06): : 647 - 656
  • [28] OPTIMIZATION OF DATA EXCHANGE IN PARALLEL COMPUTERS WITH DISTRIBUTED MEMORY
    Adutskevich, E. V.
    Likhoded, N. A.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2006, 42 (02) : 298 - 310
  • [29] Evaluating recursive filters on distributed memory parallel computers
    Stpiczynski, Przemyslaw
    COMMUNICATIONS IN NUMERICAL METHODS IN ENGINEERING, 2006, 22 (11): : 1087 - 1095
  • [30] Parallel algebraic multigrid methods on distributed memory computers
    Haase, G
    Kuhn, M
    Reitzinger, S
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2002, 24 (02): : 410 - 427