Ex Parte Laine et al

Patent Trial and Appeal Board

Sep 8, 2014

11862938 (P.T.A.B. Sep. 8, 2014)

UNITED STATES PATENT AND TRADEMARK OFFICE
_____________

BEFORE THE PATENT TRIAL AND APPEAL BOARD
_____________

Ex parte SAMULI M. LAINE, TIMO O. AILA,
and MARK J. HARRIS
_____________

Appeal 2012-002563
Application 11/862,938
Technology Center 2100
______________

Before JOHN A. JEFFERY, DAVID M. KOHUT, and
JENNIFER L. MCKEOWN, Administrative Patent Judges.

KOHUT, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2012-002563
Application 11/862,938

2
This is a decision on appeal under 35 U.S.C. § 134(a) of the Final
Rejection of claims 1-22. We have jurisdiction under 35 U.S.C. § 6(b).
We affirm-in-part the Examiner’s rejection of these claims.

INVENTION
The invention is directed to a method, system, and computer program
product for efficiently performing a scan operation by executing
computational algorithms utilizing parallel processor architectures. Spec.
[0001] and [0012]. Claims 1, 7, and 9 are illustrative of the invention and
are reproduced below:
1. A method, comprising:
traversing an array of elements by utilizing a parallel processor
architecture including a plurality of processors each capable of
physically executing a predetermined number of threads in parallel;
and
executing the predetermined number of threads of at least one
of the processors to perform a scan operation involving a number of
the elements that is a function of the predetermined number of
threads.

7. The method of claim 1, wherein the function includes a multiple.

9. The method of claim 7, wherein the multiple is at least two.

REFERENCES
Peeper US 2008/0316214 A1 Dec. 25, 2008

W. Daniel Hillis & Guy L. Steele, Jr., Data Parallel Algorithms,
Communications of the ACM, Dec. 1986, Vol. 29, No. 12, 1170-1183.1

1 Hereinafter referred to as Hillis.
Appeal 2012-002563
Application 11/862,938

3
REJECTIONS AT ISSUE
Claims 1-5, 7-9, 15-17, 19, and 20 are rejected under 35 U.S.C.
§ 102(e) as being anticipated by Peeper. Ans. 4-6.
Claims 6, 10-14, and 18 are rejected under 35 U.S.C. § 103(a) as
being unpatentable over Peeper and Hillis. Ans. 6-8.

ISSUES
Did the Examiner err in finding that Peeper discloses “a parallel
processor architecture including a plurality of processors each capable of
physically executing a predetermined number of threads in parallel,” as
recited in claim 1?
Did the Examiner err in finding that Peeper discloses “executing the
predetermined number of threads of at least one of the processors to perform
a scan operation,” as recited in claim 1?
Did the Examiner err in finding that Peeper discloses “a scan
operation involving a number of the elements that is a function of the
predetermined number of threads,” as recited in claim 1?
Did the Examiner err in finding that Peeper discloses “wherein the
function includes a multiple,” as recited in claim 7?
Did the Examiner err in finding that Peeper discloses “wherein the
multiple is one,” as recited in claim 8?
Did the Examiner err in finding that Peeper discloses “wherein the
multiple is at least two,” as recited in claim 9?

Appeal 2012-002563
Application 11/862,938

4
ANALYSIS
Claims 1-5, 15-17, and 19-22
We select claim 1 as representative of the group comprising claims 1-
5, 15-17, and 19-22 as Appellants have not argued any of the other claims
with particularity. 37 C.F.R. § 41.37(c)(1)(vii). Claim 1 recites “a parallel
processor architecture including a plurality of processors each capable of
physically executing a predetermined number of threads in parallel.” The
Examiner finds that Peeper discloses this limitation because Peeper discloses
a processing unit 904 that contains “[d]ual microprocessors and other multi-
processor architectures.” Ans. 4 and 8 (citing Peeper [0123]). Initially,
Appellants argue that “[m]erely teaching that a processing unit may include
a multi-processor architecture, as in Peeper, does not teach a ‘parallel
processor architecture including a plurality of processors each capable of
physically executing a predetermined number of threads in parallel’
(emphasis added), as specifically claimed by appellant.” App. Br. 10-11;
Reply Br. 2-5. We disagree with Appellants.
First, Appellants’ Specification does not provide a specific definition
for the term “parallel processor architecture.” Therefore, under the claim’s
broadest reasonable interpretation consistent with Appellants’ Specification,
the term “parallel processor architecture” means a computer architecture that
allows for “[a] method of processing that can run only on a computer that
contains two or more processors running simultaneously,” as indicated in the
Microsoft Computer Dictionary (5th ed. 2002). Second, we find that the
plain meaning of a “dual processor,” or dual microprocessors, includes
“[t]wo processors used in a computer to speed its operation—one processor
to control memory and the bus, and another to manage input/output,” as
Appeal 2012-002563
Application 11/862,938

