Je suis tombé sur le code MIPS suivant qui présente des risques d'utilisation des données et de la charge.

0 addi $t0,$a0,4
1 addi $t1,$a1,4
2 sub  $t2,$t0,$t1                #data hazard $t0, data hazard $t1
3 sll  $t3,$a2,2  
4 add  $t4,$t0,$t3                #data hazard $t3
5 add  $t5,$t1,$t3                #data hazard $t3
6 sw   $t2,0($t4)                 #data hazard $t4

Pour résoudre les dangers, je pourrais ajouter 5 NOPs (2 après la ligne 1, 2 après la ligne 3 et 1 après la ligne 5), ou je pourrais réécrire le code en évitant ainsi complètement les dangers. En réorganisant le code, afin de minimiser le nombre de NOPs, j'obtiens :

0 addi $t0,$a0,4
1 addi $t1,$a1,4
3 sll  $t3,$a2,2
2 sub  $t2,$t0,$t1                #data hazard $t1
4 add  $t4,$t0,$t3                
5 add  $t5,$t1,$t3                
6 sw   $t2,0($t4)                 #data hazard $t4

Les deux aléas seraient alors résolus en ajoutant 1 NOP après la ligne 3 et 1 NOP après la ligne 5. Cependant, ce code est relativement simple et court. Que se passe-t-il si je reçois 20 lignes de code MIPS à l'examen ? Existe-t-il un moyen ou une règle plus rapide permettant de réorganiser le code plus facilement et plus rapidement (à la main) ?

1
Learn To Adapt 8 févr. 2020 à 20:30

1 réponse

Meilleure réponse

Pour un algorithme d'ordonnancement d'instructions, vous devez d'abord identifier les chaînes de dépendances. (Comme vous le feriez lors de l'identification des chemins critiques de latence pour une exécution dans le désordre.)

Pour planifier des instructions pour une machine en ordre : entrelacez les instructions de différentes chaînes de services, en commençant par la plus longue.

Lors du réglage manuel (ou dans un compilateur d'optimisation), vous pouvez même faire des choses comme réorganiser les opérations associatives (comme add) pour créer différents temporaires, créant plus d'ILP (parallélisme au niveau des instructions). par exemple. transformer a+b+c+d en (a+b)+(c+d). Les mathématiques entières sont associatives ; les mathématiques à virgule flottante ne le sont généralement pas.

Bien sûr, cela n'est sûr que si le code utilise addu / addiu, pas le débordement de trap-on-signed-overflow de MIPS add/addi. Les compilateurs C n'utilisent jamais le trapping add/sub afin qu'ils puissent librement optimiser l'arithmétique avec des temporaires différents de ceux de la source C. Vous devriez également, à moins que vous ne veuillez spécifiquement une instruction pour éventuellement intercepter le débordement signé.


Apparemment, les assembleurs MIPS classiques pourraient réorganiser votre code pour que vous remplissiez les créneaux de délai de chargement et de branchement ; ce manuel d'assemblage de Silicon Graphics de 1992 entre dans quelques détails sur la réorganisation agressive des instructions par l'assembleur (sauf si vous utilisez .set noreorder et que les slots de délai de branche deviennent visibles.) Le livre Voir MIPS Run peut également le mentionner.

Vraisemblablement, l'assembleur SGI détecte les blocs de base en termes d'étiquettes et d'instructions de branchement, et effectue l'ordonnancement des instructions au sein de blocs uniques.

Bien sûr, les bons compilateurs pour les langages de haut niveau font également la planification des instructions. (Par exemple GCC). Je ne pense pas que l'assembleur GNU dispose d'un mode de réorganisation optimisé ; il est conçu comme un back-end pour un compilateur qui planifie lui-même les instructions.


Contrairement à votre exemple de jouet avec une latence à plusieurs cycles avant de pouvoir utiliser un résultat add, le vrai MIPS classique était un RISC classique à 5 étages avec transfert de dérivation et latence ALU à un cycle. La première génération n'avait pas de verrouillage, il y avait donc un créneau de retard de charge de 1 cycle, et la dérivation les créneaux de retard sont restés architecturalement visibles. Mais les instructions ALU simples ont une latence de 1 cycle. Ainsi, les vrais MIPS avaient beaucoup moins de risques à éviter lors de la planification des instructions. Mais même ainsi, la révision MIPS ultérieure a supprimé le slot de délai de chargement pour une meilleure densité de code lorsque les compilateurs relativement primitifs de l'époque ne pouvaient rien trouver à y mettre. (Décrochage au lieu d'avoir besoin d'un NOP.)

Une vraie machine avec autant de slots de délai (et aucun verrouillage matériel pour caler) serait très peu pratique pour la densité de code / l'empreinte du cache L1i, ainsi que de mauvaises performances. Il y a une raison pour laquelle les conceptions commerciales du monde réel contournent la transmission au lieu de caler. Mais votre exemple de latence à plusieurs cycles est réaliste pour la virgule flottante.

(fait amusant : MIPS peut transférer une adresse cible de succursale à partir de première moitié de EX à un demi-cycle IF pour un total de seulement 1 cycle de latence de branche.

MIPS était bloqué avec des créneaux de délai de branche jusqu'à ce qu'une réorganisation majeure (et non rétrocompatible) des opcodes introduise des branches sans délai (MIPS32/64r6 en 2014). L'instruction dans le créneau de délai de branchement s'exécute que le branchement soit effectué ou non, de sorte que le matériel MIPS ultérieur n'a pas pu le supprimer comme il le pourrait pour les créneaux de délai de chargement. RISC-V a évité cette erreur.

1
Peter Cordes 8 févr. 2020 à 20:24