Estimation of dynamical characteristics of a parallel program on a model. (English. Russian original) Zbl 1117.68327

Program. Comput. Softw. 32, No. 4, 203-214 (2006); translation from Programmirovanie 2006, No. 4, 21-37 (2006).
Summary: 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.


68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)


Full Text: DOI


[1] 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/ .
[2] Defense Advanced Research Projects Agency (DARPA) Program: High Productivity Computing Systems (HPCS), http://www.highproductivity.org/ .
[3] 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.
[4] 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.
[5] 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. · Zbl 1076.76584
[6] 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.
[7] Gosling, J., Joy, B., Steele, G., and Bracha, G., Java(TM) Language Specification, Addison-Wesley, 2005. · Zbl 0865.68001
[8] 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 .
[9] MPI: A Message-Passing Interface Standard, http://www.mpi-forum.org/docs/mpi-11-html/mpi-report.html . · Zbl 0875.68206
[10] 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. · Zbl 1099.68573
[11] 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. · Zbl 05007769
[12] New Features and Enhancements J2SE 5.0. High-Precision Timing Support, http://java.sun.com/j2se/1.5.0/docs/relnotes/features.html .
[13] 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.
[14] 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. · Zbl 0970.68596
[15] 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. · Zbl 1037.68041
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] Konovalov, N.A. and Kryukov, V.A., Parallel Programs for Computational Clusters and Networks, Otkrytye Sistemy, 2002, no. 3.
[21] 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.
[22] 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.
[23] 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.
[24] Sharir, M., Structural Analysis: a New Approach to Flow Analysis in Optimizing Compilers, Computer Languages, 1980, vol. 5, pp. 141–153. · Zbl 0444.68021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.