Ex Parte Huffman

Board of Patent Appeals and Interferences

Sep 24, 2007

09909704 (B.P.A.I. Sep. 24, 2007)

The opinion in support of the decision being entered today
is not binding precedent of the Board.

UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________

Ex parte WILLIAM A. HUFFMAN
____________

Appeal 2007-0662
Application 09/909,704
Technology Center 2100
____________

Decided: September 24, 2007
____________

Before ANITA PELLMAN GROSS, MAHSHID D. SAADAT,
and JEAN R. HOMERE, Administrative Patent Judges.

SAADAT, Administrative Patent Judge.

DECISION ON APPEAL
STATEMENT OF THE CASE
Appellant appeals under 35 U.S.C. § 134(a) from the Examiner’s
rejection of claims 1-15, which are all of the claims pending in this
application. We have jurisdiction under 35 U.S.C. § 6(b).
Appellant invented a system for managing distributed shared memory
by providing a memory arbitration scheme that includes an arbitration
queue. Entries are received from any point in the queue and higher order
Appeal 2007-0662
Application 09/909,704

2
entries ripple down to fill the voids in the queue created by previously
serviced entries (Specification 6).
Claim 1 is representative of the claims on appeal and reads as follows:
1. A method of managing an arbitration queue having a
plurality of queue entries comprising:

introducing entries into the queue at a first, highest order queue
location;

determining if lower order queue locations are available;

if lower order queue locations are available, moving all higher
order queue location contents to an adjacent lower order queue
location per cycle until all lower order locations are filled;

associating each entry after placement in the queue to one of a
plurality of groups, each of the plurality of groups having a different
transaction parameter criteria;

determining which particular one of the plurality of groups to
service based on the transaction parameter criteria;

servicing a particular entry in the particular one of the plurality
of groups based on servicing criteria; and

moving all higher order queue entries, with respect to the
particular entry being serviced, to an adjacent lower order location in
the queue.

The evidence relied upon by the Examiner in rejecting the claims on
appeal is:
Meyers US 5,375,223 Dec. 20, 1994
Garcia US 6,145,061 Nov. 7, 2000
Bauman US 6,160,812 Dec. 12, 2000
Trull US 6,185,672 B1 Feb. 6, 2001
Appeal 2007-0662
Application 09/909,704

3

In re Yount, 171 F.2d 317, 80 USPQ 141 (CCPA 1948).

The rejections as presented by the Examiner are as follows:
1. Claims 1-3 and 5-7 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Bauman and Trull.
2. Claim 4 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Bauman, Trull, and Garcia.
3. Claim 8 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Bauman, Trull, and in view of In re Yount.1
4. Claims 9-14 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Meyers, Bauman, and Trull.
5. Claim 15 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Meyers, Bauman, Trull, and in view of In re Yount.

ISSUES
(1) Under 35 U.S.C § 103(a), with respect to appealed claims 1-3 and
5-7, would one of ordinary skill in the art at the time of the
invention have found it obvious to combine Bauman and Trull to
render the claimed invention unpatentable?
(2) Under 35 U.S.C § 103(a), with respect to appealed claims 4 and 8-
15, would the ordinarily skilled artisan have found it obvious to
modify the combination of Bauman and Trull separately with

1 The Examiner probably meant to include In re Yount in order to support
the propriety of the combination of Bauman and Trull.
Appeal 2007-0662
Application 09/909,704

4
either Garcia, In re Yount, or Meyers to render the claimed
invention unpatentable?

FINDINGS OF FACT
The following findings of fact (FF) are relevant to the issues involved
in the appeal and are believed to be supported by a preponderance of the
evidence.
1. Bauman relates to a method and apparatus for supplying new
requests to a scheduler in an input-buffered multiport switch which involves
selecting a request that does not target a conflicting output channel targeted
by requests that are already accessible to the scheduler (Abstract).
2. Bauman fills the request buffers according to the packet priority
scheme implemented in the switch, such that if the scheme is based on time,
the oldest request has the highest priority (col. 8, ll. 15-21) while other
factors may also be used as the basis for the priority scheme such as the
source of data or the type of data (col. 8, ll. 33-36).
3. As depicted in Figure 17, Bauman provides for input-output
controllers 242, 244, 246, and 248 which supply the scheduler with new
requests formed in request queues 252, 254, 256, and 258 while queue
managers 262-268 and secondary schedulers 272-278 process the requests
from the queue (col. 16, ll. 17-36).
4. The request queues 252-258 depicted within each I/O controller
242-248 relate on a one-to-one basis to the ports 292, 294, 296, and 298 that
are connected to the I/O controller or may be queued in a single request
queue if only one port is available. The request queues are time-ordered
Appeal 2007-0662
Application 09/909,704

