Estimating Performance of Mergesort on a Network of Transputers
Patrik Möller, Kallol Kumar Bagchi · 2005
The estimation of the implemented behavior like execution time etc., of a parallel algorithm is a difficult task. The bound estimates may typically differ from measured parameters of an implemented algorithm by several orders of magnitude, due to the presence of a number of virtual layers between such theoretical bound models and the implemented versions. A systematic procedure for obtaining a realistic estimate of the execution time of a non-trivial parallel algorithm like mergesort is outlined in this paper. The measured hardware instruction cycles are in close agreement with the calculated theoretical instruction cycles.