Abstract
This paper considers a model of a parallel program that can efficiently be interpreted on an instrumental computer, providing a means for a sufficiently accurate prediction of the actual time needed for execution of the parallel program on a given parallel computational system. The model is designed for parallel programs with explicit message passing written in Java with calls to the MPI library and is a part of the ParJava environment. The model is obtained by transforming the program control tree, which, for Java programs, can be constructed by modifying the abstract syntax tree. The communication functions are simulated on the basis of the LogGP model, which makes it possible to take into account specific features of the distributed computational system.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Report of President’s Information Technology Advisory Committee (PITAC) to the President of Computational Science: Ensuring America’s Competitiveness, http://www.nitrd.gov/pitac/reports/.
Defense Advanced Research Projects Agency (DARPA) Program: High Productivity Computing Systems (HPCS), http://www.highproductivity.org/.
Shanmugam, K., Malony A., and Mohr, B., Speedy: An Integrated Performance Extrapolation Tool for pC++ Programs, Proc. of the Joint Conf. Performance Tools’95 and MMB’95, Heidelberg, 1995.
Yan, J.C., Sarukkai, S.R., and Mehra P., Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs Using the AIMS Toolkit, Software Practice and Experience, 1995, vol. 25, no. 4, pp. 429–461.
Ivannikov, V., Gaissaryan, S., Avetisyan, A., and Padaryan, V., Improving Properties of a Parallel Program in ParJava Environment, Lecture Notes in Computer Science (Proc. Tenth EuroPVM/MPI Conf.), 2003, vol. 2840, pp. 491–494.
Alexandrov, A., Ionescu, M.F., Schauser, K.E., and Scheiman, C., LogGP: Incorporating Long Messages into the LogP Model—One Step Closer Towards a Realistic Model for Parallel Computation, Technical Report TRCS95-09, Univ. of California at Santa Barbara, 1995.
Gosling, J., Joy, B., Steele, G., and Bracha, G., Java(TM) Language Specification, Addison-Wesley, 2005.
Java Native Interface Specification. JNI Types and Data Structures, Type Signatures, http://java.sun.com/j2se/1.5.0/docs/guide/jni/spec/types.html#wp16432.
MPI: A Message-Passing Interface Standard, http://www.mpi-forum.org/docs/mpi-11-html/mpi-report.html.
Pugh, W. and Spacco, J., MPJava: High-Performance Message Passing in Java Using java.nio, Proc. 16th Int. Workshop on Languages and Compilers for Parallel Computing, College Station, USA, 2003, pp. 323–339.
Zheng, G., Wilmarth, T., Jagadishprasad, P., and Kale, L.V., Simulation-Based Performance Prediction for Large Parallel Machines, Int. J. Parallel Programming, 2005, vol. 33, nos. 2–3, pp. 183–207.
New Features and Enhancements J2SE 5.0. High-Precision Timing Support, http://java.sun.com/j2se/1.5.0/docs/relnotes/features.html.
Prakash, S. and Bagrodia, R., MPI-SIM: Using Parallel Simulation to Evaluate MPI Programs, Proc. of the Winter Simulation Conf., Washington, DC, USA: IEEE, 1998, pp. 467–474.
Al-Tawil, Kh. and Moritz, C.A., Performance Modeling and Evaluation of MPI, J. Parallel and Distrib. Computing, 2001, vol. 61, no. 2, pp. 202–223.
Avetisyan, A.I., Gaisaryan, S.S., and Samovarov, O.I., Possibilities of Optimal Execution of Parallel Programs Containing Simple and Iterated Loops on Heterogeneous Parallel Computational Systems with Distributed Memory, Programmirovanie, 2002, vol. 28, no. 1, pp. 38–54.
Culler, D.E., Karp, R.M., Patterson, D.A., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., and von Eicken, T., LogP: Towards a Realistic Model of Parallel Computation, Proc. 4th ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, ACM, 1993, pp. 1–12.
Martin, R.P., Vahdat, A.M., Culler, D.E., and Anderson, T.E., Effects of Communication Latency, Overhead, and Bandwidth in a Cluster Architecture, Proc. 24th Annual Int. Symposium on Computer Architecture, Denver, USA, 1997, pp. 85–97.
Brown, D., Hackstadt, S., Malony, A., and Mohr, B., Program Analysis Environments for Parallel Language Systems: The TAU Environment, Proc. 2nd Workshop on Environments and Tools For Parallel Scientific Computing, Townsend, USA, 1994, pp. 162–171.
Labarta, J., Girona, S., Pillet, V., Cortes, T., and Gregoris, L., DiP: A Parallel Program Development Environment, Proc. of the Second Int. Conf. On Parallel Processing “Euro-Par’96”, 1996, vol. 2, pp. 665–674.
Konovalov, N.A. and Kryukov, V.A., Parallel Programs for Computational Clusters and Networks, Otkrytye Sistemy, 2002, no. 3.
Konovalov, N.A., Kryukov, V.A., Mikhailov, S.N., and Pogrebtsov, A.A., FortranDVM—A Language for the Development of Portable Parallel Programs, Programmirovanie, 1995, vol. 21, no. 1, pp. 49–54.
Konovalov, N.A., Kryukov, V.A., and Sazanov, Yu.L., C-DVM—A Language for the Development of Portable Parallel Programs, Programmirovanie, 1999, vol. 25, no. 1, pp. 54–65.
Padaryan, V.A., An Estimate for the Time of Execution of a Parallel Program Using an Interpreter of the ParJava Environment, Preprint of Inst. of System Programming, Russ. Acad. Sci., Moscow, 2005, no. 6.
Sharir, M., Structural Analysis: a New Approach to Flow Analysis in Optimizing Compilers, Computer Languages, 1980, vol. 5, pp. 141–153.
Author information
Authors and Affiliations
Additional information
Original Russian Text © V.P. Ivannikov, S.S. Gaisaryan, A.I. Avetisyan, V.A. Padaryan, 2006, published in Programmirovanie, 2006, Vol. 32, No. 4.
Rights and permissions
About this article
Cite this article
Ivannikov, V.P., Gaisaryan, S.S., Avetisyan, A.I. et al. Estimation of dynamical characteristics of a parallel program on a model. Program Comput Soft 32, 203–214 (2006). https://doi.org/10.1134/S0361768806040037
Received:
Issue Date:
DOI: https://doi.org/10.1134/S0361768806040037