5
queues such that the oldest request is depicted at the bottom of the queue and
the youngest request is depicted at the top of the queue, although this is not
critical to the invention (col. 16, ll. 37-45).
5. Bauman further discloses that the secondary schedulers 272-
278 are the units that arbitrate which requests, from the group of requests
that are stored in the request queues 252-258, will be supplied to the primary
arbitration queue when a new request is needed for the primary scheduler
132 (col. 16, ll. 60-64).
6. Figure 18 of Bauman shows that a section of the time-ordered
request queue 252 are considered by the secondary scheduler 272 for
arbitration by the primary arbitrator 282 (col. 17, ll. 14-20).
7. As shown in Figure 19 of Bauman, the requests in the
secondary arbitration queue 302 are ordered from oldest to youngest, with
the oldest request being at the bottom of the queue and the youngest request
being at the top of the queue (col. 17, ll. 54-59).
8. In the example depicted in Figure 19, the secondary scheduler
272 first compares the oldest request in the secondary arbitration queue 302,
identifying output channel 0, to the primary arbitration queue 282. Since
there is a conflict at output channel 0, the oldest request is bypassed.
Similarly the next 2 youngest requests, identifying output channels 1 and 3,
are then compared to the primary arbitration queue and there is a conflict at
both output channels 1 and 3. The next youngest request, corresponding to
output channel 2, which does not conflict with any of the output channels
requested in the primary arbitration queue is supplied to the primary
Appeal 2007-0662
Application 09/909,704

6
scheduler as the new request that is the next oldest and does not identify a
conflicting output channel (col. 18, ll. 6-25).
9. Trull relates to a microprocessor having an instruction queue
capable of out-of-order instruction dispatch and compaction of unaligned
strings of empty storage locations. This compaction may be performed by
selectively shifting the instructions remaining in the queue either zero or N
storage locations, wherein N is a predetermined positive integer (Abstract).
10. Trull identifies the large size of the queue with slowing down
and negative effects on the performance of the device (col. 3, ll. 34-45),
specially where the microprocessor may be configured to read instructions
from an instruction cache, store them in a queue, and then read them from
the queue in an out-of-order fashion (col. 3, ll. 52-54). Reading the
instructions in this manner may create bubbles or gaps of empty storage
locations within the queue, which may be compacted out by shifting the
remaining instructions a fixed number of storage locations (col. 3, ll. 54-58).
11. Trull further teaches that new instructions are written into the
“top” or start of the queue, while the oldest eligible instructions are read
from different positions within the queue. As instructions are read out of the
queue, bubbles of empty storage locations form in the queue. To reduce or
eliminate these bubbles, the remaining instructions in the queue are shifted
down the queue, thereby making room for new instructions at the top of the
queue. When instructions are shifted in the queue (referred to as the
“compaction” process), the instructions are shifted from their current storage
location to a corresponding destination storage location further down the
queue (col. 45, ll. 31-42).
Appeal 2007-0662
Application 09/909,704

7

