A multithreaded program includes sequences of events wherein each sequence is associated with one of a plurality of execution threads. In a record mode, the software tool of the present invention records a run-time representation of the program by distinguishing critical events from non-critical events of the program and identifying the execution order of such critical events. Groups of critical events are generated wherein, for each group G.sub.i, critical events belonging to the group G.sub.i belong to a common execution thread, critical events belonging to the group G.sub.i are consecutive, and only non-critical events occur between any two consecutive critical events in the group G.sub.i. In addition, the groups are ordered and no two adjacent groups include critical events that belong to a common execution thread. For each execution thread, a logical thread schedule is generated that identifies a sequence of said groups associated with the execution thread. The logical thread schedules are stored in persistent storage for subsequent reuse. In a replay mode, for each execution thread, the logical thread schedule associated with the execution thread is loaded from persistent storage and the critical events identified by the logical thread schedule are executed.