THE IMPLEMENTATION OF OPTIMAL BROADCAST AND SUMMATION ALGORITHMS IN THE Log MODEL
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Compared with other parallel computation models,the LogP model reflects the characteristics of MPC(massively parallel computers)more reasonably.In this paper the authors try to use the LogP model to write portable algorithms for MPC.They first propose a general recurrence formula for the defining of optimal broadcast tree,then design and analysis the complete optimal single item broadcast algorithm and optimal summation algorithm in the LogP model whose parameters may have any given values.

    Reference
    1 Valiant L G.A bridging model for parallel computation.Communications of the ACM,1990,33(8):103~111. 2 Culler D E,Karp R M,Patterson D et al.LogP:towards a realistic model of parallel computation.In:Proc.of 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,1993.1~12. 3 Bonniger T,Esser R,Krekel D.CM-5E,KSR2,Paragon XP/S:a comparative description of massively parallel computers.Parallel Computing,1995,21:199~232. 4 Karp R M,Sahay A,Santos E et al.Optimal broadcast and summation in the LogP model.In:Proc.of 5th Sy- posium on Parallel Algorithms and Architectures, June 1993. 5 Eicken T,Culler D E,Goldstein S C et al.Active message:a mechanism for integrated communication and compu- tation.In:Proc.of 19th International Symposium on Computer Architecture.May 1992. 6 Sahay A.Hiding communication costs in bandwidth limited parallel FFT computation.TR UCB/CSD 92/722,UC Berkeley,1992.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

寿标,陈国良. LogP模型上的最优播送与求和算法的实现.软件学报,1997,8(1):22-28

Copy
Share
Article Metrics
  • Abstract:3805
  • PDF: 4945
  • HTML: 0
  • Cited by: 0
History
  • Revised:December 22,1995
You are the first2038652Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063