JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]


Journal of Information Science and Engineering, Vol. 14 No. 1, pp. 281-298


Replication and Partitioning for Data Arrays in Distributed Memory Systems


Sheng-De Wang and Wei-Der Jwo
Department of Electrical Engineering 
National Taiwan University 
Taipei 106, Taiwan


    In distributed memory systems, the communication overhead may offset the benefits gained by exploiting of parallelism. In order to efficiently utilize computing resources, efforts have been devoted to eliminating the communication overhead. We propose applying a data replication approach together with data alignment to solve the problem. In the proposed method, data arrays can be replicated as the whole or in part into all processors or subsets of processors. The existing alignment approach is not well suited to this kind of problem. Therefore, an abstract computation array is proposed as the template, and data distribution is achieved by partitioning the template among processors. A data array can be fully replicated to eliminate the spatial data dependences if there exists no true dependence across iterations on the data array. Arrays with loop-carried data dependences can be partly replicated if we properly dispatch the iterations to processors. Performance evaluation was carried out in a Cray T3D, and the results show that the proposed approach is effective under a restricted loop model.


Keywords: data partitioning, data replication, array alignment, single program multiple data, distributed memory systems

  Retrieve PDF document (JISE_199801_14.pdf)