Method and system for trace generation using memory index hashing

• US 20070234016A1
• Filed: 03/28/2006
• Published: 10/04/2007
• Est. Priority Date: 03/28/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Fu, Cong, Davis, John
• Granted Patent: US 7,444,499 B2
• Time in Patent Office: Days
• US Class Current: 712/227
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3877 using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel

Abstract

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≧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.

Claims

1. A method, comprising:

generating an extended instruction trace representative of M distinct threads of instruction execution from an instruction trace representative of N distinct threads of instruction execution, wherein N is an integer greater than or equal to 1, and wherein M is an integer greater than N;

wherein each of said N distinct threads of said instruction trace includes memory references to respective memory addresses, and wherein generating said extended instruction trace from said instruction trace comprises;

replicating said N distinct threads to generate said M distinct threads;

assigning a respective unique identifier to each of said M distinct threads; and

for at least some of said memory references included in a given one of said M distinct threads, hashing a first portion of each of said respective memory addresses dependent upon said respective unique identifier of said given one of said M distinct threads, wherein said first portion of each of said respective memory addresses corresponds to at least part of an index of a memory structure shared by at least two of said M distinct threads.

2. The method as recited in claim 1, wherein generating said extended instruction trace from said instruction trace further comprises:

for said at least some of said memory references included in said given one of said M distinct threads, modifying a second portion of each of said respective memory addresses to reflect said respective unique identifier of said given one of said M distinct threads.

3. The method as recited in claim 1, wherein for a given one of said at least some of said memory references having a given respective memory address, said hashing a first portion of each of said respective memory addresses comprises performing an exclusive-OR function on a first portion of said given respective memory address and said respective unique identifier of said given one of said M distinct threads.

4. The method as recited in claim 1, wherein said memory structure corresponds to a set-associative cache memory.

5. The method as recited in claim 1, further comprising executing said N distinct threads of instruction execution on a computer system and generating said instruction trace dependent upon execution behavior of said computer system.

6. The method as recited in claim 1, further comprising simulating said N distinct threads of instruction execution within a simulation model and generating said instruction trace dependent upon simulation behavior of said simulation model.

7. The method as recited in claim 1, further comprising simulating said M distinct threads of instruction execution within a simulation model dependent upon said extended instruction trace.

8. The method as recited in claim 7, wherein generating said extended instruction trace is completed prior to said simulating said M distinct threads of instruction execution within a simulation model dependent upon said extended instruction trace.

9. The method as recited in claim 7, wherein generating said extended instruction trace occurs concurrently with said simulating said M distinct threads of instruction execution within a simulation model dependent upon said extended instruction trace.

10. The method as recited in claim 1, wherein for said given one of said M distinct threads, said respective identifier comprises a core identifier uniquely identifying a particular one of a plurality of processor cores and a thread identifier uniquely identifying said given one of said M distinct threads within said particular processor core.

11. A computer-accessible medium comprising program instructions, wherein the instructions are executable to:

generate an extended instruction trace representative of M distinct threads of instruction execution from an instruction trace representative of N distinct threads of instruction execution, wherein N is an integer greater than or equal to 1, and wherein M is an integer greater than N;

wherein each of said N distinct threads of said instruction trace includes memory references to respective memory addresses, and wherein to generate said extended instruction trace from said instruction trace, the instructions are further executable to;

replicate said N distinct threads to generate said M distinct threads;

assign a respective unique identifier to each of said M distinct threads; and

for at least some of said memory references included in a given one of said M distinct threads, hash a first portion of each of said respective memory addresses dependent upon said respective unique identifier of said given one of said M distinct threads, wherein said first portion of each of said respective memory addresses corresponds to at least part of an index of a memory structure shared by at least two of said M distinct threads.

12. The computer-accessible medium as recited in claim 11, wherein to generate said extended instruction trace from said instruction trace, the instructions are further executable to:

for said at least some of said memory references included in a given one of said M distinct threads, modify a second portion of each of said respective memory addresses to reflect said respective unique identifier of said given one of said M distinct threads.

13. The computer-accessible medium as recited in claim 11, wherein to hash a first portion of each of said respective memory addresses for a given one of said at least some of said memory references having a given respective memory address, the instructions are further executable to perform an exclusive-OR function on a first portion of said given respective memory address and said respective unique identifier of said given one of said M distinct threads.

14. The computer-accessible medium as recited in claim 11, wherein said memory structure corresponds to a set-associative cache memory.

15. The computer-accessible medium as recited in claim 11, wherein the instructions are further executable to generate said instruction trace dependent upon execution behavior of a computer system configured to execute said N distinct threads of instruction execution.

16. The computer-accessible medium as recited in claim 11, wherein the instructions are further executable to simulate said N distinct threads of instruction execution within a simulation model and to generate said instruction trace dependent upon simulation behavior of said simulation model.

17. The computer-accessible medium as recited in claim 11, wherein the instructions are further executable to simulate said M distinct threads of instruction execution within a simulation model dependent upon said extended instruction trace.

18. The computer-accessible medium as recited in claim 11, wherein for said given one of said M distinct threads, said respective identifier comprises a core identifier uniquely identifying a particular one of a plurality of processor cores and a thread identifier uniquely identifying said given one of said M distinct threads within said particular processor core.

19. A system, comprising:

a system memory configured to store instructions; and

one or more processors configured to access said system memory, wherein the instructions are executable by at least one of said one or more processors to;

generate an extended instruction trace representative of M distinct threads of instruction execution from an instruction trace representative of N distinct threads of instruction execution, wherein N is an integer greater than or equal to 1, and wherein M is an integer greater than N;

wherein each of said N distinct threads of said instruction trace includes memory references to respective memory addresses, and wherein to generate said extended instruction trace from said instruction trace, the instructions are further executable by said at least one of said one or more processors to;

replicate said N distinct threads to generate said M distinct threads;

assign a respective unique identifier to each of said M distinct threads; and

for at least some of said memory references included in a given one of said M distinct threads, hash a first portion of each of said respective memory addresses dependent upon said respective unique identifier of said given one of said M distinct threads, wherein said first portion of each of said respective memory addresses corresponds to at least part of an index of a memory structure shared by at least two of said M distinct threads.

20. The system as recited in claim 19, wherein to generate said extended instruction trace from said instruction trace, the instructions are further executable by said at least one of said one or more processors to:

for said at least some of said memory references included in a given one of said M distinct threads, modify a second portion of each of said respective memory addresses to reflect said respective unique identifier of said given one of said M distinct threads.