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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement
The information disclosure statements (IDS) submitted on February 29, 2024, August 7, 2024, November 13, 2024, and November 15, 2024 was filed on/after the filing date of the application on February 29, 2024. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statements are being considered by the examiner.
Drawings
The drawings were received on February 29, 2024. These drawings are accepted.
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.
Claim(s) 1-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Graham et al. (US 2019/0156206) in view of Vipin Sharma, “Sparse SubManifold Convolutions,” August 27, 2021, 23 pages, https://medium.com/geekculture/3d-sparse-sabmanifold-convolutions-eaa427b3a196 (NOTE: A copy of this NPL has been provided therein as the copy provided as part of the Information Disclosure Statement (IDS) filed February 29, 2024 has markups).
As to claim 1, Graham et al. disclose a method of implementing a sparse submanifold convolution on a graphics processing unit, the method comprising: receiving, at the graphics processing unit, an input tensor in a dense format ([0079] notes a d-dimensional convolutional network may be defined as a network that takes as input that is a (d+1)-dimensional tensor); identifying, at the graphics processing unit, active positions of the input tensor ([0079] and [0080] notes a site in the input may be defined to be active if any elements in the feature vector is not in its ground state, e.g. if it is non-zero); performing, at the graphics processing unit, an indexed unfold operation on the input tensor based on the identified active positions of the input tensor to generate an input matrix comprising elements of the input tensor in each active window of the input tensor ([0088] notes to implement S(SC), generating one or more hash tables and one or more rule books and a matrix, where the one or more hash tables may comprise location information associated with the plurality of active sites, the one or more rule books may comprise a plurality of input-output pairs associated with the plurality of active sites, the input-output pairs may be determined based on the one or more sparse convolutions, and the matrix may have a size a x m and contain one row for each of the a active sites); and performing, at the graphics processing unit, a matrix multiplication between a weight matrix (e.g. parameter matrix Wi) and the input matrix (e.g. input feature matrix) to generate an output matrix (e.g. output feature matrix) that comprises elements of an output tensor of the sparse submanifold convolution based on the active windows ([0089] and [0090] notes parameter matrix Wi, and for each jϵ{1…,k}, multiplying the Ri (j,1)-th row of the input feature matrix by Wi and add it to the Ri (j,2)-th row of the output feature matrix, which may be implemented on a GPU as a matrix-matrix multiply-add operation).
As noted above, Graham et al. describes implementing the sparse submanifold convolution by generating one or more hash tables and rule books, which is considered to correspond to the “indexed unfold operation.” For support, Vipin Sharma discloses traditional convolution may perform image-to-column (im2col) to transform an input image into a matrix, then performing matrix multiplication using the matrix, where im2col is known as a “unfold operation” (pages 4-7, “How regular/vanilla convolutions are implemented”). However, Vipin Sharma further discloses, for sparse convolutions, using indices generation algorithms and rulebooks to schedule and execute all atomic operations instead of im2col, which includes hash table generation regarding active input sites and corresponding active output sites, rulebook generation, where once the hash table has been generated, we have the information regarding active input sites as well as the corresponding output sites they would generate, the rulebook is similar to im2col, e.g. to convert convolution operation from a mathematical form into an efficient programmable form (pages 12-17, “How sparse convolutions are implemented”). Vipin Sharma further discloses processes performed as a parallel sparse convolution schema in a graphics processing unit (GPU)(pages 17-18, “How sparse convolutions are implemented” further under “Computation Pipeline”).
It would have been obvious to one of ordinary skill in the art at the time of the invention to incorporate the teachings of Vipin Sharma’s hash table and rulebook generation with Graham et al.’s hash table and rule book generation to replace the image-to-column (im2col), e.g. indexed unfold operation, to obtain all information required regarding active input sites as well as corresponding active output sites and further converting convolution operation from a mathematical form into an efficient programmable form (page 14, “Rule Book Generation” of Vipin Sharma).
As to claim 2, Graham et al. modified with Vipin Sharma disclose the input tensor has at least a height dimension, a width dimension and a channel dimension and an active position of the input tensor is a height and width position in which at least one channel of the input tensor has a non-zero element (Graham, [0079] notes (d+1)-dimensional tensor, the tensor may contain d spatiotemporal dimensions, e.g. length, width, height, time etc., and one additional feature space dimension, e.g. RGB color channels or surface normal vectors).
As to claim 3, Graham et al. modified with Vipin Sharma disclose identifying the active positions of the input tensor comprises: identifying a height, width, and channel position of each non-zero element in the input tensor; identifying unique height and width pairs from the identified height, width and channel positions; and identifying the unique height and width pairs as the active positions (Graham, [0079] notes (d+1)-dimensional tensor, the tensor may contain d spatiotemporal dimensions, e.g. length, width, height, time, etc., and one additional feature space dimension, e.g. RGB color channels or surface normal vectors, where a sparse input may correspond to a d-dimensional grid of sites that is associated with a feature vector, where a site in the input may be defined to be active if any element in the feature vector is not in its ground state, e.g. if it is non-zero, [0081] notes submanifold dilation, where if the input data contains a single active site, then after applying a 3d convolution, there may be 3d active sites, applying a second convolution of the same size may yield 5d active sites, and so on, [0088] further notes the one or more hash tables may comprise location information associated with the plurality of active sites, the one or more rule books may comprise a plurality of input-output pairs associated with the plurality of active sites, the input-output pairs may be determined based on the one or more sparse convolutions).
As to claim 4, Graham et al. modified with Vipin Sharma disclose an active window of the input tensor is a window of the input tensor, used to generate an element of the output tensor of the sparse submanifold convolution, in which one or more predetermined positions within the window are active positions (Graham, e.g. as noted in claim 1, a site in the input may be defined to be active if any element in the feature vector is not in its ground state, e.g. if it is non-zero, where a matrix stored as the state of an input/hidden layer, the matrix is used, e.g. matrix-matrix multiply-add operation to generate the output feature matrix).
As to claim 5, Graham et al. modified with Vipin Sharma disclose performing the indexed unfold operation on the input tensor comprises identifying, from the identified active positions and one or more parameters of the sparse submanifold convolution, the active windows of the input tensor (Graham, e.g. as noted in claim 1, matrix may contain one row for each of the a active sites, the hash table may contain (location, row) pairs for all active sites: the location may be a tuple of integer coordinates, and the row number may indicate the corresponding row in the feature matrix).
As to claim 6, Graham et al. modified with Vipin Sharma disclose identifying, from the identified active positions and the one or more parameters of the sparse submanifold convolution, the active windows of the input tensor comprises, for each identified active position: determining if the active position is at a predetermined position within a window of the input tensor for the sparse submanifold convolution; and in response to determining that the active position is at the predetermined position within a window of the input tensor for the sparse submanifold convolution, identifying the window as an active window (Graham, [0088] notes the one or more hash tables may comprise location information associated with the plurality of active sites, the one or more rule books may comprise a plurality of input-output pairs associated with the plurality of active sites, the input-output pairs may be determined based on the one or more sparse convolutions).
As to claim 7, Graham et al. modified with Vipin Sharma disclose the active windows of the input tensor are based on a version of the input tensor that is padded such that when the sparse submanifold convolution has a stride of one in each sparse submanifold convolution dimension there is an active window for each active position, and identifying, from the identified active positions and the one or more parameters of the sparse submanifold convolution, the active windows of the input tensor comprises identifying the active window corresponding to each active position (Graham, [0085] notes letting f denote an odd number then a submanifold sparse convolution SSC(m, n, f) may be defined as a modified SC(m, n, f, s=1) convolution, first, the input may be padded with (f−1)/2 on each side, so that the output may have the same size as the input, next, an output site may be restricted to be active if and only if the site at the corresponding site in the input is active (i.e., if the central site in the receptive field is active), thus whenever an output site is determined to be active, its output feature vector may be calculated by the SC operation).
As to claim 8, Graham et al. modified with Vipin Sharma disclose performing the indexed unfold operation on the input tensor comprises identifying the elements of the input tensor in each active window (Graham, modified with Vipin Sharma, pages 12-18, “How sparse convolutions are implemented” notes sparse convolution uses indices generation algorithms and rulebooks to schedule and execute all atomic operations instead of im2col, where rule book generation similar to im2col, e.g. to convert convolution operation from a mathematical form into an efficient programmable form, where rulebook collects all the atomic operations involved in the convolution and associates them to corresponding kernel elements (under “Rule Book Generation”)).
As to claim 9, Graham et al. modified with Vipin Sharma disclose identifying the elements of the input tensor in an active window comprises implementing a series of nested loops, the series of nested loops comprising a loop for each dimension of an active window that loops from a predetermined position within the window through the elements of the active window in that dimension (Graham, modified with Vipin Sharma, pages 12-18, “How sparse convolutions are implemented” further notes creating hash table containing information regarding active input sites and the corresponding active output sites, the building the Rulebook, which collects all the atomic operations involved in the convolution and associates them to corresponding kernel elements).
As to claim 10, Graham et al. modified with Vipin Sharma disclose performing the indexed unfold operation on the input tensor comprises storing the elements of each active window in the input matrix (Graham, modified with Vipin Sharma, e.g. as noted in claim 1, storing as one or more hash tables, rule books, and a matrix).
As to claim 11, Graham et al. modified with Vipin Sharma disclose receiving a zeroed input matrix, and the elements of each active window of the input tensor are stored in the received input matrix (Graham, [0079] notes a site in the input may be defined to be active if any element in the feature vector is not in its ground state, for instance, if it is non-zero).
As to claim 12, Graham et al. modified with Vipin Sharma disclose performing, at the graphics processing unit, an indexed fold operation on the output matrix based on the active windows to generate the output tensor of the sparse submanifold convolution in a dense format (Graham, [0087] notes training the machine-learning model may comprise applying, for each of the plurality of content objects, one or more deconvolution operations to the one or more active sites, e.g. a deconvolution operation DC(⋅, ⋅, f, s) may be defined as an inverse of the SC(⋅, ⋅, f, s) convolution, the set of active output sites from a DC convolution may be exactly the set of input active sites to the matching SC convolution, the set of connections between input-output sites may be simply inverted, e.g. performing the inverse of unfold operation as noted in claim 1).
As to claim 13, Graham et al. modified with Vipin Sharma disclose there is an active window for each active position of the input tensor, and performing the indexed fold operation on the output matrix comprises placing each element in the output matrix at the corresponding active position in a channel of the output tensor (Graham, [0087] notes performing sparse manifold deconvolution, which is the inverse of the process of sparse submanifold convolution, e.g. performing inverse of unfold operation of claim 1 with claim 4).
As to claim 14, Graham et al. modified with Vipin Sharma disclose performing the indexed fold operation on the output matrix comprises, for each active window, looping through each channel of the output tensor and placing the element of the output matrix corresponding to that active position and that channel at the active position of that channel in the output tensor (Graham, [0087] notes performing sparse manifold deconvolution, which is the inverse of the process of sparse submanifold convolution, e.g. performing inverse of unfold operation of claim 1 with claims 8 and 9).
As to claim 15, Graham et al. modified with Vipin Sharma disclose performing the indexed fold operation on the output matrix comprises identifying a position in the output tensor of each element in the output matrix, based on the active windows and one or more parameters of the sparse submanifold convolution, and placing each element of the output matrix in the corresponding identified position in the output tensor (Graham, e.g. [0087] notes performing sparse manifold deconvolution, which is the inverse of the process of sparse submanifold convolution, e.g. performing inverse of unfold operation of claim 1 with claim 5).
As to claim 16, Graham et al. modified with Vipin Sharma disclose receiving a zeroed output tensor, and the elements of the output matrix are stored in the received output tensor (Graham, [0090] notes initializing the output matrix to all zeros).
As to claim 17, Graham et al. modified with Vipin Sharma disclose performing the indexed fold operation on the output matrix further comprises storing zeroes at each position of the output tensor that does not comprise an element of the output matrix (Graham, e.g. [0087] notes performing sparse manifold deconvolution, which is the inverse of the process of sparse submanifold convolution, where [0090] notes initializing the output matrix to all zeros, e.g. performing inverse of unfold operation of claim 1 with claims 10 and 11).
As to claim 18, Graham et al. modified with Vipin Sharma disclose the input matrix comprises a column for each active window of the input tensor and each column of the input matrix comprises the elements of the input tensor in the corresponding active window (Graham, modified with Vipin Sharma, as noted in claim 1, generating one or more hash tables and rule books for active input sites and corresponding active output sites in place of image-to-column); and wherein the weight matrix comprises a row for each filter to be applied to the input tensor and each row of the weight matrix comprises all weights forming the corresponding filter (Graham, as noted in claim 1, [0088] notes convolution with filter size f, and to implement an SC (m,n,f,s), [0089] and [0090] notes parameter matrix Wi, and for each jϵ{1…,k}, multiplying the Ri (j,1)-th row of the input feature matrix by Wi and add it to the Ri (j,2)-th row of the output feature matrix).
As to claim 19, Graham et al. modified with Vipin Sharma disclose a graphics processing unit Graham, [0090] notes operations performed on GPU; modified with Vipin Sharma, “Computation Pipeline” as GPU) configured to perform the method as set forth in claim 1. Please see the rejection and notes regarding claim 1 above.
As to claim 20, Graham et al. modified with Vipin Sharma disclose a non-transitory computer readable storage medium (Graham, e.g. memory 1404 and/or storage 1406) having stored thereon computer readable code (Graham, [0156] notes memory 1404 storing instructions for execution, [0157] notes storage 1406 storing data and instructions) configured to cause a graphics processing unit (Graham, e.g. processor 1402, further implemented as a graphics processing unit, [0155] notes processor may be any suitable processor, where [0090] notes operations performed on GPU; modified with Vipin Sharma, “Computation Pipeline” as GPU) to perform the method as set forth in claim 1 when the code is run. Please see the rejection and notes regarding claim 1 above.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JACINTA M CRAWFORD whose telephone number is (571)270-1539. The examiner can normally be reached 8:30a.m. to 4:30p.m.
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, King Y. Poon can be reached at (571)272-7440. 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.
/JACINTA M CRAWFORD/Primary Examiner, Art Unit 2617