More Web Proxy on the site http://driver.im/

research-article

Open access

Fast Linear Interpolation

Authors:

Maya GuptaAuthors Info & Claims

ACM Journal on Emerging Technologies in Computing Systems (JETC), Volume 17, Issue 2

Article No.: 20, Pages 1 - 15

https://doi.org/10.1145/3423184

Published: 15 April 2021 Publication History

All formats PDF

Abstract

We present fast implementations of linear interpolation operators for piecewise linear functions and multi-dimensional look-up tables. These operators are common for efficient transformations in image processing and are the core operations needed for lattice models like deep lattice networks, a popular machine learning function class for interpretable, shape-constrained machine learning. We present new strategies for an efficient compiler-based solution using MLIR to accelerate linear interpolation. For real-world machine-learned multi-layer lattice models that use multidimensional linear interpolation, we show these strategies run 5-10× faster on a standard CPU compared to an optimized C++ interpreter implementation.

References

[1]

H. M. Aus and G. A. Korn. 1969. Table-lookup/interpolation function generation for fixed-point digital computations. IEEE Trans. Comput. 18 (1969), 745--749.

Digital Library

[2]

F. Bach. 2013. Learning with submodular functions: A convex optimization perspective. Found. Trends Mach. Learn. 6, 2 (2013).

[3]

K. E. Batcher. 1968. Sorting networks and their applications. In Proceedings of AFIPS. ACM, New York, NY, 307--314.

Digital Library

[4]

K. Canini, A. Cotter, M. M. Fard, M. R. Gupta, and J. Pfeifer. 2016. Fast and flexible monotonic functions with ensembles of lattices. Adv. Neural Info. Process. Syst. 29, 1 (2016), 2927--2935.

[5]

Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An automated end-to-end optimizing compiler for deep learning. In Proceedings of OSDI. USENIX, 578--594. Retrieved from https://www.usenix.org/conference/osdi18/presentation/chen.

[6]

M. Codish, L. Cruz-Filipe, M. Frank, and P. Schneider-Kamp. 2014. Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten). In Proceedings of ICTAI. IEEE Computer Society, 186--193.

[7]

Andrew Cotter, Maya Gupta, Heinrich Jiang, Erez Louidor, James Muller, Tamann Narayan, Serena Wang, and Tao Zhu. 2019. Shape constraints for set functions. In Proceedings of MLR, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. 1388--1396. Retrieved from http://proceedings.mlr.press/v97/cotter19a.html.

[8]

W. Farr. 1860. On the construction of life tables, illustrated by a new life table of the healthy districts of England. J. Inst. Actuar. 9 (1860), 121--141.

[9]

A. Fog. 2018. Retrieved from https://www.agner.org/optimize/microarchitecture.pdf.

[10]

Eric Garcia and Maya Gupta. 2009. Lattice regression. In Advances in Neural Information Processing Systems, vol. 22, Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (Eds.). Curran Associates, 594--602. Retrieved from http://papers.nips.cc/paper/3694-lattice-regression.pdf.

[11]

E. K. Garcia, R. Arora, and M. R. Gupta. 2012. Optimized regression for efficient function evaluation. IEEE Trans. Image Process. 21, 9 (2012), 4128--4140.

Digital Library

[12]

M. R. Gupta, D. Bahri, A. Cotter, and K. Canini. 2018. Diminishing returns shape constraints for interpretability and regularization. Adv. Neural Info. Process. Syst. 31, 1 (2018), 6835--6845.

[13]

M. R. Gupta, A. Cotter, J. Pfeifer, K. Voevodski, K. Canini, A. Mangylov, W. Moczydlowski, and A. Van Esbroeck. 2016. Monotonic calibrated interpolated look-up tables. J. Mach. Learn. Res. 17, 109 (2016), 1--47.

[14]

M. R. Gupta, E. Louidor, N. Morioka, T. Narayan, and S. Zhao. 2020. Multi-dimensional shape constraints. In Proceedings of ICML (2020).

[15]

K. He, X. Zhang, S. Ren, and J. Sun. 2016. Deep residual learning for image recognition. In Proceedings of CVPR.770--778.

[16]

A. Howard and T. Jebara. 2007. Learning monotonic transformations for classification. In Advances in Neural Information Processing Systems. MIT Press.

[17]

Zhihao Jia, Sina Lin, Charles R. Qi, and Alex Aiken. 2018. Exploring hidden dimensions in parallelizing convolutional neural networks. In Proceedings of the 35th International Conference on Machine Learning (ICML’18). 2279--2288. Retrieved from http://proceedings.mlr.press/v80/jia18a.html.

