{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:09:23Z","timestamp":1750306163676,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,12,5]],"date-time":"2016-12-05T00:00:00Z","timestamp":1480896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TaMaDi project of the French ANR","award":["ANR 2010 BLAN 0203 01"],"award-info":[{"award-number":["ANR 2010 BLAN 0203 01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>The IEEE 754-2008 standard recommends the correct rounding of some elementary functions. This requires solving the Table Maker\u2019s Dilemma (TMD), which implies a huge amount of CPU computation time. In this article, we consider accelerating such computations, namely the Lef\u00e8vre algorithm on graphics processing units (GPUs), which are massively parallel architectures with a partial single instruction, multiple data execution.<\/jats:p>\n          <jats:p>We first propose an analysis of the Lef\u00e8vre hard-to-round argument search using the concept of continued fractions. We then propose a new parallel search algorithm that is much more efficient on GPUs thanks to its more regular control flow. We also present an efficient hybrid CPU-GPU deployment of the generation of the polynomial approximations required in the Lef\u00e8vre algorithm. In the end, we manage to obtain overall speedups up to 53.4 \u00d7 on one GPU over a sequential CPU execution and up to 7.1 \u00d7 over a hex-core CPU, which enable a much faster solution of the TMD for the double-precision format.<\/jats:p>","DOI":"10.1145\/2935746","type":"journal-article","created":{"date-parts":[[2016,12,6]],"date-time":"2016-12-06T16:03:07Z","timestamp":1481040187000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["GPU-Accelerated Generation of Correctly Rounded Elementary Functions"],"prefix":"10.1145","volume":"43","author":[{"given":"Pierre","family":"Fortin","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9s and CNRS, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mourad","family":"Gouicem","sequence":"additional","affiliation":[{"name":"LIRMM, CNRS\/Universit\u00e9 Montpellier 2, Sorbonne Universit\u00e9s, and CNRS, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stef","family":"Graillat","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9s and CNRS, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"volume-title":"Modern Computer Arithmetic","author":"Brent Richard","unstructured":"Richard Brent and Paul Zimmermann . 2010. Modern Computer Arithmetic . Cambridge University Press . Richard Brent and Paul Zimmermann. 2010. Modern Computer Arithmetic. Cambridge University Press.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.5555\/2337159.2337166"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/ASAP.2011.6043267"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/PDP.2012.64"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/PDP.2012.62"},{"volume-title":"Lindemann theorem. Encyclopedia of Mathematics.","author":"Galochkin Aleksandr Ivanovich","unstructured":"Aleksandr Ivanovich Galochkin . 2011. Lindemann theorem. Encyclopedia of Mathematics. Available at http:\/\/www.encyclopediaofmath.org\/index.php?title&equals;Lindemann_theorem&oldid&equals;&equals;14026. Aleksandr Ivanovich Galochkin. 2011. Lindemann theorem. Encyclopedia of Mathematics. Available at http:\/\/www.encyclopediaofmath.org\/index.php?title&equals;Lindemann_theorem&oldid&equals;&equals;14026.","key":"e_1_2_1_6_1"},{"issue":"0","key":"e_1_2_1_7_1","first-page":"1","article-title":"GNU MP","volume":"5","author":"Granlund Torbj\u00f6rn","year":"2010","unstructured":"Torbj\u00f6rn Granlund and the GMP Development Team . 2010 . GNU MP : The GNU Multiple Precision Arithmetic Library. 5 . 0 . 1 . http:\/\/gmplib.org\/. Torbj\u00f6rn Granlund and the GMP Development Team. 2010. GNU MP: The GNU Multiple Precision Arithmetic Library. 5.0.1. http:\/\/gmplib.org\/.","journal-title":"The GNU Multiple Precision Arithmetic Library."},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1964179.1964184"},{"unstructured":"IEEE Computer Society. 2008. IEEE Standard for Floating-Point Arithmetic.  IEEE Computer Society. 2008. IEEE Standard for Floating-Point Arithmetic.","key":"e_1_2_1_9_1"},{"unstructured":"Aleksandr Yakovlevich Khinchin. 1997. Continued Fractions. Dover Mineola NY.  Aleksandr Yakovlevich Khinchin. 1997. Continued Fractions. Dover Mineola NY.","key":"e_1_2_1_10_1"},{"unstructured":"Khronos Group. 2011. The OpenCL Specification Version 1.2.  Khronos Group. 2011. The OpenCL Specification Version 1.2.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1109\/ARITH.2005.32"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.5555\/872021.872470"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1109\/12.736435"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1869389.1869392"},{"unstructured":"Maplesoft. 2016. Maple User Manual.  Maplesoft. 2016. Maple User Manual.","key":"e_1_2_1_17_1"},{"volume-title":"Handbook of Floating-Point Arithmetic","author":"Muller Jean-Michel","unstructured":"Jean-Michel Muller , Nicolas Brisebarre , Florent de Dinechin , Claude-Pierre Jeannerod , Vincent Lef\u00e8vre , Guillaume Melquiond , Nathalie Revol , Damien Stehl\u00e9 , and Serge Torres . 2009. Solving the Table Maker\u2019s Dilemma . In Handbook of Floating-Point Arithmetic . Birkhauser , Boston, MA , 405--460. Jean-Michel Muller, Nicolas Brisebarre, Florent de Dinechin, Claude-Pierre Jeannerod, Vincent Lef\u00e8vre, Guillaume Melquiond, Nathalie Revol, Damien Stehl\u00e9, and Serge Torres. 2009. Solving the Table Maker\u2019s Dilemma. In Handbook of Floating-Point Arithmetic. Birkhauser, Boston, MA, 405--460.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.2316\/P.2011.757-041"},{"unstructured":"Yuri Valentinovich Nesterenko and Michel Waldschmidt. 1996. On the approximation of the values of exponential function and logarithm by algebraic numbers. Mat. Zapiski 23--42. English version available at http:\/\/arxiv.org\/abs\/math\/0002047.  Yuri Valentinovich Nesterenko and Michel Waldschmidt. 1996. On the approximation of the values of exponential function and logarithm by algebraic numbers. Mat. Zapiski 23--42. English version available at http:\/\/arxiv.org\/abs\/math\/0002047.","key":"e_1_2_1_20_1"},{"unstructured":"NVIDIA. 2011. CUDA C Programming Guide version 4.1. NVIDIA.  NVIDIA. 2011. CUDA C Programming Guide version 4.1. NVIDIA.","key":"e_1_2_1_21_1"},{"unstructured":"NVIDIA. 2012a. CUDA C Best Practices Guide version 4.1. NVIDIA.  NVIDIA. 2012a. CUDA C Best Practices Guide version 4.1. NVIDIA.","key":"e_1_2_1_22_1"},{"unstructured":"NVIDIA. 2012b. Parallel Thread Execution ISA Version 3.0. NVIDIA.  NVIDIA. 2012b. Parallel Thread Execution ISA Version 3.0. NVIDIA.","key":"e_1_2_1_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1017\/S0305004100026086"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1017\/S0305004100042195"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/786450.786635"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/TC.2005.55"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1017\/S1446788700031062"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/258726.258745"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/114697.116813"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935746","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2935746","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:56Z","timestamp":1750217996000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935746"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,5]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/2935746"],"URL":"https:\/\/doi.org\/10.1145\/2935746","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2016,12,5]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}