Ordenamiento de memoria

El orden de la memoria es el orden de acceso a la memoria de la computadora por parte de una CPU . El orden de la memoria depende tanto del orden de las instrucciones generadas por el compilador en tiempo de compilación como del orden de ejecución de la CPU en tiempo de ejecución . ^{[1] [2]} Sin embargo, el orden de la memoria es de poca importancia fuera del multihilo y la E/S mapeada en memoria , porque si el compilador o la CPU cambian el orden de cualquier operación , necesariamente deben asegurarse de que la reordenación no cambie la salida del código ordinario de un solo subproceso . ^{[1] [2] [3]}

Se dice que el orden de la memoria es fuerte o secuencialmente consistente cuando el orden de las operaciones no puede cambiar o cuando dichos cambios no tienen un efecto visible en ningún hilo. ^{[1] [4]} Por el contrario, el orden de la memoria se llama débil o relajado cuando un hilo no puede predecir el orden de las operaciones que surgen de otro hilo. ^{[1] [4]} Muchos algoritmos paralelos escritos de forma ingenua fallan cuando se compilan o ejecutan con un orden de memoria débil. ^{[5] [6]} El problema se resuelve con mayor frecuencia insertando instrucciones de barrera de memoria en el programa. ^{[6] [7]}

Para utilizar completamente el ancho de banda de diferentes tipos de memoria, como cachés y bancos de memoria , pocos compiladores o arquitecturas de CPU garantizan un ordenamiento perfectamente fuerte. ^{[1] [5]} Entre las arquitecturas comúnmente utilizadas, los procesadores x86-64 tienen el orden de memoria más fuerte, pero aún pueden diferir las instrucciones de almacenamiento de memoria hasta después de las instrucciones de carga de memoria. ^{[5] [8]} En el otro extremo del espectro, los procesadores DEC Alpha prácticamente no ofrecen garantías sobre el orden de la memoria. ^[5]

La mayoría de los lenguajes de programación tienen alguna noción de un hilo de ejecución que ejecuta instrucciones en un orden definido. Los compiladores tradicionales traducen expresiones de alto nivel a una secuencia de instrucciones de bajo nivel relativas a un contador de programa en el nivel de máquina subyacente.

Los efectos de ejecución son visibles en dos niveles: dentro del código del programa en un nivel alto, y en el nivel de la máquina como lo ven otros hilos o elementos de procesamiento en programación concurrente , o durante la depuración cuando se utiliza una ayuda de depuración de hardware con acceso al estado de la máquina (algo de soporte para esto a menudo está integrado directamente en la CPU o el microcontrolador como circuitos funcionalmente independientes aparte del núcleo de ejecución que continúa operando incluso cuando el núcleo mismo se detiene para la inspección estática de su estado de ejecución). El orden de memoria en tiempo de compilación se ocupa de lo primero y no se ocupa de estas otras vistas.

Durante la compilación, las instrucciones de hardware suelen generarse con una granularidad más fina que la especificada en el código de alto nivel. El principal efecto observable en un lenguaje de programación procedimental es la asignación de un nuevo valor a una variable con nombre.

  suma = a + b + c;
  imprimir(suma);

La sentencia print sigue a la sentencia que asigna a la variable suma y, por lo tanto, cuando la sentencia print hace referencia a la variable calculada, sumhace referencia a este resultado como un efecto observable de la secuencia de ejecución anterior. Como se define en las reglas de secuencia de programas, cuando la printllamada de función hace referencia a sum, el valor de sumdebe ser el de la asignación ejecutada más recientemente a la variable sum(en este caso, la sentencia inmediatamente anterior).

A nivel de máquina, pocas máquinas pueden sumar tres números en una sola instrucción, por lo que el compilador tendrá que traducir esta expresión en dos operaciones de suma. Si la semántica del lenguaje del programa restringe al compilador a traducir la expresión en orden de izquierda a derecha (por ejemplo), entonces el código generado parecerá como si el programador hubiera escrito las siguientes declaraciones en el programa original:

  suma = a + b;
  suma = suma + c;

Si se permite al compilador explotar la propiedad asociativa de la suma, podría generar en su lugar:

  suma = b + c;
  suma = a + suma;

Si al compilador también se le permite explotar la propiedad conmutativa de la suma, podría generar en su lugar:

  suma = a + c;
  suma = suma + b;

