DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending.
Response to Arguments
Regarding: Prior Art Rejections:
Applicant’s amendments and arguments regarding the rejection of claims 1-9, 12, 13, and 18-20 under 35 U.S.C. 102(a)(2) have been fully considered and are found to be not persuasive. The rejections of claims 1-9, 12, 13, and 18-20 under 35 U.S.C. 102(a)(2) are maintained. The rejections of claims 10, 11, 14, 15, and 17 under 35 U.S.C. 103 are maintained.
Examiner appreciates applicant’s clarification of the invention. Applicant’s remarks recite:
Mantor does not describe a resource allocator being configured to, in response to receiving the shared memory resource request for first memory resources in respect of the first-received task of a workgroup, allocate to the entire workgroup a block of memory portions of a shared memory. Instead, as referenced above, Mantor describes determining the size of the memory block required for each of its individual threads by determining how many of its threads require memory allocations and/or how much of a total memory allocation is required for its threads (see paragraph 0044, cited in the rejection). Mantor therefore describes allocating a memory block to an entire workgroup by looking at the memory requirements of each thread of that work group, and not in respect of the first-received task of the workgroup.
Examiner contends applicant’s claimed invention remains within the teachings of Mantor. Examiner’s broadest reasonable interpretation of the claimed resource allocator is as follows:
receive a memory resource request for first memory resources in respect of a first- received task of a workgroup, the workgroup comprising a plurality of tasks (A resource allocator is able to receive requests for allocations of a piece of memory. The first memory resources to have a relation to a first task in a workgroup of tasks).
in response to receiving the memory resource request, allocate to the entire workgroup a block of memory portions of a shared memory that is sufficient in size for each task of the workgroup to receive memory resources in the block equivalent to the first memory resources (When the resource allocator services the request for memory, a piece of memory is reserved to be shared among the tasks in the workgroup of tasks. This piece of memory is large enough for each task to have a memory allocation the same size as the first memory resources for the first task).
The distinction within applicant’s arguments is that the claimed invention is to reserve memory enough to equally divide into sections equal to the size of a first memory resource in respect to a first task. The memory allocator of Mantor is capable of the claimed reserving a block of memory large enough for each thread of a wavefront to receive an equal subsection of the block with respect to a first thread (Mantor [0047] In an embodiment where each thread in a wavefront that requires a memory allocation (i.e., each task in a workgroup) is allocated sub-blocks of the same size; [0054] each wavefront may update the global memory block counter with a number of sub-blocks required for its threads where it is known that all sub-blocks are of the same size).
Claim Rejections - 35 USC § 102
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.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-9, 12, 13, 18-20 are rejected under 35 U.S.C. 102(a)(2) as being anticipated over Mantor et al. US 20110055511 A1.
Regarding claim 1, Mantor teaches the invention as claimed including:
A resource allocator ([0011] a compact memory allocator) configured to:
receive a memory resource request for first memory resources in respect of a first- received task of a workgroup ([0042] A wavefront is considered to have detected a request for memory allocation when at least one thread in that wavefront has detected a request for memory allocation), the workgroup comprising a plurality of tasks ([0029] a wavefront as a group of threads executing on a single SIMD processor. For example, the wavefront on SIMD processor 111 can include 64 threads, each concurrently processing a separate pixel of the same image); and
in response to receiving the memory resource request, allocate to the entire workgroup a block of memory portions of a shared memory that is sufficient in size for each task of the workgroup to receive memory resources in the block equivalent to the first memory resources ([0044] In step 207, each wavefront determines the size of the memory block required for its threads. In this step, each wavefront determines how many of its threads require memory allocations and/or how much of a total memory allocation is required for its threads; [0045] In step 209, a memory block is allocated to a wavefront. The size of the memory block allocated corresponds to, or is based on, the size determined in step 207).
Regarding claim 2, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein each task of the workgroup is a single- instruction multiple data (SIMD) task ([0029] the following description considers a wavefront as a group of threads executing on a single SIMD processor. For example, the wavefront on SIMD processor 111 can include 64 threads, each concurrently processing a separate pixel of the same image).
Regarding claim 3, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the memory resource request indicates the size of memory resources required for the first-received task of the workgroup ([0044] each wavefront determines the size of the memory block required for its threads), and wherein the block of memory portions is allocated based on the indicated size of the memory resources required for that task ([0045] The size of the memory block allocated corresponds to, or is based on, the size determined in step 207).
Regarding claim 4, Mantor teaches the resource allocator of claim 3.
Mantor further teaches wherein the size of the allocated block of memory portions is at least N times the size of the memory resources indicated in the memory resource request, where N is the number of tasks in the workgroup ([0047] each thread calculates the starting address of its memory sub-block).
Regarding claim 5, Mantor teaches the resource allocator of claim 1.
Mantor further teaches further configured to receive, with the memory resource request, an indication of the number of tasks in the workgroup ([0044] each wavefront determines how many of its threads require memory allocations and/or how much of a total memory allocation is required for its threads).
Regarding claim 6, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the resource allocator is configured to allocate the block of memory portions as a contiguous block of memory portions ([0025] Embodiments of the present invention also ensure that the memory allocated to threads are contiguous).
Regarding claim 7, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the resource allocator is configured to, on servicing the first-received task of the workgroup, allocate to that task the requested first memory resources from the block and reserve the remaining memory portions of the block so as to prevent allocation to tasks of other workgroups ([0040] it may be preconfigured that the first dispatched thread in a wavefront includes the functionality to perform steps 203-209 on behalf of all the threads in the wavefront).
Regarding claim 8, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the resource allocator is configured to, in response to subsequently receiving a memory resource request in respect of a second-received task of the workgroup, allocate memory resources of the block to that second- received task ([0043] Each thread in the wavefront that detects a request for memory allocation, for example, a pending write instruction, accesses functions for having its sub-block (blocks refer to memory allocations for wavefronts and sub-blocks refer to memory allocations for threads) of memory allocated. In the SIMD processing environment of this example, multiple threads are likely to detect a corresponding request for memory allocation at substantially the same time. Having detected that at least one of its constituent threads require a memory allocation, the wavefront then accesses the procedures for obtaining its memory block allocated).
Regarding claim 9, Mantor teaches the resource allocator of claim 8.
Mantor further teaches wherein the resource allocator is configured to allocate a first portion of the block of memory portions to the first-received task, and to allocate a second portion of the block of memory portions to the second-received task, the second portion being adjacent to the first portion within the memory block ([0048] steps 205-213 enable the allocation of contiguous memory blocks to respective wavefronts launched in step 201. The memory allocated by process 200 is contiguously allocated selectively only to threads that have a pending write to memory).
Regarding claim 12, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the resource allocator is further configured to maintain a fine status array arranged to indicate whether each memory portion of the shared memory is allocated to a task ([0030] The thread memory counter associated with each SIMD processor can, in some embodiments, be implemented as a bit mask or vector having a corresponding bit position for each of a maximum number of threads that may concurrently execute on the associated SIMD processor … Using a 64-bit mask as thread memory counter 117 enables SIMD processor 111 to keep track of the memory requirements of each concurrent thread. It should be understood that thread memory counter 117, for example, can be implemented as an incrementing counter that can be used to keep track of the memory requirements of each concurrent thread).
Regarding claim 13, Mantor teaches the resource allocator of claim 12.
Mantor further teaches wherein the resource allocator is configured to, in response to receiving the memory resource request in respect of the first-received task of the workgroup, search a current window for a contiguous block of memory portions which are indicated by the fine status array as being available for allocation, the resource allocator being configured to, if such a contiguous block is identified in the current window, allocate that contiguous block to the workgroup ([0065] an incrementing counter implementation of the thread memory counter can facilitate threads in a wavefront to allocate different sizes of sub-blocks; [0090] each wavefront receives a different value for the global memory block counter pre-operation value; [0091] the global memory block counter is updated to reflect the assignment of the memory block to the subject reader wavefront. In an embodiment of the present invention, a message from the subject reader wavefront can trigger global memory access coordinator 113 to perform the steps of acquiring access to the wavefront atomic operation for the subject reader wavefront, assigning memory for the subject reader wavefront, and releasing the subject reader wavefront from the wavefront atomic operation. The message received from the subject reader wavefront can include a number of parameters including, for example, the size of the memory block required by the subject reader wavefront; Examiner notes: the global memory block counter indicates the window/starting point of the wavefront’s assigned memory block which is modified based upon the amount of memory required by the threads of the wavefront represented in the thread memory counter).
Regarding claim 18, Mantor teaches the resource allocator of claim 1.
Mantor further teaches the resource allocator being implemented within a memory subsystem for use with a processor comprising a plurality of processing units configured for processing one or more workgroups each comprising a plurality of tasks, the memory subsystem further comprising the shared memory that is partitioned into a plurality of memory portions for allocation to tasks that are to be processed by the processor (Fig 1, SIMD Proc 1, 2, etc., Data Memory 107).
Regarding claim 19, it is the method of claim 1. Therefore, it is rejected for the same reasons as claim 1.
Regarding claim 20, it is the non-transitory computer readable storage medium of claim 1. Therefore, it is rejected for the same reasons as claim 1.
Mantor further teaches non-transitory computer readable storage medium having stored thereon a computer readable dataset description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a resource allocator configured to (Claim 20 A computer readable media storing instructions wherein said instructions when executed are adapted to allocate).
Claim Rejections - 35 USC § 103
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.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Mantor et al. US 20110055511 A1 in view of Jula US 20110154346 A1.
Regarding claim 10, Mantor teaches the resource allocator of claim 1.
Mantor further teaches wherein the resource allocator is arranged to receive memory resource requests from a plurality of different requestors ([0043] Each thread in the wavefront that detects a request for memory allocation)
Mantor does not explicitly teach in response to allocating the block of memory portions to the workgroup, preferentially service memory requests received from the requestor from which the first-received task of that workgroup was received.
However, Jula teaches in response to allocating the block of memory portions to the workgroup, preferentially service memory requests received from the requestor from which the first-received task of that workgroup was received ([0010] a multi-core processor wherein relations between queues and cores are affinity relations wherein execution resumption of suspended tasks has priority on the core that originally executed the tasks partly before suspension).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Jula’s task prioritizing with the system of Mantor. A person of ordinary skill in the art would have been motivated to make this combination to provide Mantor’s system with the advantage of improved task execution efficiency (see Jula [0103] Arrows F and G indicate the preference that the execution of suspended tasks (S-tasks) has priority over N-tasks. For suspended tasks, the core may have data in the cache that could be reused when the core resumes execution).
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Mantor et al. US 20110055511 A1 in view of Braverman et al. US 10467045 B1.
Regarding claim 11, Mantor teaches the resource allocator of claim 1.
Mantor does not explicitly teach wherein the resource allocator is further configured to, in response to receiving an indication that processing of a task of the workgroup has completed, deallocate the memory resources allocated to that task without waiting for processing of the workgroup to complete.
However, Braverman teaches wherein the resource allocator is further configured to, in response to receiving an indication that processing of a task of the workgroup has completed, deallocate the memory resources allocated to that task without waiting for processing of the workgroup to complete (terminating the task 2-tsk-1 when the task ends; and then immediately releasing the sub-set 4-sub-1 of the physical memory 4-mem for usage by other tasks, and regardless of said setting of memory values which are now no longer relevant upon said termination, Col 8 3-8).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Bravermans memory freeing with the system of Mantor. A person of ordinary skill in the art would have been motivated to make this combination to provide Mantor’s system with the advantage of on demand resource allocation for tasks (see Pan [0005] When finishing execution of each of the tasks, the system may de-allocated/release the respective sub-set of resources for other tasks or purposes. The result may be that at the time the requestor gets its response, the sub-set of resources that has served the requestor is already allocated by the system to another task; this flow of events demonstrates the real-time potential of the system, which could facilitate massive scaling and the serving of a very large number of requests/isolated execution of tasks concurrently, Col 4 46-55).
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Mantor et al. US 20110055511 A1 in view of Chamberlain et al. US 20070277036 A1.
Regarding claim 14, Mantor teaches the resource allocator of claim 13.
Mantor does not explicitly teach wherein the resource allocator is configured to allocate the contiguous block of memory portions such that the block starts at the lowest possible position in the window.
However, Chamberlain teaches wherein the resource allocator is configured to allocate the contiguous block of memory portions such that the block starts at the lowest possible position in the window ([0171] Allocate(S) if there is a free block of size S allocate the block of size S with the lowest address).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Chamberlain’s memory allocation scheme with the system of Mantor. A person of ordinary skill in the art would have been motivated to make this combination to provide Mantor’s system with the advantage of efficiently allocating memory on disk (see Chamberlain [0170] more greatly ensure contiguous space on the disk for an allocation request. If a contiguous allocation cannot be satisfied, the defragmentation algorithm tries to free space so as to satisfy the allocation request. This defragmentation algorithm does not defragment the entire disk. Instead, it incrementally defragments a portion of the disk to enable the new allocation request to be satisfied in an incremental manner.).
Claim 15 is rejected under 35 U.S.C. 103 as being unpatentable over Mantor et al. US 20110055511 A1 in view of Burrows et al. US 20030126590 A1.
Regarding claim 15, Mantor teaches the resource allocator of claim 13.
Mantor does not explicitly teach wherein the resource allocator is further configured to maintain a coarse status array arranged to indicate, for each window of the shared memory, whether all the memory portions of the window are unallocated, the resource allocator being configured to, in parallel with searching the current window for a contiguous block of memory portions, check the coarse status array to determine whether the size of the requested block can be accommodated by one or more subsequent windows; the resource allocator being configured to, if both a sufficiently large contiguous block cannot be identified in the current window and the requested block can be accommodated by one or more subsequent windows, allocate the block to the workgroup comprising memory portions starting at the first memory portion of the current window in a contiguous block with the subsequent window(s) and extending into those subsequent window(s).
However, Burrows teaches wherein the resource allocator is further configured to maintain a coarse status array arranged to indicate, for each window of the shared memory, whether all the memory portions of the window are unallocated, the resource allocator being configured to, in parallel with searching the current window for a contiguous block of memory portions, check the coarse status array to determine whether the size of the requested block can be accommodated by one or more subsequent windows; the resource allocator being configured to, if both a sufficiently large contiguous block cannot be identified in the current window and the requested block can be accommodated by one or more subsequent windows, allocate the block to the workgroup comprising memory portions starting at the first memory portion of the current window in a contiguous block with the subsequent window(s) and extending into those subsequent window(s) ([0023] the dynamic data-type checker of the present invention presents a novel way to check memory validity and integrity against the requirements of computer program instructions. The data-type checker sets up shadow arrays for all locations of memory--e.g., the registers, stack, and heap. Each location in the shadow arrays corresponds to a location in memory and stores the data type corresponding to that memory location).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Burrows’ memory checker with the system of Mantor. A person of ordinary skill in the art would have been motivated to make this combination to provide Mantor’s system with the advantage of validating memory locations to allocate blocks for Simd operations preventing memory errors (see Burrows [0002] Memory errors occur when a program attempts to access portions of memory for which access is not allowed, or is not appropriate. These types of errors can be fatal and cause application or system crashes because of the likelihood of system corruption, either from writing to portions of memory that store critical values, or reading out values from memory that are critically different than the expected data; [0008] it would be desirable to provide a system and method for dynamically verifying program operation by dynamically checking the integrity of the data types of memory locations accessed during execution of a program).
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over Mantor et al. US 20110055511 A1 in view of Decker et al. US 20180039445 A1.
Regarding claim 17, Mantor teaches the resource allocator of claim 1.
Mantor does not explicitly teach wherein the resource allocator maintains a data structure identifying which of the one or more workgroups are currently allocated a block of memory portions.
However, Decker teaches wherein the resource allocator maintains a data structure identifying which of the one or more workgroups are currently allocated a block of memory portions (Fig 1; [0015] a first array for storing process identifiers. For example, when a process initiates execution, the process identifier for the process can be entered into the first empty location in the first array. The process can include process specific data. One or more blocks of the shared memory can be allocated for the process specific data. A reference (e.g., pointer, etc.) to the process specific data and/or to the one or more blocks of shared memory can be used by the process to access the process specific data).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Decker’s memory allocation tracking with the system of Mantor. A person of ordinary skill in the art would have been motivated to make this combination to provide Mantor’s system with the advantage of improving shared memory management (see Decker [0002] When multiple processes contribute to the shared resources, such as the shared memory, memory corruption and/or memory leaks can occur during initialization and/or reinitialization of a system.).
Allowable Subject Matter
Claim 16 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
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the
examiner should be directed to HARRISON LI whose telephone number is (703) 756-1469. The
examiner can normally be reached Monday-Friday 9:00am-5:30pm ET.
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, Aimee Li can be reached on (571) 272-4169. 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.
/H.L./
Examiner, Art Unit 2195
/Aimee Li/Supervisory Patent Examiner, Art Unit 2195
Prosecution Insights