A Data Space Fusion Based Approach for Global Computation and Data Decompositions
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [15]
  • |
  • Related [20]
  • |
  • Cited by [3]
  • | |
  • Comments
    Abstract:

    Computation and data decompositions are key factors of affecting the performance of parallel programs running on distributed memory multicomputers. This paper presents a theoretical framework of data space fusion and an effective global computation and data decomposition approach based on it, which can be used to solve computation and data decomposition problems on distributed memory multicomputers. The approach can exploit the parallelism of computation space as high as possible, use the technique of data space fusion to optimize data distribution, and search the optimizing global computation and data decompositions. The approach can also be integrated with data replication and offset alignment naturally, and therefore can make the communication overhead as low as possible. Experimental results show that the approach presented in the paper is effective.

    Reference
    [1]Chen TS, Chang CY. Skewed data partition and alignment techniques for compiling programs on distributed memory multicomputers. The Journal of Supercomputing 2002,21 (2): 191~211.
    [2]Chang WL, Chu CP, Wu JH. Communication-Free alignment for array references with linear subscripts in three loop index variables or quadratic subscripts. The Journal of Supercomputer; 2001,20(1):67~83.
    [3]Shih KP, Sheu JP, Huang CH. Statement-Level communication-free partitioning technique for parallelizing compilers. The Journal of Supercomputing, 2000,15(3):243~269.
    [4]Lim AW. Improve parallelism and data locality with affine partitioning[Ph.D. Thesis]. Palo Alto: Stanford University, 2001.
    [5]Chen TS, Sheu JP. Communication-Free data allocation techniques for parallelizing compilers on multicomputers. IEEE Trans on Parallel and Distributed Systems, 1994,5(9):924~938.
    [6]Ramanujam J, Sadayappan P. Compile-Time techniques for data distribution in distributed memory machines IEEE Trans. on Parallel and Distributed systems, 1991,2(4):472~482.
    [7]Huang CH, Sadayappan P. Communication-Free hyperplane partitioning of nested loops. Journal of Parallel ard Distributed Computing, 1993,19(2):90~102.
    [8]Wolf M. High Performance Compilers for Parallel Computing. Redwood Addison-Wesley Publishing Company, 1996. 137~510.
    [9]Wolf M, Lam M. A data locality optimizing algorithm. In: Mauney J, ed. Proc. of the SIGPLAN'91 Conf. on Programming Language Design and Implementation. New York: ACM Press, 1991.30~44.
    [10]Shen ZY, Hu ZA, Liao XK, Wu HP, Zhao KJ, Lu YT. Methods of Parallel Compilation. Beijing: National Defence Industry Press,2000.31~127 (in Chinese).
    [11]Anderson JM. Automatic computation and data decomposition for multiprocessors Technique Report, CSL-TR-97-719, Palo Alto:Stanford University, 1997. 1~192.
    [12]Ayguade E, Garcia J, Kremer U. Tools and techniques for automatic data layout: A case study. Parallel Computing,1998,24(3-4):557~578.
    [13]Li J, Chen M. The data alignment phase in compiling programs for distributedmemory machines. Journal of Parallel and Distributed Computing, 1991,13(2):213~221.
    [14]Cierniak M, Wei L. Unifying data and control transformations for distrihsted shared-memory machines. In: Sestoft P, ed. Proc. of the ACM SIGPLAN'95 Conf. on Programming Language Design and Implementation New York: ACM Press, 1995. 205~217.
    [10]沈志宇,胡子昂,廖湘科,吴海平,赵克佳,卢宇彤.并行编译方法.北京:国防工业出版社,2000.31~127.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

夏军,杨学军.基于数据空间融合的全局计算与数据划分方法.软件学报,2004,15(9):1311-1327

Copy
Share
Article Metrics
  • Abstract:3987
  • PDF: 5244
  • HTML: 0
  • Cited by: 0
History
  • Received:April 21,2003
  • Revised:December 08,2003
You are the first2038704Visitors
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