Programación de la instrucción

En informática , la planificación de instrucciones es una optimización del compilador que se utiliza para mejorar el paralelismo a nivel de instrucción , lo que mejora el rendimiento en máquinas con arquitecturas de procesamiento en paralelo . En pocas palabras, intenta hacer lo siguiente sin cambiar el significado del código:

• Evite bloqueos en la tubería reorganizando el orden de las instrucciones. ^{[ 1 ]}
• Evite las operaciones ilegales o semánticamente ambiguas (que suelen implicar problemas sutiles de sincronización en la canalización de instrucciones o recursos no interconectados).

Las interrupciones en la tubería de procesamiento pueden deberse a riesgos estructurales (límite de recursos del procesador), riesgos de datos (la salida de una instrucción es necesaria para otra) y riesgos de control (ramificaciones).

La planificación de instrucciones se realiza normalmente en un único bloque básico . Para determinar si la reorganización de las instrucciones del bloque de cierta manera preserva el comportamiento de dicho bloque, necesitamos el concepto de dependencia de datos . Existen tres tipos de dependencias, que también coinciden con los tres riesgos de datos :

1. Lectura después de escritura (RAW o "Verdadero"): La instrucción 1 escribe un valor que la instrucción 2 utilizará posteriormente. La instrucción 1 debe ejecutarse primero, o la instrucción 2 leerá el valor antiguo en lugar del nuevo.
2. Escritura después de lectura (WAR o "Anti"): La instrucción 1 lee una ubicación que posteriormente es sobrescrita por la instrucción 2. La instrucción 1 debe ejecutarse primero, o leerá el nuevo valor en lugar del antiguo.
3. Escritura tras escritura (WAW o "Salida"): Dos instrucciones escriben en la misma ubicación. Deben ejecutarse en su orden original.

Técnicamente, existe un cuarto tipo, Lectura tras lectura (RAR o "Input"): Ambas instrucciones leen la misma ubicación. La dependencia de entrada no restringe el orden de ejecución de dos instrucciones, pero resulta útil para la sustitución escalar de elementos de matrices.

Para garantizar el respeto de los tres tipos de dependencias, construimos un grafo de dependencias, que es un grafo dirigido donde cada vértice representa una instrucción y existe una arista de I1 _a I2 _si I1 _debe preceder a _I2 debido a una dependencia. Si se omiten las dependencias de bucle, el grafo de dependencias se convierte en un grafo dirigido acíclico . En este caso, cualquier ordenación topológica de este grafo constituye una planificación de instrucciones válida. Las aristas del grafo suelen estar etiquetadas con la latencia de la dependencia. Esta latencia representa el número de ciclos de reloj que deben transcurrir antes de que la tubería pueda ejecutar la instrucción objetivo sin detenerse.

El algoritmo más sencillo para encontrar una ordenación topológica se utiliza con frecuencia y se conoce como planificación por lista . Conceptualmente, selecciona repetidamente un origen del grafo de dependencias, lo añade a la planificación de instrucciones actual y lo elimina del grafo. Esto puede provocar que otros vértices se conviertan en orígenes, los cuales también se considerarán para la planificación. El algoritmo finaliza si el grafo está vacío.

Para lograr una buena programación, se deben evitar las demoras. Esto se determina mediante la elección de la siguiente instrucción a programar. Se utilizan comúnmente varias heurísticas:

• Se registran los recursos del procesador utilizados por las instrucciones ya programadas. Si una instrucción candidata utiliza un recurso que está ocupado, su prioridad disminuirá.
• Si la prioridad de un candidato se reduce a una fecha más cercana a la de sus predecesores que la latencia asociada, su prioridad disminuirá.
• Si un candidato se encuentra en la ruta crítica del grafo, su prioridad aumentará. Esta heurística proporciona una forma de anticipación en un proceso de decisión que, de otro modo, sería local.
• Si la elección de un candidato genera muchas fuentes nuevas, su prioridad aumentará. Esta heurística tiende a generar mayor libertad para el planificador.

