Ex Parte Thompson

Board of Patent Appeals and Interferences

Jul 19, 2011

10175267 (B.P.A.I. Jul. 19, 2011)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
10/175,267 06/18/2002 Carol L. Thompson 10015595-1 9340
7590 07/20/2011
HEWLETT-PACKARD COMPANY
Intellectual Property Administration
P.O. Box 272400
Fort Collins, CO 80527-2400
EXAMINER
KISS, ERIC B
ART UNIT PAPER NUMBER
3992
MAIL DATE DELIVERY MODE
07/20/2011 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________________

Ex parte CAROL L. THOMPSON
____________________

Appeal 2009-008594
Application 10/175,267
Technology Center 2100
____________________

Before JOHN A. JEFFERY, THU A. DANG, and ANDREW J. DILLON,
Administrative Patent Judges.

DANG, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2009-008594
Application 10/175,267

2

I. STATEMENT OF THE CASE
Appellant appeals under 35 U.S.C. § 134(a) from a Final Rejection of
claims 1-6, 8-12, and 14-18. Claims 7 and 13 have been cancelled. We
have jurisdiction under 35 U.S.C. § 6(b).
We reverse.

A. INVENTION
According to the Appellant, the invention allows a large number of
possibilities of instruction ordering within an issue group, and avoids
imposing unnecessary ordering between instructions as they are selected for
scheduling, to achieve very high efficiency on a processor that can process
many instructions at once but have considerable dependency constraints and
no internal mechanism for dealing with these constraints, such as the
Itanium class of processors (Spec. 4, ll. 16-21).

B. ILLUSTRATIVE CLAIM
Claim 1 is exemplary:
1. A computer readable medium storing a compiler
computer program which, when run on a computer, performs a
method using a computer model for compiling a set of
instructions for a processor which can process at least two
instructions in a cycle, the method comprising:

a. selecting, from a set of instructions, a first
instruction and a second instruction to be issued to the
processor in an issue group;

b. generating dependency data reflecting
dependencies between the first and second instructions;
Appeal 2009-008594
Application 10/175,267

3

c. determining whether the dependency data, in any
possible order of the instructions, satisfies the model;

d. if the dependency data satisfies the model,
proceeding to step (e) and, if not, rejecting the second
instruction, selecting an alternate second instruction from the
set of instructions, and returning to step (c); and

e. reordering the instructions in the issue group to an
order that satisfies the model, wherein the relative order of
instructions in the issue group to be executed within a cycle of
the processor affects a function of the processor; and

f. only after all instructions for the issue group have
been selected and reordered, scheduling the instructions for
execution by the processor.

C. REJECTION
The prior art relied upon by the Examiner in rejecting the claims on
appeal is:

Reinders US 5,819,088 Oct. 06, 1998

Claims 1-6, 8-12, and 14-18 stand rejected under 35 U.S.C. § 102(b)
as being anticipated by Reinders.

II. ISSUE
The dispositive issue is whether the Examiner has erred in
determining that Reinders teaches “selecting, from a set of instructions, a
first instruction and a second instruction,” “generating dependency data
reflecting dependencies between the first and second instructions,”
“determining whether the dependency data … satisfies the model” and “if
Appeal 2009-008594
Application 10/175,267

4
the dependency data satisfies the model, proceeding to step (e) and, if not,
rejecting the second instruction, selecting an alternate second instruction
from the set of instructions, and returning to step (c)” (claim 1, emphasis
added). In particular, the issue turns on whether Reinder’s rescheduling
method comprises determining whether dependency data reflecting
dependencies between first and second instructions satisfies a model and
selecting an alternate second instruction from the set of instructions (from
which the second instruction is selected) if not, as required by claim 1.

III. FINDINGS OF FACT
The following Findings of Fact (FF) are shown by a preponderance of
the evidence.
Reinders
1. Reinders discloses a scheduler that determines whether a basic
block can be scheduled with a schedule of a particular size (col. 2, ll. 44-48).
2. A scheduler repeatedly attempts to schedule the program loop
for various schedule sizes, starting with the smallest schedule (maximum
compaction) and systematically increasing the schedule size towards the
largest schedule (zero compaction) until either an attempt is successful or the
largest schedule is reached (col. 2, ll. 66 to col. 3, l. 6).
3. Upon setting the schedule size, the scheduler attempts to
schedule a program loop with a schedule of the set size; wherein, if the
scheduler is successful, an optimal schedule is found for the program loop,
but if the scheduler is unsuccessful, the schedule size is incremented by one
and another attempt is made to schedule a program loop with the
incremented size (col. 7, ll. 8-19; Fig. 6a).
Appeal 2009-008594
Application 10/175,267

5
4. The process continues until either the scheduler is successful in
scheduling the program loop with the set schedule size or the incremented
schedule size equals the uncompacted size of the basic block (col. 7, ll. 19-
22).

