Ex Parte Moir et al

Board of Patent Appeals and Interferences

Jan 23, 2012

10620748 (B.P.A.I. Jan. 23, 2012)

UNITED STATES PATENT AND TRADEMARK OFFICE
________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
________________

Ex parte MARK S. MOIR, VICTOR M. LUCHANGCO, and
MAURICE HERLIHY
________________

Appeal 2009-014014
Application 10/620,748
Technology Center 2100
________________

Before ALLEN R. MacDONALD, ROBERT E. NAPPI, and
JASON V. MORGAN, Administrative Patent Judges.

MORGAN, Administrative Patent Judge.

DECISION ON APPEAL
Appeal 2009-014014
Application 10/620,748

2

STATEMENT OF THE CASE
Introduction
This is an appeal under 35 U.S.C. § 134(a) from the Examiner’s final
rejection of claims 1 – 44. We have jurisdiction under 35 U.S.C. § 6(b).
We reverse.
Invention
The invention relates to structures and techniques for facilitating non-
blocking implementations of shared data structures, enabling coordination
amongst execution sequences in a multiprocessor computer (Spec. ¶ [1002]).
Independent claim 1 is directed to a computer readable storage medium
encoding program code implementing a double-ended array in which
concurrent execution of access operations are mediated using a single-target
synchronization primitive. Independent claim 19 is directed to a computer
readable storage medium encoding program code to implement a single-
target synchronization based deque (double-ended queue). Independent
claim 30 is directed to a method of managing obstruction-free access to a
shared double-ended array. Independent claim 40 is directed to an apparatus
including means for coordinating concurrent non-blocking access to a deque.
Independent claim 43 is directed to a method of operating on a double-ended
queue data structure.
Exemplary Claim
1. A computer readable storage medium encoding
program code executable on one or more processors to
implement:
instantiating a data structure implementation in a memory
comprising a double-ended array;
Appeal 2009-014014
Application 10/620,748

3
executing a plurality of opposing-end access operations
that, when executed on the one or more processors, access the
memory, and provide concurrent push-type and pop-type access
to at least one of the opposing ends and concurrent, opposing-
end accesses that are non-interfering for at least some states of
the array; and
mediating concurrent execution of the access operations
using a single-target synchronization primitive;
wherein the data structure implementation is linearizable
and non-blocking, and
wherein the single-target of the single-target
synchronization primitive includes a value encoding for an
element of the array and a version number encoded integrally
therewith.
(Emphases added).
Evidence Examiner Relies Upon
Martin US 2001/0047361 A1 Nov. 29, 2001
Latour US 2002/0078123 A1 Jun. 20, 2002
Rowlands US 2003/0217115 A1 Nov. 20, 2003
Examiner’s Rejections
The Examiner rejects claims 1 – 4, 6 – 10, 12 – 14, 16 – 22, 24, 26 –
33, and 35 – 44 under 35 U.S.C. §§ 102(a) and 102(e) as being anticipated
by Martin (Ans. 3 – 14).
The Examiner rejects claims 5, 25, and 34 under 35 U.S.C. § 103(a) as
being unpatentable over Martin and Rowlands (Ans. 14 – 15).
The Examiner rejects claims 11, 15, and 23 under 35 U.S.C. § 103(a)
as being unpatentable over Martin and Latour (Ans. 16 – 17).
ISSUE
Did the Examiner err in finding that Martin discloses the recitations of
claim 1?
Appeal 2009-014014
Application 10/620,748

4
ANALYSIS
Claim 1
Claim 1 recites “instantiating a data structure . . . comprising a
double-ended array . . . executing a plurality of opposing-end access
operations . . . and mediating concurrent execution of the access operations
using a single-target synchronization primitive . . . wherein the single-target
of the single-target synchronization primitive includes a value encoding for
an element of the array and a version number encoded integrally therewith”
(emphases added).
The Examiner finds that Martin’s disclosure of a compare-and-swap
(CAS) operation (Martin ¶ [0012]) discloses the claimed single-target
synchronization primitive (Ans. 5). The Examiner further finds that the CAS
operation and Martin’s disclosure of elements V1, V2, and V3 (Martin fig.1)
disclose “wherein the single-target of the single-target synchronization
primitive includes a value encoding [f]or an element of the array and a
version number encoded integrally therewith” (Ans. 5 – 6) (emphasis
omitted).
Appellants contend “the V numbers of Martin represent value
encodings for respective array elements, not version numbers” (App. Br.
13). We agree with Appellants. The target of the claimed single-target
synchronization primitive includes both a value encoding for an element of
the array and a version number. See, for example, figure 1 of the
Specification, elements VN 113a (an element of the array) and CTR 113b (a
version number). Martin’s elements V1, V2, and V3 represent value fields in
a double-linked list (Martin fig.1 and ¶ [0074]). Thus, in Martin, each value
Appeal 2009-014014
Application 10/620,748

