Ex Parte Browning et al

Board of Patent Appeals and Interferences

Mar 13, 2003

08497481 (B.P.A.I. Mar. 13, 2003)

The opinion in support of the decision being entered today was not written
for publication and is not binding precedent of the Board.
Paper No. 24
UNITED STATES PATENT AND TRADEMARK OFFICE
____________
BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________
Ex parte LUKE M. BROWNING
and JEFFREY S. PEEK
_________
Appeal No. 2001-0048
Application No. 08/497,481
________
ON BRIEF
____________
Before BARRETT, FLEMING, and SAADAT, Administrative Patent Judges.
SAADAT, Administrative Patent Judge.
DECISION ON APPEAL
This is a decision on appeal from the Examiner’s final
rejection of claims 1, 3, 6, 7, 9, 10, 12 and 13. Claims 2, 4,
5, 8 and 11 have been canceled.
We affirm-in-part.
BACKGROUND
Appellants’ invention is directed to a method and system for
optimizing thread processing in a multiprocessor data processing
system by establishing a priority order of threads executed
within the system. Threads are assigned to a local execution
Appeal No. 2001-0048
Application No. 08/497,481
2
queue and are executed in a particular order such that the
affinity threads that have a high degree of shared resource
utilization are assigned to the same local queue (specification,
page 1). The queue order is determined by selecting a most
favored runnable thread from among either a current thread, a
most favored thread, or an affinity thread (specification, page
4). Alternatively, the current thread is dispatched for
execution if it is runnable and has the same priority as the
highest priority thread (specification, page 12). Otherwise, the
system selects the affinity thread if it has the same priority as
the thread with the highest priority (id.).
Representative independent claims 1 and 3 are reproduced
below:
1. A method, within a multiprocessor data processing
system including a plurality of processors, and a single
execution queue of multiple threads from which threads are
dispatched for execution by any of said plurality of
processors in a priority order, for establishing said
priority order, said method comprising:
(a) determining whether a current executing thread may
still be run on a selected one of said plurality of
processors;
(b) in response to said current executing thread being
runnable, placing said current executing thread on said
single execution queue;
Appeal No. 2001-0048
Application No. 08/497,481
3
(c) in response to an availability of said selected one
of said plurality of processors selecting a thread having
the highest priority on said single execution queue;
(d) determining whether said current executing thread
has the same priority as said thread having highest priority
selected from said single execution queue;
(e) upon determining said current executing thread and
said highest priority thread are equal, running said current
executing thread;
(f) otherwise, if said highest priority thread is
greater in priority than said current executing thread,
determining whether a thread having affinity has the same
priority as said highest priority thread; and
(g) running said affinity thread if equal to said
thread having highest priority.
3. A method for establishing a priority order of threads
within a single execution queue of a multiprocessor data
processing system, comprising:
selecting for execution within a selected
processor a most favored runnable thread from either a
current thread executing within said selected processor
having the same priority as a most favored thread or an
affinity thread having the same priority as said most
favored thread.
The Examiner relies on the following references in rejecting
the claims:
Raj Vaswani et al. (Vaswani), “The Implications of Cache
Affinity on Processor Scheduling for Multiprogrammed, Shared
Memory Multiprocessors,” ACM, 1991, pp. 26-40.
Cochcroft, Jr. et al. (Cochcroft) 5,317,738 May. 31, 1994
Appeal No. 2001-0048
Application No. 08/497,481
1 A supplemental appeal brief was filed apparently in response to a
communication from the Examiner (paper No. 20, mailed August 30, 1999)
subsequent to filing the original appeal brief (Paper No. 19, filed June 14,
1999).
4
Claims 1, 3, 6, 7, 9, 10, 12 and 13 stand rejected under
35 U.S.C. § 103(a) as being unpatentable over Vaswani and
Cochcroft.
Rather than reiterate the viewpoints of the Examiner and
Appellants, we make reference to the answer (Paper No. 22, mailed
November 22, 1999) for the Examiner’s complete reasoning in
support of the rejection and the appeal brief1 (Paper No. 21,
filed September 13, 1999) for Appellants’ arguments thereagainst.
OPINION
At the outset, we note that Appellants state that claims 1,
7, 10 and 13 constitute one group while claims 3, 6, 8, 9 and 12
stand or fall together (brief, page 6). It is unclear why
Appellants have grouped independent claims 3, 9 and 12 separately
from their corresponding dependent claims 7, 10 and 13. Although
Appellants have provided a statement regarding the groupings of
the claims, Appellants provide no particular explanation in
support of grouping claims 7, 10 and 13 with claim 1 as required
by 37 C.F.R. § 1.192(c)(7) (1997), nor do we discern proper
justification from the language of the claims. We will, thereby,
Appeal No. 2001-0048
Application No. 08/497,481
5
consider claim 1 as one group and the remaining claims as another
group represented by independent claim 3.
With respect to the rejection of claim 1, Appellants
recognize that the current/last task of Vaswani is actually the
task with the greatest affinity with a particular processor
(brief, Page 7). Appellants further point out that Vaswani
executes the current/last task if it is runnable and has a
priority equal to the highest priority task but executes only the
highest priority task otherwise (id.). Referring to the
situation in which the current/last task is not runnable or has a
priority not equal to the highest priority task, Appellants
assert that claim 1 differs from the prior art since it requires
the additional step of determining whether an affinity task
having the same priority as the highest priority task is present
(brief, page 8).
In response to Appellants’ arguments, the Examiner asserts
that Vaswani’s last task is not necessarily the current task and
“is determined by checking the history; e.g. a process having
affinity for that processor is located” (answer, pages 4 & 5).
The Examiner also argues that it is this last task which is run
if “that task is runnable and has a priority as high as any
runnable process” (answer, page 5). The Examiner concludes that
Appeal No. 2001-0048
Application No. 08/497,481
6
the claimed step of determination of an affinity thread having
the same priority as the highest priority thread is the same as
Vaswani’s “identifying the last task from the processor’s history
and executing it if its priority is as high” (id.).
In rejecting claims under 35 U.S.C. § 103, the Examiner
bears the initial burden of presenting a prima facie case of
obviousness. See In re Rijckaert, 9 F.3d 1531, 1532, 28 USPQ2d
1955, 1956 (Fed. Cir. 1993). The conclusion that the claimed
subject matter is obvious must be supported by evidence, as shown
by some objective teaching in the prior art or by knowledge
generally available to one of ordinary skill in the art that
would have led that individual to combine the relevant teachings
of the references to arrive at the claimed invention. See In re
Fine, 837 F.2d 1071, 1074, 5 USPQ2d 1596, 1598 (Fed. Cir. 1988).
Furthermore, to reach a conclusion of obviousness under § 103,
the examiner must also produce factual basis supported by
teaching in a prior art reference or shown to be common knowledge
of unquestionable demonstration, consistent with the holding in
Graham v. John Deere Co., 383 U.S. 1 (1966). Our reviewing court
requires this evidence in order to establish a prima facie case.
In re Piasecki, 745 F.2d 1468, 1471-72, 223 USPQ 785, 787-88
Appeal No. 2001-0048
Application No. 08/497,481
7
(Fed. Cir. 1984); In re Cofer, 354 F.2d 664, 668, 148 USPQ 268,
271-72 (CCPA 1966).
Our review of Vaswani confirms that the reference relates to
a scheduling order of tasks to be executed on multiprocessor
systems by considering affinity of the task in order to improve
processing efficiency. Section A.1 on page 31 of the reference,
as relied on by the Examiner, and the two preceding paragraphs,
state in part:
Introducing affinity to Dynamic requires that the
allocator have access to processor and task histories ....
We incorporated processor affinity into Dynamic’s
allocation decisions as follows:
A.1 Whether a processor becomes available for reallocation,
the last task to have run on it is identified using the
processor’s history. If that task (last-task) is not
currently active on some other processor but is runnable
with useful work to perform, and if the priority of the job
to which last-task belongs is as high as that of any job
currently requesting processors, then last-task is activated
on the available processor. Otherwise, the processor is
allocated to the requesting job of highest priority.
Therefore, Vaswani selects the last task to be executed if it is
runnable and has a priority as high as the highest priority
running task, otherwise selects the highest priority task.
Whether the last task is interpreted as the current task, as
pointed out by Appellants, or as the affinity task, as asserted
by the Examiner, Vaswani executes the highest priority task only
Appeal No. 2001-0048
Application No. 08/497,481
8
if the last task is not runnable or does not have a priority
equal to the highest priority task. Vaswani does not separately
determine whether the priority of a current task and the priority
of an affinity task are equal to the highest priority before
allocating the processor to the highest priority task. We
disagree with the Examiner’s characterization of the last task as
both the claimed current task and the affinity task (final
rejection, pages 1& 2) since Vaswani determines the priority of
the last task only once before moving on to executing the task
with the highest priority. Therefore, the last task may be
characterized as either the current task or the affinity task,
not both, whereas claim 1 requires first, the selection of the
current task having a priority equal to the highest priority,
otherwise, the selection of the affinity task having the same
priority as the highest priority.
Cochcroft, on the other hand is relied on by the Examiner
for teaching the selection of processors from a single run queue
(final rejection, page 2). However, Cochcroft fails to overcome
the above deficiencies of Vaswani with respect to claim 1.
Assuming, arguendo, that it would have been obvious to utilize
the single run queue of Cochcroft in Vaswani’s processor
scheduling method, as held by the Examiner, the combination of
Appeal No. 2001-0048
Application No. 08/497,481
9
references would still not disclose the claimed sequence of
priority order from the current task to the affinity task.
Accordingly, since the Examiner has failed to establish a prima
facie case of obviousness, the 35 U.S.C. § 103 rejection of
independent claim 1 cannot be sustained.
Turning now to the rejection of claim 3, we note that
Appellants merely repeat the claim language and argue that
Vaswani is silent on the subject of selecting a most favored
thread (brief, page 9). The Examiner responds by questioning the
meaning of a “most favored thread” in claim 3 and pointing to the
alternative format of the claim which, as one of the
alternatives, recites “selecting an affinity thread having the
same priority as the most favored thread” (answer, page 5). The
Examiner further characterizes the high priority threads and
affinity threads of Vaswani as the most favored threads which may
be selected as “a most favored thread (the thread which is
finally selected) among favored threads (from high priority
threads and threads having affinity for the particular
processor)” (id.).
Before addressing the claim rejection based on prior art, as
pointed out by our reviewing court, we must first determine the
scope of the claim. “[T]he name of the game is the claim.” In
Appeal No. 2001-0048
Application No. 08/497,481
10
re Hiniker Co., 150 F.3d 1362, 1369, 47 USPQ2d 1523, 1529 (Fed.
Cir. 1998). The terms used in the claims bear a “heavy
presumption” that they mean what they say and have the ordinary
meaning that would be attributed to those words by persons
skilled in the relevant art. Texas Digital Systems, Inc. v.
Telegenix, Inc., 308 F.3d 1193, 1201-1202, 64 USPQ2d 1812, 1817
(Fed. Cir. 2002). Furthermore, claims will be given their
broadest reasonable interpretation consistent with the
specification, and limitation appearing in the specification are
not to be read into the claims. In re Etter, 756 F.2d 852, 858,
225 USPQ 1, 5 (Fed. Cir. 1985). Additionally, for proper claim
interpretation, the starting point must be the words of the claim
which will be given their ordinary and accustomed meaning, unless
it appears that the inventor used them differently. Envirotech
Corp. v. Al George, Inc., 730 F.2d 753, 759, 221 USPQ 473, 477
(Fed. Cir. 1984).
A review of claim 3 reveals that the recited step of
selecting “a most favored runnable thread” requires selection
from “either a current thread” or “an affinity thread.” The
current thread and the affinity thread must further have the same
priority as a most favored thread. We find that Appellants’
specification merely mentions the claimed “most favored thread”
Appeal No. 2001-0048
Application No. 08/497,481
11
(specification, page 4, lines 14-27 and page 11, lines 19-26),
but does not specifically describe how a thread becomes the most
favored thread. Here, absent detailed disclosure to the contrary
of what Appellants mean by the “most favored thread,” the
Examiner’s interpretation of the term as the thread that is
favored over another as it has for example, the highest priority
or an affinity, is reasonable (answer, page 5). Therefore, the
Examiner has properly corresponded Vaswani’s thread, which is
finally selected, to the claimed most favored thread which is
selected as an affinity thread that has high priority. In
response, Appellants have not pointed out any error in the
Examiner’s position and instead, have merely repeated the claim
language and asserted that the prior art does not teach selecting
a most favored thread (brief, page 9). Accordingly, we sustain
the 35 U.S.C. § 103 rejection of independent claims 3, 9 and 12,
as well as claims 6, 7, 10 and 13 dependent thereupon, over
Vaswani and Cochcroft.

Appeal No. 2001-0048
Application No. 08/497,481
12
CONCLUSION
In view of the foregoing, the decision of the Examiner
rejecting claim 1 under 35 U.S.C. § 103 is reversed but sustained
with respect to the rejection of claims 3, 6, 7, 9, 10, 12 and
13.
No time period for taking any subsequent action in
connection with this appeal may be extended under 37 CFR
§ 1.136(a).
AFFIRMED-IN-PART
LEE E. BARRETT )
Administrative Patent Judge )
)
)
)
) BOARD OF PATENT
MICHAEL R. FLEMING ) APPEALS
Administrative Patent Judge ) AND
) INTERFERENCES
)
)
)
MAHSHID D. SAADAT )
Administrative Patent Judge )
MDS/dal
Appeal No. 2001-0048
Application No. 08/497,481
13
Bracewell & Patterson, LLP
Intellectual Property Law
P.O. Box 969
Austin, TX 78767