Pushing the limits : different kinds of multithreading and GNO. The text below is the theory of the different kinds of multithreading to understand the GNO multithreading. I need help to locate and understand the GNO multithreading. MULTITHREAD CONCURRENT Le principe est d'associer plusieurs threads à chaque processeur. Lorsqu'une latence a pour effet de bloquer l'exécution d'un thread, alors une commutation de contexte est réalisée afin de lancer l'exécution d'un autre thread. Si le temps de commutation de contexte est faible par rapport au temps d'accès aux données alors il est possible de recouvrir les latences par du traitement (issu d'autres threads). Le nombre d'instructions contenues dans un thread étant très faible, il s'avère qu'un thread est caractérisé par un contexte d'exécution très réduit (seulement quelques registres). Il est donc possible d'intégrer les mécanismes nécessaires à une commutation de contexte efficace au niveau du matériel. En général, cela se fait au niveau du processeur qui intègre plusieurs ensembles de registres. Dans ce cas, le temps de commutation est faible. Toutefois, ce temps de commutation n'est pas toujours aussi faible qu'il y paraît car il se peut qu'une commutation de contexte engendre le besoin de recharger les différents caches (instructions et/ou données). Il n'existe pas de préemption entre les threads, ce qui veut dire que leur exécution ne peut pas être interrompue. En d'autres termes, un thread s'exécute jusqu'à ce qu'il soit bloqué à cause d'une latence ou bien qu'il se termine. Là, c'est lui-même qui commute de contexte afin de permettre l'exécution d'un autre thread. Inversement, pour qu'un thread ait des chances de s'exécuter, il faut que le thread actuellement actif commute de contexte. Le nombre moyen d'instructions exécutées entre deux commutations de contexte (ce qui est appelé la granularité) ainsi que le nombre de threads associés à chaque processeur vont jouer un rôle important dans l'obtention des performances. En effet, une granularité fine générera beaucoup de commutations de contexte. Si le nombre de threads est insuffisant alors les latences ne seront que partiellement recouvertes. Sans compter que ces commutations risquent d'engendrer des défauts de cache et donc d'induire des latences supplémentaires. En contrepartie, chaque thread aura plus de chances d'accéder à la ressource d'exécution. A l'opposé, une granularité grossière ne permettra que très rarement l'exécution de chaque thread. Ceci sera d'autant plus vrai que le nombre de threads sera important. Par contre, peu de threads sont nécessaires pour recouvrir une latence et le nombre de commutations de contexte est réduit. Il n'existe pas de règles qui permettent de s'assurer de l'obtention d'un maximum de performances. Des études comparatives ont été menées et il apparaît que la granularité des threads et leur nombre doivent être déterminés en fonction de l'algorithme mais aussi en fonction de la machine d'exécution. Une autre préoccupation est de déterminer quel est l'instant le plus favorable pour réaliser la commutation de contexte. C'est ce qui a donné naissance à plusieurs modèles de commutation. Le modèle SWITCH-EVERY-CYCLE Dans ce modèle, le processeur commute vers un thread différent après chaque instruction, ou bien, à chaque cycle, le processeur exécute une instruction issue d'un thread différent. Ce qui revient à faire du temps partagé au niveau des threads. Ceux-ci disposent de la ressource d'exécution chacun à leur tour et pour une durée limitée (une instruction). Cette approche est intéressante car les threads n'ont pas à attendre que la ressource d'exécution soit disponible. De plus, cela permet d'exploiter efficacement les architectures pipeline des processeurs actuels puisqu'il n'y a plus de dépendances entre les données et les instructions qui sont dans le pipeline. Mais ce modèle nécessite la mise en oeuvre de mécanismes d'ordonnancement très complexe. De plus, les performances en simple thread sont restreintes. Le modèle SWITCH-ON-LOAD Dans ce modèle, une commutation de contexte a lieu à chaque fois qu'un thread émet une requête de chargement d'une donnée distante. Les écritures ou émissions de données n'engendrent pas de commutations car le thread n'a pas besoin d'attendre la terminaison de ces opérations pour pouvoir continuer à s'exécuter. L'avantage est qu'un thread peut s'exécuter avec un maximum de performances jusqu'à ce qu'il ait besoin de charger une donnée distante et donc de commuter de contexte. Par contre, un thread peut être sujet à des commutations de contexte fréquentes s'il doit charger beaucoup de données, ce qui va dégrader ses performances. Dans ce cas, is serait plus intéressant pour lui de pouvoir regrouper les chargements de données afin de commuter moins souvent. Le modèle SWITCH-ON-USE Un compilateur peut organiser les données de manière à initier le chargement d'une donnée distante, plusieurs instructions avant de l'utiliser. La commutation de contexte n'aura lieu qu'au moment d'utiliser la donnée. Dans ce cas, le thread recouvre lui-même une partie de la latence. Ceci est intéressant quand il y a peu de threads en concurrence. L'intérêt majeur de ne commuter de contexte que lors de l'utilisation de la donnée plutôt que lors de son chargement est qu'il est possible de regrouper le chargement de plusieurs données. Dans ce cas, la commutation de contexte aura lieu seulement lors de l'utilisation de la première d'entre elles. Le thread ne pourra être de nouveau activé que lorsque toutes les données seront disponibles. Le modèle EXPLICIT-SWITCH Ce modèle permet également d'exploiter les avantages du regroupement des chargements des données distantes. Le principe est d'insérer explicitement une commutation de contexte entre les chargements et l'utilisation des données. L'avantage est de laisser au programmeur la décision de l'instant où il faut commuter de contexte. Ce qui lui laisse la possibilité d'orchestrer de manière plus souple le multithread. De plus, le programmeur a la possibilité d'affiner la granularité d'un thread en insérant de manière judicieuse de telles commutations. Le modèle FORK-AND-JOIN Ce modèle est une autre alternative au regroupement des chargements des données distantes. Ici, un thread va donner naissance à d'autres threads à l'aide de l'instruction fork. Chacun d'eux va initier le chargement d'une donnée puis va commuter de contexte (SWITCH-ON-LOAD). Lorsque le chargement est effectif, le thread va exécuter l'instruction join (tous les threads exécuteront la même instruction join). Si le thread n'est pas le dernier à exécuter cette instruction alors il meurt. De cette manière, il ne reste plus qu'un seul thread vivant après l'instruction join (le dernier à exécuter l'instruction). Le modèle SWITCH-ON-MISS Les caches mémoire permettent de charger des données partagées sans avoir nécessairement besoin d'accéder à le mémoire partagée. Il est donc peu intéressant pour un thread de commuter de contexte sur le chargement d'une donnée alors que celle-ci est disponible dans le cache. Dans le modèle SWITCH-ON-MISS, la commutation de contexte n'aura lieu que si la tentative de chargement engendre un défaut de cache. Par ailleurs, des caches peuvent aussi être utilisés entre le processeur et la mémoire locale. Avec ce modèle, il est possible de recouvrir les latences dues au chargement du cache de la mémoire locale. En pratique, comme la commutation de contexte n'est activée que très tardivement, il n'est pas possible d'éviter un désamorçage du pipeline du processeur ce qui a pour effet de dégrader les performances. De plus, la granularité est difficilement maîtrisable puisqu'elle devient fonction de l'état du cache. Le modèle SWITCH-ON-USE-MISS Dans ce modèle, les commutations de contexte n'ont lieu qu'au moment d'utiliser une donnée dont le chargement a engendré un défaut de cache. Cette approche permet de cumuler les avantages du modèle SWITCH-ON-USE, à savoir le regroupement de chargement et ceux du modèle SWITCH-ON-MISS, à savoir la commutation conditionnée par un défaut de cache. Mais les inconvénients sont également conservés, notamment le désarmorçage du pipeline du processeur. Le modèle CONDITIONAL-SWITCH Ce modèle est dérivé du modèle EXPLICIT-SWITCH auquel il ajoute la prise en compte du cache. La différence est que la commutatio de contexte explicite est conditionnée par l'existence d'un défaut de cache. Il est donc possible de regrouper des chargements de données distantes et de ne tenter de commuter qu'avant de les utiliser. La commutation n'aura lieu que si au moins une de ces données n'était pas disponible dans le cache.