DETAILED ACTION
Status of Claims
This action is in reply to the application filed on 01/17/2024.
Claims 1-20 are currently pending and have been examined.
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 .
Allowable Subject Matter
Claims 4-6 and 10-13 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
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-3, 7-9, and 14-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Pouchet (“Iterative Optimization in the Polyhedral Model”, 2010).
Claims 1, 19, and 20:
Pouchet discloses the limitations as shown in the following rejections:
A method comprising, by a computing device including a processor coupled to tangible, non-transitory processor-readable memory (pg. 124, § 8.4.1);
receiving a computer program having a first statement and a second statement, the second statement having a dependency on the first statement, the first statement having associated thereto a first schedule, the second statement having associated thereto a second schedule, the first schedule and the second schedule each having a respective plurality of rows, each plurality of rows corresponding to a same plurality of dimensions; (pg. 25, § 2.2.6; pg. 28, § 2.3.2; pg. 30, 2.4.1)” “A schedule is a function which associates a logical execution date (a timestamp) to each execution of a given statement. In the target program, statement instances will be executed according to the increasing order of these execution dates...This date can be either a scalar (we will talk about one-dimensional schedules), or a vector (multidimensional schedules).”
receiving one or more schedule primitives each defining a respective schedule modification (transformation); modifying, in accordance with the one or more schedule primitives, the first schedule and the second schedule so that each row of the respective plurality of rows is either known or unknown (undefined/incomplete), each known row being either constant or variable (iterator variables) (pg. 26, § 2.3; pg. 31; pg. 35, last para.; pg. 74, last para.) “A transformation in the polyhedral model is represented as a set of affine schedules, one for each polyhedral statements, together with optional modification of the polyhedral representation”
determining, for at least one dimension of the plurality of dimensions, when the corresponding row of at least one plurality of rows is unknown…a respective strong row solution for each unknown corresponding row of the first schedule and the second schedule, the strong row solutions strongly satisfying the dependency of the second statement for the at least one dimension (pg. 31, § 2.4.2; pg. 36-39; pg. 77-81); disclosing a method for “the construction of a practical space of legal, distinct affine multi-dimensional schedules…In multidimensional schedules, the legality constraints can also be built time dimension per time dimension, with the difference that a dependence needs to be weakly satisfied for the first time dimensions until it is strongly satisfied at a given time dimension d. Once a dependence has been strongly satisfied, no additional constraint is required for legality…The output of our algorithm is in the form of a list of polyhedra of legal schedules, one for each time dimension.” (pg. 77) and generates solutions for each dimension/row employing two procedures for each dependence: “Procedure buildWeakLegalSchedules builds the constraints on the scheduling coefficients such that the dependence is weakly satisfied by any schedule in the computed set…Procedure buildStrongLegalSchedules builds the constraints on the scheduling coefficients such that the dependence is strongly satisfied by any schedule in the computed set” (pg. 78). See additionally pg. 101-104 and pg. 115-123 which discloses an alternative algorithm which also teaches the limitation.
Examiner notes that since Pouchet’s algorithm generates “strong row solutions strongly satisfying the dependency” for each dimension, if includes the situation when a next row of each plurality of rows is known and constant, the next row of each plurality of rows corresponding to a next dimension of the plurality of dimensions, and when the next row of the plurality of rows of the first schedule is lexically greater than the next row of the plurality of rows of the second schedule.
generating an executable code from the computer program in accordance with each of the first schedule and the second schedule (pg. 31-32, § 2.5)
Claims 2 and 3:
Pouchet discloses the limitations as shown in the rejections above. Pouchet further discloses determining, for at least one other dimension of the plurality of dimensions…a respective weak row solution for each unknown corresponding row of the first schedule and the second schedule, the weak row solutions weakly satisfying the dependency of the second statement for the at least one other dimension (pg. 31, § 2.4.2; pg. 36-39; pg. 77-81) including under the conditions recited in claims 2 and 3 as described in the rejection to claim 1 above.
Claim 7:
Pouchet discloses the limitations as shown in the rejections above. Pouchet further discloses the dependency of the second statement on the first statement defines a dependence polyhedron representing one or more iterator dependences; and the method further comprises, by the computing device: updating, when the respective strong row solution for each unknown corresponding row of the first schedule and the second schedule is determined for the at least one dimension of the plurality of dimensions, the dependence polyhedron in accordance with each of the strong row solutions to remove at least one iterator dependence of the one or more iterator dependences (pg. 39; pg. 77) “To avoid the combinatorial selection of this dimension, we conditionally nullify constraint (3.1) on the schedules when the dependence was strongly satisfied at a previous dimension” (pg. 39); “Once a dependence has been strongly satisfied, no additional constraint is required for legality at dimensions” (pg. 77).
Claim 8, 9, 14-16:
Pouchet discloses the limitations as shown in the rejections above. Pouchet further discloses:
the computer program includes one or more iterators and one or more symbols (global parameters) each of the first statement and the second statement includes a respective set of iterators from the one or more iterators and a respective set of symbols from the one or more symbols (pg. 24, § 2.2.4).
each of the first statement and the second statement has associated thereto a respective statement basis comprising a respective plurality of basis items (instantiated/solved scheduling dimensions for prior rows/dimensions) depending from at least one of the respective set of iterators, the respective set of symbols, and the one or more schedule primitives; and each strong row solution is a respective linear combination comprising one or more basis items of the respective plurality of basis items…the respective plurality of basis items includes each known row (solved/instantiated of the respective plurality of rows (pg. 115-116, § 8.3; pg. 117, para. 1; pg. 118); "We first present additional conditions on the schedules to improve the performance of the generated transformation, by integrating parallelism and tilability as criteria. As we progressively instantiate the schedule dimensions, constructing the set of legal interleaving at a given level is simplified: we have reduced the number of unknowns, as we know exactly which dependences have been solved at a previous level...Selecting schedules such that each dimension is independent with respect to all others enables a more efficient tiling. Rectangular or close to rectangular blocks are achieved when possible, avoiding complex loop bounds in the case of arbitrarily shaped tiles. We resort to augmenting the constraints, level-by-level, with independence constraints. At this stage, this implies: to compute schedule dimension k, we need to have instantiated a schedule for all previous dimensions 1 to k−1." (pg. 117).
Claim 17 and 18:
Pouchet discloses the limitations as shown in the rejections above. Pouchet further discloses, wherein at least one schedule modification defined by one of the one or more schedule primitives is for one of fusing, skewing, distributing, tiling, reordering, and strip mining…wherein each of the first schedule and the second schedule are represented by a respective affine function (pg. 27, Fig. 2.7; pg. 81: “we represent legal schedules as multidimensional affine functions”).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure:
The following are directed to compiler optimization methods employing polyhedral models: US 20170097815 A1; US 9489180 B1; US 8572595 B1; US 20100218196 A1; US 20090083724 A1; US 6772415 B1, EP 4302180 B1, “Polyhedral Search Space Exploration in the ExaStencils Code Generator”.
“PolyMorphous An MLIR-Based Polyhedral Compiler with Loop Transformation Primitives” overlapping authorship with the instant application.
“Iterative Optimization in the Polyhedral Model: Part II, Multidimensional Time” related to reference Pouchet in rejection above.
Any inquiry of a general nature or relating to the status of this application or concerning this communication or earlier communications from the Examiner should be directed to Paul Mills whose telephone number is 571-270-5482. The Examiner can normally be reached on Monday-Friday 11:00am-8:00pm. If attempts to reach the examiner by telephone are unsuccessful, the Examiner’s supervisor, April Blair can be reached at 571-270-1014.
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.
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.
/P. M./
Paul Mills
05/29/2026
/HIREN P PATEL/Primary Examiner, Art Unit 2196
Prosecution Insights