Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper proposes an auto-tuning framework for `matmul` and `2d convolution` operators targeted for CPUs. The authors talk about combining analytical cache models with ML trained with real hardware measurements to improve the final performance of running these operations on CPU. Finally, few pruning strategies was proposed to reduce the search space for scheduling.
main_review: - The paper tackles the interesting problem of `auto-tuning machine learning operations on CPUs`. However, the paper is not clear about the contributions. For example, the authors talked about the analytic ideal cache model (which as mentioned it is not their contribution) with ML models trained with real hardware measurements. However, I couldn't clearly understand how the analytical model and ML models are integrated and used together or what is the performance implications of each of these.

- It would be great if the authors summarize the last few figures in the paper and provide insights about the experiments. Without a proper explanation of the figures, it is not straightforward to understand what is the goal of each figure and what it presents. 

- In the `Evaluation of Automatic Schedule Chosen`, it was mentioned that `ConvOpt` is the default implementation. Does it mean that the search algorithm do no tune any parameters for convolution?

- Do you have any explanation on why the speedup is better for the matrices with prime number sizes? Is it because of the data locality?

- Which CPU platforms were used for the presented results? Are there any significant differences in the performance numbers across different CPU platforms?

- Do you use the existing search algorithm in AutoTVM + proposed schedules or there are contributions on the search algorithm as well?

- Figure 6 x-axis indicates different configurations? Can you provide some explanation on the high variance in SA+RANK and how REG reduces the variance in the results? How many times you ran the search?
limitations_and_societal_impact: As mentioned earlier, the paper tackles an interesting problem, however without proper explanation of the main contributions it is not clear how the proposed approach can be used. It would be good if the results are explained in a more clear way to better understand the contributions. One of the main limitations of this work in my opinion is the applicability of the proposed approach across different CPU platforms with different caching hierarchy.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work introduces AutoMCL - a new auto-tuning framework aimed at making compiled output higher performing, while improving the compile-time as well though better pruning of the search space. Authors focus primarily on lower-level library primitives, specifically: fully connected and convolution layers. Their primary contribution is a mix of analytical and ML-driven models. More specifically authors introduce some analytical models, suited for assessing effectiveness of various tiling strategies on CPUs, with the help of ideal cache models and parameters learning/modeling cache complexity. These help both cutting down the search space with respect to prior work based on ML-based learning, and find in some cases better schedules as well.  Net gain on optimization/compile time is more significant (more than 2x over AutoTVM).  Gain in inference performance through better schedule generation at kernel level is less - about 37% for full-connected networks. CNNs show just about 2% improvement in throughput and optimization time.


main_review: This submission's technical contributions are quite limited: a) applicable to CPUs only, b) primary contribution is some analytical models for cache subsystem which, in combination with learned parameters cut down search space and find better schedules, and c) very limited performance or throughput gains, best case only 37% for FCNNs.

Paper is reasonably well-written. Section 3 - which is where most of the new content (analytical model) is explained - is not easy to read.

Experimental evaluation is reasonable too - as it looks at both Intel and AMD CPUs. It would have been better to extend the work to ARM CPUs as well. Overall, this section (Sec 4) is the better-written and easier to read and follow.

Gain over AutoTVM is all that matters - since it is the primary and relevant prior-art for this work (not TensorFlow). And this gain is quite limited.

For observations like that in line 185: "For conv2d, the learning approach does not work quite well" - it would help the reader if you can offer more insight as to how/why the learned schedule does show much improved over static selection.


limitations_and_societal_impact: I cannot foresee how this work adds to or reduces potential negative societal use of the prior state-of-the-art they are contributing to.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents an application of the classic cache complexity analysis
of the classic matrix multiplication and convolution algorithm used in deep learning workloads.
The paper provides a simple yet effective way to find the ideally optimal tile sizes
on both of the operators given a specific schedule.
The contribution includes:
- A novel tile size initialization and search space pruning techniques.
- A few schedule templates in AutoTVM to cover more search space.
- Implemented the methodology into a new system called AutoMCL,
which reuses the frontend and codegen backend of AutoTVM.

main_review: **Strengths.** This paper enumerates 6 different scheduling strategies for matmul,
and another 6 for conv2d. The author calculated analytically on the closed form of potential
cache misses in the each of the 6 strategies. Although very simple and straightforward,
it does provide some insight on the effectiveness of the tile size choice.
Compared with polyhedral models, this method does not necessarily require the affine map
and solve a complicated optimization problem.
Although loop skewing is not supported in this particularly case,
which leads to smaller search space, 
it doesn't affect the tuning result.

**Weaknesses.** The reviewer is wondering if such analysis can be formalized and conducted automatically.
For example, Ansor actually does cache-related feature extraction
(see the bullet point "Buffer Access Feature" in Appendix B).
It is possible that the cache complexity can be analyzed and extracted automatically,
as it is part of a simple loop analysis,
and if it can be done, we are able to generalize this simple yet effective method to arbitrary workloads
other than matmul and conv2d.

**Correctness.** The paper is correct from the reviewer's perspective.

**Relation to prior work.** The paper doesn't provide comprehensive enough comparison
with some of the related analytical or polyhedral models,
including Tensor Comprehension [2] and MOpt [3].
The reviewer believes that it could be improvement in the rebuttal process.

**Clarity.** Overall looks good. Some annotations need to be declared and explained
before being used. For example, $T_m$ in Theorem 1.

[1] Zheng, Lianmin, et al. "Ansor: Generating high-performance tensor programs for deep learning." 14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20). 2020.

[2] Vasilache, Nicolas, et al. "Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions." arXiv preprint arXiv:1802.04730 (2018).

[3] Li, Rui, et al. "Analytical characterization and design space exploration for optimization of CNNs." Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2021.

limitations_and_societal_impact: 1) Extending to real-world CPU architecture is an interesting future work.
The paper focuses only on an ideal cache model where the cache is single stage and fully associative,
with a simple replacement policy. Therefore, it is less realistic with the modern CPU architecture.
2) Also, the paper didn't consider VNNI and other instructions for low-bit deployment,
which plays an important role in deep learning deployment.
3) It would be very interesting, though non-trivial, to extend the paper to other architectures,
e.g. GPUs and TPUs, because of the different memory hierarchy and execution model.
4) There are other interesting instructions to be used, for example, prefetching.

The reviewer is not aware of any negative social impact on this paper.
review_title: null

Meta-review: The reviewers generally felt that this is an interesting and potentially useful paper. However, there are still outstanding issues. Limited scope (CPUs only), idealized scenario that may not generalize to real-world architectures, clarity issues (some of which were addressed in the discussion), the relatively minor improvement over AutoTVM, and a lack of comparison with other related models. Addressing these will help improve the paper.
Decision: Reject