Tenga en cuenta que el tipo de datos entero en la mayoría de los lenguajes de programación solo sigue el álgebra para los números enteros matemáticos en ausencia de desbordamiento de enteros y que la aritmética de punto flotante en el tipo de datos de punto flotante disponible en la mayoría de los lenguajes de programación no es conmutativa en los efectos de redondeo, lo que hace que los efectos del orden de expresión sean visibles en pequeñas diferencias del resultado calculado (sin embargo, las pequeñas diferencias iniciales pueden convertirse en diferencias arbitrariamente grandes a lo largo de un cálculo más largo).

Si al programador le preocupan los efectos de desbordamiento de números enteros o de redondeo en punto flotante, el mismo programa puede codificarse en el alto nivel original de la siguiente manera:

  suma = a + b;
  suma = suma + c;

Muchos lenguajes tratan el límite de la sentencia como un punto de secuencia , lo que obliga a que todos los efectos de una sentencia se completen antes de que se ejecute la siguiente. Esto obligará al compilador a generar código correspondiente al orden de sentencia expresado. Sin embargo, las sentencias suelen ser más complicadas y pueden contener llamadas a funciones internas .

  suma = f(a) + g(b) + h(c); 

A nivel de máquina, llamar a una función generalmente implica configurar un marco de pila para la llamada de función, lo que implica muchas lecturas y escrituras en la memoria de la máquina. En la mayoría de los lenguajes compilados, el compilador es libre de ordenar las llamadas de función f, g, y hcomo le parezca conveniente, lo que da como resultado cambios a gran escala en el orden de la memoria del programa. En un lenguaje de programación funcional puro, se prohíbe que las llamadas de función tengan efectos secundarios en el estado visible del programa (aparte de su valor de retorno ) y la diferencia en el orden de la memoria de la máquina debido al orden de las llamadas de función será intrascendente para la semántica del programa. En los lenguajes procedimentales, las funciones llamadas pueden tener efectos secundarios, como realizar una operación de E/S o actualizar una variable en el ámbito global del programa, los cuales producen efectos visibles con el modelo del programa.

Nuevamente, un programador preocupado por estos efectos puede volverse más pedante al expresar el programa fuente original:

  suma = f(a);
  suma = suma + g(b);
  suma = suma + h(c);

En los lenguajes de programación donde el límite de la declaración se define como un punto de secuencia, la función llama a f, gy hahora debe ejecutarse en ese orden preciso.

Consideremos ahora la misma suma expresada con indirección de puntero, en un lenguaje como C o C++ que admite punteros :

  suma = *a + *b + *c; 

La evaluación de la expresión *xse denomina " desreferenciar " un puntero e implica leer desde la memoria en una ubicación especificada por el valor actual de x. Los efectos de leer desde un puntero están determinados por el modelo de memoria de la arquitectura . Al leer desde el almacenamiento de programa estándar, no hay efectos secundarios debido al orden de las operaciones de lectura de memoria. En la programación de sistemas integrados , es muy común tener E/S mapeadas en memoria donde las lecturas y escrituras en la memoria desencadenan operaciones de E/S o cambios en el modo operativo del procesador, que son efectos secundarios muy visibles. Para el ejemplo anterior, supongamos por ahora que los punteros apuntan a la memoria de programa normal, sin estos efectos secundarios. El compilador es libre de reordenar estas lecturas en el orden del programa como lo considere oportuno y no habrá efectos secundarios visibles para el programa.

¿Qué pasa si el valor asignado también es un puntero indirecto?

  *suma = *a + *b + *c; 

En este caso, es poco probable que la definición del lenguaje permita al compilador descomponer esto de la siguiente manera:

  // tal como lo reescribió el compilador
  // generalmente prohibido
  *suma = *a + *b;
  *suma = *suma + *c;

En la mayoría de los casos, esto no se consideraría eficiente y las escrituras de punteros tienen posibles efectos secundarios en el estado visible de la máquina. Dado que al compilador no se le permite esta transformación de división en particular, la única escritura en la ubicación de memoria de sumdebe seguir lógicamente a las tres lecturas de punteros en la expresión de valor.

Supongamos, sin embargo, que el programador está preocupado por la semántica visible del desbordamiento de enteros y divide la declaración en partes a nivel de programa de la siguiente manera:

  // tal como lo creó directamente el programador
  // con problemas de alias
  *suma = *a + *b;
  *suma = *suma + *c;