PRINCIPLES OF LAW
To reach a conclusion of obviousness under section 103, the Examiner
bears the burden of producing factual basis supported by teaching in a prior
art reference or shown to be common knowledge of unquestionable
demonstration. 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 (Fed. Cir. 1984).
Furthermore, the test for obviousness is what the combined teachings
of the references would have suggested to one of ordinary skill in the art.
See In re Kahn, 441 F.3d 977, 987-88, 78 USPQ2d 1329, 1336 (Fed. Cir.
2006), In re Young, 927 F.2d 588, 591, 18 USPQ2d 1089, 1091 (Fed. Cir.
1991) and In re Keller, 642 F.2d 413, 425, 208 USPQ 871, 881 (CCPA
1981).
“Section 103 forbids issuance of a patent when ‘the differences
between the subject matter sought to be patented and the prior art are such
that the subject matter as a whole would have been obvious at the time the
invention was made to a person having ordinary skill in the art to which said
subject matter pertains.’” KSR Int'l Co. v. Teleflex Inc., 127 S.Ct. 1727,
1734, 82 USPQ2d 1385, 1391 (2007).
“The combination of familiar elements according to known methods
is likely to be obvious when it does no more than yield predictable results.”
Leapfrog Enter., Inc. v. Fisher-Price, Inc., 485 F.3d 1157, 1161,
82 USPQ2d 1687, 1691 (Fed. Cir. 2007) (quoting KSR Int’l v. Teleflex, Inc.,
127 S. Ct. 1727, 1739, 82 USPQ2d 1385, 1395 (2007)). “One of the ways in
Appeal 2007-0662
Application 09/909,704

8
which a patent’s subject matter can be proved obvious is by noting that there
existed at the time of invention a known problem for which there was an
obvious solution encompassed by the patent’s claims.” KSR, 127 S. Ct. at
1742, 82 USPQ2d at 1397.

ANALYSIS
Rejection of claims 1-3 and 5-7 over Bauman and Trull
Appellant contends that Bauman processes requests from the request
buffer based on the order they were placed in the buffer or according to a
FIFO scheme (Br. 10). Based on such interpretation, Appellant argues that
one of ordinary skill in the art would not combine Bauman’s FIFO approach
with the out of order dispatch of Trull since they relate to different
functionalities (Br. 8). Specifically, Appellant contends that Bauman uses
four registers in either a first in first out manner or a first priority manner
and cannot be combined with Trull which dispatches instructions from an
instruction queue in an out of order manner (Br. 8). Appellant further argues
that the requests in Bauman enter the request queue in a time ordered
manner while the grouping of requests is determined prior to placement into
a request queue (Br. 10). Appellant specifically refers to request queue 282
of Bauman and asserts that once in request queue 282, there is no further
grouping of the requests as arbitration is performed among all of the requests
therein (id.). The Examiner argues that Bauman places packets in request
queues 252-258 before grouping them into primary arbitration queues 282-
288 (Answer 23). The Examiner concludes that the priority scheme used by
Bauman for grouping the request into primary arbitration queues 282-288 is
Appeal 2007-0662
Application 09/909,704

9
the same as the claimed associating the entries to one of a plurality of groups
having different transaction parameter criteria (id.).
Initially, we note that Appellant’s arguments appear to challenge
characterizing the four registers in primary arbitration queue 282 of Bauman
as the claimed queue containing the entries. As such, Appellant states that
the four register buffers are used as FIFO buffers causing the request at its
L0 register always to leave first (Reply Br. 9). In fact, the Examiner relies
on request queues 252-258 of Bauman as the entry queues, which are
grouped into primary arbitration queues 282-288 (FF 3-6). While the
primary registers 282-288 may use FIFO as one of the schemes for arranging
the requests and servicing them accordingly (FF 8), other priority schemes
may also be used for arranging the requests into the group in primary
arbitration queues 282-288 (FF2).
Additionally, Bauman may move a request from any part of queue
252 to queue 282, based on the requirements set forth by the application
such as output availability (FF 6). Once the requirement is met, the
youngest entry that meets the requirement is taken from its location in the
queue and supplied to the primary arbitration queue, where it may be
organized, among other schemes, in a FIFO scheme (FFs 7-8). Therefore,
we disagree with Appellant (Br. 8-9) that such process, by which an empty
position in the queue is created, is in conflict with the teachings of Trull and
may not benefit from compaction of the instruction queue taught by Trull
(FFs 9-10).
Additionally, we remain unconvinced by Appellant’s assertion (Br. 9-
10) that grouping of the requests of Bauman is determined prior to placing
Appeal 2007-0662
Application 09/909,704

