DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: an operation scheduler configured to … in claim 1.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-11 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1 limitation “an operation scheduler configured to…” invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function.
The operation scheduler is described by its function in the specification (see, e.g., ¶0023 and 0066) and illustrated as a rectangle with no structural elements (see, e.g., Fig 1:114). Given that the specification provides no structural detail for the identified system element, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph.
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph;
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
Claims 2-11 are rejected as being dependent from, but failing to cure the deficiencies of, a rejected base claim.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claims do not fall within at least one of the four categories of patent eligible subject matter because the claimed invention is directed to an abstract idea without significantly more. The independent claims recite manipulating or generating interference graphs and managing the placement of data objects based on the interference graph. This judicial exception is not integrated into a practical application because the only additional elements are generically recited computing components. Accordingly, these additional elements do not integrate the abstract idea into a practical application because it does not impose meaningful limits on practicing an abstract idea. The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional elements of using generically recited computing components to perform the listed steps amounts to no more than mere instructions to apply the exception using a generic computer component. Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. Additionally, the applicant appears to explicitly acknowledge that the claimed abstract idea can be practically performed in the mind (see, e.g., ¶0017-0018). The additional limitations of the remaining claims are directed towards common computing elements and introduce variables associated with these components, but they still represent an abstract idea embodied in a generic computer that performs a method that could be done by a human without the aid of a computer. For at least these reasons, the claims are not patent eligible.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim 18 is rejected under 35 U.S.C. 102(a)(1) as being anticipated by GOEBEL (US Patent 6,139,200).
Consider Claim 18,
GOEBEL teaches a method comprising:
receiving an interference graph for a computational task that assigns data objects involved in the computational task to respective locations in a memory (GOEBEL, e.g., Fig 1(104); Col 2:27-59, describes that a received interference graph is to be analyzed.);
identifying that one or more of the respective locations in the memory allocated by the interference graph are unavailable (GOEBEL, e.g., Fig 1(106); Col 2:7-25, identify that there are not enough memory locations for the specified data.);
generating an adapted interference graph that assigns the data objects involved in the computational task to available locations in the memory, responsive to identifying that the one or more of the respective locations in the memory allocated by the interference graph are unavailable (GOEBEL, e.g., Fig 1(112), rebuild the interference graph if memory locations are not available.); and
allocating the memory for the computational task using the adapted interference graph (GOEBEL, e.g., Fig 1; Col 5:6-7, Figure 1 is a flow chart for allocating memory spaces.).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim 19 is rejected under 35 U.S.C. 103 as being unpatentable over GOEBEL in view of NAG et al. (US PGPub No. 2021/0303355), hereinafter referred to as NAG.
Consider Claim 19,
GOEBEL teaches the method of claim 18, above, and further teaches wherein the interference graph is generated at compile time for the computational task (GOEBEL, e.g., Fig 4;Col 7:58-8:26, interference graph is generated by a compiler.), but fails to detail wherein generating the adapted interference graph is performed at runtime for the computational task. NAG is directed towards systems and methods for optimizing data placement in a memory system and is considered analogous prior art. NAG does describe determining an allocation pattern in response to a request to perform a memory operation (NAG, e.g., ¶0038-0039, at runtime). It would have been obvious to a person of ordinary skill in the art, prior to the effective filing date of the claimed invention, to modify the system of GOEBEL wherein generating the adapted interference graph is performed at runtime for the computational task because it is a matter of design choice which avoids errors associated with changes to the memory environment between compilation and runtime.
Claims 1-6 and 10-17 are rejected under 35 U.S.C. 103 as being unpatentable over NAG in view of Peri et al. (US PGPub No. 2005/0289322), hereinafter referred to as PERI.
Consider Claim 1,
NAG teaches a system comprising:
a memory module including a memory and a processing-in-memory circuit (NAG, e.g., Fig 1(104); ¶0018, RAM includes module for processing-in-memory operations.);
a processor including at least one core (NAG, e.g., Fig 1(102), processor.) configured to generate an graph for a computational task that assigns data objects involved in the computational task to respective locations in the memory (NAG, e.g., ¶0044, generate a graph for each processing-in-memory operation (i.e., computational task); ¶0045, allocate memory for data structure operands.); and
an operation scheduler configured to allocate the data objects to the respective locations in the memory and schedule the computational task for execution by the processing-in-memory circuit (NAG, e.g., Fig 2;¶0023 and 0025, describes allocating data objects to respective locations in memory; ¶0024, describes the scheduling of processing-in-memory operations for execution.).
NAG fails to expressly describe the use of an interference graph. PERI is directed towards systems and methods for allocating data according to program variables and is considered analogous prior art. PERI does describe using an interference graph to assign memory locations (PERI, e.g., Fig 7; ¶0021-0023, construct an interference graph.). It would have been obvious to a person of ordinary skill in the art, prior to the effective filing date of the claimed invention, to modify the system of NAG with at least the cited elements of PERI because it minimizes execution time (PERI, e.g., ¶0013).
Consider Claim 2,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph automatically and independent of user input (PERI, e.g., Fig 2; ¶0012,0015, compiler generates interference graph.).
Consider Claim 3,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph based on a number of banks in a channel of the memory that is accessible by the processing-in-memory circuit (NAG, e.g., Fig 2; ¶0026-0029, describes allocating memory based at least on a number of banks in a channel; PERI, e.g., ¶0024, describes generating an interference graph based on memory banks.).
Consider Claim 4,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph by representing each of the data objects involved in the computational task as a node in the interference graph (PERI, e.g., Fig 7; ¶0023, nodes correspond to data objects.).
Consider Claim 5,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph by establishing an edge between a pair of nodes in the interference graph that represent two data objects involved in a common operation of the computational task (PERI, e.g., Fig 7;¶0023, lines represent interferences between objects due to parallel access (i.e., common operation).).
Consider Claim 6,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph by assigning a weight to the edge, wherein the weight is a value representing a computational cost incurred by allocating the two data objects to a common bank in the memory (PERI, e.g., ¶0026, describes using weights based on parallelism; ¶0001, the degree of parallelism in placement affects the number of bank accesses. In other words, the weight represents a computational cost.).
Consider Claim 10,
The combination of NAG and PERI, as combined, further teaches wherein the processor is configured to generate the interference graph with an objective of allocating data objects involved in a common operation for the computational task to different banks in the memory (PERI, e.g., ¶0015, interference graph is based on parallel accesses to the same bank; ¶0012, allocate variables to different banks.).
Consider Claim 11,
The combination of NAG and PERI, as combined, teaches the system of claim 1, above, but fails to additionally describe wherein the operation scheduler is configured to allocate the data objects to the respective locations in the memory and schedule the computational task for execution by the processing-in-memory circuit in response to identifying that the memory is available to allocate the data objects as indicated by the interference graph at runtime for the computational task. The examiner takes official notice of the fact that verifying availability of a required resource before scheduling a task is notoriously well-known in the art and a common feature of human activities (i.e., planning). It would have been obvious to a person of ordinary skill in the art, prior to the effective filing date of the claimed invention, to modify the system of NAG and PERI to schedule the computational task for execution by the processing-in-memory circuit in response to identifying that the memory is available to allocate the data objects as indicated by the interference graph at runtime for the computational task because it provides the obvious benefit of avoiding task failure due to inadequate resources and is extremely common in the art.
Consider Claim 12,
NAG teaches a method comprising:
receiving an operation chain that includes a plurality of operations for execution by a processing-in-memory circuit (NAG, e.g., ¶0023-0024, describes receiving an operation chain that includes a plurality of operations for execution by a PIM circuit.);
generating an graph that assigns data objects involved in the operation chain to respective locations in a memory (NAG, e.g., ¶0044, generate a graph for each processing-in-memory operation (i.e., computational task); ¶0045, allocate memory for data structure operands.); and
allocating the data objects involved in the operation chain to the respective locations in the memory (NAG, e.g., Fig 2;¶0023 and 0025, describes allocating data objects to respective locations in memory.).
NAG fails to expressly describe the use of an interference graph. PERI is directed towards systems and methods for allocating data according to program variables and is considered analogous prior art. PERI does describe using an interference graph to assign memory locations (PERI, e.g., Fig 7; ¶0021-0023, construct an interference graph.). It would have been obvious to a person of ordinary skill in the art, prior to the effective filing date of the claimed invention, to modify the system of NAG with at least the cited elements of PERI because it minimizes execution time (PERI, e.g., ¶0013).
Consider Claim 13,
The combination of NAG and PERI, as combined, further teaches wherein generating the interference graph and allocating the data objects are performed prior to the processing-in-memory circuit executing the operation chain (PERI, e.g., ¶0012, generation and allocation occurs at compile time (i.e., prior to execution).).
Consider Claim 14,
The combination of NAG and PERI, as combined, further teaches wherein generating the interference graph is performed automatically and independent of user input (PERI, e.g., Fig 2; ¶0012,0015, compiler generates interference graph.).
Consider Claim 15,
The combination of NAG and PERI, as combined, further teaches wherein generating the interference graph is performed based on a number of banks in a channel of the memory that is accessible by the processing-in-memory circuit (NAG, e.g., Fig 2; ¶0026-0029, describes allocating memory based at least on a number of banks in a channel; PERI, e.g., ¶0024, describes generating an interference graph based on memory banks.).
Consider Claim 16,
The combination of NAG and PERI, as combined, further teaches wherein generating the interference graph comprises representing each of the data objects involved in the operation chain as a node in the interference graph (PERI, e.g., Fig 7; ¶0023, nodes correspond to data objects.).
Consider Claim 17,
The combination of NAG and PERI, as combined, further teaches wherein generating the interference graph comprises establishing an edge between a pair of nodes in the interference graph that represent two of the data objects involved in a common operation of the operation chain (PERI, e.g., Fig 7;¶0023, lines represent interferences between objects due to parallel access (i.e., common operation).).
Allowable Subject Matter
Claims 7-9 and 20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Gary W Cygiel whose telephone number is (571)270-1170. The examiner can normally be reached Monday - Thursday 11am-3pm PST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Arpan P Savla can be reached at (571) 272-1077. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Gary W. Cygiel/Primary Examiner, Art Unit 2137