La primera instrucción codifica dos lecturas de memoria, que deben preceder (en cualquier orden) a la primera escritura en *sum. La segunda instrucción codifica dos lecturas de memoria (en cualquier orden) que deben preceder a la segunda actualización de *sum. Esto garantiza el orden de las dos operaciones de adición, pero potencialmente introduce un nuevo problema de alias de direcciones : cualquiera de estos punteros podría hacer referencia a la misma ubicación de memoria.

Por ejemplo, supongamos en este ejemplo que *cy *sumtienen un alias en la misma ubicación de memoria, y reescribamos ambas versiones del programa con *sumreemplazos para ambas.

  *suma = *a + *b + *suma; 

No hay problemas aquí. El valor original de lo que escribimos originalmente como *cse pierde al asignarlo a *sum, y también el valor original de *sumpero esto se sobrescribió en primer lugar y no es de especial importancia.

  // En qué se convierte el programa con *c y *sum alias
  *suma = *a + *b;
  *suma = *suma + *suma;

Aquí se sobrescribe el valor original de *sumantes de su primer acceso y en su lugar obtenemos el equivalente algebraico de:

  // equivalente algebraico del caso con alias anterior
  *suma = (*a + *b) + (*a + *b);

que asigna un valor completamente diferente *sumdebido a la reorganización de la declaración.

Debido a los posibles efectos de alias, las expresiones de puntero son difíciles de reorganizar sin correr el riesgo de que se produzcan efectos visibles en el programa. En el caso común, es posible que no haya ningún efecto de alias, por lo que el código parece ejecutarse normalmente como antes. Pero en el caso extremo en el que hay alias, pueden producirse graves errores de programa. Incluso si estos casos extremos están completamente ausentes en la ejecución normal, abren la puerta a que un adversario malintencionado diseñe una entrada en la que exista alias, lo que podría dar lugar a un ataque de seguridad informática .

Una reordenación segura del programa anterior es la siguiente:

// declara una variable local   temporal 'temp' del tipo adecuado
  temperatura = *a + *b;
  *suma = temperatura + *c;

Finalmente consideremos el caso indirecto con llamadas de función agregadas:

  *suma = f(*a) + g(*b); 

El compilador puede elegir evaluar *ay *bantes de la llamada de función, puede diferir la evaluación de *bhasta después de la llamada de función fo puede diferir la evaluación de *ahasta después de la llamada de función g. Si las funciones fy gestán libres de efectos secundarios visibles para el programa, las tres opciones producirán un programa con los mismos efectos visibles para el programa. Si la implementación de fo gcontiene el efecto secundario de cualquier puntero escrito sujeto a alias con punteros ao b, las tres opciones pueden producir diferentes efectos visibles para el programa.

En general, los lenguajes compilados no son lo suficientemente detallados en sus especificaciones como para que el compilador determine formalmente en tiempo de compilación qué punteros pueden tener alias y cuáles no. La acción más segura es que el compilador asuma que todos los punteros pueden tener alias en todo momento. Este nivel de pesimismo conservador tiende a producir un rendimiento terrible en comparación con la suposición optimista de que nunca existen alias.

Como resultado, muchos lenguajes compilados de alto nivel, como C/C++, han evolucionado hasta tener especificaciones semánticas complejas y sofisticadas acerca de dónde se le permite al compilador hacer suposiciones optimistas en el reordenamiento del código en busca del mayor rendimiento posible, y dónde se le requiere al compilador hacer suposiciones pesimistas en el reordenamiento del código para evitar riesgos semánticos.

La clase más grande de efectos secundarios en un lenguaje procedimental moderno involucra operaciones de escritura en memoria, por lo que las reglas en torno al ordenamiento de la memoria son un componente dominante en la definición de la semántica del orden del programa. La reordenación de las llamadas de funciones mencionadas anteriormente puede parecer una consideración diferente, pero esto generalmente deriva en preocupaciones sobre los efectos de memoria internos a las funciones llamadas que interactúan con las operaciones de memoria en la expresión que genera la llamada de función.

