Title page for etd-0721105-234855


[Back to Results | New Search]

URN etd-0721105-234855
Author Sheng-Wen Bai
Author's Email Address swbai@cse.nsysu.edu.tw
Statistics This thesis had been viewed 5581 times. Download 2441 times.
Department Computer Science and Engineering
Year 2004
Semester 2
Degree Ph.D.
Type of Document
Language English
Title Efficient Methods for Arbitrary Data Redistribution
Date of Defense 2005-07-12
Page Count 92
Keyword
  • GBCC
  • ECC
  • Data Redistribution
  • MPI User-Defined Datatypes
  • Data Distribution
  • Abstract In many parallel programs, run-time data redistribution is usually required to enhance data locality and reduce remote memory access on the distributed memory multicomputers. For the heterogeneous computation environment, irregular data redistributions can be used to adjust data assignment. Since data redistribution is performed at run-time, there is a performance trade-off between the efficiency of the new data distribution for a subsequent phase of an algorithm and the cost of redistributing array among processors. Thus, efficient methods for performing data redistribution are of great importance for the development of distributed memory compilers for data-parallel programming languages.
    For the regular data redistribution, two approaches are presented in this dissertation, indexing approach and packing/unpacking approach. In the indexing approach, we propose a generalized basic-cycle calculation (GBCC) technique to efficiently generate the communication sets for a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors data redistribution. In the packing/unpacking approach, we present a User-Defined Types (UDT) method to perform BLOCK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution, using MPI user-defined datatypes. This method reduces the required memory buffers and avoids unnecessary movement of data. For the irregular data redistribution, in this dissertation, an Essential Cycle Calculation (ECC) method will be presented.
    The above methods are originally developed for one dimension array. However, the multi-dimension array can also be performed by simply applying these methods dimension by dimension starting from the first (last) dimension if array is in column-major (row-major).
    Advisory Committee
  • Yeh-Ching Chung - chair
  • Li-Ming Tseng - co-chair
  • Shyan-Ming Yuan - co-chair
  • Yau-Hwang Kuo - co-chair
  • Chyi-Nan Chen - co-chair
  • Lih-Shyang Chen - co-chair
  • Tsung-Chuan Huang - co-chair
  • Chua-Huang Huang - co-chair
  • Chu-Sing Yang - advisor
  • Files
  • etd-0721105-234855.pdf
  • indicate access worldwide
    Date of Submission 2005-07-21

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys