Ex Parte Bélanger et al

Patent Trial and Appeal Board

Jun 15, 2016

12875753 (P.T.A.B. Jun. 15, 2016)

UNITED STA TES p A TENT AND TRADEMARK OFFICE
APPLICATION NO. FILING DATE
12/875,753 09/03/2010
43168 7590 06/17/2016
LAW OFFICE OF MARCIAL. DOUBET, P. L.
PO BOX 1087
Lake Placid, FL 33862
FIRST NAMED INVENTOR
David P. Belanger
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
ATTORNEY DOCKET NO. CONFIRMATION NO.
CA920100024US1 9869
EXAMINER
MITCHELL, JASON D
ART UNIT PAPER NUMBER
2199
NOTIFICATION DATE DELIVERY MODE
06/17/2016 ELECTRONIC
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.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address( es):
mld@mindspring.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Exparte DAVID P. BELANGER,
CHRISTOPHER A. LAPKOWSKI, and
CHWAN-HANGLEE
Appeal2014-009763
Application 12/875,753
Technology Center 2100
Before MAHSHID D. SAADAT, JOHNNY A. KUMAR, and
JON M. JURGOV AN, Administrative Patent Judges.
SAADAT, Administrative Patent Judge.
DECISION ON APPEAL
Appellants 1 appeal under 35 U.S.C. § 134(a) from the Final Rejection
of claims 1-20, which are all the claims pending in this application. We
have jurisdiction under 35 U.S.C. § 6(b ).
We affirm.
1 According to Appellants, the real party in interest is International Business
Machines Corp. (App. Br. 4).
Appeal2014-009763
Application 12/875,753
STATEMENT OF THE CASE
Introduction
Appellants' invention relates to register allocation during compilation
of computer program code (Spec. if 1 ). Exemplary claim 1 under appeal
reads as follows:
1. A computer-implemented method of allocating registers
in a computing system during compilation, comprising:
determining a count of hardware registers available for
allocating during the compilation;
doubling the determined count of hardware registers to
reflect independent usage of halves of the hardware registers;
and
invoking a register coloring algorithm using the doubled
count of hardware registers as a number of registers to be
allocated.
The Examiner's Rejections
Claims 1-3, 6-9, 11-13, and 16-18 stand rejected under 35 U.S.C.
§ 103(a) as unpatentable over Chaitin (Gregory J. Chaitin et al., Register
Allocation Via Coloring, Computer Languages, Vol. 6, pp. 47-57 (1981))
and Li (Bengu Li, et al., Speculative Subword Register Allocation in
Embedded Processors, Lecture Notes in Computer Science, Vol. 3602/2005,
pp. 56-71 (2005)) (see Ans. 2-7).
Claims 4, 5, 19, and 20 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Chaitin, Li, and Greiner (US 2009/0182992 Al; July 16,
2009) (see Ans. 7-9).
2
Appeal2014-009763
Application 12/875,753
Claim 10 stands rejected under 35 U.S.C. § 103(a) as unpatentable
over Chaitin, Li, and Applicants' Admitted Prior Art (AAP A; Spec. i-f 26)
(see Ans. 9-10).
ANALYSIS
We have reviewed the Examiner's rejections in light of Appellants'
contentions that the Examiner erred. We disagree with Appellants'
conclusions.
Independent Claims 1, 12, and 16
First Issue - Doubling Determined Count of Hardware
Registers
Appellants contend Li's disclosure of simultaneous assignment of two
variables to the same register does not teach "doubling the determined count
of hardware registers" that are available for allocating during compilation
(App. Rr. 12). Appellants argue Li does not mention doubling the number
of registers available for allocation, and instead implements a known register
coloring algorithm using the actual number of physical registers, then later
assigns additional variables to a subset of the already-assigned registers
using speculative allocation (App. Br. 12, 18-23).
We are not persuaded of Examiner error. The Examiner finds, and we
agree, that Li teaches 16 user visible 32-bit registers, wherein each available
register can be assigned a whole word (i.e., Ri-32) or two half words (i.e., Ri-
16 and R17-32), at least for the case where variable size is 16 bits or fewer
(Ans. 3-5, 7, 11-12; citing Lip. 1, Section 1; p. 3, Section 2; and p. 5,
Section 3 .1 ). Therefore, Li teaches determining the count of available
hardware registers (i.e., 16 user visible 32-bit registers) and doubling the
3
Appeal2014-009763
Application 12/875,753
determined count of registers to reflect independent usage of halves of the
registers (see Li, p. 5, Section 3.1, "When the bit Bis set, the two halves of
the register store two 16-bit values.").
Second Issue - Invoking Register Coloring Algorithm using
Doubled Count of Hardware Registers
Appellants contend Li does not teach "invoking a register coloring
algorithm using the doubled count of hardware registers" because Li
performs a first pass of register allocation using a known register coloring
algorithm with the actual count of physical registers, and then performs a
speculative allocation algorithm that relies on a run-time decision as to
whether a second variable can be stored in the same register with a first
variable (App. Br. 12-17). Appellants argue that, because register coloring
has finished executing during the first pass and all "registers available for
allocating" have been allocated, it would not make sense to then invoke a
register coloring algorithm using a doubled count of the registers (id.).
Appellants contend the Examiner ignores the speculative allocation
technique of Li and conducts impermissible hindsight analysis by picking
and choosing fragments of the reference to reject the claims (Reply Br. 2---6).
Appellants' contentions have not persuaded us of Examiner error in
rejecting the claims. The Examiner finds Li's concept of using two halves
of a register to double the register space is applicable to both speculative
allocation and standard allocation algorithms, and properly states that there
is no requirement for the secondary reference, Li, to be bodily incorporated
into the primary reference, Chaitin (Ans. 11-14). See In re Keller, 642 F.2d
413, 425 (CCP A 1981) (The test for obviousness is not whether the features
of a secondary reference may be bodily incorporated into the structure of the
4
Appeal2014-009763
Application 12/875,753
primary reference .... Rather, the test is what the combined teachings of the
references would have suggested to those of ordinary skill in the art"). Thus,
we agree with the Examiner's finding that the speculative allocation method
of Li need not be bodily incorporated into the register coloring algorithm of
Chaitin; rather, the combined teachings of Li and Chaitin would have
suggested to a skilled artisan to use the concept of independently assigning
halves of a register to a standard register coloring method, in order to double
the number of available register storage locations (Ans. 11-14).
Third Issue - Motivation to Combine Chaitin and Li
Appellants contend the Examiner has not provided a proper
motivation to combine the teachings of Chaitin and Li (App. Br. 23-25;
Reply Br. 6-9). We are not persuaded by Appellants' contention, and find
the Examiner's motivation of doubling the number of available register
storage locations (Ans. 12-14) provides an "articulated reasoning with some
rational underpinning to support the legal conclusion of obviousness." See
KSR Int'! Co. v. Teleflex Inc., 550 U.S. 398, 418 (quoting In re Kahn, 441
F.3d 977, 988 (Fed. Cir. 2006)).
Dependent Claim 3
Appellants contend that, because the combination of Chai tin and Li
does not teach "invoking a register coloring algorithm using the doubled
count of hardware registers," it follows that the combination does not teach
"independently allocating the halves of the hardware registers according to a
result of invoking the register coloring algorithm" (App. Br. 25-27; Reply
Br. 9). Appellants' contention does not persuade us of Examiner error,
because we agree with the Examiner's finding that the combination of
5
Appeal2014-009763
Application 12/875,753
Chaitin and Li teaches doubling the register count and invoking a register
coloring algorithm using the doubled count, as discussed supra regarding
independent claim 1.
Dependent Claim 6
Appellants contend the combination of Chaitin and Li does not teach
adding interferences for "high-word register halves when an operand of an
instruction is limited to allocation to a low-word register half (App. Br. 27-
30). Appellants reason that Chaitin's "special case consideration" for
interferences does not mention high-word or low-word register halves, and
Li's "four new instructions" that speculatively store a value in the upper half
of the register are not operands for which a compile-time graph coloring
algorithm is attempting to assign registers (App. Br. 28-30; Reply Br. 10).
Appellants' arguments do not persuade us of Examiner error. We agree with
the Examiner;s findings that because the claim has no specific requirement
regarding how, or when, the "operand is limited to allocation to a low-word
register half," Li's accessing of the lower half of a register by normal
instructions teaches an operand that is limited to allocation to a low-word
register half (Ans. 15-17; citing Lip. 5, Section 3.1). We note that
Appellants have not presented any arguments in the Reply Brief to rebut this
finding regarding Li (see Reply Br. 10).
CONCLUSION
As discussed herein, Appellants' arguments have not persuaded us
that the Examiner erred in finding Chaitin and Li teaches or suggests the
disputed limitations of claims 1, 3, 6, 12, and 16, as well as the remaining
6
Appeal2014-009763
Application 12/875,753
claims which are not argued separately (see App. Br. 30-31 ). Therefore, we
sustain the rejections of claims 1-20.
DECISION
We affirm the Examiner's decision to reject claims 1-20.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(l )(iv).
AFFIRMED
7