Programación de instrucciones

En informática , la programació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 secuencias de instrucciones . En términos más simples, intenta hacer lo siguiente sin cambiar el significado del código:

• Evite los bloqueos en la cadena de suministro reorganizando el orden de las instrucciones. ^[1]
• Evite operaciones ilegales o semánticamente ambiguas (que generalmente involucran problemas sutiles de sincronización en el flujo de instrucciones o recursos no entrelazados).

Los bloqueos de la tubería pueden ser causados ​​por peligros estructurales (límite de recursos del procesador), peligros de datos (salida de una instrucción necesaria para otra instrucción) y peligros de control (ramificación).

Peligros de los datos

La programación de instrucciones se realiza normalmente en un único bloque básico . Para determinar si la reorganización de las instrucciones del bloque de una determinada manera preserva el comportamiento de ese bloque, necesitamos el concepto de dependencia de datos . Existen tres tipos de dependencias, que también son los tres peligros de los datos :

1. Leer después de escribir (RAW o "Verdadero"): la instrucción 1 escribe un valor utilizado posteriormente por la instrucción 2. La instrucción 1 debe venir primero, o la instrucción 2 leerá el valor antiguo en lugar del nuevo.
2. Escribir después de leer (WAR o "Anti"): la instrucción 1 lee una ubicación que luego es sobrescrita por la instrucción 2. La instrucción 1 debe venir primero, o leerá el nuevo valor en lugar del anterior.
3. Escritura tras escritura (WAW o "Output"): dos instrucciones escriben en la misma ubicación. Deben ocurrir 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 es útil en el reemplazo escalar de elementos de matriz.

Para asegurarnos de respetar los tres tipos de dependencias, construimos un gráfico de dependencia, que es un gráfico dirigido donde cada vértice es una instrucción y hay un borde de I ₁ a I ₂ si I ₁ debe venir antes que I ₂ debido a una dependencia. Si se omiten las dependencias llevadas a cabo en bucle, el gráfico de dependencia es un gráfico acíclico dirigido . Entonces, cualquier ordenación topológica de este gráfico es una programación de instrucciones válida. Los bordes del gráfico suelen estar etiquetados con la latencia de la dependencia. Este es el número de ciclos de reloj que deben transcurrir antes de que la secuencia pueda continuar con la instrucción de destino sin detenerse.

Algoritmos

El algoritmo más simple para encontrar una clasificación topológica se utiliza con frecuencia y se conoce como programación de listas . Conceptualmente, selecciona repetidamente una fuente del gráfico de dependencia, la agrega a la programación de instrucciones actual y la elimina del gráfico. Esto puede hacer que otros vértices sean fuentes, que luego también se considerarán para la programación. El algoritmo finaliza si el gráfico está vacío.

Para lograr una buena programación, se deben evitar los bloqueos. Esto se determina mediante la elección de la siguiente instrucción que se va a programar. Se utilizan varias heurísticas:

• Se registran los recursos del procesador utilizados por las instrucciones ya programadas. Si un candidato utiliza un recurso que está ocupado, su prioridad disminuirá.
• Si un candidato está programado más cerca de sus predecesores que la latencia asociada, su prioridad disminuirá.
• Si un candidato se encuentra en la ruta crítica del gráfico, su prioridad aumentará. Esta heurística proporciona algún tipo de previsión en un proceso de decisión que, de otro modo, sería local.
• Si la elección de un candidato generará muchas fuentes nuevas, su prioridad aumentará. Esta heurística tiende a generar más libertad para el planificador.

Orden de fases

La programación de instrucciones se puede realizar antes o después de la asignación de registros , o bien antes y después de ella. La ventaja de hacerlo antes de la asignación de registros es que esto da como resultado un paralelismo máximo. La desventaja de hacerlo antes de la asignación de registros es que esto puede dar como resultado que el asignador de registros necesite utilizar una cantidad de registros que exceda los disponibles. Esto provocará que se introduzca código de relleno/desbordamiento, lo que reducirá el rendimiento de la sección de código en cuestión.

Si la arquitectura que se está programando tiene secuencias de instrucciones que tienen combinaciones potencialmente ilegales (debido a la falta de interbloqueos de instrucciones), las instrucciones deben programarse después de la asignación de registros. Este segundo paso de programación también mejorará la ubicación del código de derrame/relleno.

Si la programación solo se realiza después de la asignación de registros, entonces habrá dependencias falsas introducidas por la asignación de registros que limitarán la cantidad de movimiento de instrucciones posible por parte del programador.

Tipos

Existen varios tipos de programación de instrucciones:

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

Ejemplos de compiladores

GNU Compiler Collection es un compilador conocido por realizar la programación de instrucciones, utilizando los indicadores -march(conjunto de instrucciones y programación) o -mtune(solo programación). Utiliza descripciones de latencias de instrucciones y qué instrucciones se pueden ejecutar en paralelo (o equivalentemente, qué "puerto" utiliza cada una) para cada microarquitectura para realizar la tarea. Esta característica está disponible para casi todas las arquitecturas que admite GCC. ^[2]

Hasta la versión 12.0.0, la programación de instrucciones en LLVM /Clang solo podía aceptar un conmutador -march(llamado target-cpuen el lenguaje de LLVM) tanto para el conjunto de instrucciones como para la programación. La versión 12 agrega soporte para -mtune( tune-cpu) solo para x86. ^[3]

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

• GCC y LLVM;
• Agner Fog , que recopila datos extensos para la arquitectura x86 ; ^[4]
• InstLatx64, que utiliza AIDA64 para recopilar datos sobre CPU x86. ^[5]

Los LLVM llvm-exegesisdeberían poder utilizarse en todas las máquinas, especialmente para recopilar información en aquellas que no sean x86. ^[6]

Véase también

• Predicción de ramas
• Generación de código
• Unidad de instrucción
• Ejecución fuera de orden

Referencias

1. Su, Ching-Long; Tsui, Chi-Ying; Despain, Alvin M. (1994). Diseño de arquitectura de bajo consumo y técnicas de compilación para procesadores de alto rendimiento (PDF) (Informe). Laboratorio de arquitectura informática avanzada. ACAL-TR-94-01.( Programación en frío )
2. "Opciones x86". Uso de la colección de compiladores GNU (GCC) .
3. "⚙ D85384 [X86] Agregar soporte básico para la opción de línea de comando -mtune en clang". reviews.llvm.org .
4. "Recursos para optimización de software. C++ y ensamblador. Windows, Linux, BSD, Mac OS X". Agner Fog .
5. "Volcados de latencia de instrucciones x86, x64, latencia de memoria y CPUID". instlatx64.atw.hu .Vea también el enlace “Comentarios” en la página.
6. "llvm-exegesis - Referencia de instrucciones de máquina LLVM". Documentación de LLVM 12 .

Lectura adicional

• Fisher, Joseph A. (1981). "Programación de trazas: una técnica para la compactación global de microcódigo". IEEE Transactions on Computers . 30 (7): 478–490. doi :10.1109/TC.1981.1675827. S2CID  1650655.( Programación de seguimiento )
• 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).( Programación de percolación )
• Bernstein, David; Rodeh, Michael (junio de 1991). "Programación global de instrucciones para máquinas superescalares" (PDF) . Actas de la conferencia ACM, SIGPLAN '91 sobre diseño e implementación de lenguajes de programación .( Programación global )
• Cordes, Peter. "ensamblaje - Reordenamiento de instrucciones en asm x86 / x64 - optimización del rendimiento con las últimas CPU". Desbordamiento de pila .