Ex Parte Golla et al

Board of Patent Appeals and Interferences

Jun 30, 2010

10881217 (B.P.A.I. Jun. 30, 2010)

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