Code multithread

La méthode courante pour créer des programmes informatiques consiste à utiliser un compilateur pour traduire le code source (écrit dans un langage symbolique ) en code machine . L' exécutable résultant est généralement rapide, mais, étant spécifique à une plateforme matérielle , il n'est pas portable. Une autre approche consiste à générer des instructions pour une machine virtuelle et à utiliser un interpréteur sur chaque plateforme matérielle. L'interpréteur instancie l'environnement de la machine virtuelle et exécute les instructions. Ainsi, l'interpréteur, compilé en code machine, fournit une couche d'abstraction pour les « langages interprétés » qui ne nécessitent qu'une compilation minimale pour s'y conformer (la compilation peut se limiter à la génération d'un arbre de syntaxe abstraite ) ou même aucune compilation (si la couche est conçue pour traiter directement le code source).

Les premiers ordinateurs disposaient de relativement peu de mémoire. Par exemple, la plupart des Data General Nova , IBM 1130 et de nombreux micro-ordinateurs de la première heure n'étaient équipés que de 4 ko de RAM. De ce fait, on consacrait beaucoup de temps à trouver des moyens de réduire la taille des programmes afin qu'ils tiennent dans la mémoire disponible.

Une solution consiste à utiliser un interpréteur qui lit le langage symbolique par portions et appelle des fonctions pour exécuter les actions. Comme le code source est généralement beaucoup plus dense que le code machine résultant, cela permet de réduire l'utilisation globale de la mémoire. C'est pourquoi BASIC est un interpréteur : son devait partager les 4 ko de mémoire de machines comme l' Altair 8800 avec le code source de l'utilisateur. Un compilateur traduit un langage source en code machine ; le compilateur, le code source et le résultat doivent donc tous être chargés en mémoire simultanément. Dans un interpréteur, il n'y a pas de résultat.

Le code multithread est un style de formatage du code compilé qui minimise l'utilisation de la mémoire. Au lieu d'écrire chaque étape d'une opération à chaque occurrence dans le programme, comme c'était le cas dans les assembleurs macro par exemple, le compilateur écrit chaque portion de code commune dans une sous-routine. Ainsi, chaque portion de code n'est présente qu'à un seul endroit en mémoire (voir « Ne vous répétez pas »). L'application principale de ces programmes peut ne contenir que des appels de sous-routines. Nombre de ces sous-routines, à leur tour, ne contiennent que des appels de sous-routines de niveau inférieur.

Les ordinateurs centraux et certains microprocesseurs anciens, comme le RCA 1802, nécessitaient plusieurs instructions pour appeler une sous-routine. Dans l'application principale et dans de nombreuses sous-routines, cette séquence se répétait constamment, seule l'adresse de la sous-routine changeant d'un appel à l'autre. Par conséquent, un programme comportant de nombreux appels de fonction pouvait également contenir une quantité considérable de code redondant.

Pour pallier ce problème, les systèmes de code multithread utilisaient du pseudo-code pour représenter les appels de fonction dans un seul opérateur. À l'exécution, un petit « interpréteur » parcourait le code de niveau supérieur, extrayait l'adresse mémoire de la sous-routine et l'appelait. Dans d'autres systèmes, ce même concept de base est implémenté sous la forme d'une table de branchement , d'une table de répartition ou d'une table de méthodes virtuelles , qui consistent toutes en une table d'adresses de sous-routines.

Dans les années 1970, les concepteurs de matériel ont déployé des efforts considérables pour rendre les appels de sous-programmes plus rapides et plus simples. Sur les conceptions améliorées, une seule instruction suffit pour appeler un sous-programme ; l’utilisation d’une pseudo-instruction ne permet donc aucun gain de mémoire. De plus, les performances de ces appels sont quasiment exemptes de surcharge. Aujourd’hui, bien que la quasi-totalité des langages de programmation privilégient l’isolation du code en sous-programmes, c’est pour des raisons de clarté et de maintenabilité, et non pour économiser de l’espace.

Les systèmes de code multithreadés permettent de gagner de la place en remplaçant la liste des appels de fonction, où seule l'adresse de la sous-routine change d'un appel à l'autre, par une liste de jetons d'exécution, qui sont essentiellement des appels de fonction dont le ou les codes d'opération ont été supprimés, ne laissant subsister qu'une liste d'adresses.

Au fil des ans, les programmeurs ont créé de nombreuses variantes de cet « interpréteur » ou « petit sélecteur ». L'adresse spécifique dans la liste d'adresses peut être extraite à l'aide d'un index, d' un registre général ou d'un pointeur . Les adresses peuvent être directes ou indirectes, contiguës ou non contiguës (liées par des pointeurs), relatives ou absolues, résolues à la compilation ou construites dynamiquement. Aucune variante n'est « idéale » dans tous les cas.

Développement

Pour gagner de la place, les programmeurs ont condensé les listes d'appels de sous-programmes en simples listes d'adresses de sous-programmes, et utilisé une petite boucle pour appeler chaque sous-programme successivement. Par exemple, le pseudocode suivant utilise cette technique pour additionner deux nombres A et B. Dans cet exemple, la liste est nommée « thread » et une variable « ip » (pointeur d'instruction) indique notre position dans la liste. Une autre variable, « sp » (pointeur de pile), contient une adresse mémoire disponible pour stocker temporairement une valeur.

début : ip = & thread // pointe vers l'adresse '&pushA', et non vers l'étiquette textuelle 'thread' top : jump * ip ++ // suit ip jusqu'à l'adresse dans le thread, puis jusqu'à la sous-routine, et avance ip thread : & pushA & pushB & add ... pushA : * sp ++ = A // suit sp jusqu'à la mémoire disponible, y stocke A, et avance sp jusqu'au prochain saut top pushB : * sp ++ = B jump top add : addend1 = *-- sp // Dépile la valeur du haut addend2 = *-- sp // Dépile la deuxième valeur * sp ++ = addend1 + addend2 // Additionne les deux valeurs et stocke le résultat au sommet de la pile jump top

La boucle d'appel topest si simple qu'elle peut être répétée en ligne à la fin de chaque sous-routine. Le contrôle effectue désormais un seul saut, de la fin d'une sous-routine au début de la suivante, au lieu de deux sauts top. Par exemple :

début : ip = & thread // ip pointe vers &pushA (qui pointe vers la première instruction de pushA) jump * ip ++ // envoie le contrôle à la première instruction de pushA et avance ip vers &pushB thread : & pushA & pushB & add ... pushA : * sp ++ = A // suit sp jusqu'à la mémoire disponible, y stocke A, avance sp vers le prochain jump * ip ++ // envoie le contrôle là où ip l'indique (c'est-à-dire vers pushB) et avance ip pushB : * sp ++ = B jump * ip ++ add : addend1 = *-- sp // Dépile la valeur du haut addend2 = *-- sp // Dépile la deuxième valeur * sp ++ = addend1 + addend2 // Additionne les deux valeurs et stocke le résultat au sommet de la pile jump * ip ++

On appelle cela du code multithread direct (DTC). Bien que la technique soit plus ancienne, la première utilisation largement diffusée du terme « code multithread » est probablement l’article de James R. Bell de 1973 intitulé « Threaded Code ».

En 1970, Charles H. Moore inventa une architecture plus compacte, le code à threads indirects (ITC), pour sa machine virtuelle Forth. Moore aboutit à cette architecture car les mini-ordinateurs Nova disposaient d'un bit d'indirection dans chaque adresse, ce qui rendait l'ITC simple et rapide. Plus tard, il déclara l'avoir trouvée si pratique qu'il l'avait généralisée dans toutes les versions ultérieures de Forth.

Aujourd'hui, certains compilateurs Forth génèrent du code à threads directs, tandis que d'autres génèrent du code à threads indirects. Le comportement des exécutables reste identique dans les deux cas.

Modèles de filetage

Pratiquement tous les codes exécutables multithread utilisent l'une ou l'autre de ces méthodes pour invoquer des sous-routines (chaque méthode est appelée « modèle de threading »).

Filetage direct

Les adresses dans le thread sont des adresses machine. Cette structure est simple, mais peut engendrer des surcoûts car le thread ne contient que des adresses machine ; tous les paramètres supplémentaires doivent donc être chargés indirectement depuis la mémoire. Certains systèmes Forth produisent du code exécuté directement dans les threads. Sur de nombreuses machines, cette technique est plus rapide que l'exécution par sous-programmes (voir référence ci-dessous).

Un exemple de machine à pile pourrait exécuter la séquence « empiler A, empiler B, ajouter ». Cela pourrait se traduire par le thread et les routines suivants, où ipest initialisé à l'adresse indiquée thread(c'est-à-dire l'adresse où &pushAest stocké).

#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread // ip pointe vers &pushA (qui pointe vers la première instruction de pushA) jump * ip ++ // envoie le contrôle à la première instruction de pushA et avance ip vers &pushB thread : & pushA & pushB & add ... pushA : PUSH ( A ) jump * ip ++ // envoie le contrôle là où ip le demande (c'est-à-dire vers pushB) et avance ip pushB : PUSH ( B ) jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++

Il est également possible d'inclure les opérandes dans le thread. Cela permet de réduire l'indirection nécessaire précédemment, mais augmente la taille du thread.

#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread jump * ip ++ thread : & push & A // adresse où A est stocké, pas A littéral & push & B & add ... push : variable_address = * ip ++ // doit déplacer ip après l'adresse de l'opérande, car ce n'est pas une adresse de sous-routine PUSH ( * variable_address ) // Lire la valeur de la variable et l'empiler jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++

Filetage indirect

Le multithreading indirect utilise des pointeurs vers des emplacements qui, à leur tour, pointent vers du code machine. Le pointeur indirect peut être suivi d'opérandes stockés dans le « bloc » indirect plutôt que d'être stockés de manière répétée dans le thread. Ainsi, le code indirect est souvent plus compact que le code multithread direct. L'indirection le rend généralement plus lent, bien que généralement toujours plus rapide que les interpréteurs de bytecode. Lorsque les opérandes du gestionnaire incluent à la fois des valeurs et des types, le gain d'espace par rapport au code multithread direct peut être significatif. Les anciens systèmes FORTH produisent généralement du code multithread indirect.

Par exemple, si l'objectif est d'exécuter « push A, push B, add », on peut utiliser le code suivant. Ici, `push A` ipest initialisé à l'adresse `a` &thread, chaque fragment de code ( push`a`, add`b`) est trouvé par double indirection via `push A` ipet un bloc indirect ; et les opérandes du fragment sont trouvés dans le bloc indirect suivant l'adresse du fragment. Ceci nécessite de conserver la sous-routine courante dans ` push ipA`, contrairement à tous les exemples précédents où `push A` contenait la prochaine sous-routine à appeler.

début : ip = & thread // pointe vers '&i_pushA' jump ** ip // suit les pointeurs jusqu'à la 1ère instruction de 'push', NE PAS avancer ip pour l'instant thread : & i_pushA & i_pushB & i_add ... i_pushA : & push & A i_pushB : & push & B i_add : & add push : * sp ++ = ** ( * ip + 1 ) // recherche l'adresse de l'opérande 1 après le début du bloc indirect jump * ( *++ ip ) // avance ip dans le thread, saute au bloc indirect suivant vers la sous-routine suivante add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 jump * ( *++ ip )

Enchaînement de sous-routines

Le code dit « à sous-routines » (ou « à appels ») est constitué d'une série d'instructions d'appel en langage machine (ou adresses de fonctions à appeler, contrairement à l'utilisation du saut dans le multithreading direct). Les premiers compilateurs pour ALGOL , Fortran, Cobol et certains systèmes Forth produisaient souvent du code à sous-routines. Dans nombre de ces systèmes, le code fonctionnait sur une pile d'opérandes de type LIFO (dernier entré, premier sorti), pour laquelle la théorie des compilateurs était bien établie. La plupart des processeurs modernes disposent d'un support matériel dédié aux instructions d'appel et de retour des sous-routines, ce qui réduit considérablement la surcharge liée à une instruction machine supplémentaire par exécution.

Anton Ertl, co-créateur du compilateur Gforth , a déclaré que « contrairement aux idées reçues, l'exécution par sous-programmes est généralement plus lente que l'exécution directe » . Cependant, ses tests les plus récents montrent que l'exécution par sous-programmes est plus rapide que l'exécution directe dans 15 cas sur 25. Plus précisément, il a constaté que l'exécution directe est le modèle le plus rapide sur les processeurs Xeon, Opteron et Athlon, l'exécution indirecte sur les processeurs Pentium M et l'exécution par sous-programmes sur les processeurs Pentium 4, Pentium III et PPC.

À titre d'exemple d'enchaînement d'appels pour « push A, push B, add » :

thread : call pushA call pushB call add ret pushA : * sp ++ = A ret pushB : * sp ++ = B ret add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 ret

Enchaînement de jetons

Le code à jetons implémente le thread sous forme d'une liste d'indices pointant vers une table d'opérations. La largeur des indices est naturellement choisie pour être aussi petite que possible, afin d'optimiser la densité et l'efficacité. 1 octet (8 bits) est le choix naturel pour simplifier la programmation, mais des tailles plus petites (4 bits) ou plus grandes (12 ou 16 bits) peuvent être utilisées selon le nombre d'opérations prises en charge. Tant que la largeur des indices est inférieure à celle d'un pointeur machine, le code sera naturellement plus compact que les autres types de threads, sans effort particulier de la part du programmeur. Sa taille est généralement de la moitié à trois quarts de celle des autres types de threads, qui sont eux-mêmes quatre à huit fois plus petits que le code non multithreadé. Les pointeurs de la table peuvent être indirects ou directs. Certains compilateurs Forth produisent du code à jetons. Certains programmeurs considèrent le « p-code » généré par certains compilateurs Pascal , ainsi que le bytecode utilisé par .NET , Java , BASIC et certains compilateurs C , comme du code à jetons.

Historiquement, une approche courante consiste à utiliser le bytecode , qui emploie généralement des opcodes 8 bits avec une machine virtuelle à pile. L' interpréteur de bytecode archétypal est appelé « interpréteur de décodage et d'exécution » et se présente sous la forme suivante :

début : vpc = & thread dispatch : addr = decode ( & vpc ) // Convertit l'opération bytecode suivante en un pointeur vers le code machine qui l'implémente // Toutes les opérations inter-instructions sont effectuées ici (par exemple, mise à jour de l'état global, traitement d'événements, etc.) jump addr CODE_PTR decode ( BYTE_CODE ** p ) { // Dans un encodage plus complexe, il peut y avoir plusieurs tables parmi lesquelles choisir ou des indicateurs de contrôle/mode return table [ * ( * p ) ++ ]; } thread : /* Contient du bytecode, pas des adresses machine. Par conséquent, il est plus compact. */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/ table : & add /* table[0] = adresse du code machine qui implémente le bytecode 0 */ & pushA /* table[1] ... */ & pushB /* table[2] ... */ pushA : * sp ++ = Déclenchement du saut A pushB : * sp ++ = Déclenchement du saut B add : addend1 = *-- sp addend2 = *-- sp * sp ++ = Déclenchement du saut addend1 + addend2

Si la machine virtuelle utilise uniquement des instructions sur un octet, decode()l'opération consiste simplement à extraire une valeur de la fonction `opcode`. threadCependant, il arrive souvent qu'elle utilise des instructions courantes sur un octet, ainsi que des instructions multioctets moins fréquentes (voir les ordinateurs à jeu d'instructions complexe ), auquel cas l'opération decode()est plus complexe. Le décodage des codes d'opération sur un octet peut être géré de manière très simple et efficace par une table de branchement utilisant directement le code d'opération comme index.

Pour les instructions dont les opérations individuelles sont simples, comme « push » et « add », le temps nécessaire pour déterminer l'opération à effectuer est supérieur au coût de son exécution proprement dite. De ce fait, ces interpréteurs sont souvent beaucoup plus lents que le code machine. En revanche, pour les instructions plus complexes (« composées »), le pourcentage de surcharge est proportionnellement moins important.

Il arrive que du code multithreadé par jetons s'exécute plus rapidement que le code machine équivalent lorsque ce dernier est trop volumineux pour tenir dans le cache d'instructions L1 du processeur. La densité de code plus élevée du code multithreadé, notamment du code multithreadé par jetons, lui permet de tenir entièrement dans le cache L1, évitant ainsi la saturation du cache. Cependant, contrairement au code machine qui ne consomme que le cache d'instructions, le code multithreadé consomme à la fois le cache d'instructions (pour l'implémentation de chaque opération) et le cache de données (pour le bytecode et les tables). Cela signifie que le code multithreadé réduit la quantité de données que le processeur peut traiter simultanément. Néanmoins, si le problème à résoudre implique l'application d'un grand nombre d'opérations à une petite quantité de données, l'utilisation de code multithreadé peut constituer une optimisation idéale.

Enfilage Huffman

Le code à threads de Huffman est constitué de listes de jetons stockés sous forme de codes de Huffman . Un code de Huffman est une chaîne de bits de longueur variable qui identifie un jeton unique. Un interpréteur à threads de Huffman localise les sous-programmes à l'aide d'une table d'index ou d'un arbre de pointeurs navigable grâce au code de Huffman. Le code à threads de Huffman est l'une des représentations les plus compactes connues pour un programme informatique. L'index et les codes sont choisis en fonction de la fréquence d'appel à chaque sous-programme du code. Les appels fréquents reçoivent les codes les plus courts. Les opérations de fréquences approximativement égales reçoivent des codes de longueur binaire quasi identique. La plupart des systèmes à threads de Huffman ont été implémentés comme des systèmes Forth à threads directs et utilisés pour intégrer de grandes quantités de code lent dans des microcontrôleurs petits et économiques . La plupart des applications publiées concernent les cartes à puce, les jouets, les calculatrices et les montres. Le code tokenisé orienté bit utilisé dans PBASIC peut être considéré comme un type de code à threads de Huffman.

Filetage moins utilisé

Un exemple est le chaînage de chaînes de caractères, où les opérations sont identifiées par des chaînes, généralement consultées dans une table de hachage. Ce procédé était utilisé dans les premières implémentations Forth de Charles H. Moore et dans le langage informatique expérimental interprété par le matériel de l' Université de l'Illinois . Il est également utilisé dans RPL

Le langage RPL de HP , introduit pour la première fois dans la calculatrice HP-18C en 1986, est un langage interprétatif multithread (TIL) propriétaire hybride (à la fois à exécution directe et indirecte) qui, contrairement à d'autres TIL, permet d'intégrer des « objets » RPL dans le « flux d'exécution », c'est-à-dire le flux d'adresses parcouru par le pointeur de l'interpréteur. Un « objet » RPL peut être vu comme un type de données particulier dont la structure en mémoire contient, au début de l'objet, l'adresse d'un « prologue d'objet », suivi des données ou du code exécutable. Le prologue d'objet détermine comment le corps de l'objet doit être exécuté ou traité. Grâce à la « boucle interne RPL » , inventée et brevetée par William C. Wickes en 1986 et publiée en 1988, l'exécution se déroule comme suit :