Los compiladores modernos a veces llevan esto un paso más allá mediante una regla as-if , en la que se permite cualquier reordenamiento (incluso entre sentencias) si no se produce ningún efecto en la semántica visible del programa. Bajo esta regla, el orden de las operaciones en el código traducido puede variar enormemente del orden especificado del programa. Si se permite al compilador hacer suposiciones optimistas sobre expresiones de puntero distintas que no tienen superposición de alias en un caso en el que realmente exista tal alias (esto normalmente se clasificaría como un programa mal formado que exhibe un comportamiento indefinido ), los resultados adversos de una transformación agresiva de optimización de código son imposibles de adivinar antes de la ejecución del código o la inspección directa del código. El reino del comportamiento indefinido tiene manifestaciones casi ilimitadas.

Es responsabilidad del programador consultar la especificación del lenguaje para evitar escribir programas mal formados en los que la semántica pueda verse alterada como resultado de cualquier optimización legal del compilador. Fortran tradicionalmente impone una gran carga sobre el programador para que esté al tanto de estos problemas, y los lenguajes de programación de sistemas C y C++ no se quedan atrás.

Algunos lenguajes de alto nivel eliminan por completo las construcciones de punteros, ya que este nivel de alerta y atención a los detalles se considera demasiado alto para mantenerlo de manera confiable incluso entre programadores profesionales.

Incluso entre la subpoblación de programadores de sistemas profesionales que suelen estar mejor informados en esta área temática, se considera que un conocimiento completo de la semántica del orden de la memoria es una especialización arcana. La mayoría de los programadores se conforman con un conocimiento adecuado de estas cuestiones dentro del dominio normal de su experiencia en programación. En el extremo de la especialización en semántica del orden de la memoria se encuentran los programadores que crean marcos de software que respaldan modelos de computación concurrente .

Tenga en cuenta que no se puede suponer que las variables locales estén libres de alias si un puntero a dicha variable se escapa:

  suma = f(&a) + g(a); 

fNo se puede saber qué podría haber hecho la función con el puntero suministrado a a, incluida la posibilidad de dejar una copia en estado global a la que la función gaccede más tarde. En el caso más simple, fescribe un nuevo valor en la variable a, lo que hace que esta expresión esté mal definida en el orden de ejecución. fse puede evitar de forma visible que haga esto aplicando un calificador const a la declaración de su argumento de puntero, lo que hace que la expresión esté bien definida. Por lo tanto, la cultura moderna de C/C++ se ha vuelto algo obsesiva con el suministro de calificadores const a las declaraciones de argumentos de función en todos los casos viables.

C y C++ permiten que los elementos internos de fun objeto eliminen el atributo de constness como un recurso peligroso. Si flo hace de una manera que puede romper la expresión anterior, no debería declarar el tipo del argumento del puntero como const en primer lugar.

Otros lenguajes de alto nivel se inclinan por un atributo de declaración de este tipo, lo que equivale a una garantía sólida sin lagunas que puedan violar esta garantía provista dentro del lenguaje mismo; todas las apuestas están canceladas en relación con esta garantía del lenguaje si su aplicación vincula una biblioteca escrita en un lenguaje de programación diferente (aunque esto se considera un diseño escandalosamente malo).

Estas barreras impiden que un compilador reordene las instrucciones durante el tiempo de compilación; no impiden que la CPU las reordene durante el tiempo de ejecución.

• Cualquiera de estas declaraciones de ensamblador en línea de GNU prohíbe al compilador GCC reordenar los comandos de lectura y escritura a su alrededor: ^[9]

asm volátil("" ::: "memoria");
__asm__ __volatile__ ("" ::: "memoria");

• Esta función C11/C++11 prohíbe al compilador reordenar los comandos de lectura y escritura a su alrededor: ^[10]

valla_de_señal_atómica(orden_de_memoria_acq_rel);

• El compilador Intel C++ (ICC/ICL) utiliza intrínsecos de "valla de compilador completa": ^{[11] [12]}

__barrera_de_memoria()

• El compilador Microsoft Visual C++ (MSVC) admite algunas funciones intrínsecas solo para x86/x64 (todas ellas están obsoletas): ^[13]

_LeerBarrera()
_WriteBarrier()
_Lectura y escritura Barrera()

En muchos lenguajes de programación, se pueden combinar distintos tipos de barreras con otras operaciones (como cargar, almacenar, incrementar atómicamente, comparar atómicamente e intercambiar), por lo que no se necesita una barrera de memoria adicional antes o después (o ambas). Según la arquitectura de CPU a la que se apunte, estas construcciones del lenguaje se traducirán en instrucciones especiales, en instrucciones múltiples (es decir, barrera y carga) o en instrucciones normales, según las garantías de ordenamiento de la memoria del hardware.

