A method and system for trace generation using memory index hashing. A method may include generating an extended trace representative of M threads of instruction execution from a trace representative of N threads of instruction execution, where N and M are integers, N.gtoreq.1 and M>N, and where each of the N threads of the trace includes memory references to respective memory addresses. Generating the extended trace from the trace may include replicating the N threads to generate the M threads, assigning a respective identifier to each of the M threads, and for a given one of the M threads, hashing a first portion of each of the respective addresses dependent upon the respective identifier of the given thread, where the first portion of each of the respective addresses corresponds to at least part of an index of a memory structure shared by at least two of the M threads.