Le 10/11/2023 par Alix :

Les algorithmes d’apprentissage profond permettent de nos jours de traiter de nombreux problèmes complexes dans des champs disciplinaires variés tels que la vision par ordinateur, la reconnaissance automatique de la parole ou des applications à la santé. Le développement de ces techniques est en grande partie lié à l’essor des moyens de calcul qui permettent l’utilisation de réseaux de neurones beaucoup plus importants en taille.

Les téléphones mobiles et l’arrivée de dispositifs portables intégrant des applications autour de la réalité augmentée ou de la réalité virtuelle nécessitent le développement de dispositifs embarqués capables de supporter des algorithmes d’apprentissage avec un nombre de neurones important. Les systèmes matériels devront alors supporter l’exécution des algorithmes d’inférence avec peu d’énergie consommée et une vitesse élevée [3].

Dans ce stage, on considère un ensemble de réseaux de neurones profonds à exécuter sur une architecture pipelinée. Les contraintes du système sont les suivantes, et correspondent à des hypothèses issues d'architecture AI développées dans un contexte industriel [4].

•  On dispose d'une architecture constituée de $m$ machines ${\cal M}=\{1,2,\ldots m\}$. Chaque machine $k\in{\cal M}$ est composée de $m_k$ processeurs parallèles. La machine ne peut exécuter qu'une tâche à la fois sans préemption;
• Soit ${\cal N}=\{1,\ldots,n\}$ l'ensemble des réseaux de neurones considérés. Chaque réseau de neurones $j\in {\cal N}$ est modélisé par un ensemble de tâches $I_j$ avec des contraintes de précédence sous la forme d'une chaîne.  Pour $1\le i\le |I_j|$  on note $i_j$ la $i^{\agrave eme}$ tâche de la chaine. Chaque tâche $i_j$ correspond à une couche du réseau;  son poids $p_{i_j}$ correspond au nombre de valeurs (ou de neurones) produites par la couche $i_j$; on suppose que le nombre de couches est supérieur ou égal au nombre de machines;
•  La durée d'une tâche $i_j$ lorsqu'elle est faite sur la machine $k$ est  $D(i_j,k)=\lceil \frac{p_{i_j}}{m_k} \rceil$. Elle nécessite une puissance notée $W(i_j,m_k)$. %qui est décroissante pour $i_j$ fixé en fonction du nombre de machines $m_k$.

Une allocation du réseau de neurones $j\in\cal N$ est une fonction $\sigma_j:I_j\rightarrow {\cal M}$ qui alloue à chaque tâche $i_j\in I_j$ une machine, de sorte que chaque machine exécute au moins l'une des tâches de la chaîne et que deux tâches $i_j$ et $\ell_j$ avec $i\le \ell$  sont affectées à des machines telles que $\sigma_j(i_j)\le \sigma_j(\ell_j)$ %surjective et croissante. 
Ainsi, $\sigma_j(1_j)=1$ et $\sigma_j({\vert I_j\vert}_j)=m$. On appelle période de l'allocation de $I_j$ selon $\sigma_j$ la durée maximum d'utilisation d'une machine  $\delta(I_j,\sigma_j)$ pour ce réseau. 

Etant donnés les allocations $\sigma_j$, $j\in \cal N$, la période de l'exécution du système est alors le maximum des périodes 
$\delta(I_j,\sigma_j)$. Le problème consiste à déterminer les allocations $\sigma_1,\ldots \sigma_n$ de période minimale et dont la puissance est bornée par une valeur $W$ fixée.

Ce problème est une version particulière du problème \og Assembly Line Balancing\fg [1]. Pour un seul réseau de neurones, le problème se résout par un algorithme polynomial de programmation dynamique inspiré par [2].

La première question posée pour ce stage est de déterminer si ce type d'approche peut permettre d'obtenir un algorithme polynomial, ou de complexité paramétrée par rapport à un ou plusieurs paramètres à déterminer. Par la suite, on pourra également y introduire des contraintes supplémentaires en lien avec la taille des mémoires entre les différentes machines pour stocker les résultats intermédiaires. Une autre version intéressante du problème est de déterminer les caractéristiques de l'architecture qui permet d'optimiser les deux critères considérées (puissance vs. période).

Les algorithmes obtenus devront être programmés et testés sur des instances générées aléatoirement et sur des réseaux de neurones de la littérature.
Enfin,  les résultats algorithmiques et expérimentaux obtenus viendront à l'appui d'une future publication en revue et/ou en conférence internationale.

Conditions du stage
Le stage aura lieu en $2024$ au LIP6 sur le campus Pierre et Marie Curie (4 place Jussieu, 75252 Paris) et sera co-encadr\'e par Claire Hanen et Alix Munier Kordon pour une durée
de $6$ mois. 
La gratification prévue est approximativement de $580$ Euros par mois.

Le candidat doit être en Master $2$ de recherche opérationnelle, de mathématiques appliquées, d'informatique ou une école
d'ingénieur avec un cursus en informatique.
Il doit avoir de solides connaissances en programmation et en algorithmique.

Pour postuler, envoyez par mail aux deux encadrantes Claire.Hanen@lip6.fr et Alix.Munier@lip6.fr un CV avec au minimum les notes de $M1$ et
de $M2$.

Références 
[1] Nils Boysen, Philipp Schulze, and Armin Scholl. Assembly line balancing : What happened in the last fifteen years ? European Journal of Operational Research, 301(3) :797–814, 2022.
[2] Michael Held, Richard M Karp, and Richard Shareshian. Assembly-line balancing—dynamic programming with precedence constraints. Operations research, 11(3) :442–459, 1963.
[3] Yann LeCun. 1.1 deep learning hardware : Past, present, and future. In 2019 IEEE International Solid-State Circuits Conference - (ISSCC), pages 12–19, 2019.
[4] Ali Oudrhiri, Emilien Taly, Nathan Bain, Alix Munier-Kordon, Roberto Guizzetti, and Pascal Urard. Performance Modeling and Estimation of a Configurable Output Stationary Neural Network Accelerator. working paper or preprint, July 2023.