Analysis of replicated data algorithms on processor array architectures

Processor array machines have gained popularity in practical parallel processing, particularly in data parallel application areas such as image processing. The data parallel paradigm underutilizes a massively parallel machine when relatively small data structures are processed on it, which occur due to popular algorithmic techniques such as divide-and-conquer. We devised the technique of data replication combining operation parallelism with data parallelism to speed up some image processing algorithms analytically and practically. In this paper, we analyze replicated data algorithms on three popular array interconnection networks to determine the conditions under which speedup can be obtained. Our analysis shows that the data replication technique can attain significant speedup even on non-global architectures such as the 3-D mesh. We also compare the analysis with experimental speedup obtained on the hypercube connected Connection Machine.