We present fast implementations of linear interpolation operators for piecewise linear functions and multi-dimensional look-up tables. We use a compiler-based solution using MLIR to accelerate this family of workloads. On two-layer and deep lattice networks, we show these strategies run 5 − 10× faster on a standard CPU compared to a C++ interpreter implementation that uses prior techniques, producing runtimes that are 1000s of times faster than TensorFlow 2.0 for single evaluations.
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