5
field encodes an element of the list, but does not further encode a version
number.
Appellants further contend, with respect to claim 6, that “DCAS
(double compare-and-swap) is clearly not a single-target synchronization
primitive, as it operates on two different target locations explicitly identified
by operands of the instruction” (App. Br. 16). This argument is also
appurtenant to claim 1, which introduces the single-target synchronization
primitive limitation in the context of “mediating concurrent execution of the
access operations.”
Martin discloses both a single-target compare-and-swap and a dual-
target double compare-and-swap (Martin ¶¶ [0012, 0013, and 0048]). A
double compare-and-swap primitive operates on two targets (memory
addresses A1 and A2) (Martin ¶¶ [0013 and 0048]). Martin also discloses
that single-target compare-and-swaps are “not expressive enough to support
design of efficient non-blocking algorithms” (Martin ¶ [0013]). As
illustrated in the push right and pop right functions, Martin uses double
compare-and-swaps, not single-target compare-and-swaps, to mediate
concurrent execution of access operations (Martin ¶¶ [0084, 0087]).
The Examiner notes (Ans. 7) that Martin discloses that a single-target
compare-and-swap “can be used to ensure a precise count” (Martin
¶ [0123]). However, the claim is directed to using a single-target
synchronization primitive for mediating concurrent execution of the access
operations, not for ensuring precise counts.
For these reasons, we do not sustain the Examiner’s rejection of claim
1 under 35 U.S.C. §§ 102(a) and 102(e).
Appeal 2009-014014
Application 10/620,748

6
Claims 2 – 18 and 30 – 44
Independent claims 30, 40, and 43 have similar recitations to the
disputed recitations of claim 1. Claims 2 – 18, 31 – 39, 41, 42, and 44
incorporate the dispute recitations, or similar recitations, as dependent
claims. The Examiner has not shown that Rowlands or Latour cure the
deficiencies of Martin. Accordingly, for the reasons above, we do not sustain
the Examiner’s §§ 102(a) and 102(e) rejections of claims 2 – 4, 6 – 10, 12 –
14, 16 – 18, 30 – 33, and 35 – 44 and the Examiner’s § 103(a) rejections of
claims 5, 11, 15, and 34.
Claim 19
Claim 19 is directed to a computer readable storage medium encoding
program code executable to implement “a single-target synchronization
primitive based . . . deque.” The broadest reasonable interpretation in light of
the Specification of “single-target synchronization primitive based” is that
concurrent access to the deque is managed using a single-target
synchronization primitive. This is supported by the Specification’s
disclosure of a “single-target synchronization based (e.g., CAS-based) . . .
deque implementation” (Spec. ¶ [1015]) that uses single-target
synchronization primitives to mediate concurrent access to push and pop
operations (Spec. ¶¶ [1036 – 38]). Moreover, the Specification distinguishes
“single-target synchronization primitive based” deques from prior art
“implementations [that] depend on a hardware DCAS (double compare-and-
swap) instruction, which is not widely supported in practice” (Spec.
¶ [1017]).
As discussed above, Martin uses double compare-and-swaps to
manage concurrent access. The Examiner finds that Martin’s “deque
Appeal 2009-014014
Application 10/620,748

7
requires only a single DCAS for most pushes and pops (abstract)” (Ans. 22).
However, even a single double compare-and-swap targets two memory
addresses, not just one.
As such, we do not sustain the Examiner’s rejection of claim 19 under
35 U.S.C. §§ 102(a) and 102(e).
Claims 20 – 29
Dependent claims 20 – 29 incorporate the recitations of claim 19
discussed previously. The Examiner has not shown that Rowlands or Latour
cure the deficiencies of Martin. Accordingly, for the reasons above, we do
not sustain the Examiner’s §§ 102(a) and 102(e) rejections of claims 20 –
22, 24, and 26 – 29 and the Examiner’s § 103(a) rejections of claims 23 and
25.

DECISION
We reverse the Examiner’s decision rejecting claims 1 – 44.

REVERSED

tj