Interpolating and extrapolating memoization in the Planning C language

Cover Page

Cite item

Full Text

Abstract

This paper discusses the possibilities of increasing the speed of execution of programs that implement mainly mathematical algorithms using some special types of memoization. A brief overview of the existing basic approaches to memoization is carried out, and a conclusion is made about the lack of knowledge of the possibilities of explicit program memoization based on one or another method of approximating the results missing in the memoization cache. The possibilities of such memoization are analyzed, the syntax and semantics of possible program constructions are described, indicating the need for its inclusion for functions/procedures (void functions). The proposed variants of memoization are tested, it is shown that for some mathematical algorithms, a significant acceleration of work is possible with a fairly low error. The novelty of this study lies in the fact that for the first time the syntax, semantics and basic mechanisms for implementing explicit program memoization based on interpolation (by neural networks of direct propagation or by the method of group accounting of arguments) or linear extrapolation are proposed and described. This memoization is introduced into the Planning C language. The conditions of justification of memoization are formulated. For the proposed variant of memoization, the concept of a grouping parameter is introduced, which allows using sets of interpolators for various combinations of input arguments of a memoized procedure/function in order to reduce additional time spent on training the interpolator and increase the likelihood of its results. The concept of an ordinal parameter used to establish the order of key points of extrapolating memoization is also introduced. The adequacy of the proposed approaches and memoization algorithms is shown by a number of examples from the field of numerical modeling.

About the authors

Vladimir Viktorovich Pekunov

Email: pekunov@mail.ru

References

  1. Городняя Л.В. Парадигмы программирования. Часть 4. Параллельное программирование //Новосибирск. Препринт ИСИ СО РАН. – URL: http://www.iis.nsk.su/files/preprints/gorodnyaya_175.pdf (дата обращения: 05.11.2021).
  2. Mayfield, James, Timothy W. Finin and M. R. Hall. Using automatic memoization as a software engineering tool in real-world AI systems // Proceedings the 11th Conference on Artificial Intelligence for Applications (1995): pp.87-93.
  3. Perl 5.34.0 Documentation. URL: https://perldoc.perl.org/Memoize (дата обращения: 05.11.2021)
  4. Arjun Suresh, Bharath Narasimha Swamy, Erven Rohou, and Andre Seznec. Intercepting functions for memoization: A case study using transcendental functions // ACM Trans. Architec. Code Optim. 12, 2, Article 18 (June 2015), 23 pages. DOI: http://dx.doi.org/10.1145/2751559
  5. Y. Kamiya, T. Tsumura, H. Matsuo and Y. Nakashima. A Speculative Technique for Auto-Memoization Processor with Multithreading // Proc. International Conference on Parallel and Distributed Computing, Applications and Technologies, 2009, pp. 160-166, doi: 10.1109/PDCAT.2009.67.
  6. G. Zhang and D. Sanchez. Leveraging Hardware Caches for Memoization // IEEE Computer Architecture Letters, vol. 17, no. 1, pp. 59-63, 1 Jan.-June 2018, doi: 10.1109/LCA.2017.2762308.
  7. M. H. Lipasti and J. P. Shen. Exceeding the dataflow limit via value prediction // Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture. MICRO 29, 1996, pp. 226-237, doi: 10.1109/MICRO.1996.566464.
  8. B. Calder, G. Reinman and D. M. Tullsen. Selective value prediction // Proceedings of the 26th International Symposium on Computer Architecture (Cat. No.99CB36367), 1999, pp. 64-74, doi: 10.1109/ISCA.1999.765940.
  9. Yiannakis Sazeides and James E. Smith. The predictability of data values // In Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture (MICRO 30). IEEE Computer Society, USA,1997, pp. 248-258.
  10. Evers, M., Yeh, T.Y. Understanding branches and designing branch predictors for high performance microprocessors // Proceedings of the IEEE 89, 1610-1620 (2001).
  11. Monchiero M., Palermo G. (2005) The Combined Perceptron Branch Predictor. // In: Cunha J.C., Medeiros P.D. (eds) Euro-Par 2005 Parallel Processing. Euro-Par 2005. Lecture Notes in Computer Science, vol 3648. Springer, Berlin, Heidelberg. DOI:https://doi.org/10.1007/11549468_56
  12. Salil Pant and Greg Byrd. A case for using value prediction to improve performance of transactional memory // In TRANSACT ’09: 4th Workshop on Transactional Computing, feb 2009. URL: http://transact09.cs.washington.edu/35_paper.pdf (дата обращения: 31.08.2020).
  13. Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. Neural acceleration for generalpurpose approximate programs // In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-45). 449-460. DOI:http://dx.doi.org/10.1109/MICRO.2012.48.
  14. Пекунов В.В. Язык программирования Planning C. Инструментальные средства. Новые подходы к обучению нейронных сетей. – LAP LAMBERT Academic Publishing, 2017. – 171 с.
  15. Дюк, В., Самойленко, А. Data mining: учебный курс. СПб: Питер, 2001.
  16. Пекунов, В.В. Новые методы параллельного моделирования распространения загрязнений в окрестности промышленных и муниципальных объектов // Дис. докт. тех. наук. – Иваново, 2009. – 274 с.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).