IV. ANALYSIS
The Examiner finds that Reinders teaches “generating dependency
data reflecting dependencies between the first and second instructions”
because “the resource utilization and tracking arrays store dependency data
which is updated as instructions are added” (Ans. 3). Further, the Examiner
finds that Reinders teaches “if the dependency data satisfies the model,
proceeding to step (e) and, if not, … selecting an alternate second instruction
from the set of instructions, and returning to step (c)” because Reinders
describes “an iterative approach of list scheduling (selecting and reordering
instructions) for successively larger schedules until a final scheduling (for
execution by the processor) is achieved” (id.). According to the Examiner,
“when the scheduling algorithm of Reinders fails to schedule the basic block
with a schedule size …, the scheduler tries again with an increased schedule
size” (Ans. 7), and therefore “when the initial scheduling of Reinders fails
…, new alternate instructions are selected as part of the next scheduling
attempt” (id.). Thus, according to the Examiner, Reinder teaches “selecting
alternate second/third instructions and again checking dependency data to
see if the data satisfies the model (determining if a successful schedule can
be created)” (id.).
However, Appellant contends that “[t]he complete rescheduling for a
new scheduling size, as taught by Reinders, is different from selecting an
Appeal 2009-008594
Application 10/175,267

6
alternate second instruction from the set of instructions” (App. Br. 7).
According to Appellant, “[i]n Reinders, the rescheduling is performed for a
new scheduling size in response to failure of scheduling” (id.). Therefore,
Appellant contends that “the rescheduling in response to failure of
scheduling, as performed in Reinders, is not in response to determining that
dependency data has been satisfied” (id.).
Upon review of the record, we agree with Appellant. In particular, we
do not find any teaching of “selecting, from a set of instructions, a first
instruction and a second instruction,” “generating dependency data reflecting
dependencies between the first and second instructions,” “determining
whether the dependency data … satisfies the model” and “if the dependency
data satisfies the model, proceeding to step (e) and, if not, rejecting the
second instruction, selecting an alternate second instruction from the set of
instructions, and returning to step (c),” in the portions of Reinders relied
upon by the Examiner. In particular, we do not find any teachings of
determining whether dependency data reflecting dependencies between first
and second instructions satisfies a model and selecting an alternate second
instruction from the set of instructions (from which the second instruction is
selected) if not, as required by claim 1.
Reinders discloses determining whether a basic block can be
scheduled with a schedule of a particular size (FF 1), wherein a scheduler
repeatedly attempts to schedule the program loop for various schedule sizes,
starting with the smallest schedule and systematically increasing the
schedule size towards the largest schedule (FF 2). In particular, upon setting
the schedule size, the scheduler attempts to schedule a program loop with a
schedule of the set size; wherein, if the scheduler is successful, an optimal
Appeal 2009-008594
Application 10/175,267

7
schedule is found for the program loop, but if the scheduler is unsuccessful,
the schedule size is incremented by one and another attempt is made to
schedule a program loop with the incremented size (FF 3-4).
We find the rescheduling as described in these portions cited by the
Examiner of Reinders to merely comprise determining whether or not the
scheduler can schedule a program loop with a schedule initially set at a small
size, and if not, reschedule with a schedule of an increased size, whereby the
size is increased until the scheduler is successful. That is, these portions of
Reinders do not disclose by any teaching of determining whether
dependency data reflecting dependencies between first and second
instructions satisfies a model or selecting an alternate second instruction
from the set of instructions (from which the second instruction is selected) if
not. In fact, we do not find any teachings of determining whether the
dependency data satisfies a model. That is, in Reinders, the determination is
made as to whether the scheduler is successful in scheduling with a certain
schedule size. Thus, we agree with Appellant’s contention that “the
rescheduling in response to failure of scheduling” and “not in response to
determining that dependency data has been satisfied” (App. Br. 7).
Furthermore, we agree with Appellant that “[t]he complete
rescheduling for a new scheduling size, as taught by Reinders, is different
from selecting an alternate second instruction from the set of instructions”
(App. Br. 7, emphasis omitted). In particular, the complete rescheduling for
a new scheduling size does not comprise rejecting the second instruction
(but not the first instruction), selecting an alternate second instruction from
the set of instructions, and returning to step (c) (where the dependency data
Appeal 2009-008594
Application 10/175,267

8
between the old first instruction and the new second instruction is
determined to satisfy a model), as required by claim 1.
Accordingly, we find that Appellant has shown that the Examiner
erred in rejecting representative claim 1 over Reinders. Independent claims
2, 8, and 14 recite similar features and thus stand with claim 1, as well as
claims 3-6, 9-12, and 15-18 depending respectively therefrom.

V. CONCLUSION AND DECISION
The Examiner’s rejection of claims 1-6, 8-12, and 14-18 under
35 U.S.C. § 102(b) is reversed.

REVERSED

peb