Fast Linear Interpolation for Piecewise-Linear Functions, GAMs, and Deep Lattice Networks
Authors: Nathan Zhang
Kevin Canini
Sean Silva
and Maya R. Gupta
Venue:  (2020)
Keywords: hardware
compiler
MLIR
runtime
CPU
interpolation

Abstract: We present fast implementations of linear interpolation operators for both piecewise linear functions and multi-dimensional look-up tables. We use a compiler-based solution (using MLIR) for accelerating this family of workloads. On real-world multi-layer lattice models and a standard CPU, we show these strategies deliver $5-10\times$ faster runtimes 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.

Under review as a conference paper at ICLR 2020
FAST LINEAR INTERPOLATION FOR PIECEWISE-LINEAN FUNCTIONS, GAMS, AND DEEP LATTICE NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We present fast implementations of linear interpolation operators for piecewise linear functions and multi-dimensional look-up tables. We use a compiler-base based solution using MLIR to accelerate this family of workloads. On two-layer and deep lattice networks, we show these strategies run 5 - 10x faster on a standard CPU compared C++ interpreter implementation that uses prior techniques. producing runtimes that are 1000s of times faster than TensorFlow 2.0 for single evaluations.
INTRODUCTION
Linearly-interpolated look-up tables (LUTs) are core operation of many machine-learned mod- els, ranging from simple one-dimensional piccewise-lincal (PWL) functions (see Fig. D. to D- dimensional generalized additive models (Hastie & Tibshirani] 1986 (GAMs) that are a linear combination of PWL on each input variable, to D-dimensional interpolated LUTs also known as lattices. Interpolated LUTs can be used efficiently express arbitrarily flexible functions over an arbitrary number of inputs D by increasing the size of the underlying LUTs, or by using ensembles or multiple layers of lattices (Canini et al., 2016 You et al., 2017 Cotter et al.) 2019).
Interpolated LUT's have long been standard choice for applications where fast evaluation and flexible models are needed. For example, two-layer models formed by PWLs followed by lattices are part of the International Color Consortium standard for colorspace transformations (Sharma & Bala, 2002). Garcia & Gupta (2009) showed that lattices can be trained by empirical risk minimization. As concerns grow about the black-box nature of AI, the highly-structree nature of interpolated LUTs has made them a popular choice for producing AI with safety guarantees such as bounded outputs and satisfying shape constraints (Groeneboom & Jongbloed 2014 Chetverikov al. 2018). such as monotonicity which guarantee that a model only responds positively to increases in designated inputs (Barlow et al. 1972. Howard & Jebara, 2007: Gupta et al. 2016); Canini al. 2016 You
et al., 2017). and other shape constraints (Pya & Wood 2015
Chen & Samworth 2016: Gupta
al. 2018 Cotter al. 2019).
Fast evaluation of models is paramount for real-time estimation needs, and cheap evaluation is key lowering the costs of AI. In theory, what makes interpolating LUTs so fast is that only small subset of parameters is needed for any given evaluation, in contrast to models like DNNs where every parameter may be needed for every evaluation.
In this paper we investigate how fast one can evaluate interpolated LUT's on standard CPUs. The main contributions of this paper are: (i) we give two new strategies to reduce the runtime PWLs, and (ii) show how to optimize the kernels for two types of multi-dimensional linear interpolation (simplex and multilinear). Overall we show a 5-10x speed-up for the runtime of real-world lattice models, compared
C++ interpreter implementation that uses prior techniques, producing times that are 1000s of times faster than TensorFlow 2.0 for single evaluations. All comparisons are on the same standard CPUs.

---

Under review as a conference paper at ICLR 2020
07
Let j max such that k; S x
114
15
1/
Then f(x) = wy (z))z + +(1 (1- (1-=s(x))ess)
07
where w,(x) kit1 I
kj+1 - Kg
01
1/2
kg
kg
ks
Ko
lry
Kg
Figure 1: An example PWL defined by key-value pairs, and the formula for linearly interpolating the PWL at any point r E (ki,k)) (inputs outside the domain are clipped to the domain).
BACKGROUND ON LINEAR INTERPOLATION OPERATORS AND SOME INITIAL ANALYSIS
We review PWLs and the two standard types of multi-ddimensional interpolation, and what the chal- lenges are in making them run fast.
2.1 PIECEWISE-LINES FUNCTIONS (PWLS)
PWLs old technique for efficiently representing functions (Sang 1875 Perry 1899 Farr 1860). Multi-layer machine-learned models may use thousands of PWLs to transform the inputs in their first-layer. which makes the overall performance of lattice model highly sensitive to the runtime of the PWL kernel. As illustrated in Fig. []] we define a PWL by N key-value pairs (k,, o.) where the keys are sorted K; k4+1, and the values are interpolated to evaluate any input x: E [k1, kx] as the formula in Fig. [
The key challenge to efficiently evaluating PWLS to quickly find the index in the linear in- terpolation formula in Fig. needed for given x. We estimate the cost of memory load and compare at cycles speculative memory loads are allowed, and 4 cycles if they are not, due to the 2-3 cycle latency of memory load. Each branch misprediction costs expected 15-20 cy- cles depending on architecture (Fog, 2018). As a result, we estimate the overall expected cost to be El# Cycles] 4 x El# Comparisons] + 17 x E(# Mispredictions]. Here, assume that all parameters are within the L.1-cache because there are few enough parameters to be loaded together.
2.1.1 LINEAR SEARCH FOR PWLS IS SLOW, EVEN FOR SMALL PWLS
Linear search over the N keypointss requires E[# Comparisons] this section, it is the branch mispredictions that are the bigger problem. Recent recommendations for machine-learned lattice models, e.g. (Gupta et al. 2016 2018), on the quantiles of the training examples for that input: assign keypoint k to the minimum possible value of the PWL's domain, assign the last keypoint ky the maximum possible value of the PWL's domain, and assign the remaining N - keypoints to equally-spaced quantiles of the training trained (though their corresponding values {2:} are trained). Quantile keypoints are good for machine-leariigg because each keypoint sees roughly 1/N of the training examples, reducing the chance of overfitting any of the trained PWL values {. Quantile keypoints also aid in interpretability because the PWI. can be visualized, and quantile keypoints show how the training data was distributed over the input domain. However, next show that quantile keypoints terrible for PWL runtimes because each keypoint equally likely to be the left-keypoint for a random input æ.
N+11 However, as show in
set the keypoints based
examples' inputs. We assume the keypoints stay fixed at these values and
Recall that branch predictor predicts whether not given branch is taken, and optimal branch predictor always predicts the outcome associated with the highest probability. During the linear search, branch prediction will predict whether the for-loop over the keypoints will stop, for each i = 1....,N. N. Typically, a branch predictor is able to access a summary its history, and any static information the compiler may be able to provide. For quantile keypoints, each of the
2

---

3 to 10, and is the baseline Under review as a conference paper at ICLR 2020
first N keypoints is equally likely to be the correct index. Thus the optimal branch prediction
to continue unless the linear search has reached i = N - 2, in which case there is a 50-50 chance of either of the remaining two keypoints being the right one. However, (N -2)((N 1) of the examples will find their correct index before the linear search reaches i = N 2, which means the branch prediction will he wrong once with probability (N 22/(N 1), producing E|# Mispredictions] = (N - () - 1).
2.1.2 BINARY SEARCH FOR PWLS
In a branch-free implementation of binary search with known depth, the compiler is able to fully unroll the structure and thus avoid branch mispredictions. Additionally, well-optimized binary search implementation is able to perform each step of the binary search in approximately cycles [Khuong 2012). It thus takes binary search roughly 2 x more efficient than linear search even for that any proposed indexing must beat.
[log cycles to find the appropriate location. This makes
2.1.3 A MAP-TO-INDE FUNCTION FOR PWLS
More abstractly, the goal is to construct an efficient function that can map an input x to the correct index j. An old trick is to build an auxiliary LUT over [K1, kN] with B uniformly-spaced buckets, use that to map z to bucket, and then linearly-search through all the keypoints that fell in that bucket. However, with irregularly-see sasacer keypoints, a uniform bucket can still have (NN) key- points search through. Aus & Korn (1969) proposed constructing hierarchy of such auxiliary uniformly-spaced LUTs to better cover irregular keypoints. O'Grady & Young (199T) proposed us- ing sufficiently large B such that uniform bucket contains more than one keypoint, but the cost of potentially large B. An analogous problem arises in database indexing. where recent work has proposed muchine-learning two-layer DNN to produce the map-to-index function (Kraska et al. 2018). Our proposed solution will be in a similar spirit but lighter-weight.
2.2 MULTILINEAR INTERPOLATION
Consider cell of D-dimensional LUT, which without loss of generality is a D-dimensional unit hypercube parameterized by LUT values v E R22 corresponding to the ((2)) vertices of 2-
the hypercube. For an input E [0, 1] multilinear interpolation outputs f() 2i (,w,(r),
where v, is the stored multi-d LUT value for the ith vertex in the D-dimensional unit hypercube, and w. (x)) the multilinear interpolation weight on the ith unit hypercube vertex & E [0, 1)2 taken in lexicographical order, computed from x E [0. 1] as:
(x(x))
II x Sild (1 x2)) I-Ea for all i =1, 1,...,20 2D d=1
For example, for D E 0, & 1, and thus w (x) 1 and w2(w)) x, the same in given that there are only two keypoints h = 0 and k2 = 1. For D = 2, this is standard bilinear interpolation.
the PWL formula in Fig.
Gupta et al. (2016) gave an O(2P) dynamic programming algorithm for computing
We note that while asymptotically efficient, the dynamic programming solution introduces loop-carry de- pendency, and thus prevents critical compiler optimizations, a problem we show how to avoid.
2.3 SIMPLEX INTERPOLATION
Simplex interpolation a more efficient linear interpolation of a D-dimensional LUT cell that pro- duces locally linear surface comprised of D! pieces. For each input [0, 1] the D components of x are sorted, the resulting sort order determines a set D + vertices whose simplex is guar- anteed to contain æ, and then sparse inner product is taken with the corresponding D + LUT values to produce fxx (Rovatti et al. 1998 Weiser & Zarantonello 1988 Gupta et al. 2016). This algorithm is the same as the Lovász extension submodularity (Bach 2013).
Gupta et al. (2016) gave runtimes for single-layer models that only did either multilinear and simplex interpolation and were implemented in C++ single-threaded 3.5GHz Intel Ivy Bridge proces-
3

---

Under review as a conference paper at ICLR 2020
sor: for D = 4 inputs both interpolations ran in about 50 nanoseconds, but for D 20, simplex interpolation ran in 750 nanoseconds, and multilinear interpolation ran in 12 milliseconds, around 15,000x slower. Despite the slower runtime for D > 4, multilinear interpolation might be preferred because it produces a smoother surface and might produce more accurate models for some prob- lems. Furthermore, the large-scale multiplications needed for multilinear a better match than the sorting needed for simplex for machine learning libraries such as TensorFlow.
Like with PWLs, branch prediction poses a significant challenge when implementing the simplex interpolation kernel. For example, we found that LLVM defaults to using either a hard-coded inser- tion sort or quicksort depending on the input size, which is determined at runtime. However, we note that this run-time decision is not needed for machine learning models, because the number of inputs D is fixed and known. Using std: : sort worttstttto <std: : ppai pairrdoublle sorting operation accounts for approximately 70% of the simplex kernel's overall runtime.
i int>>> we found that the
COMPILATION MATTERS DUE To LARGE DISPATCH OVERHEAD
Recent work investigated the use of compilers to speed-up machine-learned models (Rotem et al. 2018 Chen al. 2018 Vasilache et al., 2018), but focused models with large operations, such as convolutional networks or large matrix mullipliess models, where the operations takes hundreds of times longer than the dispatch process. For example, ResNett34 performs 3.6 billion floating point ops across 34 layers, averaging over 100 million floating point operations per kernel (He et al., 2016). In contrast, for small operation models like linear interpolation, the cost of dispatch can be bigger than the computation, and thus reducing dispatch overhead becomes key. For example, the proprietary multi-layer lattice models described this paper execute at most a few thousand floating point ops per kernel, and many useful models use a few hundred or fewer ops per kernel. Additionally, many usages of lattice models are to evaluate a single example at a time in a latency- sensitive pipeline, negating the chance to amortize overhead by batching.
To reduce dispatch overhead, we use the MLIR framework (Google 2019) to convert the trained models into compiler-optimized C++ code. This change alone removes significant portion of the dispatch overhead, providing a speedup of 3x. In the next sections, we show how to reduce the runtime further by taking advantage of the details of the linear interpolation ops.
4 How To MAKE PWLS RUN FASTER
We describe two complementary techniques for making PWLs run faster. In Section 4.1 we show how to construct a better auxiliary mnde--mapping function that takes into account the spacing of the keypoints. In Section 4 we show that ensemble or deep lattice models often pass the same input through multiple PWLs, allowing us to remove redundant index searches.
4.1 KEYPOINT DEPENDENT OPTIMIZATION
We propose a new way to construct an index mapping function m that first transforms the keypoints to be more uniformly-spacee index using an optimal number of uniform buckets. The resulting implementation is constant-time in the number pieces in the PWL.
and then applies an auxiliary LUT to map the transformed space to an
Let (x) be the cost of evaluating the mapping of correcting the predicted keypoint index. This naturally produces the procedure x - m(x) + Adjust(m(z)). If we know the model will be evaluated random examples propose finding the mapping m from a family of possible mapping function M that minimizes the expected cost over random examples to be evaluated:
an input x, and Cm.Adjus (x) be the cost
P. then
arg min P + Cm,AAjjst(())) mE.M
We propose using mappings of the form m(x) LUT + (T(x) where T supp(P) - R is some 1-d monotonic transform, and LUT has B uniformly spaced buckets of size that each map to the smallest index encountered in the bucket's interval.
4

---

Under review as a conference paper at ICLR 2020
100
double, untuned
Amortized Time (ns)
750
double, tuned
double, opt
500
float, untuned
float, tuned
250
float, opt
16
64
256
1024
Batch Size
Figure 2: The effect of the proposed optimized index-mapping on calibrated multilinear model with 8 PWLs. Untumed refers to the compiled implementation using an auxiliary mapping function that has B = 50 uniform buckets. Tuned refers to our proposed keypoint-dependen tuned index mapping. Opr also uses bounded linear search
We estimate the cost Cr (x) be Cr(z) + XB where relatively insensitive parameter that should represents the cache behavior cost of large arrays, and is set to 0.001 for all of our experiments.
For most modern CPUs, the branch-misprediccton penalty is high, so we propose Adjust and T functions that are branch-free. A consequence that the cost Cr(x) = CT is independent x, and we set the Adjust function to be fixed-step linear search that always executes the worst-case number steps needed. With these choices, the mapping optimization of ( becomes:
(Cr+AB+
max Index(r) LUT(La + (T())) (=Exupp(P)
arg min BER,
(3)
where Index(2) x)) is the correct left keypoint index for æ, and supp P) is the support of the probability
distribution æ. Note the adjustment cost maxpesipp(() Index(2) - LUT[L [[a + (T is created by the pair of points with maximally different indices that get mapped to the same bucket:
max Index(æ:) Index(z) such that |a (T(x)) E.ppsppp(P)
[a (T(=))
(4)
Next we show how to take advantage of the case that the keypoints are quantile keypoints as de- scribed in Section 2. If we set the LUT to span the keypoint range [Na, kx)] the worst case ad- justment needed in (4) is defined by the maximum number of the N corresponds to keypoint, and hence possible Index) that end up in the same bucket. Thus, the optimal transform would map the irregularly-ppaced keypoints to a uniform spacing, and the re- sulting worst-case adjustment would be [NN 2}/B]. Actually finding that optimal T we leave as future work. Experimentally, we approximated T by choosing the best out of a small fixed set of simple monotonic transformations, including fast approximate log2(x) and an approximate 2", which resulted in needing at most 3 steps for the Adjust linear scan for our models. We note that the problem of constructing T, m in general, may be problem well suited for superoptimizers.
quantiles (each of which
Fig. 2 gives example speed-ups for a two-layer calibrated lattice model with 8 PWLs in its first layer (described in Section as whole path model).
4.2 EFFICIENT HANDLING OF SHARED INDEX PWL.S
Next, we consider models that have shared index PWLs such that the same input is passed through multiple PWLs in order transform the same input in different ways. As a very simple example, the one-dimensional function fxx 3
2n.² for E [0, 1] can be represented as the sum of four PWLs on the same input. This situation commonly arises with ensembles calibrated lattices (Canini et al. 2016). If the keypoints are the same for each PWL for quantile keypoints). then the work to determine the proper parameter index is duplicated across all PWLs that act the same input. We propose model transformation step to convert the PWL execution into separate indexing and interpolation phases so we can map each input x to its index only once for all PWLS the input
input (as is the case
5

---

Under review as a conference paper at ICLR 2020
Sign (1)
Exponent (8)
Mantissa (23)
Mantissa (23 (Ng)(N))
Index (log,(N)
Figure 3: We propose encoding the index in the low-order bits of the interpolation weight for better memory usage. For the double-precision floating point format the exponent instead has 11 bits and the mantissa has 53 bits.
The proposed indexing phase takes in input and finds the index and the interpolation weight wy (z: to form the pair (j. wy(xx) (x)), which is needed by all the PWLs that act on x. Then the proposed interpolation phase consumes this pair compute each PWL's interpolated value using its PWL values as (z) + Us+1 (1 - ww(()), as in Fig.
However, this requires handling the pair (j, my (2r) efficiently. A naive solution would encode this information literally as a pair of values (j Ind, wz(x) Real). To avoid the need to separately track the integer portion of the pair, we propose bit-packing technique that encodes the index in the low-order bits of the interpolation weight as shown in Fig. We originally tried a different strategy of adding the index (an integer) to the interpolation weight (in [0, 1). However, modern processors have 4 cycle latency when converting an int to a double to execute that addition, and another 4 cycles extract the index back to an int. Our proposal in i faster, because only requires bit mask and an OR to encode the index (2 cycles), and only a bit mask to decode the index (1 cycle). The precision loss of these two approaches similar: our proposal loses log2(N) low-order bits from the interpolation weight, while the alternate approach loses [log2(1)] bits to encode index i. This proposal uses half the memory as the original pair of values, even though we only remove an int, because standard compilers like Clang add padding for memory alignment (Raymond 2019).
Consider an index-weight pair (j, (y(m)) (z)), where (x)(x) E [0, 1) is computed with absolute precision It.. Then this encoding method results in a new precision of (e x (N)1). The interpolation can then be expressed as (y x (1 + (e x 2[logg (N)I)) + +0++1 (1 - wy (=) (1 + ( 2 ((00))))))))), which produces an absolute error of at most 2 max("), 1)+1) x (#t(e x (N)1). Note that e = 2-23 23 for single-precision floating point numbers, so the overall error is small, but caution should nevertheless be exercised when constructing deep networks using single precision.
On the real-world ensembles calibrated lattices models that we tested this on, this technique provided 10% speedup when compared against the alternate packing scheme, with larger speed-ups for models with more shared indexing.
5 How To MAKE MULTILINEAR INTERPOLATION RUN FASTER
Gupta et al. 2016) give (22)) dynamic programming algorithm for multilinear interpolation that iterates over the D inputs, and on each iteration doubles the number of computed weights. Thus the last iteration is half of the work, but for that last iteration, we note that one can interleave in the next step of computing the inner product between the interpolation weights and the LUT values. This interleaving of operations helps the processor be productive while the next value fetched. This trick is an example of latency hiding. popular computing technique for performing useful work while waiting on a data fetch (Manjikian) 1997; Mowry 1991), and critical for performance using accelerators (Chen et al. 20188) get this latency hiding, we take the trained model parameters, and generate C++ code for the multilinear interpolation such that the compiler will do this interleaving. This provides around 10- (5%5 end-to-end speed-up up for many models.
How TO MAKE SIMPLEX INTERPOLATION RUN FASTER
As described in Algorithm of Gupta et al. (016). the simplex interpolation algorithm requires sorting permutation æ over the inputs. On D-dimensional hypercube, the simplex interpolation

---

Under review as a conference paper at ICLR 2020
requires D+ weights, but constructing the sorting permutation requires O(Dlog(D)) comparisons which we found dominates the overall runtime.
As with piccewise linear functions, the cost of even single branch misprediction is high, so desire a branch-free algorithm. We use sorting networks (Batcher 1968), which construct sequences of max and min operations in order construct branch-free sorting implementation for inputs of fixed size.
A sorting permutation would typically be constructed by sorting (key, index) pairs, but such paired min-max operations require a comparison followed by six conditional moves. We note that sorting over basic datatypes is much more efficient: min-max on basic datatypes only requires a min and max operation, requiring fewer than half the cycles. This is particularly important for the small sorting problems that arise in simplex interpolation (D generally 2 was25), since small sorting problems can be handled almost entirely in registers, meaning optimal sorting code is effectively purely computation. To leverage this more efficient sorting, we adopt the same bit-packing technique described in Fig. [] encoding the index in the low-order bits. The lost precision on the key is (D)] bits; a lattice with 28 parameters would lose 5 bits of precision. By definition the interpolation weights are each w; E [0, 1), so we can bound the absolute error each w; by <[log2(D) As a result, the interpolation output has relative error of at most e [[log(())
7 PERFORMANCE EVALUATION
To illustrate the overall value of these proposals, some of which synergize, we compare runtimes on four machine-learned multi-layer lattice models: one benchmark and three proprictary (described below).
Our baseline a C++ interpreter implementation of the interpolation algorithms described in Gupta et al.] (2016), with the added speed-up that it uses fixed auxiliary index mndex-map for each PWL with no transform T, B = 50 uniform buckets, a = k1, 3 = (k,, -k)) k10/50. We benchmarked this C++ inter- preter code at 397x x faster than TensorFlow Lattice (Google Al Blog 2017) for single-evaluations on a two-layer calibrated lattice model with inputs (the model was just PWL.s followed by four- dimensional lattice interpolated with multilinear interpolation). TensorFlow does get more efficient when evaluated on batches: for batch size of 4,000 examples, the amortized runtime is only 13x slower than C++ interpreter baseline.
Simplex Interpolation: Fig. 4 shows runtime results for two models where the lattices are interpo- lated with simplex interpolation. For these we show the baseline interpreter runtime, and the runtime produced by an interpreter with our proposed simplex kernel that uses bit-packing, and a compiled implementation with all of proposals (faster PWLs and faster simplex) for both double and float. The proposed bit- bit-packing for the simplex kernel does lose a small amount of precision. The worst observed deviation in model output when compared to the C++ implementation was 10-13 for double-precision evaluation and 10 for single-precision.
The left results in Fig. 4 are for the Kaggle Wine dataset using the Kaggle notebook used in Gupta et al. (2018). There are 150 inputs, but all of them are Boolean features except for one continuous feature, which passes through five 40-piece PWLs. The second-layer layer is an ensemble of 50 lattices, each of which acts on 8 first-layer outputs. Runtime was compared on 84.6k IID examples, and the proposals delivered speed-ups of 5.8 9.5x.
The right results in Fare for proprietary selector model that predicts whether certain database should queried for results in response to a given query. The model is an ensemble of 200 cali- brated lattices, each on 8 features, so each of the 30 inputs is mapped through an average of 53.33 PWLs in the model's 's first layer. The PWLs have an average of 15 pieces each. Runtime was com- pared on 650k IID examples, and the proposals delivered speed-ups of 5 6.5x.
Multilinear Interpolation: Fig. 5 shows runtime results for two models where the lattices are interpolated with multilinear interpolation. For these, show the baseline interpreter runtime, and the runtime for a compiled implementation with all of our proposals (faster PWLS and latency hiding for multilinear) for both double and float.
The left results in Fig. 5 are for a proprietary model that predicts how long will take a car to travel given road. The model is 4-layer model 39 inputs, where the first layer passes the 39 inputs
7

---

Under review as a conference paper at ICLR 2020
100
Interpreter
15
75
Interpreter
Amortized Time
Lattice
10
50
Compiler
(double)
25
Compiler
(foat
0
4
16
64
256
1024
1
16
64
256
1024
Batch Size
Batch Size
Figure 4: Left: Wine Model. The proposed strategies with float (in red) is 5.8 9.5x faster than the baseline interpreter (in dark green). Right: Selector Model. The proposed strategies with float (in red) is 6.5x faster than the baseline interpreter (in dark green).
10000
2000
Amortized Time (ns)
Interpreter
7500
1500
Compiler (double)
5000
1000
Compiler (float)
2500
500
4
16
64
2561022
256
1024
16
1024
Batch Size
Batch Size
Figure 5: Left: Travel Time Estimation Model. The proposed strategies with float (in red) is 5.25 11.5x faster than the baseline interpreter (in dark green). The big speed-up here is because there lot of PWLs compared to the other operations, and the proposed indexed calibrator strategy takes advantage of the fact that there are 4 PWLs for each of 39 inputs. Right: Whole Path Model. The proposed strategies with float (in red) is 3.7 4.4x faster than the baseline interpreter (in dark green). For this relatively small model, much of the speed-up up came just from moving to the compiler.
through 156 PWLs (each input goes through different PWLs) where each PWL has 50 pieces. The second layer is linear embedding that maps the 156 calibrated inputs down to four dimensions, then another calibrator layer PWLs. The final layer takes those four inputs and fuses another four inputs with eight-dimensional lattice and multilinear interpolation. Runtime compared on 94k IID examples, and the proposals delivered speed-ups of 5.25 11.5x.
The right results in Fig. 5 are for proprietary model that fuses travel time estimates for different parts of a route into travel time estimate for the whole path. This model is a 2-layer calibrated lattice model 8 inputs, with PWLs that have 100-168 pieces. Runtime was compared on million IID examples, and the proposals delivered speed-ups of 3.7 444x.
8 CONCLUSIONS AND OPEN QUESTIONS
This paper presents set of techniques for fast implementations of linear interpolation, using both operation-level optimizations and compiler transformations, which together demonstrate 3-1 11x speed-ups compared to an interpreter-basee implementation on several benchmark and real-world models. These speedups are achieved by reducing both fixed overhead costs well improving the efficiency of per-example computations. In real-world applications, latency-sensitive MI. models must often score one example at time, so the fixed overheads cannot be reduced by simply batching examples. Here we focused CPUs, which are cheap and readily available. Faster solutions may possible with GPUs, but if the inputs are not already on the GPU, then this may not net win due to the kernel launch latency of GPU. We hypothesize that significantly faster speeds might be possible with FPGAs.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
H. M. Aus and G. A. Korn. Table-bokuppmncepolatiion function generation for soedtpoint digital computations. IEEE Trans. Computers, 18:745-749, 1969.
Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, 6(2), 2013.
R. Barlow, D. J. Bartholomew, J. Bremner, and H. D. Brunk. Statistical inference under order restrictions; the theory and application of isotonic regression. Wiley, New York, USA, 1972.
K. E. Batcher. Sorting networks and their applications. In Proceedings of the April 30-May 2, 1968, spring joint computer conference, pp. 307-314, ACM, 1968.
K. Canini, A. Cotter, M. M. Fard, M. R. Gupta, and J. Pfeifer. Fast and flexible monotonic functions with ensembles of lattices. Advances in Neural Information Processing Systems (NIPS), 2016.
T. Chen, T. Moreau, Z. Jiang, L. Zheng, E. Yan, H. Shen, M. Cowan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, and A. Krishnamurthy. TVM: An automated end-to-end optimizing compiler for deep learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, pp. 578,594, 2018.
Y. Chen and R. J. Samworth. Generalized additive and index models with shape constraints, Journal Royal Statistical Society B, 2016.
D. Chetverikov, A. Santos, and A. M. Shaikh. The econometrics shape restrictions. Annual Review of Economics, 2018.
A. Cotter, M. Gupta, H. Jiang. E. Louidor, J. Muller, T. Narayan, S. Wang, and Zhu. Shape constraints for set functions. ICML, 2019.
W. Farr. On the construction of life tables, illustrated by new life table of the healthy districts of england. Journal of the Institute of Actuaries, 9:121-141, 1860.
A. Fog. https: /www agner.
ze mi wrr.ccccrrrrcccitcctrree.
2018.
E. K. Garcia and M. R. Gupta. Lattice regression. Advances in Neural Information Processing Systems (NIPS), 2009.
Google. MLIR: Multi-level intermediate representation for compiler infrastructure, 2019. URL
https:/ //tp:////ttttttttt www./tenooffoow//ooooooooooooooe
Google AI Blog. knowledge, 2017.
Tensorflow URL
lattice:
Flexibility
empowered by prior
https://ai. /ttp:://a..goggebllo..oomm wtt.a//0ccccoom0///10000 tensorflow wwwp:wwwaattteee-teee wew.ticcfflexxbiittt.. html
P. Groeneboom and G. Jongbloed. Nonparametric estimation under shape constraints. Cambridge Press, New York, USA, 2014.
M. R. Gupta, A. Cotter, J. Pfeifer, K. Voevodski, K. Canini, A. Mangylox, W. Moczydlowski, and A. Van Esbroeck. Monotonic calibrated interpolated look-up tables. Journal of Machine Learning Research, 17(109):--47, 2016.
M. Gupta, D. Bahri, A. Cotter, and K. Canini. Diminishing returns shape constraints for inter- pretability and regularization. Advances in Neural Information Processing Systems (NIPS), 2018.
T. Hastic and R. Tibshirani. Generalized additive models. Statistical Science, 1(3):297-310, 08 1986.
K. He. X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. pp. 770-778, 06 2016. doi: 10.1 109/CVPR.20066900
A. Howard and T. Jebara. Learning monotonic transformations for classification. In Advances in Neural Information Processing Systems, 2007.

---

Under review as a conference paper at ICLR 2020
P. Khuong.
Binary
search
*eliminates* branch
mis mis-predictions,
2012.
ctlkk/.a/BBBaa http://wwww.ppa..aaalo////////// URL -ttessttarr---aee
o htw.aaatatttaaa--aaaaaaaaaaeeaaa
Kraska, A. Beutel, Chi, Dean, and N. Polyzotis. The case for learned index structures. SIGMOD, 2018.
N. Manjikian. Combining loop fusion with prefetching on shared-memory multiprocessors. In Proceedings the 1997 International Conference Parallel Processing, pp. 78 82, Aug 1997.
Mowry. Tolerating latency through softwarecontrolleed data prefetching. PhD Thesis, 1991.
E. P. O'Grady and B.-K. Young. A hardware-oriented algorithm fo floating-point function genera- tion. IEEE Trans. Computers, 40:237-241, 1991.
Perry. Practical Mathematics. Wiley and Sons, 1899.
N. Pya and S. Wood. Shape constrained additive models. Statistics and Computing, 2015.
E. Raymond. The lost art of structure packing, 2019. URL Structure-packine
N. Rotem, J. Fix, Abdulrasool, S. Deng, R. Dzhabarov, J. Hegeman, R. Levenstein, B. Maher, N. Satish, J. Olesen, J. Park, A. Rakhov, and M. Smelyanskiy. Glow: Graph lowering compiler
techniques for neural networks. CoRR, abs/1805.00901. 2018. URL hatp:://axii...a.../////////
abs 100./1855.00 00907
R. Rovatti, M. Borgatti, and R. Guerrieri. A geometric approach to maximum-speed n-dimensional continuous linear interpolation rectangular grids. IEEE Trans. on Computers, 47(8):894-899, 1998.
E. Sang. On last-place enrors in Vlacq's table of logarithms. Proceedings of the Royal Society of Edinburgh, 8:371-376, 1875.
G. Sharma and R. Bala. Digital Color Imaging Handbook. CRC Press, New York, 2002.
N. Vasilache, O. Zinenko, T. Theodoridis, P. Goyal, Z. DeVito, W. S. Moses, S. Verdoolaege, A. Adams, and A. Cohen. Tensor comprehensions: Framework-agnostt high-performance ma- chine learning abstractions. CoRR, abs/1882.04430, 2018. URL httt::///rxiiv.tr//aa 18C2.04733
A. Weiser and S. F. Zarantonello. note on piecewise linear and multilinear table interpolation in many dimensions. Mathematics of Computation,
January 1988.
You, K. Canini, D. Ding, Pfeifer, and M. R. Gupta. Deep lattice networks. Advances Neural Information Processing Systems (NIPS), 2017.
10


Reviews:
[{"review_id": "SkghvLwZ9H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\nAuthors 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.\nThey compare proposed method to C++ interpreter implementation on two-layer and deep lattice networks and achieve 5-10x speed improvements.\n\nIt 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. \nMoreover, 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.  \n\nIt would be better to highlight why the proposed method is meaningful and provide more background knowledge to understand this paper. \n\nThis is only consider optimization on CPUs. What about the case of using GPUs?\n\nIs branch free assumption for functions ‘Adjust’ & ‘T’ is valid? (I don’t have much knowledge on compiler..)", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "H1xNJi32KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nGiven 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):\n\n(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.\n\n(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.\n\n(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?\n\n(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. \n\n(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?\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlQ28YpFB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\n- 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.\n- A memory-efficient bit-packing technique to store both integer and floating point representations together.\n- Speed-up for multilinear interpolation using latency hiding\n- Branch-free implementation of sorting permutation, needed for simplex interpolation\nThe 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.\n\nWhile 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.\n\nStrengths\n- The paper is well-motivated and relevant to the ML community\n- Low-level speed optimizations are needed but overlooked in the community\n- Reasonable choice of experimental conditions (focus on unbatched CPU evaluation, testing on a selection of 4 different tasks)\n- Proposed techniques are sensible\n\nWeaknesses (roughly in order of decreasing significance)\n- 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.\n- 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).\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- The introduction could be a bit more concrete on describing tasks where PWLs are relevant", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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