Existen varios modelos de consistencia de memoria para sistemas SMP :

• Consistencia secuencial (todas las lecturas y todas las escrituras están en orden)
• Consistencia relajada (se permiten algunos tipos de reordenamiento)
  • Las cargas se pueden reordenar después de las cargas (para un mejor funcionamiento de la coherencia de la caché, mejor escalabilidad)
  • Las cargas se pueden reordenar después de las tiendas.
  • Las tiendas se pueden reordenar después de las tiendas.
  • Las tiendas se pueden reordenar después de las cargas.
• Consistencia débil (las lecturas y escrituras se reordenan arbitrariamente, limitadas solo por barreras de memoria explícitas )

En algunas CPU

• Las operaciones atómicas se pueden reordenar con cargas y almacenamientos. ^[14]
• Puede haber una canalización de caché de instrucciones incoherente, lo que impide que se ejecute código automodificable sin instrucciones especiales de vaciado/recarga de caché de instrucciones.
• Las cargas dependientes se pueden reordenar (esto es exclusivo de Alpha). Si el procesador primero obtiene un puntero a algunos datos y luego los datos, es posible que no obtenga los datos en sí, sino que use datos obsoletos que ya ha almacenado en caché y aún no ha invalidado. Permitir esta relajación hace que el hardware de caché sea más simple y rápido, pero conduce al requisito de barreras de memoria para lectores y escritores. ^[15] En el hardware Alpha (como los sistemas multiprocesador Alpha 21264 ) las invalidaciones de líneas de caché enviadas a otros procesadores se procesan de manera diferida de forma predeterminada, a menos que se solicite explícitamente que se procesen entre cargas dependientes. La especificación de la arquitectura Alpha también permite otras formas de reordenamiento de cargas dependientes, por ejemplo, utilizando lecturas de datos especulativas antes de saber el puntero real que se va a desreferenciar.

Modelos de ordenamiento de memoria RISC-V

OMM

Orden de memoria débil (predeterminado)

Operador de sistema de transmisión

Pedido total de la tienda (solo compatible con la extensión Ztso)

Modos de ordenamiento de memoria SPARC

Operador de sistema de transmisión

Pedido total de la tienda (predeterminado)

OMR

Orden de memoria relajada (no compatible con CPU recientes)

PSO

Pedido de tienda parcial (no compatible con CPU recientes)

Muchas arquitecturas con soporte SMP tienen instrucciones de hardware especiales para vaciar lecturas y escrituras durante el tiempo de ejecución .

• x86 , x86-64

lfence (asm), vacío _mm_lfence(vacío)
sfence (asm), vacío _mm_sfence(vacío) [18] 
mfence (asm), vacío _mm_mfence(vacío) [19]

• PC de potencia

sincronización (asm)

• MIPS

sincronización (asm) [20] [21]

• Itanio

mf (ensamblaje)

• FUERZA

dcs (asm)

• ARMv7 ^[22]

dmb (conjunto)
dsb (asm)
isb (asm)

Algunos compiladores admiten funciones integradas que emiten instrucciones de barrera de memoria de hardware:

• GCC , ^[23] versión 4.4.0 y posteriores, ^[24] tiene __sync_synchronize.
• Desde C11 y C++11 atomic_thread_fence()se agregó un comando.
• El compilador de Microsoft Visual C++ tiene MemoryBarrier()una macro en el encabezado de la API de Windows (obsoleta). ^{[25] [13]}
• Sun Studio Compiler Suite ^[26] tiene __machine_r_barrier, __machine_w_barriery __machine_rw_barrier.

• Modelo de memoria (programación)

• Modelos de consistencia de memoria compartida: un tutorial de Sarita V Adve y Kourosh Gharachorloo
• Ordenación de la memoria en los microprocesadores modernos por Paul E McKenney
• Modelos de memoria débil y fuerte por Jeff Preshing
• Un modelo formal de ordenamiento de memoria del núcleo de Jade Alglave et al.
• Ordenación de memoria de IA (arquitectura Intel) en YouTube - Google Tech Talk por Richard L Hudson
• Arquitectura de computadoras: un enfoque cuantitativo . Cuarta edición. J Hennessy, D Patterson, 2007. Capítulo 4.6