Replaying the execution of a parallel program from a runtime trace is a standard approach to performance analysis and debugging of a program with nondeterministic behavior. We propose two improvements to a previous trace-and-replay system. The first is a refinement of a previous trace-reduction strategy called incremental tracing, which generates a coarse trace at the expense of longer replay time. We propose a compiletime heuristic to choose the level of runtime tracing, to improve the balance between runtime-trace size and replay time. The second improvement is an extension of the replay strategy. During replay, the coarse trace that was generated at runtime is expanded incrementally aa it is required by the replay. © 1991, ACM. All rights reserved.