Ex Parte Detlefs et al

Patent Trial and Appeal Board

Apr 28, 2017

12400209 (P.T.A.B. Apr. 28, 2017)

United States Patent and Trademark Office
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
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
12/400,209 03/09/2009 David L. Detlefs 324898.01 3623
69316 7590 05/02/2017
MICROSOFT CORPORATION
ONE MICROSOFT WAY
REDMOND, WA 98052
EXAMINER
BROPHY, MATTHEW J
ART UNIT PAPER NUMBER
2191
NOTIFICATION DATE DELIVERY MODE
05/02/2017 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):
u sdocket @ micro soft .com
chriochs @microsoft.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte DAVID L. DETLEFS, YOSSEFF LEVANONI, WEIRONG
ZHU, DANA GROFF, and ALEXANDER DADIOMOV
Appeal 2017-002642
Application 12/400,209
Technology Center 2100
Before JAMES R. HUGHES, JOHN P. PINKERTON, and
STEVEN M. AMUNDSON, Administrative Patent Judges.
HUGHES, Administrative Patent Judge.
DECISION ON APPEAL
STATEMENT OF THE CASE
Appellants seek our review under 35 U.S.C. § 134(a) of the
Examiner’s final decision rejecting claims 1, 3—14, and 16—20. Claims 2 and
15 have been canceled. Final Act. 1—2; App. Br. I.1 We have jurisdiction
under 35 U.S.C. § 6(b).
We affirm.
1 We refer to Appellants’ Specification (“Spec.”), filed Mar. 9, 2009; Appeal
Brief (“App. Br.”) filed Apr. 8, 2016; and Reply Brief (“Reply Br.”) filed
Dec. 5, 2016. We also refer to the Examiner’s Answer (“Ans.”) mailed Oct.
5, 2016, and Final Office Action (Final Rejection) (“Final Act.”) mailed Oct.
7, 2015.
Appeal 2017-002642
Application 12/400,209
Appellants ’ Invention
The invention generally concerns privatization artifacts, software
transactional memory (STM) systems, computer readable storage devices,
and methods utilized by an STM system for ensuring that a privatization
artifact will not occur. A privatization artifact occurs between a first
transaction associated with a first thread and a subsequent second transaction
due to access of an object by the first thread after the second transaction
(access and modification of the object during the second transaction) and
after the object has been privatized by the first thread. The method ensures
against the privatization artifact by determining that a first transaction is not
a damaging transaction (a transaction that would perform a damaging write)
to a privatized object and thereby create a privatization artifact. Spec. 1—
3, 5, 32—36; Abstract.
Representative Claim
Independent claim 1, reproduced below with key disputed limitations
emphasized, further illustrates the invention:
1. A method performed by a software transactional
memory (STM) system in a computer system, the method
comprising:
ensuring that a privatization artifact will not occur
between a first transaction in a first thread and a second
transaction that is later than the first transaction in a completion
order, the privatization artifact would have occurred from access
of an object by the first thread after the second transaction
accesses and modifies the object after the object has been
privatized by the first thread including:
determining that the first transaction is not a damaging
transaction that would perform a damaging write to a privatized
object and thereby create a privatization artifact to ensure that
the privatization artifact will not occur, and
2
Appeal 2017-002642
Application 12/400,209
allowing the second transaction to complete prior to the
first transaction completing.
Rejections on Appeal
1. The Examiner rejects claims 1, 3—5, 7—11, 13, 14, 16—18, and
20 under pre-America Invents Act (AIA) 35 U.S.C. § 103(a) as being
unpatentable over Adl-Tabatabai et al. (US 2010/0162250 Al, published
June 24, 2010 (filed Dec. 24, 2008)) (“Adl-Tabatabai”); Spear et al.,
Privatization Techniques for Software Transactional Memory, 338—339,
Proc. of the 26th annual ACM symposium on Principles of Distributed
Computing (PODC ‘07) (2007) (“Spear-Privatization”); and Spear et al.,
RingSTM: Scalable Transactions with a Single Atomic Instruction, Proc. of
the 20th annual ACM symposium on Parallelism in Algorithms and
Architectures (SPAA ‘08) (2008) (“Spear-RingSTM”).
2. The Examiner rejects claims 6, 12, and 19 under 35 U.S.C.
§ 103(a) as being unpatentable over Adl-Tabatabai, Spear-Privatization,
Spear-RingSTM, and Ni et al., Design and implementation of transactional
constructs for C/C++, 195—212, Proc. of the 23rd ACM SIGPLAN
conference on Object-Oriented Programming Systems Languages and
Applications (OOPSLA ‘08) (2008) (“Ni”).
ISSUES
Based upon our review of the record, Appellants’ contentions, and the
Examiner’s findings and conclusions, the issue before us follows:
1. Did the Examiner err in finding that Adl-Tabatabai, Spear-
Privatization, and Spear-RingSTM collectively would have taught or
suggested “determining that the first transaction is not a damaging
3
Appeal 2017-002642
Application 12/400,209
transaction that would perform a damaging write to a privatized object and
thereby create a privatization artifact to ensure that the privatization artifact
will not occur” within the meaning of Appellants’ claim 1 and the
commensurate limitations of claims 8 and 14?
ANALYSIS
Appellants argue independent claims 1 and 14 together as a group.
See App. Br. 5—10. Appellants do not separately argue dependent claims 3—
5, 7, 9-11, 13, 16—18, and 20. See App. Br. 10. Appellants provide
additional separate arguments with respect to independent claim 8. See App.
Br. 9-10. We select independent claim 1 as representative of Appellants’
arguments and grouping with respect to claims 1, 3—5, 7—11, 13, 14, 16—18,
and 20. 37 C.F.R. § 41.37(c)(l)(iv). We also address Appellants’ separate
arguments with respect to claim 8.
We adopt as our own (1) the findings and reasons set forth by the
Examiner in the action from which this appeal is taken (see Final Act. 2—14;
see also Ans. 2—14), and (2) the reasons set forth by the Examiner in the
Examiner’s Answer (see Ans. 26—32) in response to Appellants’ Appeal
Brief. We concur with the findings and conclusions reached by the
Examiner, and we provide the following for emphasis.
Appellants contend that Adl-Tabatabai, Spear-Privatization, and
Spear-RingSTM do not teach the disputed features of claim 1. See App. Br.
6—10; Reply Br. 2—5. Specifically, Appellants contend Spear-RingSTM
does not teach “determining that the first transaction is not a damaging
transaction that would perform a damaging write to a privatized object and
thereby create a privatization artifact” (App. Br. 7 (quoting claim 1)
4
Appeal 2017-002642
Application 12/400,209
(emphasis omitted); see App. Br. 6—7; Reply Br. 3). Appellants also contend
Spear-Privatization does not teach
ensuring that a privatization artifact will not occur between a first
transaction in a first thread and a second transaction that is later
than the first transaction in a completion order, the privatization
artifact would have occurred from access of an object by the first
thread after the second transaction accesses and modifies the
object after the object has been privatized by the first thread.
App. Br. 7 (quoting claim 1) (emphasis omitted); see App. Br. 7—9; Reply
Br. 2—3. Further, Appellants contend Spear-Privatization does not teach
determining a first completion order of a first transaction in a first
thread and a second transaction in a second thread executed by a
STM system, and implementing a second completion order of the
first and the second transactions that differs from the first
completion order in response to determining that a privatization
artifact will not occur between the first and the second
transactions, the privatization artifact would have occurred from
access of an object by one of the first and second threads after
one of the first and second transactions accesses and modifies the
object after the object has been privatized by the one of the first
and second threads as defined by independent claim 8.
App. Br. 10 (quoting claim 1) (emphasis omitted); see App. Br. 9—10; Reply
Br. 3^4.
The Examiner makes specific findings with respect to each of the
disputed limitations in Appellants’ claim 1. See Final Act. 2—8; Ans. 27—32.
We agree with the Examiner and find a preponderance of the evidence
demonstrates that the combination of Adl-Tabatabai, Spear-Privatization,
and Spear-RingSTM would have taught or at least suggested the disputed
features of Appellants’ claim 1. Appellants do not directly dispute the
Examiner’s findings with respect to the teachings of Adl-Tabatabai, Spear-
Privatization, and Spear-RingSTM as they apply to the proffered
5
Appeal 2017-002642
Application 12/400,209
combination. Instead, Appellants quote the disputed limitations, state that
the individual references do not teach certain aspects of the quoted
limitation, and then summarize or quote the relevant portions of the
individual references. See App. Br. 7—9. In each case, Appellants do not
address the Examiner’s specific findings with respect to the teachings of the
prior art.
Appellants first contend that Spear-RingSTM does not teach
“determining that the first transaction is not a damaging transaction that
would perform a damaging write to a privatized object and thereby create a
privatization artifact” (claim 1). See App. Br. 6—7; Reply Br. 3. We agree
with the Examiner that Adl-Tabatabai and Spear-RingSTM describe
determining that the first transaction is not a damaging transaction — that a
transaction does not write to a privatized object. See Final Act. 3—5, 7—8;
Ans. 27—28 (citing Adl-Tabatabai Tflf 19-26, 55—56, 76; Fig. 3; and Spear-
RingSTM Secs. 1.3, 2, 2.2). As explained by the Examiner, Adl-Tabatabai
describes determining a potentially conflicting access that would produce a
privatization artifact. Ans. 27. The Examiner further explains that Spear-
RingSTM describes checking intersections between read/write sets for
transactions to determine if a transaction will create a data violation (i.e.,
“would be [a] ‘damaging transaction[]’”). Ans. 27. Appellants do not
explicitly address the Examiner’s findings, nor do they persuasively rebut
these findings.
Appellants next contend that Spear-Privatization does not teach the
recited ensuring functionality — “ensuring that a privatization artifact will
not occur ...” (claim 1) — or the recited completion order (a second
transaction that is later than a first transaction in a completion order, and
6
Appeal 2017-002642
Application 12/400,209
avoiding a second transaction modifying an object after the object has been
privatized by the first thread (the first transaction)). See App. Br. 7—9; Reply
Br. 2—3. We again agree with the Examiner that Adl-Tabatabai and Spear-
Privatization describe the recited functionality and completion order. See
Final Act. 3—7; Ans. 27, 31—32 (citing Adl-Tabatabai Tflf 19-26, 55—56, 76;
Fig. 3; and Spear-Privatization Sec. 3.2). As explained by the Examiner,
Adl-Tabatabai describes determining a potentially conflicting access and
holding a potentially conflicting transaction (implementing a safety
mechanism) allowing transactions to complete out of their original order,
e.g., allowing a second transaction to complete before privatizing an object
(first transaction). Final Act. 4—5; Ans. 27. The Examiner further explains
that Spear-Privatization explicitly describes a transaction execution scenario
to be prevented or avoided where an object is privatized (thread T1
privatizes an object in a first transaction) and a second thread T2 executes a
transaction on the privatized object. See Final Act. 5—6; Ans. 31—32; Spear-
Privatization Sec 3.2. Appellants do not explicitly address the Examiner’s
findings, nor do they persuasively rebut these findings.
Appellants further contend, with respect to independent claim 8, that
Adl-Tabatabai and Spear-Privatization do not teach the recited first and
second completion orders — “determining a first completion order of a first
transaction in a first thread and a second transaction in a second thread” and
“implementing a second completion order of the first and the second
transactions that differs from the first completion order in response to
determining that a privatization artifact will not occur” (claim 8). See App.
Br. 9—10; Reply Br. 3^4. We agree with the Examiner that Adl-Tabatabai
and Spear-Privatization describe the recited first and second threads, first
7
Appeal 2017-002642
Application 12/400,209
and second transactions, and first and second completion orders. See Final
Act. 8—14; Ans. 27, 31—32 (citing Adl-Tabatabai Tflf 19-26, 55—57, 61; Fig.
3; and Spear-Privatization Sec. 3.2). As explained by the Examiner, Adl-
Tabatabai describes first and second threads, first and second transactions,
first and second completion orders, as well as determining a potentially
conflicting access and holding a potentially conflicting transaction
(implementing a safety mechanism) allowing transactions to complete out of
their original order. Final Act. 8—11; Ans. 27. The Examiner further
explains that Spear-Privatization explicitly describes a transaction execution
scenario to be prevented where an object is privatized (thread T1 privatizes
an object in a first transaction) and a second thread T2 executes a transaction
on the privatized object. See Final Act. 11—12; Ans. 31—32; Spear-
Privatization, Sec 3.2. Appellants do not explicitly address the Examiner’s
findings, nor do they persuasively rebut these findings.
Thus, Appellants do not persuade us of error in the Examiner’s
obviousness rejection of claim 1. For these same reasons, Appellants also
do not persuade us of error in the Examiner’s obviousness rejection of
independent claims 8 (including the additional limitations of claim 8,
discussed supra) and 14, or dependent claims 3—5, 9-11, 13, 16—18, and 20,
not separately argued with particularity {supra). Accordingly, we affirm the
Examiner’s obviousness rejection of claims 1, 3—5, 7—11, 13, 14, 16—18, and
20.
With respect to the obviousness rejection of dependent claims 6, 12,
and 19, rejected as obvious over Adl-Tabatabai, Spear-Privatization, Spear-
RingSTM, and Ni, we agree with the Examiner’s findings and conclusions
for the same reasons set forth with respect to claim 1 {supra). Appellants do
8
Appeal 2017-002642
Application 12/400,209
not separately argue the rejections of these claims with particularity. App.
Br. 11.
CONCLUSIONS
Appellants have not shown that the Examiner erred in rejecting claims
1, 3-14, and 16-20 under 35 U.S.C. § 103(a).
DECISION
We affirm the Examiner’s rejection of claims 1, 3—14, and 16—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
9