AgeNts Distribues, Robotique, Recherche Opérationnelle, Interaction, DEcision

AgeNts Distribues, Robotique, Recherche Opérationnelle, Interaction, DEcision

By new-androide on Sun, 2019-12-29 15:42

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

Lieu:

Boulogne-Billancourt

Thématiques:

Encadrant:

Jean-Marie Lagnez

Référent Universitaire:

n/a

Attribué:

No

Année:

2 020

Deprecated:

No