[18]

P. Khuong. 2012. Binary Search *Eliminates* Branch Mis-predictions. Retrieved from https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/.

[19]

T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. 2018. The case for learned index structures. In Proceedings of SIGMOD’18.

[20]

Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2020. MLIR: A Compiler Infrastructure for the End of Moore’s Law. Retrieved from https://arxiv:cs.PL/2002.11054.

[21]

N. Manjikian. 1997. Combining loop fusion with prefetching on shared-memory multiprocessors. In Proceedings of the International Conference on Parallel Processing. 78--82.

Digital Library

[22]

T. Mowry. 1991. Tolerating latency through software controlled data prefetching. PhD Thesis, Stanford University.

[23]

E. P. O’Grady and B.-K. Young. 1991. A hardware-oriented algorithm for floating-point function generation. IEEE Trans. Comput. 40 (1991), 237--241.

Digital Library

[24]

J. Perry. 1899. Practical Mathematics. Wiley and Sons.

[25]

N. Rotem, J. Fix, S. Abdulrasool, S. Deng, R. Dzhabarov, J. Hegeman, R. Levenstein, B. Maher, N. Satish, J. Olesen, J. Park, A. Rakhov, and M. Smelyanskiy. 2018. Glow: Graph lowering compiler techniques for neural networks. Retrieved from http://arxiv.org/abs/1805.00907.

[26]

R. Rovatti, M. Borgatti, and R. Guerrieri. 1998. A geometric approach to maximum-speed n-dimensional continuous linear interpolation in rectangular grids. IEEE Trans. Comput. 47, 8 (1998), 894--899.

Digital Library

[27]

E. Sang. 1875. On last-place errors in Vlacq’s table of logarithms. Proc. Roy. Soc. Edinburgh 8 (1875), 371--376.

[28]

G. Sharma and R. Bala. 2002. Digital Color Imaging Handbook. CRC Press, New York.

[29]

Arvind K. Sujeeth, HyoukJoong Lee, Kevin J. Brown, Hassan Chafi, Michael Wu, Anand R. Atreya, Kunle Olukotun, Tiark Rompf, and Martin Odersky. 2011. OptiML: An implicitly parallel domain-specific language for machine learning. In Proceedings of ICML.

[30]

TensorFlow Blog. 2020. TensorFlow Lattice: Flexible, Controlled, and Interpretable ML. Retrieved from https://blog.tensorflow.org/2020/02/tensorflow-lattice-flexible-controlled-and-interpretable-ML.html.

[31]

N. Vasilache, O. Zinenko, T. Theodoridis, P. Goyal, Z. DeVito, W. S. Moses, S. Verdoolaege, A. Adams, and A. Cohen. 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. Retrieved from http://arxiv.org/abs/1802.04730.

[32]

S. Wang and M. R. Gupta. 2020. Deontological ethics by monotonicity shape constraints. In Proceedings of AIStats.

[33]

A. Weiser and S. E. Zarantonello. 1988. A note on piecewise linear and multilinear table interpolation in many dimensions. Math. Comp. 50, 181 (Jan. 1988), 189--196.

[34]

S. You, K. Canini, D. Ding, J. Pfeifer, and M. R. Gupta. 2017. Deep lattice networks and partial monotonic functions. Adv. Neural Info. Process. Syst. 30, 1 (2017), 2985--2993.

Cited By

Yu SXie LLu CQian YLiu ZSongze DYu SXie LLu CQian YLiu ZSongze D(2024)Research on Design of Electric Vehicle Sound Synthesis Based on Frequency Shift AlgorithmSAE Technical Paper Series10.4271/2024-01-2335Online publication date: 16-Apr-2024
https://doi.org/10.4271/2024-01-2335
Bin Kamilin MYamaguchi SBin Ahmadon M(2024)Radian Scaling and Its Application to Enhance Electricity Load Forecasting in Smart Cities Against Concept DriftSmart Cities10.3390/smartcities70601337:6(3412-3436)Online publication date: 8-Nov-2024
https://doi.org/10.3390/smartcities7060133
Chakkour T(2024)High-quality implementation for a continuous-in-time financial API in C#Frontiers in Computer Science10.3389/fcomp.2024.13710526Online publication date: 25-Jul-2024
https://doi.org/10.3389/fcomp.2024.1371052
Show More Cited By

Index Terms

Fast Linear Interpolation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

High accuracy geometric Hermite interpolation

We describe a parametric cubic spline interpolation scheme for planar curves which is based on an idea of Sabin for the construction of C^1 bicubic parametric spline surfaces. The method is a natural generalization of [standard] Hermite interpolation. ...
A note on cubic polynomial interpolation

