Faster sorting algorithms discovered using deep reinforcement learning.
Journal
Nature
ISSN: 1476-4687
Titre abrégé: Nature
Pays: England
ID NLM: 0410462
Informations de publication
Date de publication:
Jun 2023
Jun 2023
Historique:
received:
25
07
2022
accepted:
23
03
2023
medline:
9
6
2023
pubmed:
8
6
2023
entrez:
7
6
2023
Statut:
ppublish
Résumé
Fundamental algorithms such as sorting or hashing are used trillions of times on any given day
Identifiants
pubmed: 37286649
doi: 10.1038/s41586-023-06004-9
pii: 10.1038/s41586-023-06004-9
pmc: PMC10247365
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
257-263Informations de copyright
© 2023. The Author(s).
Références
Amazon. Amazon S3—two trillion objects, 1.1 million requests/second. AWS https://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-million-requests-second/ (2013).
Cormen, T. H. et al. Introduction to Algorithms (MIT Press, 2022).
Gelmi, M. Introduce branchless sorting functions for sort3, sort4 and sort5. LLVM.org https://reviews.llvm.org/D118029 (2022).
Bansal, S. & Aiken, A. Automatic generation of peephole superoptimizers. ACM SIGARCH Comput. Arch. News 34, 394–403 (2006).
Alur, R. et al. Syntax-Guided Synthesis (IEEE, 2013).
Phothilimthana, P. M. et al. Scaling up superoptimization. In Proc. Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems 297–310 (ACM, 2016).
Barthe, G. et al. From relational verification to SIMD loop synthesis. In Proc. of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 123–134 (ACM, 2013).
Schkufza, E., Sharma, R. & Aiken, A. Stochastic superoptimization. ACM SIGPLAN Notices 48, 305–315 (2013).
Bunel, R. et al. Learning to superoptimize programs. In Proc. International Conference on Learning Representations (ICLR, 2016).
Phothilimthana, P. M. et al. Chlorophyll: synthesis-aided compiler for low-power spatial architectures. ACM SIGPLAN Notices 49, 396–407 (2014).
Vinyals, O. et al. Grammar as a foreign language. Adv. Neural Inform. Proc. Syst. 28, 2773–2781 (2015).
Chen, X., Liu, C. & Song, D. Towards synthesizing complex programs from input-output examples. In Proc. International Conference on Learning Representations (ICLR, 2018).
Devlin, J. et al. Robustfill: neural program learning under noisy i/o. In Proc. International Conference on Machine Learning 990–998 (PMLR, 2017).
Li, Y. et al. Competition-level code generation with AlphaCode. Science 378, 1092–1097 (2022).
Pearce, H. et al. Can codex and other large language models help us fix security bugs? Preprint at https://arxiv.org/abs/2112.02125 (2021).
Chen, M. et al. Evaluating large language models trained on code. Preprint at https://arxiv.org/abs/2107.03374 (2021).
Bingmann, T., Marianczuk, J. & Sanders, P. Engineering faster sorters for small sets of items. Software: Pract. Exper. 51, 965–1004 (2021).
Levcopoulos, C. & Petersson, O. Splitsort: an adaptive sorting algorithm. Inform. Proc. Lett. 39, 205–211 (1991).
Helman, D. R., Bader, D. A. & JáJá, J. A randomized parallel sorting algorithm with an experimental study. J. Parallel Distrib. Comput. 52, 1–23 (1998).
Goodrich, M. T. Randomized shellsort: a simple oblivious sorting algorithm. In Proc. of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms 1262–1277 (ACM, 2010).
Mehlhorn, K., Sanders, P. & Sanders, P. Algorithms and Data Structures: The Basic Toolbox Vol. 55. (Springer, 2008).
Knebl, H. Algorithms and Data Structures (Springer, 2020).
Karatzoglou, A., Baltrunas, L. & Shi, Y. Learning to rank for recommender systems. In Proc. of the 7th ACM Conference on Recommender Systems 493–494 (ACM, 2013).
Yang, J. Y., Zhang, B. & Mao, Y. Study on Information Retrieval Sorting Algorithm in Network-BasedManufacturing Environment. In Applied Mechanics and Materials Vol. 484, 183–186 (Trans Tech Publishing, 2014).
Krallmann, J., Schwiegelshohn, U. & Yahyapour, R. On the design and evaluation of job schedulingalgorithms. In Workshop on Job Scheduling Strategies for Parallel Processing 17–42 (Springer, 1999).
White, S. K., Martinez, T. & Rudolph, G. Generating a novel sort algorithm using Reinforcement Programming. In Proc. IEEE Congress on Evolutionary Computation 1–8 (IEEE, 2010).
Srivastava, S., Gulwani, S. & Foster, J. S. From program verification to program synthesis. In Proc. of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 313–326 (ACM, 2010).
Ansel, J. et al. Petabricks: a language and compiler for algorithmic choice. ACM Sigplan Notices 44, 38–49 (2009).
Smith, D. R. The design of divide and conquer algorithms. Sci. Comput. Program. 5, 37–58 (1985).
Irvine, K. R. et al. Assembly Language for Intel-Based Computers (Prentice Hall, 2003).
Shannon, C. E. XXII. Programming a computer for playing chess. London, Edinb. Dublin Philos. Mag. J. Sci. 41.314, 256–275 (1950).
Silver, D. et al. Mastering the game of Go with deep neural networks and tree search. Nature 529, 484–489 (2016).
Silver, D. et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 1140–1144 (2018).
Vaswani, A. et al. Attention is all you need. Adv. Neural Inform. Proc. Syst. 30, 5999–6009 (2017).
LLVM. LLVM users https://llvm.org/Users.html (LLVM, 2022).
Bartlett, J. Learn to Program with Assembly 271–273 (Apress, 2021).
Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction 2nd edn (MIT Press, 2018).
Schrittwieser, J. et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature 588, 604–609 (2020).
Maillard, O.-A., Ryabko, D. & Munos, R. Selecting the state-representation in reinforcement learning. Adv. Neural Inform. Proc. Syst. 24, 2627–2635 (2011).
Qian, R. et al. Spatiotemporal contrastive video representation learning. In Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition 6964–6974 (IEEE, 2021).
Brown, T. et al. Language models are few-shot learners. Adv. Neural Inform. Proc. Syst. 33, 1877–1901 (2020).
Shazeer, N. Fast transformer decoding: one write-head is all you need. Preprint at https://arxiv.org/abs/1911.02150 (2019).
Bundala, D. & Závodny, J. Optimal sorting networks. In Proc. International Conference on Language and Automata Theory and Applications 236–247 (Springer, 2014).
Hahn, G. J. & Meeker, W. Q. Statistical Intervals: A Guide for Practitioners Vol. 92 (John Wiley & Sons, 2011).
Google. Protocol buffers, version 0.2.5; https://developers.google.com/protocol-buffers (2022).
Google. VarInt protocol buffer serialization and deserialization, version 0.2.5; https://developers.google.com/protocol-buffers/docs/encoding (2022).
Protvin, R. & Levenberg, J. Why Google stores billions of lines of code in a single repository. Commun. ACM 59, 78–87 (2016).
Berman, I. et al. Multi-collision resistant hash functions and their applications. In Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques 133–161 (Springer, 2018).
Damgård, I. B. Collision free hash functions and public key signature schemes. In Workshop on the Theory and Application of of Cryptographic Techniques 203–216 (Springer, 1987).
Hwang, M. Sort, Bitset (GitHub, 2021).
Van der Maaten, L. & Hinton, G. Visualizing data using t-SNE. J. Mach. Learn. Res. 9.11, 2579–2605 (2008).
Gulwani, S. et al. Synthesis of loop-free programs. ACM SIGPLAN Notices 46.6, 62–73 (2011).
Sasnauskas, R. et al. Souper: a synthesizing superoptimizer. Preprint at https://arxiv.org/abs/1711.04422 (2017).
Warren, H. S. Hacker’s Delight (Pearson Education, 2013).
Hamadi, Y., Jabbour, S. & Sais, L. ManySAT: a parallel SAT solver. J. Satisfiability, Boolean Model. Comput. 6, 245–262 (2010).
Wolsey, L. A. Mixed integer programming. In Wiley Encyclopedia of Computer Science and Engineering 1–10 (Wiley, 2007).
Nair, V. et al. Solving mixed integer programs using neural networks. Preprint at https://arxiv.org/abs/2012.13349 (2020).
Inoue, H. et al. AA-sort: a new parallel sorting algorithm for multi-core SIMD processors. In Proc. International Conference on Parallel Architecture and Compilation Techniques (PACT 2007) 189–198 (IEEE, 2007).
Yin, Z. et al. Efficient parallel sort on avx-512-based multi-core and many-core architectures. In Proc. IEEE 21st International Conference on High Performance Computing and Communications 168–176 (IEEE, 2019).
Blacher, M. et al. Vectorized and performance-portable Quicksort. Preprint at https://arxiv.org/abs/2205.05982 (2022).
Wikipedia. Single instruction, multiple data https://en.m.wikipedia.org/wiki/SIMD (2022).
Ellis, K. et al. Write, execute, assess: program synthesis with a REPL. Adv. Neural Inform. Proc. Syst.32, 9137–9146 (2019).
Wang, H. et al. Automating reinforcement learning architecture design for code optimization. In Proc. 31st ACM SIGPLAN International Conference on Compiler Construction 129–143 (ACM, 2022).
Shypula, A. G. et al. Learning to superoptimize real-world programs. Preprint at https://arxiv.org/abs/2109.13498 (2022).
Chen, X., Liu, C. & Song, D. Execution-guided neural program synthesis. In Proc. International Conference on Learning Representations (ICLR, 2018).
Bunel, R. et al. Leveraging grammar and reinforcement learning for neural program synthesis. In Proc. International Conference on Learning Representations (ICLR, 2018).
Aharoni, R. & Goldberg, Y. Towards string-to-tree neural machine translation. In Proc. 55th Annual Meeting of the Association for Computational Linguistics132–140 (ACL, 2017).
Dong, L. & Lapata, M. Language to logical form with neural attention. In Proc. 54th Annual Meeting of the Association for Computational Linguistics 33–43 (ACL, 2016).
Ibarz, B. et al. A generalist neural algorithmic learner. In Proc. Learning on Graphs Conference Vol. 198, 2:1–2:23 (PMLR, 2022).
Chen, X., Song, D. & Tian, Y. Latent execution for neural program synthesis beyond domain-specific languages. Adv. Neural Inform. Proc. Syst. 34, 22196–22208 (2021).
Parisotto, E. et al. Neuro-symbolic program synthesis. Preprint at https://arxiv.org/abs/1611.01855 (2016).
Ellis, K., Solar-Lezama, A. & Tenenbaum, J. Sampling for Bayesian program learning. Adv. Neural Inform. Proc. Syst. 29, 1297–1305 (2016).