Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: This paper proposes two techniques for fast linear interpolation on CPUs. They achieved speedups by reducing 1) fixed overhead cost and 2) per example computation (linear interpolation operation level optimization).
Authors consider this problem for small operation models like linear interpolation rather than the models requiring large operations such as ResNet. In this case, dispatch overhead cannot be ignored and so they use the MLIR frameworks to optimize trained model into the C++ code (reducing fixed overhead cost). This results in 2-3x speed up. Secondly, they propose the way to construct auxiliary index-mapping function by considering spacing of the key points rather just using for example evenly spaced index-mapping.
They compare proposed method to C++ interpreter implementation on two-layer and deep lattice networks and achieve 5-10x speed improvements.

It seems the topic of this paper does not fit ICLR and most machine learning researchers are unlikely to be interested in and even understand this paper. This reviewer also does not have enough knowledge and background to judge this paper. But my impression is that achieving speed up using existing MLIR framework has no surprising novelty. 
Moreover, the experimental results seems quite limited in the sense that they only experiment with trained 2 and 4-layer calibrated lattice models which are kind of small.  

It would be better to highlight why the proposed method is meaningful and provide more background knowledge to understand this paper. 

This is only consider optimization on CPUs. What about the case of using GPUs?

Is branch free assumption for functions ‘Adjust’ & ‘T’ is valid? (I don’t have much knowledge on compiler..)
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes several low-level code optimizations aimed at speeding up evaluation time for linearly interpolated look-up tables, a method often used in situations where fast evaluation times are required. The paper is very practically oriented in the sense that it does not aim for improving asymptotic speed-ups, but rather real speed-ups expressible in terms of CPU cycles that are achievable by exploiting compiler optimizations such as branch prediction and loop unrolling. The focus is on unbatched computations which can arise in many real-time situations. The proposed implementation techniques are as follows:
- A method for fast index mapping, which first transforms inputs using a monotonic function such as log_2 or 2^x, and the applying a branch-free linear search implementation on a uniformly-spaced auxiliary LUT.
- A memory-efficient bit-packing technique to store both integer and floating point representations together.
- Speed-up for multilinear interpolation using latency hiding
- Branch-free implementation of sorting permutation, needed for simplex interpolation
The proposed implementation is then evaluated on 4 different benchmarks, with considerable speed gains over interpreter-based baselines, while batching and single-vs-double precision do not have major impact on speed.

While the paper is relevant and interesting, and the proposed techniques are reasonable and probably result of a considerable amount of work, more effort is needed to improve clarity and preciseness of the explanations, and (most importantly) the experimental evaluation. Detailed strengths and weaknesses are outlined below.

Strengths
- The paper is well-motivated and relevant to the ML community
- Low-level speed optimizations are needed but overlooked in the community
- Reasonable choice of experimental conditions (focus on unbatched CPU evaluation, testing on a selection of 4 different tasks)
- Proposed techniques are sensible

Weaknesses (roughly in order of decreasing significance)
- Gains over Tensorflow performance is advertised in the intro, but only mentioned anecdotally in the experiments. Also, the Tensorflow implementation should be briefly explained to make clear where these gains come from.
- The experiments put much focus on speed performance over different batch sizes, but this is (1) not the focus of the paper (unbatched CPU operation is the focus), and (2) is little informative because the introduced methods (which do not benefit much from batching) are not compared against Tensorflow (which does benefit from batching).
- No ablation study is presented. The method description mentions informally how much speed-up is to be expected from different parts of the proposed method, but do not clarify how much this contributes to overall speed-gains.
- The description in 4.1 is rather hard to follow, even though the ideas behind it are relatively simple. An illustrative figure might be of help for readers.
- The method description in 4.1 lacks formal preciseness. For example, in 4.1. alpha, P, supp, are not defined (or in some cases introduced much after they are used first), and the “+4” in the beginning of page 5 appears out of nowhere.
- The proposed bit-packing is not well motivated. It promises to save half of the memory at a minor loss in precision (at least for the double-precision case), but it is unclear how much of a bottleneck this memory consumption is in the first place. In addition, it remains unclear to me why this is relevant particularly in the shared index case.
- While the topic is relevant for this conference, readers are likely not familiar with some of the concepts used in the paper, and a bit more explanation is needed. An example for this is “branch prediction”, which is a key concept; readers unfamiliar with this compiler concept will likely not understand the paper, and a brief explanation is needed. Another example is “loop-carry dependency”, a term that could be explained in a short footnote. A third example is FPGA, which is mentioned in the very last sentence without further explanation/justification.
- The introduction could be a bit more concrete on describing tasks where PWLs are relevant
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: The paper proposed several adjustments to speed up the existing implementations of piece-wise linear functions based on Look-up tables (LUT), including an auxiliary LUT through optimisation and sacrificing negligible precision in the standard IEEE754 protocol to reduce the time complexity.  

Given my limited experience in the field, I have several concerns and questions after reading this paper several times, which eventually leads to my decision (hopefully it was an educated one):

(1) The paper assumes that the input distribution is known to the system, but it is only true in the testing mode where we generally assume that samples in the test set come from the same distribution which is used to generate training examples. In the case where training is required or finetuning is needed to adapt the system to another distribution, the the proposed auxiliary LUT could have a hard time mapping input data properly.

(2) In my understanding, the transformation, T: supp(P) -> R, is assumed to be known whilst IMO it is crucial to the proposed method. A non-trivial effort is expected in finding T, and a whole area of research is dedicated to this which is Optimal Transport. Currently, plausible and computationally efficient method is through Sinkhorn algorithm. I don't think the paper should downplay the part of finding T as it is crucial.

(3) In the shared Index PWLs, the paper seems to have ignored the fact that different functions still have different output values, and different key-value pairs are indeed needed. For example, log(x) and x^2 (as used in the paper) have different input domains and output domains, so sharing indices between two functions is impossible. Could the authors elaborate on why it is okay to share indices?

(4) A necessary process of LUT from piece-wise linear functions of approximating the ones that we care about is to conduct 1-D density estimation on the input domain, since more fine-grained splits are required in the dense area and less splits elsewhere. The proposed methods in this paper seem to have largely ignored this effect. For example, log(x) needs splits with smaller intervals when the x is around 1. 

(5) The presented results only include the speed of the forward computation of several models. It is okay if there is a performance (accuracy or likelihood) and speed trade-off, but the paper didn't present any results on this. Could the authors present some results for this?


review_title: Official Blind Review #3

Meta-review: This paper proposes an efficient implementation of piecewise linear functions.

While this paper tackles a problem of large apparent interest, as noted by the reviewers the paper (1) is pretty far from the domain of the average ICLR paper, and (2) not written with the high standards of clarity that would make it accessible to the average ICLR reader. I am not impugning on the merits of the paper itself, but would suggest that the authors both take the reviewer's advice with regards to the clarity issues (among other) and consider submitting to the Systems for ML workshop, a systems conference, a compilers conference, or some other venue with a larger percentage of qualified readers (and reviewers).
Decision: Reject