''The NURBS Book'' [L. Piegl, W. Tiller, The NURBS Book, second edn, Springer, 1997] is very popular in the fields of computer aided geometric design (CAGD) and geometric modeling. In Section 9.5.2 of the book, the well-known problem of the local cubic ...
Shape-preserving, multiscale interpolation by univariate curvature-based cubic L₁ splines in cartesian and polar coordinates

We investigate C¹-smooth univariate curvature-based cubic L₁ interpolating splines in Cartesian and polar coordinates. The coefficients of these splines are calculated by minimizing the L₁ norm of curvature. We compare these curvature-based cubic L₁ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal on Emerging Technologies in Computing Systems

ACM Journal on Emerging Technologies in Computing Systems Volume 17, Issue 2

Hardware and Algorithms for Efficient Machine Learning

April 2021

360 pages

ISSN:1550-4832

EISSN:1550-4840

DOI:10.1145/3446841

Editor:
Ramesh Karri
Polytechnic Institute of New York University, USA

Issue’s Table of Contents

Copyright © 2021 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 15 April 2021

Accepted: 01 September 2020

Received: 01 April 2020

Published in JETC Volume 17, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
5,145
Total Downloads

Downloads (Last 12 months)1,801
Downloads (Last 6 weeks)169

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu SXie LLu CQian YLiu ZSongze DYu SXie LLu CQian YLiu ZSongze D(2024)Research on Design of Electric Vehicle Sound Synthesis Based on Frequency Shift AlgorithmSAE Technical Paper Series10.4271/2024-01-2335Online publication date: 16-Apr-2024
https://doi.org/10.4271/2024-01-2335
Bin Kamilin MYamaguchi SBin Ahmadon M(2024)Radian Scaling and Its Application to Enhance Electricity Load Forecasting in Smart Cities Against Concept DriftSmart Cities10.3390/smartcities70601337:6(3412-3436)Online publication date: 8-Nov-2024
https://doi.org/10.3390/smartcities7060133
Chakkour T(2024)High-quality implementation for a continuous-in-time financial API in C#Frontiers in Computer Science10.3389/fcomp.2024.13710526Online publication date: 25-Jul-2024
https://doi.org/10.3389/fcomp.2024.1371052
Abilova FAbilov MSelimkhanov E(2024)Construction of parallel one-dimensional interpolators in C++Herald of Dagestan State Technical University. Technical Sciences10.21822/2073-6185-2023-50-4-37-5050:4(37-50)Online publication date: 21-Jan-2024
https://doi.org/10.21822/2073-6185-2023-50-4-37-50
Grossmann TKomorowska ULatz JSchönlieb C(2024)Can physics-informed neural networks beat the finite element method?IMA Journal of Applied Mathematics10.1093/imamat/hxae01189:1(143-174)Online publication date: 23-May-2024
https://doi.org/10.1093/imamat/hxae011
Qin BZhang YYang LYang YZhang MZhou YYang Y(2024)Quickly Calculating the Activity Coefficient of a NaCl Solution Based on Machine Learning AlgorithmsACS Omega10.1021/acsomega.4c08313Online publication date: 5-Nov-2024
https://doi.org/10.1021/acsomega.4c08313
Zhang XChai XQiu FHu YDong YLi WCheng Z(2024)Characteristic Investigation on Fluid Signals Based on a Combination of Empirical Mode Decomposition and Hilbert Transform in a Jet Impact-Negative Pressure Deamination ReactorIndustrial & Engineering Chemistry Research10.1021/acs.iecr.4c0062763:26(11654-11669)Online publication date: 20-Jun-2024
https://doi.org/10.1021/acs.iecr.4c00627
Yao TLi YLi YZhu YWang GYue J(2023)Cross-modal Semantically Augmented Network for Image-text MatchingACM Transactions on Multimedia Computing, Communications, and Applications10.1145/363135620:4(1-18)Online publication date: 11-Dec-2023
https://dl.acm.org/doi/10.1145/3631356
Zhang HLi YLi X(2023)Constrained Bipartite Graph Learning for Imbalanced Multi-Modal RetrievalIEEE Transactions on Multimedia10.1109/TMM.2023.332388426(4502-4514)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1109/TMM.2023.3323884
Huang JKang PHan NChen YFang XGao HZhou G(2023)Two-Stage Asymmetric Similarity Preserving Hashing for Cross-Modal RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.328398436:1(429-444)Online publication date: 8-Jun-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3283984
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents