Abstract
This paper presents an analytical performance prediction model and methodology that can be used to predict the execution time, speedup, scalability and similar performance metrics of a large set of image processing operations running on a p-processor parallel system. The model which requires only a few parameters obtainable on a minimal system can help in the systematic design, evaluation and performance tuning of parallel image processing systems. Using the model one can reason about the performance of a parallel image processing system prior to implementation. The method can also support programmers in detecting critical parts of an implementation and system designers in predicting hardware performance and the effect of hardware parameter changes on performance. The execution of parallel image processing operations was studied and operations were arranged in three main problem classes based on data locality and the communication patterns of the algorithms. The core of the method is the derivation of the overhead function, as it is the overhead that determines the achievable speedup. The overheads were examined and modelled for each class. The use of the method is illustrated by four class-representative image processing algorithms: image-scalar addition, convolution, histogram calculation and the Fast Fourier Transform. The developed performance model has been validated on a 16-node parallel machine and it has been shown that the model is able to predict the parallel run-time and other performance metrics of parallel image processing operations accurately.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
D. H. Bailey, E. Barszcz, L. Dagum and H. D. Simon, “NAS Parallel Benchmark Results,” IEEE Parallel and Distributed Technology, pp. 43–51, February 1993.
S. H. Bokhari, “Multiphase Complete Exchange on Paragon, SP2, and CS-2 2,' IEEE Parallel and Distributed Technology, Vol. 4,No. 3., pp. 45–59, Fall 1996.
M. J. Clement and M. L. Quinn, “Analytical Performance Prediction on Multicomputers,” in Proceedings Supercomputing'93, ACM New York, pp. 886, 1993.
M. E. Crovella and T. J. LeBlanc, The Search for Lost Cycles: A New Approach to Parallel Program Performance Evaluation, Technical Report 479, The University of Rochester, December 1993.
K. Dincer, Z. Bozkus, S. Ranka and G. Fox, “Benchmarking the computation and communication performance of the CM-5,” Concurrency: Practice and Experience, Vol. 8(1), pp. 47–69, Jan–Feb 1996.
J. Dongarra and T. Dunigan, “Message-Passing Performance of Various Computers,” University of Tennessee Technical Report, CS–95–299, May 1996.
E. Gelenbe, Multiprocessor Performance, John Wiley & Sons, 1989.
A. Y. Grama, A. Gupta and V. Kumar, “Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures,” IEEE Parallel and Distributed Technology, Vol. 1,No. 3., pp. 12–21, August 1993.
A. Gupta and V. Kumar, “The scalability of FFT on parallel computers,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4,No. 8, pp. 922–932, 1993.
V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing: design and analysis of parallel algorithms, The Benjamin/Cummings Publishing Company Inc., 1994.
J. Miguel, A. Arruabarrena, R. Beivide and J.A. Gregorio, “Assessing the Performance of the New IBM SP2 Communication Subsystem,” IEEE Parallel and Distributed Technology, Vol. 4,No. 4., pp. 12–22, Winter 1996.
J. T. Pfenning and C. Moll, “Optimized communication patterns on workstation clusters,” Parallel Computing 21 pp. 373–388, 1995.
Z. Xu and K. Hwang, “Modeling Communication Overhead: MPI and MPL Performance on the IBM SP2,” IEEE Parallel and Distributed Technology, Vol. 4,No. 1., pp. 9–24, Spring 1996.
M. J. Zemerly, D. J. Kerbyson, E. Papaefstathiou, R. Ziani, Y. Papay, T. J. Atherton and G. R. Nudd, “Characterising Computational Kernels to Predict Performance of Parallel Systems,” in Proceedings Transputer Applications and Systems '94, IOS Press, pp. 105–119, 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Johasz, Z. An Analytical Method for Predicting the Performance of Parallel Image Processing Operations. The Journal of Supercomputing 12, 157–174 (1998). https://doi.org/10.1023/A:1007997931146
Issue Date:
DOI: https://doi.org/10.1023/A:1007997931146