11Notice of Pre-AIA or AIA Status
The present application is being examined under the pre-AIA first to invent provisions.
DETAILED ACTION
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the claims at issue are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); and In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on a nonstatutory double patenting ground provided the reference application or patent either is shown to be commonly owned with this application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO internet Web site contains terminal disclaimer forms which may be used. Please visit http://www.uspto.gov/forms/. The filing date of the application will determine what form should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to http://www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claims (1-20) are provisionally rejected on the ground of nonstatutory obviousness-type double patenting as being unpatentable over claims (1-10) respectively of copending U.S. Patent Application No. 16/041,066. This is a provisional obviousness-type double patenting rejection because the conflicting claims have not in fact been patented.
Claims (1-20) are provisionally rejected on the ground of nonstatutory double patenting over claims (1-10) respectively of copending Application No. 16/041,066 in view of prior art. This is a provisional double patenting rejection because the patentably indistinct claims have not in fact been patented. The subject matter claimed in the instant application is fully disclosed in the referenced copending application and would be covered by any patent granted on that copending application since the referenced copending application and the instant application are claiming common subject matter, as follows:
The claim similarities of the current application and application 16/041,066 are provided in the table below.
INSTANT APPLICATION
U.S. PATENT APPLICATION 16/041,066 in view of prior art
1, 14, 17, 20. A scheduler for a graphics rendering system for performing graphics computation, said scheduler being configured to: identify two instances of graphics computation whose concurrent execution could cause a memory conflict in accessing a memory of the graphics rendering system; and in response to identifying the two instances of graphics computation whose concurrent execution could cause a memory conflict in accessing the memory, adjust the scheduling of execution on a plurality of computation units of the graphics rendering system of both of the identified two instances of graphics computation whose concurrent execution could cause a memory conflict in accessing the memory, so as to avoid the memory conflict.
2, 18. The scheduler of claim 1, wherein adjusting the scheduling of execution of both of the identified two instances of graphics computation results in a reduction in a time taken to execute at least one of the identified instances of graphics computation (See mapping of claim 2 below).
3. The scheduler of claim 1, wherein the two instances of graphics computation whose concurrent execution could cause a memory conflict in accessing the memory are identified prior to scheduling the execution of the two instances of graphics computation (See mapping of claim 3 below).
4. The scheduler of claim 1, wherein adjusting the scheduling of execution of both of the identified two instances of graphics computation comprises serializing the execution of the identified two instances of graphics computation on the computation units (See claim 1 of 16/041,066).
5. The scheduler of claim 1, wherein the scheduler is configured to adjust an execution priority of at least one of the identified instances of graphics computation and the scheduling of execution of both of the identified two instances of graphics computation is adjusted in dependence on the adjusted execution priority (See mapping of claim 5 below).
6, 19. The scheduler of claim 1, wherein the scheduler comprises a serializer which is configured to fill available computation slots for the computation units with scheduled instances of graphics computation, and wherein the serializer is configured to: determine, during each execution cycle, whether any of the instances of graphics
computation to be executed during that execution cycle make conflicting accesses to the memory; and if it is determined that two or more instances of graphics computation to be executed during an execution cycle make conflicting accesses to the memory, providing one or more substitute instances of graphics computation to be executed instead of a respective one or more of said two or
more instances of graphics computation (See claim 2 of 16/041,066).
7. The scheduler of claim 1, wherein the scheduler is configured to schedule instances of graphics computation for execution by the computation units according to a scheduling key (See claim 3 of 16/041,066).
8. The scheduler of claim 1, wherein some of the instances of graphics computation are reentrant and other ones of the instances of graphics computation are non-reentrant (See claim 4 of 16/041,066).
9. The scheduler of claim 1, wherein only non-reentrant instances of graphics computation cause potential memory conflicts in accessing the memory (See claim 5 of 16/041,066).
10. The scheduler of claim 1, wherein the scheduler comprises a profiler configured to profile program code and to flag instances of graphics computation as being re-entrant or non-reentrant (See claim 6 of 16/041,066).
11. The scheduler of claim 1, wherein the scheduler is configured to determine whether a computation instance is re-entrant or non-reentrant by comparing a memory location in the memory referenced by the computation instance with a set of memory locations identified as containing data associated with non-reentrant computation instances (See claim 7 of 16/041,066).
12. The scheduler of claim 1, wherein the scheduler is configured to categorize a computation instance as non-reentrant by comparing a memory location in the memory referenced by the computation instance with a set of memory locations identified as containing data and which can be written by a set of computation instances currently scheduled for execution (See claim 8 of 16/041,066).
13. The scheduler of claim 1, wherein adjusting the scheduling of both of the identified two instances of graphics computation results in an increase to an allocation of computation resources to
at least one of the identified instances of graphics computation (See mapping to claim 13 below).
15. The system of claim 14, wherein the computation units are configured to operate as Single Instruction Multiple Data (SIMD) computation units (See claim 9 of 16/041,066).
16. The system of claim 14, wherein the system is a ray tracing system and wherein the graphics computation is ray tracing computation (See claim 10 of 16/041,066).
1. A graphics rendering system for performing graphics computation, comprising: a memory for storing variables for use in graphics computation; a plurality of computation units configured to execute instances of graphics computation for updating variables in the memory; and a scheduler configured to schedule instances of graphics computation for execution by the computation units, wherein the scheduler is configured to: identify instances of graphics computation whose concurrent execution could cause a memory conflict in accessing the memory; and schedule the execution of the identified instances of graphics computation to thereby serialize the execution of the identified instances of graphics computation on the computation units to avoid the memory conflict.
2. The graphics rendering system of claim 1 wherein the scheduler comprises a serializer which is configured to fill available computation slots for the computation units with scheduled instances of graphics computation, and wherein the serializer is configured to: determine, during each execution cycle, whether any of the instances of graphics computation to be executed during that execution cycle make conflicting accesses to the memory; and if it is determined that two or more instances of graphics computation to be executed during an execution cycle make conflicting accesses to the memory, providing one or more substitute instances of graphics computation to be executed instead of a respective one or more of said two or more instances of graphics computation.
3. The system of claim 1 wherein the scheduler is configured to schedule instances of graphics computation for execution by the computation units according to a scheduling key.
4. The system of claim 1 wherein some of the instances of graphics computation are reentrant and other ones of the instances of graphics computation are non-reentrant.
5. The system of claim 1 wherein only non-reentrant instances of graphics computation cause potential memory conflicts in accessing the memory.
6. The system of claim 1 wherein the scheduler comprises a profiler configured to profile program code and to flag instances of graphics computation as being re-entrant or non-reentrant.
7. The system of claim 1 wherein the scheduler is configured to determine whether a computation instance is re-entrant or non-reentrant by comparing a memory location in the memory referenced by the computation instance with a set of memory locations identified as containing data associated with non-reentrant computation instances.
8. The system of claim 1 wherein the scheduler is configured to categorize a computation instance as non-reentrant by comparing a memory location in the memory referenced by the computation instance with a set of memory locations identified as containing data and which can be written by a set of computation instances currently scheduled for execution.
9. The system of claim 1 wherein the computation units are configured to operate as Single Instruction Multiple Data (SIMD) computation units.
10. The system of claim 1 wherein the system is a ray tracing system and wherein the graphics computation is ray tracing computation.
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-5, 7-10, 13-18, 20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding independent claims, the limitations identify computations and adjust scheduling, as drafted, recites functions that, under its broadest reasonable interpretation, covers a function that could reasonably be performed in the mind, including with the aid of pen and paper, but for the recitation of generic computer components. That is, the limitations as cited above as drafted, are functions that, under its broadest reasonable interpretation, recite the abstract idea of a mental process.
Thus, these limitation falls within the “Mental Processes” grouping of abstract ideas under Prong 1.
Under Prong 2, this judicial exception is not integrated into a practical application. The claim recites the following additional limitations: memory, computation units, medium. The additional elements are recited at a high-level of generality such that it amounts no more than mere instructions to apply the exception using generic computer, and/or mere computer components, MPEP 2106.05(f). Accordingly, the additional elements do not integrate the recited judicial exception into a practical application and the claim is therefore directed to the judicial exception. See MPEP 2106.05(g) (Ex. v. Consulting and updating an activity log, Ultramercial, 772 F.3d at 715, 112 USPQ2d at 1754).
Under Step 2B, the claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements of memory, computation units, medium, amount to no more than mere instructions, or generic computer/computer components to carry out the exception. See MPEP 2106.05(d) (Ex. iv. Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93;).
The recitation of generic computer instruction and computer components to apply the judicial exception, and mere data gathering do not amount to significantly more, thus, cannot provide an inventive concept. Accordingly, the claims are not patent eligible under 35 USC 101.
Regarding claim 2, 3, 4, 5, 8, 10, 13, 14, 18, the limitations of adjusting scheduling, identifying prior to scheduling, adjusting priority, ordering the scheduling, determining a type of task, updating variables, are functions that can be reasonably performed in the human mind, thus, additional mental process defined in the claims. The claim does not include any additional element, thus, no limitation that needs to be analyzed under prong 2 for practical application, or under step 2B for significantly more.
Regarding claim 7, 9, 15, 16, the limitation of utilizing a scheduling key, defining a type of task, type of computation units, type of system, are considered mere instructions, or generic computer/computer components to carry out the exception Accordingly, the additional element recited in claim 3 fails to provide a practical application under prong 2, or amount to significantly more under step 2B.
Claim Interpretation - 35 USC § 112
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.
Claim limitations 1-13 has/have been interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because it uses/they use a generic placeholder “scheduler”, “serializer”, “profiler” coupled with functional language without reciting sufficient structure to achieve the function. Furthermore, the generic placeholder is not preceded by a structural modifier. Since the claim limitation(s) invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, claim 13 has/have been interpreted to cover the corresponding structure described in the specification that achieves the claimed function, and equivalents thereof.
A review of the specification, Fig. 5 [0029] shows that the following appears to be the corresponding structure described in the specification for the 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph limitation.
If applicant wishes to provide further explanation or dispute the examiner’s interpretation of the corresponding structure, applicant must identify the corresponding structure with reference to the specification by page and line number, and to the drawing, if any, by reference characters in response to this Office action.
If applicant does not intend to have the claim limitation(s) treated under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112 , sixth paragraph, applicant may amend the claim(s) so that it/they will clearly not invoke 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, or present a sufficient showing that the claim recites/recite sufficient structure, material, or acts for performing the claimed function to preclude application of 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
For more information, see MPEP § 2173 et seq. and Supplementary Examination Guidelines for Determining Compliance With 35 U.S.C. 112 and for Treatment of Related Issues in Patent Applications, 76 FR 7162, 7167 (Feb. 9, 2011).
Claim Rejections - 35 USC § 103
The following is a quotation of pre-AIA 35 U.S.C. 103(a) which forms the basis for all obviousness rejections set forth in this Office action:
(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if 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. Patentability shall not be negatived by the manner in which the invention was made.
Claims 1-5, 7-9, 13, 17, 18, 20 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar (Pat. No. US 8,918,791) in view of Abrashkevich (Pub. No. US 2009/0217018) in further view of Schreyer (Pub. No. US 2009/0225089).
Claim 1, 17, 20 Chudgar teaches “a scheduler for a … system for performing … computation, said scheduler being configured to: identify two instances of … computation whose concurrent execution could cause a memory conflict in accessing a memory of the … system ([Fig. 2] requests 1-0 to 1-n; Examiner notes Abrashkevich teaches as evidence the purposes of granting locks of Chudgar to access shared memory by multi processes are to prevent conflicts and therefore would be obvious to one of ordinarily skilled in the art, Chudgar scheduling of tasks is to prevent corruption of memory [0004] Concurrent computing generally refers to the simultaneous execution of multiple tasks, usually on a multiprocessor system. These tasks are often implemented by a set of threads (short for "thread of execution") contained by a process (an executing computer program). The threads of a particular process often access the same data structures in memory. Allowing multiple threads to access the same data structures may lead to consistency problems and locking techniques are often used to prevent threads from interfering with each other and corrupting memory. For example, if a first thread is modifying a particular data structure in memory, then the data structure may be "locked" to prevent a second thread from accessing or modifying the data structure until the lock is released. Locking, however, is particularly pessimistic. That is, the data structure remains locked to the second thread regardless of whether concurrent access by both threads would lead to an inconsistency).); and in response to identifying the two instances of … computation whose concurrent execution could cause a memory conflict in accessing the memory, adjust the scheduling of execution on a plurality of computation units of the … system of both of the identified two instances of … computation whose concurrent execution could cause a memory conflict in accessing the memory, so as to avoid the memory conflict ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied. Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order if no other requests are subsequently received.)”.
However, the combination may be silent regarding the type of requests.
Schreyer teaches as evidence requests of Chudgar may be graphic based computations such that teaches “graphics rendering system … graphics computation ([0024] Advantageously, in certain embodiments, computing device 100 can be configured such that graphical operations in computing system 100 can be performed more efficiently than in previous devices. In other embodiments, computing device 100 can be configured such that computing device 100 can efficiently process multiple graphics processing requests and/or contexts from one or more applications executed within or received by computing device 100.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Schreyer with the teachings of Chudgar, Abrashkevich in order to provide a system that explicitly teaches graphics-based systems. The motivation for applying Schreyer teaching with Chudgar, Abrashkevich teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Schreyer with the teachings of Chudgar, Abrashkevich by known methods and gained expected results.
Claim 2, 18, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein adjusting the scheduling of execution of both of the identified two instances of graphics computation results in a reduction in a time taken to execute at least one of the identified instances of graphics computation ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied. Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order if no other requests are subsequently received. [Col. 5, Line 48] That way, conventional deadlock problems can also be avoided.)”.
Claim 3, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein the two instances of graphics computation whose concurrent execution could cause a memory conflict in accessing the memory are identified prior to scheduling the execution of the two instances of graphics computation ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied. Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order if no other requests are subsequently received)”.
Claim 4, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein adjusting the scheduling of execution of both of the identified two instances of graphics computation comprises serializing the execution of the identified two instances of graphics computation on the computation units ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied. Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order if no other requests are subsequently received)”.
Claim 5, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein the scheduler is configured to adjust an execution priority of at least one of the identified instances of graphics computation and the scheduling of execution of both of the identified two instances of graphics computation is adjusted in dependence on the adjusted execution priority ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied. Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order if no other requests are subsequently received)”.
Claim 7, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein the scheduler is configured to schedule instances of graphics computation for execution by the computation units according to a scheduling key ([Claim 1] 1. A method for queuing a request by a processor to access a shared resource, comprising: receiving the request to access the shared resource, from a processor of a plurality of processors executing an application; determining a queue order for a reply to the request based at least in part on the processor issuing the request and on a resource access priority level of the application executed by the processor; generating the reply to the request comprising a grant to the shared resource with an embedded lock ID, wherein the embedded lock ID enables access to the shared resource for a predetermined length of time;)”.
Claim 8, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein some of the instances of graphics computation are reentrant and other ones of the instances of graphics computation are non-reentrant ([Col. 4, Lines 49-58] (18) FIG. 2 is a schematic representation of a shared resource locking process. The QM 110 received requests 1-1 and 1-2 simultaneously. Giving priority to the lowest numbered FIFO of the two FIFOs 111-1 and 111-2, request 1-1 is dequeued first and a grant is issued. Grants for requests 1-2, 1-0, and 1-n are denied (i.e. non-renentrant). Requests 2-0, 2-1, 2-2, and 2-n are then enqueued simultaneously. Based upon a round robin allocation process, request 2-2 is dequeued first and a grant is issued. The other requests are initially denied, but then granted in round robin order (i.e. reentrant) if no other requests are subsequently received)”.
Claim 9, the combination teaches the claim, wherein Abrashkevich teaches “the scheduler of claim 1, wherein only non-reentrant instances of graphics computation cause potential memory conflicts in accessing the memory ([0004] Concurrent computing generally refers to the simultaneous execution of multiple tasks, usually on a multiprocessor system. These tasks are often implemented by a set of threads (short for "thread of execution") contained by a process (an executing computer program). The threads of a particular process often access the same data structures in memory. Allowing multiple threads to access the same data structures may lead to consistency problems and locking techniques are often used to prevent threads from interfering with each other and corrupting memory. For example, if a first thread is modifying a particular data structure in memory, then the data structure may be "locked" to prevent a second thread from accessing or modifying the data structure until the lock is released. Locking, however, is particularly pessimistic. That is, the data structure remains locked to the second thread regardless of whether concurrent access by both threads would lead to an inconsistency)”.
Rationale to claim 1 is applied here.
Claim 13, the combination teaches the claim, wherein Chudgar teaches “the scheduler of claim 1, wherein adjusting the scheduling of both of the identified two instances of graphics computation results in an increase to an allocation of computation resources to at least one of the identified instances of graphics computation ([Col. 3, Lines 54-67](11) The resource allocator 118 includes an allocation microprocessor 120, and an allocation application 122, enabled as a sequence of instructions stored in the memory 104 and executed by the allocation microprocessor 120, for tracking shared resource status and allocations. As noted above, in a simple aspect of the system 102, the QM hardware allocation scheme is the de facto means of allocating resources to requesting applications. However, the allocation application 122 may be designed to give resource access priority to some applications (or some processors), over other applications. Further, it should be understood that although the QM may be seen as the de {octo resource allocator, the allocation application 122 is required to track available resources, in-use resources, and scheduled resource use.)”.
Claims 6, 19 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Minkin (Pub. No. US 2011/0082961).
Claim 6, 19, the combination may not explicitly teach the limitation.
Minkin teaches “the scheduler of claim 1, wherein the scheduler comprises a serializer which is configured to fill available computation slots for the computation units with scheduled instances of graphics computation, and wherein the serializer is configured to: determine, during each execution cycle, whether any of the instances of graphics computation to be executed during that execution cycle make conflicting accesses to the memory; and if it is determined that two or more instances of graphics computation to be executed during an execution cycle make conflicting accesses to the memory, providing one or more substitute instances of graphics computation to be executed instead of a respective one or more of said two or more instances of graphics computation ([0067] In a write collapse operation, the conflict resolution unit 406 selects one of the write data requests that are associated with addresses that identify the same memory location for writing the data associated with the write data request to the memory location. The remaining write data requests are discarded. The selection of the write data request can be based on any technically feasible criteria. In one embodiment, the selection is based on the specific client subsystem 401 that transmitted the selected write data request having a higher priority than the client subsystem 401 that is not selected. In a write merge operation, the conflict resolution unit 406 determines that the write data requests that are associated with addresses that identify the same memory location can be processed together. The data associated with different write data requests is merged together such that the data associated with each such write data request fills a pre-determined portion of the memory location. When merged, the data associated with the write data requests fills the entire memory location.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Minkin with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches selecting a different instance. The motivation for applying Minkin teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Minkin are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Minkin teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Minkin with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Claims 10 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Duffy (Pub. No. US 2008/0120298).
Claim 10, the combination may not explicitly teach the limitation.
Duffy teaches “the scheduler of claim 1, wherein the scheduler comprises a profiler configured to profile program code and to flag instances of graphics computation as being re-entrant ([0068] FIG. 16 illustrates one implementation of the stages involved in using a commit arbitrator to detect and handle conflicts that arise while the parallel loop is executing. In one form, the process of FIG. 16 is at least partially implemented in the operating logic of computing device 100. The process begins at start point 600 with transforming an original sequential loop into a parallel loop using a pre-determined commit order process to ensure proper ordering (stage 602). The system executes the parallel loop (stage 604). The system then detects that the parallel loop contains more than one of the separate transactions (e.g. loop iterations) that will modify the same data element (e.g. because of lacking thread safety, because of ordering requirements, etc.) (stage 606). A commit arbitrator is used to detect and handle conflicts that arise while the parallel loop is executing, such as by detecting out-of-order executions and arranging for re-execution of successor transactions once predecessor transactions have completed (stage 608). The process ends at end point 610.) or non-reentrant”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Duffy with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches determine which instances may be rescheduled. The motivation for applying Duffy teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Duffy are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Duffy teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Duffy with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Claims 11, 12 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Saha (Pub. No. US 2007/0233970).
Claim 11, the combination may not explicitly teach the limitation.
Saha teaches “the scheduler of claim 1, wherein the scheduler is configured to determine whether a computation instance is re-entrant or non-reentrant by comparing a memory location in the
memory referenced by the computation instance with a set of memory locations identified as containing data associated with non-reentrant computation instances ([0009] Thus, for example, if a program being executed by a processor attempts a transactional read from a memory location using the services of the STM, at an address A, the STM system first computes a hash of the address of that memory location. The STM system then computes the reader-writer lock corresponding to the hash, L. The system then tries to acquire a read lock on L. If the STM system succeeds, the STM system then returns the value at location A and stores an indication into the transaction-local read set that the STM system has obtained a read lock on L. Similarly, if the program attempts a transactional write to a memory location using the services of an STM, at an address A, the STM computes the reader-writer lock, L as before, and then tries to acquire an exclusive write lock on L. If STM system succeeds, the STM system then updates the memory location A and keeps a copy of the old value of A in a log, in case the transaction has to be rolled back. In addition, the STM system also stores an indication into a transaction-local write set that the STM system has acquired a write lock on L. [0010] If implementation of a transaction by the STM system fails to acquire either a reader or writer lock in this implementation, the STM system retries after a back-off period, which may be a randomly determined period of time. A fixed number of retries is allowed, after which the STM system aborts the transaction and all locks are released. A counter may be used to track the number of retries in some embodiments. Any memory locations modified after the start of the transaction are also returned to their original value, based on the logs that have been maintained by the STM system for this transaction. This abort mechanism is intended to prevent deadlocks.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Saha with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches determine which instances may be rescheduled. The motivation for applying Saha teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Saha are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Saha teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Saha with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Claim 12, the combination may not explicitly teach the limitation.
Saha teaches “the scheduler of claim 1, wherein the scheduler is configured to categorize a computation instance as non-reentrant by comparing a memory location in the memory referenced by the computation instance with a set of memory locations identified as containing data and which can be written by a set of computation instances currently scheduled for execution ([0009] Thus, for example, if a program being executed by a processor attempts a transactional read from a memory location using the services of the STM, at an address A, the STM system first computes a hash of the address of that memory location. The STM system then computes the reader-writer lock corresponding to the hash, L. The system then tries to acquire a read lock on L. If the STM system succeeds, the STM system then returns the value at location A and stores an indication into the transaction-local read set that the STM system has obtained a read lock on L. Similarly, if the program attempts a transactional write to a memory location using the services of an STM, at an address A, the STM computes the reader-writer lock, L as before, and then tries to acquire an exclusive write lock on L. If STM system succeeds, the STM system then updates the memory location A and keeps a copy of the old value of A in a log, in case the transaction has to be rolled back. In addition, the STM system also stores an indication into a transaction-local write set that the STM system has acquired a write lock on L. [0010] If implementation of a transaction by the STM system fails to acquire either a reader or writer lock in this implementation, the STM system retries after a back-off period, which may be a randomly determined period of time. A fixed number of retries is allowed, after which the STM system aborts the transaction and all locks are released. A counter may be used to track the number of retries in some embodiments. Any memory locations modified after the start of the transaction are also returned to their original value, based on the logs that have been maintained by the STM system for this transaction. This abort mechanism is intended to prevent deadlocks.)”.
Rationale to claim 11 is applied here.
Claims 14 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Wu (Pub. No. US 2011/0057937).
Claim 14, “a graphics rendering system for performing graphics computation comprising: a memory for storing variables for use in graphics computation; and the scheduler as set forth in claim 1” is similar to claim 1 and therefore rejected with the same references and citations.
However, the combination may not explicitly teach updating variables.
Wu teaches “a plurality of computation units being configured to execute instances of graphics computation for updating variables in the memory ([0029] The parallel processed data may be further subdivided 208 into a plurality of data blocks or data clusters 210 or sub-datasets that can be distributed or assigned to the plurality of processing cores of a GPU. The data blocks may be sent to the processing cores. Each operating processing core may receive a data block. The parallel processed data 206 may be subdivided into data blocks prior to being sent to the GPU or may be subdivided into data blocks by the GPU. The GPU may process the data block in parallel on the processing cores 212 with an intermediate processed data 214 resulting from each data block processed. The intermediate processed data may be sent from the GPU to global memory. The data blocks and intermediate processed data may be stored in global memory, shared memory, constant cache, texture cache, local GPU memory, or other GPU memory. Intermediate processed data may be stored in main memory 216. The CPU may receive intermediate processed data and sequentially processed data and process 218 intermediate processed data and sequentially processed data. The CPU may generate result data 220 from intermediate processed data and sequentially processed data.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Wu with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches updating contents of memory. The motivation for applying Wu teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Wu are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Wu teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Wu with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Claims 15 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Buck (Pat. No. US 7,627,723).
Claim 15, the combination may not explicitly teach the limitation.
Buck teaches “the system of claim 14, wherein the computation units are configured to operate as Single Instruction Multiple Data (SIMD) computation units ([Fig. 5, Lines 57-62] (34) In a multi-threaded processing unit such as GPU 122, these atomic instructions can be used to prevent memory access conflicts amongst different threads. As previously described, GPU 122 may support SIMD instructions issued across P processing engines 402, with each engine supporting G threads, resulting in P*G threads in flight concurrently.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Buck with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches types of processors. The motivation for applying Buck teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Buck are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Buck teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Buck with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Claims 16 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Chudgar, Abrashkevich, Schreyer in further view of Mejdrich (Pub. No. US 2011/0283086).
Claim 16, the combination may not explicitly teach the limitations.
Mejdrich teaches “the system of claim 14, wherein the system is a ray tracing system and wherein the graphics computation is ray tracing computation ([0088] An ADS may be used to enable a physical rendering algorithm such as a ray tracing algorithm to quickly and efficiently determine with which regions of a scene an issued ray intersects any objects within a scene to be rendered. An ADS may be implemented, for example, as a spatial index, which divides a three-dimensional scene or world into smaller volumes (smaller relative to the entire three-dimensional scene) which may or may not contain primitives. An image processing system can then use the known boundaries of these smaller volumes to determine if a ray may intersect primitives contained within the smaller volumes. If a ray does intersect a volume containing primitives, then a ray intersection test can be run using the trajectory of the ray against the known location and dimensions of the primitives contained within that volume. If a ray does not intersect a particular volume then there is no need to run ray-primitive intersection tests against the primitives contained within that volume. Furthermore, if a ray intersects a bounding volume that does not contain primitives then there is no need to run ray-primitive intersections tests against that bounding volume. Thus, by reducing the number of ray-primitive intersection tests that may be necessary, the use of a spatial index greatly increases the performance of a ray tracing image processing system. Some examples of different spatial index acceleration data structures are oct-trees, k dimensional Trees (kd-Trees), and binary space partitioning trees (BSP trees). While several different spatial index structures exist, and may be used in connection with the physical rendering techniques disclosed herein, the illustrated embodiments rely on a branch tree implemented as a base b tree split up into smaller trees of depth k.)”.
It would have been obvious to one of ordinary skill in the art at the time of the invention was made to apply the teachings of Buck with the teachings of Chudgar, Abrashkevich, Schreyer in order to provide a system that explicitly teaches types of processors. The motivation for applying Buck teaching with Chudgar, Abrashkevich, Schreyer teaching is to provide a system that allows for design choice. Chudgar, Abrashkevich, Schreyer, Buck are analogous art directed towards shared resources. Together Chudgar, Abrashkevich, Schreyer, Buck teach every limitation of the claimed invention. Since the teachings were analogous art known at the time of invention, one of ordinary skill could have applied the teachings of Buck with the teachings of Chudgar, Abrashkevich, Schreyer by known methods and gained expected results.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WYNUEL S AQUINO whose telephone number is (571)272-7478. The examiner can normally be reached 9AM-5PM EST M-F.
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, Lewis Bullock can be reached at 571-272-3759. 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.
/WYNUEL S AQUINO/Primary Examiner, Art Unit 2199
Prosecution Insights