Source: http://www.google.com/patents/US7865702?dq=6819670
Timestamp: 2013-12-13 21:07:55
Document Index: 70501981

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US7865702 - Stall prediction thread management - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThread switching prevents pipeline stalls when executing multiple threads. An analysis of a first thread identifies instructions capable of causing pipeline stalls. If pipeline stalls from the identified instructions are likely, thread switching instructions are added to the first thread in place of...http://www.google.com/patents/US7865702?utm_source=gb-gplus-sharePatent US7865702 - Stall prediction thread managementAdvanced Patent SearchPublication numberUS7865702 B2Publication typeGrantApplication numberUS 12/542,157Publication dateJan 4, 2011Filing dateAug 17, 2009Priority dateJan 30, 2006Also published asUS7577826, US20070180438, US20100017582Publication number12542157, 542157, US 7865702 B2, US 7865702B2, US-B2-7865702, US7865702 B2, US7865702B2InventorsVictor SubaOriginal AssigneeSony Computer Entertainment Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (8), Non-Patent Citations (2), Classifications (5), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetStall prediction thread managementUS 7865702 B2Abstract Thread switching prevents pipeline stalls when executing multiple threads. An analysis of a first thread identifies instructions capable of causing pipeline stalls. If pipeline stalls from the identified instructions are likely, thread switching instructions are added to the first thread in place of the identified instructions. Thread switching instructions direct a microprocessor to suspend executing the thread and begin executing a second thread. Thread switching instructions can be added to the second thread to enable the resumption of the first thread at the location specified by the identified instruction. The thread switching instructions are configured to avoid pipeline stalls when switching threads. Thread switching instructions can store and retrieve thread-specific information upon the suspension and resumption of threads. Thread switching instructions can schedule the execution of two or more threads in accordance with load balancing schemes. Threads can be modified using static or dynamic code analysis and modification techniques.
identifying an instruction of a first thread as a high latency floating point instruction;
determining if a pipeline stall is likely from the identified high latency floating point instruction; and
in response to a determination that the pipeline stall is likely from the identified high latency floating point instruction, adding at least one thread switching instruction to the first thread, wherein the thread switching instruction is adapted to switch from the execution of the first thread to a second thread.
3. The method of claim 1, wherein adding the at least one thread switching instruction comprises:
4. The method of claim 3, wherein the entry point of the second thread is the beginning of the second thread.
5. The method of claim 3, wherein the entry point of the second thread is a branch target associated with a branch instruction of the second thread.
6. The method of claim 5, wherein the entry point of the second thread was previously stored by at least one thread switching instruction of the second thread.
7. The method of claim 3, wherein the entry point of the second thread is a first instruction of the second thread intended to be executed after a second instruction of the second thread, wherein the second instruction may potentially cause a pipeline stall in the second thread.
8. The method of claim 7, wherein the second instruction of the second thread is a high latency floating point instruction.
10. The method of claim 9, wherein the thread switching instruction of the second thread is configured to direct execution to a thread resumption point of the first thread.
11. The method of claim 10, wherein the thread resumption point of the first thread is a first instruction of the first thread intended to be executed following the identified instruction of the first thread.
12. The method of claim 11, wherein adding at least one thread switching instruction to the second thread further comprises:
13. The method of claim 12, wherein analyzing at least the identified instruction comprises determining a value of a condition, wherein the identified instruction is responsive to the value of the condition.
14. The method of claim 12, wherein analyzing at least the identified instruction comprises:
16. The method of claim 1, wherein the thread switching instruction of the first thread includes an instruction to retrieve data associated with the second thread and previously stored.
17. The method of claim 9, wherein adding the thread switching instruction of the second thread comprises:
identifying a high latency floating point instruction of the second thread that may potentially cause a pipeline stall;
determining if a pipeline stall is likely from the identified high latency floating point instruction of the second thread; and
19. A non-volatile storage upon which is stored a program of machine readable program code executable by a processor, the program code having operations for:
20. A computer system having optimized multithread processing, comprising:
a processor associated with a computer system, the processor configured to execute program code including:
program code to identify an instruction of a first thread as a high latency floating point instruction;
program code to determine if a pipeline stall is likely from the identified high latency floating point instruction; and
program code to, in response to a determination that the pipeline stall is likely from the identified high latency floating point instruction, add at least one thread switching instruction to the first thread, wherein the thread switching instruction is adapted to switch from the execution of the first thread to a second thread. Description
CROSS-REFERENCES TO RELATED APPLICATIONS This application is a continuation application of U.S. patent application Ser. No. 11/700,448, filed Jan. 30, 2007 (to be issued on Aug. 18, 2009 as U.S. Pat. No. 7,577,826), which is an application claiming benefit under 35 USC 119(e)(1) of U.S. Provisional Patent Application No. 60/797,762, filed May 3, 2006, entitled �Stall Prediction Thread Management,� and U.S. Provisional Patent Application No. 60/763,568, filed Jan. 30, 2006, entitled �Branch Prediction Thread Management.� This application is also related to U.S. Provisional Patent Application No. 60/763,568, filed Jan. 30, 2006, entitled �Branch Prediction Thread Management;� U.S. Provisional Patent Application No. 60/797,435, filed May 3, 2006, entitled �DMA and Graphics Interface Emulation;� U.S. Provisional Patent Application No. 60/797,761, filed May 3, 2006, entitled �Code Translation and Pipeline Optimization;� U.S. Provisional Patent Application No. 60/746,267, filed May 3, 2006, entitled �Translation Block Invalidation Prehints in Emulation of a Target System on a Host System;� U.S. Provisional Application No. 60/746,268, filed May 3, 2006, entitled �Register Mapping in Emulation of a Target System on a Host System;� and U.S. Provisional Patent Application No. 60/746,273, filed May 3, 2006, entitled �Method and Apparatus for Resolving Clock Management Issue in Emulation Involving Both Interpreted and Translated Code,� all of which are incorporated by reference herein for all purposes.
BACKGROUND OF THE INVENTION The invention relates the field of computer science and specifically to the optimization of multithreaded applications for pipelined microprocessors. Microprocessors typically perform a number of different tasks to execute an instruction. Typically, the tasks for each microprocessor instruction must be performed in sequence. For example, a microprocessor must first read or fetch an instruction; interpret or decode the instruction; read or fetch the data needed to perform the instruction, if any; execute the instruction; and store the instruction results, if any.
BRIEF SUMMARY OF THE INVENTION An embodiment of the invention uses thread switching to prevent pipeline stalls when executing multiple threads. A first thread is analyzed to identify at least one instruction capable of causing a pipeline stall. For each identified instruction, a determination is made as to whether a pipeline stall is likely. If so, the first thread is modified to include thread switching instructions in place of the identified instructions. The thread switching instruction directs a microprocessor to suspend executing the thread and begin executing a second thread. Additional thread switching instructions can be added to the second thread to enable the resumption of the execution of the first thread at the appropriate location, as specified by the identified instruction. The thread switching instructions in the first and second threads can be configured to avoid pipeline stalls when switching between thread, for example by including prehint instructions. Thread switching instructions can be used to store and retrieve thread-specific information upon the suspension and resumption of threads. Thread switching instructions can also be used to schedule the execution of two or more threads in accordance with load balancing schemes. Threads can be modified with thread switching instruction using static or dynamic code analysis and modification techniques.
DETAILED DESCRIPTION OF THE INVENTION An embodiment of the invention uses thread switching behavior to prevent pipeline stalls. Many different types of instructions can cause pipeline stalls in a microprocessor. One common source of pipeline stalls is the use of conditional branch instructions. A conditional branch instruction specifies two or more alternate paths for the program execution flow in response to the result of a specified condition. One of the first pipeline stages fetches the next instruction to be executed by microprocessor. Because the location of the next instruction following a conditional branch instruction is often unknown until just before or as the conditional branch instruction itself is executed, earlier pipeline stages must wait idle until the conditional branch instruction is complete. As a result, the instruction pipeline stalls following the conditional branch instruction until the location of the next instruction is determined and the next instruction is fetched.
An embodiment of the invention switches threads of execution in place of high latency instructions, such as conditional branch instructions, potentially causing pipeline stalls. High latency instructions include instructions that require a large number of processor cycles to complete, such as some floating point operations in the x86 processor architectures. High latency instructions may include specific combinations of instructions are known to cause cache misses and pipeline stalls in a processor architecture. For example, storing a value to memory and then immediately reading it from memory can cause a pipeline stall in the PowerPC processor architecture. In a further embodiment, branch prediction prehints in a first thread are used to specify the thread entry point or other starting location in next thread of execution. Because this �prediction� is always correct, pipeline stalls are avoided.
To prevent pipeline stalls, an embodiment of the invention modifies threads A 205 and thread B 210. Thread A 205 is modified so that conditional branch instruction 215 is replaced with a thread switching instruction 215 a. Thread switching instruction 215 a directs the microprocessor to begin executing thread B 210 beginning at thread entry point 235. To prevent a pipeline stall from occurring when changing threads, a prehint instruction 240 is also added to thread A 205 before the branch lead time 225. Because the destination of the thread switching instruction 215 a is known in advance, the �prediction� of the added prehint instruction 240 will always be correct. Therefore, a pipeline stall will never occur when switching from thread A 205 to thread B 210 in this manner.
In an embodiment, the thread switching instruction 215 a can be a specific microprocessor adapted to change threads of execution. In another embodiment, the thread switching instruction 215 a can be a general-purpose branch instruction set to the thread entry point 235.
In this example 400, the thread switching instructions 425 a direct the processor to resume execution of thread A 405. In an embodiment, thread switching instructions 425 a direct the processor to resume execution of thread A 405 at the location previously specified by thread switching instructions 410 a. For example, an embodiment configures thread switching instructions 425 a to direct the processor to jump to the location specified by the register previously used by thread switching instructions 410 a to store the branch target of conditional branch instruction 410. Similarly, an embodiment configures prehint instruction 455 to access this register to determine the jump location in advance, thereby avoiding a pipeline stall from thread switching instructions 425 a. Additionally, because thread switching instructions 425 a also replace conditional branch instruction 425, an embodiment of thread switching instructions 425 a also ensure that thread B 415 is resumed at the correct location, similar to thread switching instructions 410 a. In this example, the execution of threads A 405 and B 415 operates as follows. The microprocessor initially executes thread A 405 up to the thread switching instructions 410 a. In response to the thread switching instructions 410 a, the microprocessor stops executing thread A 405 and begins to execute thread B 415 starting at thread entry point 420. Additionally, thread switching instructions 410 a store the location to resume thread A 405, either location 412 or 414, in a first register in accordance with the value of condition A set in instruction 407. To prevent a pipeline stall from thread switching instructions 410 a, prehint instruction 450 specifies the location to begin executing thread B 415 in advance. In an embodiment, prehint instruction 450 determines this location from data stored in a second register, which is initialized to the location of thread entry point 220.
The microprocessor executes thread B 415 up to thread switching instructions 425 a. Thread switching instructions 425 a direct the microprocessor to resume execution of thread A 405 at the location previously stored in the first register by thread switching instructions 410 a. Additionally, thread switching instructions 425 a store the location to resume thread B 415, either location 445 or 470, in the second register in accordance with the value of condition B set in instruction 422. To prevent a pipeline stall from thread switching instructions 425 a, prehint instruction 455 specifies the location to resume executing thread A 405 in advance. In an embodiment, prehint instruction 455 determines this location from data previously stored in the first register by thread switching instructions 410 a. Thus, following the initial iteration of thread B 415 up to thread switching instructions 425 a, the processor resumes execution of thread A 405 at either location 412 or 414, as determined previously by thread switching instructions 410 a. If thread A 405 resumes execution at location 414, the thread will be executed until it reaches thread switching instructions 410 a again. Once again, thread switching instructions 410 a will determine the appropriate location to resume thread A 405 and then direct the processor to resume execution of thread B 415 at the location previously specified by thread switching instructions 425 a. If thread A 405 resumes execution at location 412, additional prehint and thread switching instructions, similar to instructions 450 and 410 a, are added at the end or any other location, such as another conditional branch instruction, of thread A 405 to direct the processor to resume execution of thread B 415 at the location previously specified by thread switching instructions 425 a. These additional instructions and their counterparts in thread B 415 have been omitted for clarity from example 400.
Additionally, embodiments of the invention can be utilized to improve the performance of multithreaded emulation and virtual machine applications. For example, embodiments of the invention can be used to emulate video game consoles such as the Playstation, Playstation 2, and PSP systems; x86-based computer and video game systems; PowerPC-based computer and video game systems; Java, .NET, and other virtual machine and runtime environments.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6016542Dec 31, 1997Jan 18, 2000Intel CorporationDetecting long latency pipeline stalls for thread switchingUS6272520 *Dec 31, 1997Aug 7, 2001Intel CorporationMethod for detecting thread switch eventsUS7181601 *Dec 8, 2003Feb 20, 2007Intel CorporationMethod and apparatus for prediction for fork and join instructions in speculative executionUS7213134 *Mar 6, 2002May 1, 2007Hewlett-Packard Development Company, L.P.Using thread urgency in determining switch events in a temporal multithreaded processor unitUS7281250 *Apr 29, 2002Oct 9, 2007Nec CorporationMulti-thread execution method and parallel processor systemUS7458065 *Sep 21, 2004Nov 25, 2008Intel CorporationSelection of spawning pairs for a speculative multithreaded processorUS7664936 *Feb 4, 2005Feb 16, 2010Mips Technologies, Inc.Prioritizing thread selection partly based on stall likelihood providing status information of instruction operand register usage at pipeline stagesUS20050149697Mar 2, 2005Jul 7, 2005Enright Natalie D.Mechanism to exploit synchronization overhead to improve multithreaded performance* Cited by examinerNon-Patent CitationsReference1Eichenberger, A.E. et al., "Optimizing Compiler for a CELL Processor," 2005, IEEE, 12 pages.2Mcnairy, C. et al., "Montecito: A Dual-Core, Dual Thread Itanium Processor," 2005, IEEE, pp. 10-20.Classifications U.S. Classification712/220, 712/219International ClassificationG06F9/48Cooperative ClassificationG06F8/4441European ClassificationG06F8/4441Legal EventsDateCodeEventDescriptionDec 27, 2011ASAssignmentOwner name: SONY COMPUTER ENTERTAINMENT INC., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SONY NETWORK ENTERTAINMENT PLATFORM INC.;REEL/FRAME:027449/0380Effective date: 20100401Dec 26, 2011ASAssignmentFree format text: CHANGE OF NAME;ASSIGNOR:SONY COMPUTER ENTERTAINMENT INC.;REEL/FRAME:027445/0773Effective date: 20100401Owner name: SONY NETWORK ENTERTAINMENT PLATFORM INC., JAPANDec 28, 2009ASAssignmentOwner name: SONY COMPUTER ENTERTAINMENT INC.,JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SUBA, VICTOR;US-ASSIGNMENT DATABASE UPDATED:20100413;REEL/FRAME:23707/114Effective date: 20070216Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SUBA, VICTOR;REEL/FRAME:023707/0114Owner name: SONY COMPUTER ENTERTAINMENT INC., JAPANRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google