Performance Prediction by Trace Transformation

  • Celso L. Mendes University of Illinois


Performance stability is an essential feature for the widespread adoption of multicomputers. In this paper, we report the preliminary steps of our research in performance prediction and extrapolation. Performance tuning, guided by extrapolation, may help achieve a substantial fraction of peak performance rates across a broader range of applications while providing guidance for code porting. We introduce a methodology for assessing stability of parallel programs, based on stability of the program execution graph, using time perturbation analysis. For programs with stable behavior, we present a model for performance prediction under architecture variations, by transformation of the execution traces with parameters that reflect the differences in architecture between two systems. We illustrate the use of this transformation with an example of a parallel PDE solver executing on a multicomputer.


ADVE, V. S., AND VERNON, M. K. The influence of random delays on parallel execution times. In Sigmetrics Proceedings (San Diego, May 1993).

A.G.MOHAMED, G.C.FOX, VON LASZEWSKI, G., M.PARASHAR, T.HAUPT, K.MILLS, Y.LU, N.LIN, AND N.YEH. Application benchmark set for Fortran-D and High Performance Fortran. Tech. Rep. SCCS-327, Northeast Parallel Architectures Center, 1992.

JAIN, R. The Art of Computer Systems Performance Analysis. John Wiley & Sons, New York, 1991.

LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21,7 (July 1978), 558-565.

LEVI, G. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9 (1972), 341-352.

LYON, G., SNELICK, R., AND KACKER, R. Synthetic-perturbation tuning of MIMD programs. Tech. Rep. NISTIR 5131, National Institute of Standards and Technology, February 1993.

MAK, V. W., AND LUNDSTROM, S. F. Predicting performance of parallel computations. IEEE Transactions on Parallel and Distributed Systems 1, 3 (July 1990), 257-270.

READ, R. C., AND CORNEIL, D. G. The graph isomorphism disease. Journal of Graph Theory 1 (1977), 339-363.

REED, D. A., AYDT, R. A., MADHYASTHA, T. M., NOE, R. J., SHIELDS, K. A., AND SCHWARTZ, B. W. The Pablo Performance Analysis Environment. University of Illinois at Urbana-Champaign, 1992.

SAAVEDRA-BARRERA, R. H., SMITH, A. J., AND MIYA, E. Performance prediction by benchmark and machine characterization. IEEE Transactions on Computers 38, 12 (December 1989), 1659-1679.

SPEC. SPEC benchmark suite release 1.0. SPEC Newsletter 2, 2 (1990), 3-4.

Zevissxa, B. On a certain distance between isomorphism classes of graphs. Casopis pro pěstováni matematiky 100 (1975), 371-373.
MENDES, Celso L.. Performance Prediction by Trace Transformation. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1993 . p. 59-74. DOI: