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 .
This action is responding to application papers dated 1/10/2024.
Claims 1-20 are pending in the application.
The information disclosure statements filed on 1/10/2024 and 1/11/2024 have been considered.
Claim Objections
Claims 1, 11, 13, 14, 16, 18 and 19 are objected to because of the following informalities: per claims 1, 11 and 16, “in memory” needs to be “in a memory.” Per claims 13, 14, 18 and 19, “FFT” needs to be spelled out. Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Per claims 1, 11 and 16, “in memory” on the last line is unclear to which memory it is referring. Interpretation: in the memory.
Per claims 3, 4, 12, and 17, “in memory” is unclear to which memory it is referring. Interpretation: in the memory.
Per claims 2-10, 12-15, and 17-20, these claims are rejected because they depend from claims 1, 11 and 16 respectively.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more. Specifically, claims 1-20 are directed to an abstract idea.
Per claim 1, the claim is directed to an idea of itself, mental processes that can be performed in the human mind, or by a human using a pen and paper. The steps of converting and combining can be pure mental process because a developer can do loop unrolling and fusion/jamming for execution time efficiency and parallelism manually using a pen and paper through observation, evaluation, judgment, opinion, Under Prong 1.
Under Prong 2, no additional limitations are recited. Viewing the limitations individually and as a combination, the claim recites only the mental steps of loop unrolling and jamming/fusing without integrating the abstract idea into a practical application. For at least these reasons, claim 1 is not patent eligible.
Per claims 2-10, these claims are directed to the same idea itself as in claim 1, reciting details of data and the mental steps without adding any other additional element that is significantly more. The step of producing compiled code implementing the vector instruction can be done mentally by a developer as the code or data does not need to be large and there is no recitation of the particular implementation of the vector instruction. The steps of loading, combining, vectorizing are other mental steps that can be performed by a developer. Per claim 8, this claim is directed to the same idea itself as in claim 1. Under Prong 2, the additional limitation, the step of executing a compiler is to automate the mental steps or apply the mental steps using a generic learning algorithm and computer component (HID) described at a high level of generality for applying or performing the abstract idea and do not indicate any integration of the abstract idea into a practical application. See MPEP see MPEP 2106.05(f) /2106.05(h). Therefore, the additional limitation does not integrate the abstract idea into a practical application. Viewing the limitations individually and as a combination, the additional elements merely perform the mental steps using generic computing components as tools without integrating the abstract idea into a practical application. For at least these reasons, claims 2-10 are patent eligible.
Per claims 11-15, these claims are directed to the same idea itself as in claims 1-10, reciting details of the mental steps (e.g. unrolling) without adding any other additional element that is significantly more. Therefore, the claims are rejected for the same reasons as in claims 1-10.
Per claims 16-20, these claims are directed to the same idea itself as in claims 1-10, reciting details of the mental steps and generic computing components to apply the mental steps (a processor core) without adding any other additional element that is significantly more. Using a generic learning algorithm and computer component (HID) described at a high level of generality for applying or performing the abstract idea and do not indicate any integration of the abstract idea into a practical application. See MPEP see MPEP 2106.05(f) /2106.05(h). Therefore, the additional limitation does not integrate the abstract idea into a practical application. Viewing the limitations individually and as a combination, the additional elements merely perform the mental steps using generic computing components as tools without integrating the abstract idea into a practical application. For at least these reasons, claims 16-20 are patent eligible for the same reasons as in claims 1-10.
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.
Claims 1-4, 8-12, 16, and 17 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Eichenberger et al. (US20080010634, hereafter Eichenberger).
Per claim 1:
Eichenberger discloses:
A method comprising: converting a program sequence, the program sequence comprising an inner loop nested in an outer loop, to multiple statements of the inner loop with a statement of the multiple statements changing according to an index of the outer loop (Eichenberger, see at least [0011] over the iteration of the loop, lines 110, 112, and 114 operate over a contiguous stream of memory. The loop depicted in FIG. 1C may be characterized as being "manually-unrolled," since each of lines 110, 112, and 114 represent three iterations of a semantically-equivalent loop. For example, the loop in FIG. 1C could have been written as for(int i=0; i<N; i++) a[i]=(i %3)+1; [0012] where "%" represents the "modulo" or "remainder" operator, as in the C programming language. Loop unrolling is commonly used to speed up program code written for pipelined processors, where branch instructions may incur substantial performance penalties; [0013] FIG. 1D depicts a nested pair of loops in which the inner loop has a short, known trip count. Although line 118, as written, relies on two index variables, "i" and "j," because the trip count of the inner loop is known, line 118 could be unrolled into a semantically equivalent loop of the form shown in FIG. 1C; [0014] and "loop unroll; [0018]; Note that the outer loop is unrolled, producing multiple statements of the inner loop, each statement changing according to the outer loop index); and
combining a memory access for a first statement of the multiple statements with a memory access for a second statement of the multiple statements using a vector instruction, wherein the vector instruction accesses sets of N data elements, where N is a segment size of data elements in consecutive locations in memory, and where sets of N data elements are spaced at a constant distance in memory (Eichenberger, see at least [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses. FIGS. 1A-1D provide four examples of such scenarios written in a C-like pseudocode; [0029] a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code. FIG. 2B shows the result of applying such a transformation to the loop depicted in FIG. 2A. Lines 200, 202, and 204 in FIG. 2A are replaced with a single line of vectorized code, line 208; [0020] generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into a single statement that operates on vectors of a certain length. The length of the vector is determined by the data type of the original scalar operation and the number of statements being aggregated … Finally, operations on physical vectors are converted into SIMD operations; [[Note that Isomorphic statements with adjacent memory accesses are identified and grouped, the grouped accesses are aggregated and packed directly into a single SIMD vector instruction, that is, N consecutive elements (segment) from each statement, combined into one vector operation. The vector instruction is the segmented-strided access because the contiguous elements as a segment form one statement, and the stride is the constant distance between statements in the unrolled sequence. Also, "unroll and jam" or "unroll and pack" unrolls an outer loop while packing or fusing the inner loop, optimizing how data is processed]]).
Per claim 2:
Eichenberger further discloses: The method of claim 1, wherein the vector instruction is a segmented-strided vector instruction, and wherein the segmented-strided vector instruction combines a constant- stride memory access for the first statement with a constant-stride memory access for the second statement (Eichenberger, see at least [0009] In FIG. 1A, a loop that iterates over an array of structured data types or "structures" (e.g., "structs" in C or "records" in Pascal),…creating two non-stride-one accesses; [0014] A number of techniques have been proposed to allow multiple non-stride-one accesses over contiguous memory streams to be aggregated into stride-one memory accesses. Among these are "loop rerolling," "loop collapsing," and "loop unroll-and-pack; [0019] Thus, what is needed is an efficient, general-purpose scheme for aggregating multiple non-stride-one memory references into simdized code; [0020] A generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. … operations on virtual-length vectors are "de-virtualized" into operations on multiple physical-length vectors. Finally, operations on physical vectors are converted into SIMD operations; [0029] assigns a constant to a variable. In other cases, the isomorphism between statements may be less obvious. For example, a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code; [[(Note that non-stride-one means fixed/constant stride accesses to non-consecutive memory locations- the spacing between accesses is uniform but greater than one element width; multiple accesses combined footprint covers a contiguous block of memory- so they can be treated as a single unit-stride vector load/store for SIMD)]).
Per claim 3:
Eichenberger further discloses: The method of claim 1, further comprising: producing compiled code implementing the vector instruction, wherein the compiled code is configured to transpose data elements in memory from a first ordered arrangement associated with a first matrix to a second ordered arrangement associated with a second matrix (Eichenberger, see at least claim 5, generating a data reorganization graph; [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses; [0009] In FIG. 1A, a loop that iterates over an array of structured data types or "structures" (e.g., "structs" in C or "records" in Pascal), where each of the structures has two fields. Although language syntax requires that a separate assignment statement be written for each field (thus creating two non-stride-one accesses in lines 100 and 102), the actual object code generated by the program fragment shown in FIG. 1A will result in assignments to a contiguous memory stream made up of elements of type "int," since each structure is simply a pair of adjacently-stored integers; [0014] A number of techniques have been proposed to allow multiple non-stride-one accesses over contiguous memory streams to be aggregated into stride-one memory accesses. Among these are "loop rerolling," "loop collapsing," and "loop unroll-and-pack; [[Note that a matrix is a collection of vectors and vector registers load chunks of data (matrix) contiguously from a memory and simd vector loads operate on what could be rows of a matrix. Fig. 1D shows the nested loop with two index variables i and j iterating over an array corresponding to representation of matrix access; Fig. 1A shows the struct instances (rows) and fields (columns) and accessing each field (accessing a column) is considered as a 2-column matrix. Taking data that is strided/interleaved in a memory and reorganizing it into contiguous chunks to fit into vector registers correspond to SIMD matrix transposing]]).
Per claim 4:
Eichenberger further discloses: The method of claim 1, wherein the vector instruction does at least one of: store the sets of N data elements from a vector register to locations in memory; or load the sets of N data elements from locations in memory to a vector register (Eichenberger, see at least [0005]; [0006] a load instruction loads 16-byte contiguous memory from 16-byte aligned memory, ignoring the last 4 bits of the memory address in the instruction. The same applies to store instructions. In this paper, architectures with alignment constraints refer to machines that support only loads and stores of register-length aligned memory; [0009]; [0034] Thus, the loop in FIG. 2B will be blocked so that each vector operation represents 4 iterations of the original loop. This result is shown in FIG. 2C, where the loop is modified so that the index variable "i" increments by 4 (line 212) at each iteration of the loop. Lines 214 and 216 replace lines 208 and 206, respectively. Line 214 stores a vector of 12 values that represents four iterations of line 208 in FIG. 2B into a 48-byte (12-element) slice of array "a." Similarly line 216 stores a vector of 4 values, representing four iterations of line 206 in FIG. 2B, into a 16-byte (4-element) slice of array "b."; [[Note that Alti In the ALTIVEC instruction set found on certain POWERPC microprocessors has 128-bit vector registers, loads/stores is 16-byte aligned).
Per claim 8:
Eichenberger further discloses: executing a compiler to translate the program sequence to object code, wherein the compiler combines a constant-stride memory access for the first statement with a constant-stride memory access for the second statement to implement the vector instruction (Eichenberger, see at least [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses. FIGS. 1A-1D provide four examples of such scenarios written in a C-like pseudocode; [0029] a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code. FIG. 2B shows the result of applying such a transformation to the loop depicted in FIG. 2A. Lines 200, 202, and 204 in FIG. 2A are replaced with a single line of vectorized code, line 208; [0020] generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into a single statement that operates on vectors of a certain length. The length of the vector is determined by the data type of the original scalar operation and the number of statements being aggregated … Finally, operations on physical vectors are converted into SIMD operations; [[Note that Isomorphic statements with adjacent memory accesses are identified and grouped, the grouped accesses are aggregated and packed directly into a single SIMD vector instruction, that is, N consecutive elements (segment) from each statement, combined into one vector operation. The vector instruction is the segmented-strided access because the contiguous elements as a segment form one statement, and the stride is the constant distance between statements in the unrolled sequence ]]).
9. The method of claim 1, wherein the combining includes: combining the first statement with the second statement to generate a combined statement; and vectorizing the combined statement via the vector instruction (Eichenberger, see at least [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses. FIGS. 1A-1D provide four examples of such scenarios written in a C-like pseudocode; [0029] a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code. FIG. 2B shows the result of applying such a transformation to the loop depicted in FIG. 2A. Lines 200, 202, and 204 in FIG. 2A are replaced with a single line of vectorized code, line 208; [0020] generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into a single statement that operates on vectors of a certain length. The length of the vector is determined by the data type of the original scalar operation and the number of statements being aggregated … Finally, operations on physical vectors are converted into SIMD operations; [[Note that Isomorphic statements with adjacent memory accesses are identified and grouped, the grouped accesses are aggregated and packed directly into a single SIMD vector instruction, that is, N consecutive elements (segment) from each statement, combined into one vector operation. The vector instruction is the segmented-strided access because the contiguous elements as a segment form one statement, and the stride is the constant distance between statements in the unrolled sequence. Also, "unroll and jam" or "unroll and pack" unrolls an outer loop while packing or fusing the inner loop, optimizing how data is processed]]).
10. The method of claim 1, wherein the vector instruction is a segmented-strided vector instruction, and wherein the combining includes: vectorizing the first statement via a first vector instruction; vectorizing the second statement via a second vector instruction; and combining the first vector instruction with the second vector instruction via the segmented-strided vector instruction (Eichenberger, see at least [0009] In FIG. 1A, a loop that iterates over an array of structured data types or "structures" (e.g., "structs" in C or "records" in Pascal),…creating two non-stride-one accesses; [0014] A number of techniques have been proposed to allow multiple non-stride-one accesses over contiguous memory streams to be aggregated into stride-one memory accesses. Among these are "loop rerolling," "loop collapsing," and "loop unroll-and-pack; [0019] Thus, what is needed is an efficient, general-purpose scheme for aggregating multiple non-stride-one memory references into simdized code; [0020] A generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. … operations on virtual-length vectors are "de-virtualized" into operations on multiple physical-length vectors. Finally, operations on physical vectors are converted into SIMD operations; [0029] assigns a constant to a variable. In other cases, the isomorphism between statements may be less obvious. For example, a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code; [[(Note that non-stride-one means fixed/constant stride accesses to non-consecutive memory locations- the spacing between accesses is uniform but greater than one element width; multiple accesses combined footprint covers a contiguous block of memory- so they can be treated as a single unit-stride vector load/store for SIMD)]).
Per claim 11:
Eichenberger discloses:
A method comprising: unrolling a program sequence to generate multiple statements of an inner loop, wherein a statement of the multiple statements changes by an index of an outer loop (Eichenberger, see at least [0011] over the iteration of the loop, lines 110, 112, and 114 operate over a contiguous stream of memory. The loop depicted in FIG. 1C may be characterized as being "manually-unrolled," since each of lines 110, 112, and 114 represent three iterations of a semantically-equivalent loop. For example, the loop in FIG. 1C could have been written as for(int i=0; i<N; i++) a[i]=(i %3)+1; [0012] where "%" represents the "modulo" or "remainder" operator, as in the C programming language. Loop unrolling is commonly used to speed up program code written for pipelined processors, where branch instructions may incur substantial performance penalties; [0013] FIG. 1D depicts a nested pair of loops in which the inner loop has a short, known trip count. Although line 118, as written, relies on two index variables, "i" and "j," because the trip count of the inner loop is known, line 118 could be unrolled into a semantically equivalent loop of the form shown in FIG. 1C; [0014] and "loop unroll; [0018]; Note that the outer loop is unrolled, producing multiple statements of the inner loop, each statement changing according to the outer loop index);
combining a memory access for a first statement of the multiple statements with a memory access for a second statement of the multiple statements via a vector instruction, wherein the vector instruction accesses sets of N data elements, where N is a segment size of data elements in consecutive locations in memory, and where sets of N data elements are spaced at a constant distance in memory (Eichenberger, see at least [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses. FIGS. 1A-1D provide four examples of such scenarios written in a C-like pseudocode; [0029] a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code. FIG. 2B shows the result of applying such a transformation to the loop depicted in FIG. 2A. Lines 200, 202, and 204 in FIG. 2A are replaced with a single line of vectorized code, line 208; [0020] generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into a single statement that operates on vectors of a certain length. The length of the vector is determined by the data type of the original scalar operation and the number of statements being aggregated … Finally, operations on physical vectors are converted into SIMD operations; [[Note that Isomorphic statements with adjacent memory accesses are identified and grouped, the grouped accesses are aggregated and packed directly into a single SIMD vector instruction, that is, N consecutive elements (segment) from each statement, combined into one vector operation. The vector instruction is the segmented-strided access because the contiguous elements as a segment form one statement, and the stride is the constant distance between statements in the unrolled sequence. Also, "unroll and jam" or "unroll and pack" unrolls an outer loop while packing or fusing the inner loop, optimizing how data is processed]]).
Per claim 12, it is another method version of claim 3, and is rejected for the same reasons set forth in connection with the rejection of claim 3 above.
Per claim 16:
Eichenberger discloses:
An apparatus comprising: a processor core configured to: convert a program sequence, comprising an inner loop nested in an outer loop, to multiple statements of the inner loop with a statement of the multiple statements changing by an index of the outer loop (Eichenberger, see at least [0011] over the iteration of the loop, lines 110, 112, and 114 operate over a contiguous stream of memory. The loop depicted in FIG. 1C may be characterized as being "manually-unrolled," since each of lines 110, 112, and 114 represent three iterations of a semantically-equivalent loop. For example, the loop in FIG. 1C could have been written as for(int i=0; i<N; i++) a[i]=(i %3)+1; [0012] where "%" represents the "modulo" or "remainder" operator, as in the C programming language. Loop unrolling is commonly used to speed up program code written for pipelined processors, where branch instructions may incur substantial performance penalties; [0013] FIG. 1D depicts a nested pair of loops in which the inner loop has a short, known trip count. Although line 118, as written, relies on two index variables, "i" and "j," because the trip count of the inner loop is known, line 118 could be unrolled into a semantically equivalent loop of the form shown in FIG. 1C; [0014] and "loop unroll; [0018]; Note that the outer loop is unrolled, producing multiple statements of the inner loop, each statement changing according to the outer loop index);
combine a memory access for a first statement of the multiple statements with a memory access for a second statement of the multiple statements via a vector instruction, wherein the vector instruction accesses sets of N data elements, where N is a segment size of data elements in consecutive locations in memory, and where sets of N data elements are spaced at a constant distance in memory (Eichenberger, see at least [0008] The simplest form of contiguous memory stream can be identified as a single stride-one memory access, for instance, a[i], where i is the counter of the surrounding loop and increments by 1. However, there are cases in which a contiguous memory stream is formed by a combination of non stride-one memory accesses. FIGS. 1A-1D provide four examples of such scenarios written in a C-like pseudocode; [0029] a statement that subtracts a constant from a variable is isomorphic to another statement that adds a constant to a variable, since the subtraction may be compiled into an addition instruction that adds a negative number; [0030] Once a set of isomorphic statements has been identified, that set of isomorphic statements is transformed into a single statement that operates on vectors instead of scalars. This may be referred to a "basic-block-level packing," since a basic block of isomorphic statements in the body of a loop is packed into a single vectorized statement without modifying the loop control code. FIG. 2B shows the result of applying such a transformation to the loop depicted in FIG. 2A. Lines 200, 202, and 204 in FIG. 2A are replaced with a single line of vectorized code, line 208; [0020] generating loop code to execute on Single-Instruction Multiple-Datapath (SIMD) architectures, where the loop contains multiple non-stride-one memory accesses that operate over a contiguous stream of memory. A preferred embodiment identifies groups of isomorphic statements within a loop body where the isomorphic statements operate over a contiguous stream of memory over the iteration of the loop. Those identified statements are then converted into a single statement that operates on vectors of a certain length. The length of the vector is determined by the data type of the original scalar operation and the number of statements being aggregated … Finally, operations on physical vectors are converted into SIMD operations; [[Note that Isomorphic statements with adjacent memory accesses are identified and grouped, the grouped accesses are aggregated and packed directly into a single SIMD vector instruction, that is, N consecutive elements (segment) from each statement, combined into one vector operation. The vector instruction is the segmented-strided access because the contiguous elements as a segment form one statement, and the stride is the constant distance between statements in the unrolled sequence. Also, "unroll and jam" or "unroll and pack" unrolls an outer loop while packing or fusing the inner loop, optimizing how data is processed]]).
Per claim 17, it is another method version of claim 3, and is rejected for the same reasons set forth in connection with the rejection of claim 3 above.
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.
Claims 5-7, 13-15, and 18-20 are rejected under 35 U.S.C. 103 as being unpatentable over Eichenberger in view of Bengtsson (“Development of Stockham Fast Fourier Transform using Data Centric Parallel Programing,” 2020).
Per claim 5:
Eichenberger teaches producing compiled code implementing the vector instruction, wherein the compiled code is configured to execute a computation (Eichenberger, see at least [0020], the virtual-length vectors computed from the previous step are further aggregated, across iterations, into virtual-length vectors that are of a size that is a multiple of the physical vector length. Then, operations on virtual-length vectors are "de-virtualized" into operations on multiple physical-length vectors. Finally, operations on physical vectors are converted into SIMD operations; [0029] A set of statements is isomorphic if all of the statements may be compiled into a set of instructions that differ only in the data values that are operated upon by those instructions … since the subtraction may be compiled into an addition instruction that adds a negative number; [0031] Next, stride-one accesses are further aggregated across iterations by blocking the loop … The blocking factor is computed as BlockingFactor).
Eichenberger does not explicitly teach that the computation includes a fast Fourier transform (FFT) computation. Bengtsson teaches a fast Fourier transform (FFT) computation (Bengtsson, see at least chapter 3, Stockham FFT algorithm self-sorting and avoids bit reversals, providing better performance on GPUs… is designed for wide vector operations, as opposed to small independent iterative operations). It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to have combined Bengtsson’s FFT with Eichenberger’s SIMD vectorization to modify Eichenberger’s system to combine the FFT computation, with a reasonable expectation of success, since they are analogous art because they are from the same field of endeavor related to parallel computing. Combining Bengtsson’s functionality with that of Eichenberger results in a system that allows a FFT algorithm. The modification would be obvious because one having ordinary skill in the art would be motivated to make this combination to provide the benefits of self-sorting and avoid “bit reversals, providing better performance on GPUs … designed for wide vector operations, as opposed to small independent iterative operations (Bengtsson, see at least chapter 3, Stockham FFT algorithm
self-sorting and avoids bit reversals, providing better performance on GPUs… is designed for wide vector operations, as opposed to small independent iterative operations).”
Per claim 6:
Eichenberger teaches producing compiled code implementing the vector instruction, wherein the compiled code is configured to transpose data elements associated with a matrix for a computation (Eichenberger, see at least [0020], the virtual-length vectors computed from the previous step are further aggregated, across iterations, into virtual-length vectors that are of a size that is a multiple of the physical vector length. Then, operations on virtual-length vectors are "de-virtualized" into operations on multiple physical-length vectors. Finally, operations on physical vectors are converted into SIMD operations; [0029] A set of statements is isomorphic if all of the statements may be compiled into a set of instructions that differ only in the data values that are operated upon by those instructions … since the subtraction may be compiled into an addition instruction that adds a negative number; [0031] Next, stride-one accesses are further aggregated across iterations by blocking the loop … The blocking factor is computed as BlockingFactor; [0014] A number of techniques have been proposed to allow multiple non-stride-one accesses over contiguous memory streams to be aggregated into stride-one memory accesses. Among these are "loop rerolling," "loop collapsing," and "loop unroll-and-pack; Note that a matrix is a collection of vectors and vector registers load chunks of data (matrix) contiguously from a memory and simd vector loads operate on what could be rows of a matrix. Fig. 1D shows the nested loop with two index variables i and j iterating over an array corresponding to representation of matrix access; Fig. 1A shows the struct instances (rows) and fields (columns) and accessing each field (accessing a column) is considered as a 2-column matrix. Taking data that is strided/interleaved in a memory and reorganizing it into contiguous chunks to fit into vector registers correspond to SIMD matrix transposing).
Eichenberger does not explicitly teach that the computation includes a Stockham FFT computation. Bengtsson teaches a Stockham FFT computation (Bengtsson, see at least chapter 3, Stockham FFT algorithm self-sorting and avoids bit reversals, providing better performance on GPUs… is designed for wide vector operations, as opposed to small independent iterative operations). It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to have combined Bengtsson’s FFT with Eichenberger’s SIMD vectorization to modify Eichenberger’s system to combine the FFT computation, with a reasonable expectation of success, since they are analogous art because they are from the same field of endeavor related to parallel computing. Combining Bengtsson’s functionality with that of Eichenberger results in a system that allows a FFT algorithm. The modification would be obvious because one having ordinary skill in the art would be motivated to make this combination to provide the benefits of self-sorting and avoid “bit reversals, providing better performance on GPUs … designed for wide vector operations, as opposed to small independent iterative operations (Bengtsson, see at least chapter 3, Stockham FFT algorithm self-sorting and avoids bit reversals, providing better performance on GPUs… is designed for wide vector operations, as opposed to small independent iterative operations).”
Perc alim 7:
Eichenberger teaches producing compiled code implementing the vector instruction, wherein the compiled code is configured to execute an operation (Eichenberger, see at least [0020], the virtual-length vectors computed from the previous step are further aggregated, across iterations, into virtual-length vectors that are of a size that is a multiple of the physical vector length. Then, operations on virtual-length vectors are "de-virtualized" into operations on multiple physical-length vectors. Finally, operations on physical vectors are converted into SIMD operations; [0029] A set of statements is isomorphic if all of the statements may be compiled into a set of instructions that differ only in the data values that are operated upon by those instructions … since the subtraction may be compiled into an addition instruction that adds a negative number; [0031] Next, stride-one accesses are further aggregated across iterations by blocking the loop … The blocking factor is computed as BlockingFactor; [0014] A number of techniques have been proposed to allow multiple non-stride-one accesses over contiguous memory streams to be aggregated into stride-one memory accesses. Among these are "loop rerolling," "loop collapsing," and "loop unroll-and-pack).
Eichenberger does not explicitly teach that the computation includes a matrix-multiplication. Bengtsson teaches a matrix-multiplication (Bengtsson, see at least Chapter 4, page 35, The second step of the program is to multiply the generated DFT matrix with the input vector. Usually, when performing a matrix-vector multiplication, the program would use += to sum rows, but in this case, we use a transient two-dimensional matrix (line 20) which is then summed over columns into the output using a dace.reduce on line 31, the lambda function lambda a, b: a + b describes how data should be combined. The@dace.maponline22 performs the multiplication using the input vector and newly generated DFT matrix as input and the transient matrix as the output … Stride permutation of the input in the Stockham pass is defined as a sparse matrix-vector multiplication in the form … defined using Equation 3.10, which, … are applied to the input vector as a sparse matrix-vector multiplication like; Chapter 7, page 91, As. A probable explanation for this is that larger transform sizes enable higher utilization of the massive parallelism in the GPU). It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to have combined Bengtsson’s FFT matrix multiplication with Eichenberger’s SIMD vectorization to modify Eichenberger’s system to combine the FFT matrix multiplication computation, with a reasonable expectation of success, since they are analogous art because they are from the same field of endeavor related to parallel computing. Combining Bengtsson’s functionality with that of Eichenberger results in a system that allows a FFT matrix multiplication operation. The modification would be obvious because one having ordinary skill in the art would be motivated to make this combination to achieve highly optimized calculation and accelerate computational efficiency, and achieve massive parallelism (Bengtsson, see at least Chapter 4, page 35, The second step of the program is to multiply the generated DFT matrix with the input vector. Usually, when performing a matrix-vector multiplication, the program would use += to sum rows, but in this case, we use a transient two-dimensional matrix (line 20) which is then summed over columns into the output using a dace.reduce on line 31, the lambda function lambda a, b: a + b describes how data should be combined. The@dace.maponline22 performs the multiplication using the input vector and newly generated DFT matrix as input and the transient matrix as the output … Stride permutation of the input in the Stockham pass is defined as a sparse matrix-vector multiplication in the form … defined using Equation 3.10, which, … are applied to the input vector as a sparse matrix-vector multiplication like; Chapter 7, page 91, As. A probable explanation for this is that larger transform sizes enable higher utilization of the massive parallelism in the GPU).
Per claims 13-15, they are other method versions of claims 5-7, respectively, and are rejected for the same reasons set forth in connection with the rejection of claims 5-7 above.
Per claims 18-20, they are apparatus versions of claims 5-7, respectively, and are rejected for the same reasons set forth in connection with the rejection of claims 5-7 above.
Examiner’s Note
The Examiner has pointed out particular references contained in the prior art of record within the body of this action for the convenience of the Applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may apply. Applicant, in preparing the response, should consider fully the entire reference as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the Examiner.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Anderson et al. (“Automatic Vectorization of Interleaved Data Revisited” 2015) is related to vectorization of interleaved data;
US 20190042224 is related to loop vectorization and unrolling;
CN107193535 is related to nested loops vector based on SIMD extension component parallel;
CN 110806897 is related to target program segment vector parallelism;
US20200233649 is related to unrolling an inner loop completely inside an outer loop may create a non-unit stride in memory accesses across outer-loop iterations;
Kral et al. (SIMD Vectorization of Straight Line FFT Code) is related to SIMD vectorization of FFT code; and
Xu et al. (SIMD vectorization of nested loop based on strip mining) is related to SIMD vectorization of nested loop.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to INSUN KANG whose telephone number is (571)272-3724. The examiner can normally be reached M-TR 9am-5pm.
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, Chat Do can be reached at 571-272-3721. 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.
/INSUN KANG/Primary Examiner, Art Unit 2193
Prosecution Insights