La planificación de instrucciones puede realizarse antes o después de la asignación de registros , o en ambos casos. La ventaja de hacerlo antes es que se logra el máximo paralelismo. La desventaja es que puede provocar que el asignador de registros necesite utilizar más registros de los disponibles. Esto generará código de desbordamiento/relleno, lo que reducirá el rendimiento de la sección de código en cuestión.

Si la arquitectura que se está planificando tiene secuencias de instrucciones con combinaciones potencialmente ilegales (debido a la falta de interbloqueos de instrucciones), estas deben planificarse después de la asignación de registros. Esta segunda pasada de planificación también mejorará la ubicación del código de desbordamiento/relleno.

Si la planificación se realiza únicamente después de la asignación de registros, se introducirán dependencias falsas debido a dicha asignación, lo que limitará la cantidad de movimiento de instrucciones posible por parte del planificador.

Existen varios tipos de planificación de la instrucción:

1. Planificación local ( bloque básico ) : las instrucciones no pueden moverse a través de los límites de los bloques básicos.
2. Planificación global : las instrucciones pueden moverse a través de los límites de los bloques básicos.
3. Planificación modular : un algoritmo para generar segmentación de software , que es una forma de aumentar el paralelismo a nivel de instrucción intercalando diferentes iteraciones de un bucle interno .
4. Planificación por trazas : el primer enfoque práctico para la planificación global, la planificación por trazas intenta optimizar la ruta de flujo de control que se ejecuta con mayor frecuencia.
5. Planificación de superbloques : una forma simplificada de planificación de trazas que no intenta fusionar las rutas de flujo de control en las "entradas laterales" de las trazas. En cambio, el código puede implementarse mediante más de una planificación, lo que simplifica enormemente el generador de código.

La Colección de Compiladores GNU es un compilador conocido por realizar la planificación de instrucciones, utilizando las banderas -march(tanto para el conjunto de instrucciones como para la planificación) o -mtune(solo para la planificación). Utiliza descripciones de las latencias de las instrucciones y qué instrucciones se pueden ejecutar en paralelo (o, equivalentemente, qué "puerto" utiliza cada una) para que cada microarquitectura realice la tarea. Esta característica está disponible para casi todas las arquitecturas que admite GCC. ^{[ 2 ]}

Hasta la versión 12.0.0, la planificación de instrucciones en LLVM /Clang solo podía aceptar un interruptor -march(llamado target-cpuen la jerga de LLVM) tanto para el conjunto de instrucciones como para la planificación. La versión 12 añade soporte para -mtune( tune-cpu) solo para x86. ^{[ 3 ]}

Las fuentes de información sobre latencia y uso de puertos incluyen:

• GCC y LLVM;
• Agner Fog , quien recopila datos extensos para la arquitectura x86 ; ^{[ 4 ]}
• InstLatx64, que utiliza AIDA64 para recopilar datos en CPU x86. ^{[ 5 ]}
• uops.info, que proporciona información sobre latencia, rendimiento y uso de puertos para microarquitecturas x86. ^{[ 6 ] [ 7 ]}

LLVM llvm-exegesisdebería poder utilizarse en todas las máquinas, especialmente para recopilar información en aquellas que no son x86. ^{[ 8 ]}

• Predicación de ramificación
• Generación de código
• Unidad de instrucciones
• Ejecución fuera de orden

• Fisher, Joseph A. (1981). "Trace Scheduling: A Technique for Global Microcode Compaction". IEEE Transactions on Computers . 30 (7): 478– 490. doi : 10.1109/TC.1981.1675827 . S2CID 1650655 . ( Programación de rastreo )
• Nicolau, Alexandru; Fisher, Joseph A. (1984). "Medición del paralelismo disponible para arquitecturas de palabras de instrucción muy largas". IEEE Transactions on Computers . 33 (11).( Planificación por percolación )
• Bernstein, David; Rodeh, Michael (junio de 1991). "Planificación global de instrucciones para máquinas superescalares" (PDF) . Actas de la Conferencia SIGPLAN '91 de la ACM sobre diseño e implementación de lenguajes de programación .( Planificación global )
• Cordes, Peter. "Ensamblaje: reordenamiento de instrucciones en asm x86/x64: optimización del rendimiento con las últimas CPU" . Stack Overflow .