5
indicated in the Microsoft Computer Dictionary (5th ed. 2002). Third, we
find that the plain meaning of “multiprocessing” includes “[a] mode of
operation in which two or more connected and roughly equal processing
units each carry out one or more processes (programs or sets of instructions)
in tandem,” as indicated in the Microsoft Computer Dictionary (5th ed.
2002) (emphasis added). Accordingly, even though Peeper does not
explicitly use the words “parallel processor architecture,” we agree with the
Examiner (Ans. 4 and 8) that Peeper’s “[d]ual microprocessors and multi-
processor architectures” satisfy the claimed “parallel processor architecture”
because these definitions make it clear that dual processors and multi-
processing includes at least two processors operating at the same time, or in
tandem with each other. See Peeper [0123].
Additionally, Appellants’ Specification does not provide a definition
for the term “threads.” As such, we find that the plain meaning of “threads”
in computer programming includes “a process that is part of a larger process
or program,” as indicated in the Microsoft Computer Dictionary 518 (5th ed.
2002). To be clear, the Examiner refers to portions of Peeper that disclose a
parallel processor architecture, as explained above. Ans. 5. This parallel
processor architecture described by Peeper “facilitates linearized A-buffer
storage based on utilization of a count pass and prefix sum pass to roughly
sort the fragments.” Peeper [0021]. In other words, Peeper’s architecture
executes software instructions to perform these operations. We, therefore,
agree with the Examiner (Ans. 4-5) that Peeper discloses that the plurality of
processors are “each capable” of executing a predetermined number of
threads in parallel because the executed set of instructions for each of these
Appeal 2012-002563
Application 11/862,938

6
operations are going to be known and stored in the system prior to the
execution and, as a result, the executed threads are “predetermined.”
Claim 1 additionally recites “executing the predetermined number of
threads of at least one of the processors to perform a scan operation.”
Appellants argue that Peeper does not disclose this limitation. App. Br. 12-
13; Rep. Br. 5-8. Appellants specifically argue that “[n]owhere in the [cited
portions of Peeper] is a ‘predetermined number of threads of at least one of
the processors [executed] to perform a scan operation.’” App. Br. 13
(emphasis in original). The Examiner finds that Peeper discloses processing
unit 904 that can execute stored threads to perform a “prefix sum pass to
roughly sort the fragments.” Ans. 4-5, and 9 (citing Peeper [0021] and
[0040]). Thus, the Examiner finds that the “prefix sum pass” operation
satisfies the claimed “scan operation.” Id.
As indicated supra, the plain meaning of the claim term “thread” is “a
process that is part of a larger process or program.” Accordingly, we agree
with the Examiner (Ans. 4-5 and 9-10) that the instructions executed by
processing unit 904 to carry out the prefix sum pass satisfy the phrase of
“executing the predetermined number of threads . . . to perform a scan
operation” because the instructions executed will necessarily be determined
prior to the execution of the prefix sum pass. To be clear, the executed
instructions satisfy the claimed “threads” limitation because the instructions
are a sub-part of the larger prefix sum pass process, and therefore the
instructions are “a process that is part of a larger process or program.”
Appellants further contend that Peeper does not disclose “a scan
operation involving a number of the elements that is a function of the
predetermined number of threads,” as recited in claim 1. App. Br. 13-14;
Appeal 2012-002563
Application 11/862,938

7
Rep. Br. 8-11. In particular, Appellants argue that the portion of Peeper
cited by the Examiner
merely discloses that “[o]ne or more components can reside
within a process and/or thread of execution, and a component
can be localized on one computer” (Paragraph [0118]), which
fails to even suggest appellant’s claimed “scan operation
involving a number of the elements that is a function of the
predetermined number of threads.”

App. Br. 14 (emphasis in original). The Examiner finds that Peeper
discloses executing threads, as discussed supra, to perform a prefix scan
pass, which involves at least one pixel in the array, and where the prefix
scan pass is a function of the predetermined threads. Ans. 5 (citing [0021],
[0040], [0055], [0056], [0118]).
We agree with the Examiner for the following reasons. Appellants
provide examples of “a scan operation” in their Specification where
Appellants refer to an “all-prefix-sums” operation. See e.g. Spec. [0002].
Therefore, we agree with the Examiner that Peeper’s executed “prefix sum
pass” satisfies the “scan operation” because Appellants explicitly state that a
prefix sum operation is an example of the claimed “scan operation.” In
addition, Peeper’s “prefix sum pass” involves various pixels, or elements, so
we agree with the Examiner (Ans. 5) that the scan operation involves
elements, as required by claim 1. See Peeper [0040] (describing that pixels
are involved in the prefix sum pass operation). Also, the prefix sum pass is a
function of the predetermined threads, or predetermined instructions,
because the prefix sum pass varies according to the underlying information
in the threads, or instructions.
Accordingly, for the reasons stated supra, we sustain the Examiner’s
rejection of claims 1-5, 15-17, and 19-22.
Appeal 2012-002563
Application 11/862,938

