Ex Parte Golla et alDownload PDFBoard of Patent Appeals and InterferencesJun 30, 201010881217 (B.P.A.I. Jun. 30, 2010) Copy Citation UNITED STATES PATENT AND TRADEMARK OFFICE ____________ BEFORE THE BOARD OF PATENT APPEALS AND INTERFERENCES ____________ Ex parte ROBERT T. GOLLA, PAUL J. JORDAN, and JAMA I. BARREH ____________ Appeal 2009-001886 Application 10/881,2171 Technology Center 2100 ____________ Decided: June 30, 2010 ____________ Before LEE E. BARRETT, LANCE LEONARD BARRY, and HOWARD B. BLANKENSHIP, Administrative Patent Judges. BARRETT, Administrative Patent Judge. DECISION ON APPEAL This is a decision on appeal under 35 U.S.C. § 134(a) from the final rejection of claims 1-27. We have jurisdiction pursuant to 35 U.S.C. § 6(b). We reverse. 1 Filed June 30, 2004, titled "Delay Slot Handling in a Processor." The real party in interest is Sun Microsystems, Inc. Appeal 2009-001886 Application 10/881,217 2 STATEMENT OF THE CASE The invention The invention relates handling of delay slots following control transfer instructions in processors. Spec. ¶ 0001. Some processor instruction set architectures (ISAs) define delayed control transfer instructions (DCTIs). A control transfer instruction may transfer program execution flow (either conditionally or unconditionally) to a target address. A DCTI transfers execution after the next instruction in the program flow (subsequent to the DCTI). The subsequent instruction is said to be in the delay slot of the DCTI, and is referred to as the "delay slot instruction." The delay slot instruction may be the next sequential instruction (stored adjacent to the DCTI in memory). DCTIs and their delay slot instructions complicate processor design. For example, if a DCTI is taken (that is, it transfers program execution flow to the target address) and instructions from the not-taken (usually sequential) execution path have been fetched, the instructions need to be flushed from the processor and the instructions from the taken execution path need to be fetched. However, the delay slot instruction may not be flushed. Thus, the delay slot instruction must be located and preserved when a taken DCTI is executed. The delay slot instruction may generally be in many places (e.g. the fetch may not have been started yet, the fetch may be in progress and the delay slot instruction may be in the process of being returned from memory, the delay slot instruction may be on the way out of the instruction cache, or Appeal 2009-001886 Application 10/881,217 3 may be elsewhere in the pipeline of the processor). Accordingly, locating the delay slot instruction may generally be complex. Spec. ¶ 0003. The invention inhibits selection of the DCTI until the delay slot instruction is available, simplifying the process of locating the delay slot instruction. Spec. ¶ 0021. Instructions are stored in an instruction buffer 302A-302H in Figure 4, where "Ins." indicates the instruction. Spec. ¶ 0065. The instructions are selected for execution by pick circuits 304A-304B in instruction pick unit 206. Spec. ¶ 0068. If an instruction of the instruction buffer 302A-302D is a DCTI, the pick circuit may inhibit scheduling the DCTI if the delay slot instruction is absent from the instruction buffer. Spec. ¶ 0070. Illustrative claim Claim 1 is reproduced below for illustration:2 1. A processor comprising: an instruction buffer configured to store instructions from a thread being executed by the processor; and a circuit coupled to the instruction buffer, wherein the circuit is configured to select instructions from the instruction buffer to issue for execution, and wherein the circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI. 2 It appears that "delay slot" on the last line should be "delay slot instruction." Appeal 2009-001886 Application 10/881,217 4 The references Ando US 5,809,294 Sep. 15, 1998 Seshan US 6,055,628 Apr. 25, 2000 Burns US 6,651,158 B2 Nov. 18, 2003 Irie US 6,772,325 B1 Aug. 3, 2004 (filed Oct. 1, 1999) The rejections Claims 1, 2, 7-9, 14-16, 20-25, and 27 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Burns and Irie. Claims 5 and 12 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Burns and Irie, further in view of Ando. Claims 6, 13, 19, and 26 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Burns and Irie, further in view of Seshan. The rejection of claims 3, 4, 10, 11, 17, and 18 under § 103(a) has been withdrawn (Ans. 3). DISCUSSION Claims 1, 2, 7-9, 14-16, 20-25, and 27 Issue Does Irie teach or suggest "wherein the circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI," as recited in independent claim 1? Independent claims 8, 15, 21, and 24 contain corresponding limitations. The dependent claims in the first ground of rejection are not Appeal 2009-001886 Application 10/881,217 5 separately argued. Accordingly, the rejection of claims 1, 2, 7-9, 14-16, 20-25, and 27 stands or falls with representative claim 1. Principles of law "[T]he test [for obviousness] is what the combined teachings of the references would have suggested to those of ordinary skill in the art." In re Keller, 642 F.2d 413, 425 (CCPA 1981). All claim limitations must be taught or suggested. 35 U.S.C. § 103(a). Findings of fact Irie The Examiner relies on the following portion of Irie, especially the underlined sentence: To support mode B delayed branch instructions, the fall- through instruction in Mode A is executed unconditionally. For branches that are actually taken, BRCTL 150 holds on to the branch target address until FECTL 101 can accept it for initiating a new instruction fetch. This is because a mode B delay-slot instruction may be on a different cache line in IC 105, so it is not necessarily loaded in the correct time, location in IB 110. Normally, BRCTL 150 determines the branch direction, and then re-directs the fetch path without waiting. In the case of a delayed branch, however, if the delay slot instruction has missed the cache access, direction of the program flow cannot be changed until it has been fetched. Col. 31, ll. 23-34 (emphasis added). We interpret the "delayed branch instruction" in the quotation to correspond to the claimed "delayed control transfer instruction (DCTI)." Appeal 2009-001886 Application 10/881,217 6 The above section of Irie is part of a section headed "Additional Operation Modes for Different Instruction Sets" (col. 30, l. 13). This section describes that the computing system may support two separate instruction sets, Set A and Set B, so that the processor operates in two separate modes of operation, Mode A and Mode B. Col. 30, ll. 14-19. The computing system is optimized to execute Mode A instructions, which are 32-bit instructions, but it is also capable of supporting instruction Set B, which consists of 16-bit instructions. "To execute the Set B instructions, it is preferable to emulate them using the other Set A instructions, so that hardware and programming complexity are reduced." Col. 30, ll. 34-37. Burns The teachings of Burns are not in contention. Analysis Initially, we interpret "selection of a[n] . . . instruction . . . from the instruction buffer" in the limitation at issue to mean "selection of an instruction from an instruction buffer to schedule for execution." Spec. ¶ 0040 ("Pick unit 206 . . . may be configured to attempt to select one instruction to schedule for execution . . . ."). Therefore, we interpret "to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer" to mean inhibiting a DCTI from being scheduled for execution. Spec. ¶ 0080 ("the pick circuit 304A may inhibit scheduling a DCTI instruction in a thread using a combination of the wait state for the Appeal 2009-001886 Application 10/881,217 7 thread's state machine and cancelling pick, in this embodiment."); Figure 10 and Spec. ¶¶ 0092-0094. As to claim 1, the Examiner finds that Burns teaches "an instruction buffer configured to store instructions from a thread being executed by the processor" and "a circuit coupled to the instruction buffer, wherein the circuit is configured to select instructions from the instruction buffer to issue for execution," but does not teach "wherein the circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI." Final Office Action (FOA) 3. The Examiner finds: However, Irie disclosed wherein the circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI (Irie: Column 31 lines 23-35)(When the delay slot instruction misses the instruction cache and must be retrieved from external caches or main memory, the branch instruction isn't allowed to change the program flow until the delay slot instruction has been fetched. One of ordinary skill in the art at the time of the invention would realize that one way to implement preventing the program flow from changing would be to prevent the delayed branch instruction from issuing until the delay slot instruction is fetched.). The advantage of using delayed branches is that useful instructions can be inserted into the delay slot(s) that comprises the normal delayed latency it takes for a branch to execute, where the useful instructions are executed regardless of the branch direction taken. This will lead to increased performance by minimizing the penalty of branch instruction delays on changing the control flow of the program. One of ordinary skill in the art would have been motivated by this advantage to implement delayed branch instructions. Thus, it would have been obvious to one of ordinary Appeal 2009-001886 Application 10/881,217 8 skill in the art at the time of the invention to implement delayed branches for the processor of Burns for the advantage of reducing the delay penalty of branch instructions. FOA 3-4 (emphasis added). Appellants argue that obviousness cannot be proved by the mere assertion that a claim feature would be obvious: "Specifically, one of skill in the art would not be apprised of all the possible ways to accomplish a given result (preventing the change in program flow) merely by being taught that such a result is desired." Br. 5. The Examiner asserts that there are a finite number of solutions to the problem of not changing program flow. Ans. 15. Appellants reply that the prior art does not show that there are a finite number of solutions and that the enumerated examples are not complete. It is argued that "[t]here are numerous solutions, both known and unknown, and one of ordinary skill in the art would not be apprised of all solutions merely by presentation with the problem." Reply Br. 2. The Examiner implicitly admits that Irie does not expressly teach a circuit to "inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI" as recited in claim 1, but concludes that such action would have been obvious, i.e., "[o]ne of ordinary skill in the art at the time of the invention would realize that one way to implement preventing the program flow from changing would be to prevent the delayed branch instruction from issuing until the delay slot instruction is fetched" (FOA 3; Ans. 4). We agree with Appeal 2009-001886 Application 10/881,217 9 Appellants that such statement is conclusory. In addition, we agree with Appellants that the Examiner has not established that the claimed solution is one of a limited number of solutions which would have been obvious or that the Examiner's limited number of solutions is complete. Indeed, the Examiner has not established that the problem addressed by Appellants, that "DCTIs and their delay slot instructions complicate processor design" (Spec. 1, l. 21) because "the delay slot instruction must be located and preserved when a taken DCTI is executed" (Spec. 1, ll. 26-27) and "locating the delay slot instruction may generally be complex" (Spec. 2, ll. 2-3), was known, so as to suggest the solution of inhibiting selection of the DCTI when the delay slot instruction is absent. Moreover, even if there was a limited number of solutions, this is a complicated art and there would be no way for a reviewing court to review such a factual finding. For these reasons, the Examiner's conclusion of obviousness is not persuasive. Appellants argue that Irie teaches a different mechanism for preventing the program flow from changing wherein the branch instruction is actually executed but the program flow is not re-directed until the delay slot instruction has been fetched. Br. 5. The Examiner finds that Irie describes processing delayed branches in Mode B and column 31, lines 31-34 of Irie discloses that the program flow can't be changed until the delayed branch instruction has been fetched. The Examiner finds that the branch control BRCTL 150 in Figure 1 changes the Appeal 2009-001886 Application 10/881,217 10 program flow with either a branch prediction or determines if a branch is possible (referring to col. 12, ll. 18-39): This results in the program flow being changed in the very next cycle, being the decode stage. Thus, it's obvious to one of ordinary skill in the art at the time of the invention that in order to prevent the program flow from being changed, the delayed branch would be stalled until the delay slot instruction is fetched to that the program flow isn't allowed to be changed. FOA 16 in "Response to Arguments." Irie teaches that the program flow is not changed until the delay slot instruction has been fetched, but this does not say that the delayed branch instruction is inhibited from selection for execution until the delay slot instruction has been fetched. We agree with Appellants that Irie teaches that the delayed branch instruction is actually executed and the branch target address for branches actually taken is stored in BRCTL 150. For a delayed branch instruction (a DCTI), the program flow cannot be changed to go to this branch address until the delay slot instruction has been fetched. Irie teaches that the delay slot instruction must be fetched before the instruction at the branch address is fetched, not that the delayed branch instruction is inhibited until the delay slot instruction is fetched. Thus, Irie does not teach or suggest "to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI" as claimed. The Examiner's reasoning that "the delayed branch would be stalled until the delay slot instruction is fetched" does not address the specific claim language "to inhibit selection of a delayed control Appeal 2009-001886 Application 10/881,217 11 transfer instruction (DCTI)" because stalling the fetching of instructions at the branch target address after the delayed branch instruction has been executed to produce a branch target address is not the same as inhibiting the delayed branch instruction from execution in the first place. Appellants argue that "Irie includes no teaching that mode B instructions are directly executed." Br. 6. It is also argued that "Irie teaches that branch prediction is not performed for mode B branches" (id.) and Irie "describes how branches that are actually taken, and thus already executed, are handled" (id.), so Irie does not teach a "circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI)." We agree with Appellants that Irie does not teach a "circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI)" for the reasons discussed above and accordingly, are persuaded of error in the rejection. Conclusion Irie does not teach or suggest "wherein the circuit is configured to inhibit selection of a delayed control transfer instruction (DCTI) from the instruction buffer in response to an absence of a delay slot of the DCTI," as recited in representative independent claim 1. Accordingly, the rejection of claims 1, 2, 7-9, 14-16, 20-25, and 27 is reversed. Claims 5 and 12 The Examiner does not rely on Ando to cure the deficiencies of Burns and Irie. Therefore, the rejection of dependent claims 5 and 12 is reversed. Appeal 2009-001886 Application 10/881,217 12 Claims 6, 13, 19, and 26 The Examiner does not rely on Seshan to cure the deficiencies of Burns and Irie. Therefore, the rejection of dependent claims 6, 13, 19, and 26 is reversed. CONCLUSION The rejections of claims 1-27 under 35 U.S.C. § 103(a) are reversed. REVERSED rwk MHKKG/Oracle (Sun) P.O. BOX 398 AUSTIN, TX 78767 Copy with citationCopy as parenthetical citation