DOCSEARCHbyAlgolia
Submit Docs

AlphaDev Documentation

repository·main·Indexed 20 days ago

https://github.com/google-deepmind/alphadev

A repository providing pseudocode and discovered assembly programs for faster sorting algorithms found using deep reinforcement learning. It includes the Assembly Game RL environment, AlphaZero-based agent logic, and verified assembly programs for fixed-size and variable-size sorters.

Tokens
511
Snippets
1
Records
3
Agent score
23%

What's inside AlphaDev

  1. Understand the AlphaDev RL environment and agent components

    main

    The alphadev.py module provides pseudocode for reproducing the AlphaDev agent and the Assembly Game RL environment. The core components are:

    • AssemblyGame: Represents the Assembly Game RL environment. The state includes the current program, memory, and registers. Calling the step method adds a new assembly instruction to the program. Rewards are calculated based on a combination of correctness and latency over an input distribution. Note: The assembly runner is not included; execution can be delegated to external libraries like AsmJit.
    • AlphaDevConfig: Stores hyperparameters for the AlphaDev agent, including configurations for AlphaZero, MCTS, and the underlying networks.
    • play_game: Contains the logic for running an AlphaDev game, including the MCTS procedure and game storage.
    • RepresentationNet and PredictionNet: Implement the networks used in the AlphaZero algorithm, utilizing a MultiQuery Transformer to represent assembly instructions.

  2. Install and run assembly program tests

    main

    To verify the correctness of the discovered assembly sorting programs, you must use bazel. The repository officially supports Linux with clang, though other platforms may work.

    To run the tests defined in sort_functions_test.cc, use the following command:

    CC=clang bazel test :sort_functions_test

  3. Reference discovered assembly sorting programs

    main

    The repository includes several discovered assembly programs for sorting elements, which are verified in sort_functions_test.cc. These include fixed-size sorters and variable-size sorters:

    Fixed-size sorters:

    • Sort3AlphaDev: 3 elements, 17 instructions
    • Sort4AlphaDev: 4 elements, 28 instructions
    • Sort5AlphaDev: 5 elements, 43 instructions
    • Sort6AlphaDev: 6 elements, 57 instructions
    • Sort7AlphaDev: 7 elements, 76 instructions
    • Sort8AlphaDev: 8 elements, 91 instructions

    Variable-size sorters:

    • VarSort3AlphaDev: up to 3 elements, 25 instructions
    • VarSort4AlphaDev: up to 4 elements, 57 instructions
    • VarSort5AlphaDev: up to 5 elements, 80 instructions