8
Claims 6 and 18
Appellants argue that dependent claims 6 and 18 are allowable for the
same reasons indicated above with respect to independent claims 1 and 15.
App. Br. 19; Reply Br. 17. Therefore, we sustain the Examiner’s rejection
of claims 6 and 18 for the same reasons as claims 1 and 15.

Claims 7 and 8
Claim 7 recites “wherein the function includes a multiple,” and claim
8 recites “wherein the multiple is one.” The Examiner finds that Peeper
discloses these limitations since Peeper discloses a thread that processes
multiple pixels wherein one of the multiples is 1. Ans. 5-6 and 10.
Appellants disagree with the Examiner’s findings. App. Br. 15-18; Rep. Br.
11-15. Appellants contend that
merely generating counts of fragments per pixel, in addition to
calculating locations in a location buffer to store fragments
linearly, as in Peeper, fails to even suggest that that [sic] “a
thread may process multiple pixels,” as argued by the
Examiner, much less appellant’s claimed technique “wherein
the function includes a multiple[,]”

(App. Br. 15 (emphasis in original)) and where “the multiple is one” (App.
Br. 17 (emphasis in original)). We disagree with Appellants.
Peeper discloses a system that calculates all of the pixels in each
thread. Ans. 5-6 and 10. Thus, Peeper’s pixels are the number of elements
and the function or multiple is each thread, i.e., one. As such, we sustain the
Examiner’s rejection of claims 7 and 8.

Appeal 2012-002563
Application 11/862,938

9
Claim 9
Claim 9 recites “wherein the multiple is at least two.” Again, the
Examiner finds that Peeper’s disclosure of processing multiple pixels of a
thread reads on the claim. Ans. 6 and 10. Appellants make the same
arguments with respect to claim 9 as with claims 7 and 8. Appeal Br. 18-19;
Reply Br. 15-17. However, in this instance, we agree with Appellants.
While the reference discloses calculating the number of pixels for each
thread, the Examiner fails to show, nor do we find, that Peeper discloses
calculating the number of pixels for more than one thread in one scan
operation. As such, we cannot sustain the Examiner’s rejection of claim 9.

Claims 10-14
Appellants argue that claims 10-14 are allowable based upon the same
reasons as argued with respect to claim 9, which claims 10-14 are dependent
upon. App. Br. 20; Reply Br. 17. As indicated above, we agree with
Appellants that Peeper does not disclose the limitations of claim 9. The
Examiner did not cite to Hillis to teach or suggest the deficiencies noted
above and we will not engage in any inquiry as to whether Hillis cures any
of those deficiencies. As such, we cannot sustain the Examiner’s rejection
of claims 10-14.

CONCLUSION
The Examiner did not err in finding that Peeper discloses “a parallel
processor architecture including a plurality of processors each capable of
physically executing a predetermined number of threads in parallel,” as
recited in claim 1.
Appeal 2012-002563
Application 11/862,938

10
The Examiner did not err in finding that Peeper discloses “executing
the predetermined number of threads of at least one of the processors to
perform a scan operation,” as recited in claim 1.
The Examiner did not err in finding that Peeper discloses “a scan
operation involving a number of the elements that is a function of the
predetermined number of threads,” as recited in claim 1.
The Examiner did not err in finding that Peeper discloses “wherein the
function includes a multiple,” as recited in claim 7.
The Examiner did not err in finding that Peeper discloses “wherein the
multiple is one,” as recited in claim 8.
The Examiner erred in finding that Peeper discloses “wherein the
multiple is at least two,” as recited in claim 9.

SUMMARY
The Examiner’s decision to reject claims 1-5, 7, 8, 15-17, 19, and 20
under 35 U.S.C. § 102(e) and claims 6 and 18 under 35 U.S.C. § 103(a) is
affirmed.
The Examiner’s decision to reject claim 9 under 35 U.S.C. § 102(e)
and claims 10-14 under 35 U.S.C. § 103(a) is reversed.

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).
AFFIRMED-IN-PART

tkl