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
Received May 1, 1997; revised November 29, 1997.
Communicated by PeiZong Lee.