10
them in the queue. In that regard, as pointed out supra, the grouping is
actually achieved by selecting entries from the request queue 252 to be
placed in the primary arbitration queue 282 (FF 8). Therefore, using the
compaction scheme of Trull in arrangement of the request queue 252 of
Bauman is not in conflict with the principals of the references and does
provide the claimed functionality.
Furthermore, contrary to Appellant’s assertion against combinability
of the references (Br. 7), combining Bauman and Trull is based on common
schemes for efficient use of queues once empty storage locations are present
in a queue. Trull shifts the instructions in a queue by a predetermined
number in order to fill the gap left by the instructions pulled out of order for
processing (FF 9-10). In fact, since Trull’s instructions are more efficiently
written into the “top” position of the queue and the gap left behind after
instructions are read out is eliminated by shifting down the instructions in
the queue (FF 10), one of ordinary skill in the art would have combined the
references to benefit from the compaction scheme of Trull (FF 11).
Thus, in light of these findings, we find that the combination of
Bauman and Trull suggests the subject matter of Claim 1 as well as claims 2,
3, and 5-7, argued together as one group.
Rejection of claims 4 and 8 over Bauman, Trull, and In re Yount
Appellant relies on the same arguments previously raised for claim 1
and asserts that Garcia adds nothing to the combination of Bauman and Trull
that would have made the subject matter of claim 4 unpatentable (Br. 12).
Similarly, Appellant provides no additional arguments for claim 8 and
merely relies on the arguments made for patentability of claim 1 (Br. 13).
Appeal 2007-0662
Application 09/909,704

11
Therefore, in light of our findings above, we find that the teachings of
Bauman and Trull combined with Garcia or In re Yount suggest the subject
matter of Claims 4 and 8. See In re Young, 927 F.2d 588, 590, 18 USPQ2d
1089, 1091 (Fed. Cir. 1991). See also 37 C.F.R. § 41.37(c)(1)(vii).
Rejection of claims 9-14 over Meyers, Bauman, and Trull
Appellant argues that the Examiner has not shown that Bauman and
Trull may be properly combined and shift registers be incorporated as taught
by Meyers (Br. 14; Reply Br. 16). Appellant further asserts that the
combination of the references would still be unable to group entries after
their placement into a queue followed by servicing of a particular entry of a
group, as required by the claims (Br. 15; Reply Br. 17). The Examiner
points to the arguments made with respect to claim 1 and states that the
rejection is based on combining Bauman and Trull with the computer system
of Meyers (Answer 26-29).
We agree with the Examiner and find that combining Meyers with
Bauman and Trull requires nothing more than combining familiar elements
producing predictable results. Not only does the combination of Bauman
and Trull teach collapsing the queue and grouping the requests according to
different transaction parameter criteria, but also one of ordinary skill in the
art would have used such arrangement for improving the arbitration queue in
the distributed memory system of Meyers. Accordingly, we find the
Examiner’s position rejecting these claims to be reasonable.
Rejection of claim 15 over Meyers, Bauman, Trull, and In re Yount
Appellant provides no additional arguments for claim 15 and merely
relies on the arguments made for the patentability of claim 9 (Br. 16).
Appeal 2007-0662
Application 09/909,704

12
Therefore, in light of our findings above, we find that the teachings of
Meyers as combined with Bauman and Trull in view of In re Yount suggest
the subject matter of claims 15. See In re Young, 927 F.2d at 590, 18
USPQ2d at 1091 (Fed. Cir. 1991). See also 37 C.F.R. § 41.37(c)(1)(vii).

CONCLUSION OF LAW
Because Appellant has failed to point to any error in the Examiner’s
position, we sustain the 35 U.S.C. § 103 rejection of claims 1-3 and 5-7 over
Bauman and Trull; of claim 4 over Bauman, Trull, and Garcia; of claim 8
over Bauman, Trull, and In re Yount; of claims 9-14 over Meyers, Bauman,
and Trull; and of claim 15 over Meyers, Bauman, Trull, and in view of In re
Yount.

DECISION
The decision of the Examiner rejecting claims 1-15 is affirmed.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv).

Appeal 2007-0662
Application 09/909,704

13
AFFIRMED

eld

Baker Botts L.L.P.
Suite 600
2001 Ross Avenue
Dallas, TX 75201-2980