Instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which
is an important step for improving the performance of object code produced by a compiler. Put more
simply, it tries to avoid pipeline stalls by rearranging the order of instructions without changing the
meaning of the code. Nevertheless, even for simple processors, solving the problem is NP-complete.
However, modern processors have multiple pipelined functional units and can issue more than one
instruction per clock cycle, which makes the problem even more difficult in pratice. This has led
to the belief that in production compilers, a heuristic or approximation algorithm approach must be
used rather than an exact approach to instruction scheduling [1].
Monte Carlo tree search (MCTS) is a heuristic search algorithm which can be used for some decision
processes. It uses randomness for deterministic problems difficult or impossible to solve using other
approaches. More precisely, MCTS focuses on the promising moves, expanding the search tree based
on random sampling of the search space. Roughly, MCTS process can be divided into four steps:
• Selection: start from root and select successive child nodes until a leaf node is reached. The
section is generally based on the exploitation/exploration paradigm;
• Expansion: unless the leaf is a finite state, new child are created and one of them is chosen to
be developed;
• Simulation: try several configurations (often randomly generated) in order to estimate the node
that was just opened at the expansion phase;
• Backpropagation: use the result of the simulation in order to update information in the nodes
on the path from the root to the node opened at the expansion phase.
The aim of this work is to design a MCTS solver for the instruction scheduling problem. The
objectives for this internship are as follows:
The aim of this work is to design a MCTS solver for the instruction scheduling problem. The
objectives for this internship are as follows:• implementing a generic platform to manage the MCTS process;
• designing and evaluating an instruction scheduling solver based on the platform implemented;
• verifying the coherence of the computed results by implementing an adhoc solution checker.
Contact: jean.marie.lagniez@huawei.com