Mecanismo para una atomicidad fuerte en un sistema de memoria transaccional.

Un procedimiento para proporcionar mecanismos para una atomicidad fuerte en un sistema de memoriatransaccionalcaracterizado por:

detectar una operación de carga no transaccional en una función, siendo la operación de carga notransaccional, cuando se ejecuta, para cargar desde una ubicación de memoria;

insertar en la función una pluralidad de operaciones de atomicidad fuerte en respuesta a la detección de laoperación de carga no transaccional en la función, siendo las operaciones de atomicidad fuerte paragarantizar la validez entre accesos a memoria transaccionales y no transaccionales;

en el que las operaciones de atomicidad fuerte, cuando son ejecutadas, garantizan la validez determinando(415) si la ubicación (215) de memoria o las ubicaciones (205) de memoria han sido actualizadas por unatransacción, habiendo tenido lugar dicha actualización desde el inicio de la función, en el que dicha insercióncomprende:

insertar una primera operación de atomicidad fuerte en la función que, cuando es ejecutada, actualiza unregistro con una copia (301b, 302b) de valor de transacción local LTV de un valor de transacción global(305), siendo dicho valor de transacción global un valor incrementado en respuesta a la finalización de unatransacción y ocurriendo dicha actualización del registro al inicio de dicha función;

insertar una segunda operación de atomicidad fuerte que, cuando es ejecutada, obtiene un valor de versiónasociado con la ubicación (215) de memoria; e

insertar una tercera operación de atomicidad fuerte que, cuando es ejecutada, compara el valor de versióncon la copia (301b, 302b) de LTV para determinar si la ubicación (215) de memoria ha sido actualizadadesde el inicio de la función;

y en el que el procedimiento comprende, además, insertar (420) una pluralidad de operaciones de vía lenta quehan de ser ejecutadas en respuesta a la determinación (415) de que la ubicación (215) de memoria o lasubicaciones (205) de memoria han sido actualizadas desde el inicio de la función, para resolver el conflictoentre la transacción y la operación de carga no transaccional, en el que dichas operaciones de vía lentaincluyen:

entrar en bucle o esperar en un bloqueo asociado con el valor de versión,

adquirir la propiedad de los bloqueos y/o

volver a llevar a cabo la operación de carga no transaccional.

Mecanismo para una atomicidad fuerte en un sistema de memoria transaccional Campo La presente invención se refiere al campo de la ejecución en procesador y, en particular, acerca de la ejecución de grupos de instrucciones.

Antecedentes Los avances en el procesamiento de semiconductores y en el diseño de lógica han permitido un aumento en la cantidad de lógico que puede estar presente en dispositivos de circuitos integrados. En consecuencia, han evolucionado configuraciones de sistemas de ordenadores desde circuitos integrados únicos o múltiples en un sistema a múltiples núcleos y múltiples procesadores lógicos presentes en circuitos integrados individuales. Típicamente, un procesador o un circuito integrado comprende un único dado procesador, pudiendo incluir el cubo procesador cualquier número de núcleos o de procesadores lógicos.

El número siempre creciente de núcleos y procesadores lógicos en los circuitos integrados permite que se ejecuten de forma concurrente más hilos de soporte lógico. Sin embargo, el aumento en el número de hilos de soporte lógico que pueden ser ejecutados simultáneamente ha creado problemas de sincronización de datos compartidos entre los hilos de soporte lógico. Una solución común para acceder a datos compartidos en sistemas de múltiples núcleos o de múltiples procesadores lógicos comprende el uso de bloqueos para garantizar la exclusión mutua en accesos múltiples a los datos compartidos. Sin embargo, la capacidad siempre creciente de ejecutar múltiples hilos de soporte lógico potencialmente da como resultado una falsa disputa y una serialización de la ejecución.

Por ejemplo, consideremos una tabla de claves calculadas que contiene datos compartidos. Con un sistema de bloqueos, un programador puede bloquear toda la tabla de claves calculadas, permitiendo que un hilo acceda a toda la tabla de claves calculadas. Sin embargo, el desempeño y el rendimiento de otros hilos se ve potencialmente afectado de manera adversa, ya que son incapaces de acceder a ninguna entrada de la tabla de claves calculadas hasta que se quite el bloqueo. Alternativamente, puede bloquearse cada entrada de la tabla de claves calculadas. Sin embargo, esto aumenta la complejidad de programación, ya que los programas tienen que responder de más bloqueos dentro de una tabla de claves calculadas.

Otra técnica de sincronización de datos incluye el uso de memoria transaccional (TM) . A menudo, la ejecución transaccional incluye la ejecución especulativa de una agrupación de una pluralidad de microoperaciones, operaciones o instrucciones. En el ejemplo que antecede, ambos hilos se ejecutan dentro de la tabla de claves calculadas, y sus accesos son monitorizados/seguidos. Si ambos hilos acceden/alteran la misma entrada, una de las transacciones puede ser abortada para resolver el conflicto. Un tipo de ejecución transaccional incluye una memoria transaccional de soporte lógico (STM) en la que los accesos son objeto de seguimiento, la resolución de conflictos, el aborto de tareas y otras tareas transaccionales son llevados a cabo en soporte lógico.

Previamente, para garantizar que no ocurren conflictos en tiempo de ejecución entre operaciones de memoria transaccional y operaciones de memoria no transaccional, los compiladores tratan cada operación de memoria no transaccional como una transacción de una sola operación. En otras palabras, se insertan operaciones transaccionales en operaciones de memoria no transaccional para garantizar que no ocurren conflictos de tiempo de ejecución. Sin embargo, la ejecución de barreras exhaustivas en las operaciones de memoria no transaccional desperdicia potencialmente ciclos de ejecución.

El documento “Transactional Lock-Free Execution of Lock-Based Programs”, de Ravi Rajwar y James Goodman (publicado en PROCEEDINGS OF THE 10TH SYMPOSIUM ON ARCHITECTURAL SUPPORT FOR PROGRAMMING LANGUAGES AND OPERATING SYSTEMS) , propone una técnica denominada “eliminación transaccional de bloqueos” (TLR) que permite que un programa que usa la sincronización basada en bloqueos sea ejecutado por el soporte físico de una manera libre de bloqueos. El bloqueo define el alcance de la transacción. El código que usaba el bloqueo es ejecutado entonces especulativamente como una transacción sin solicitar ni adquirir el bloqueo. Se usa un esquema de resolución de conflictos para ejecutar transacciones contrapuestas en el debido orden.

El documento “Virtualizing Transactional Memor y ”, de Rajwar et. al. (publicado en COMPUTER ARCHITECTURE. 2005. ISCA ’05. PROCEEDINGS. 32ND INTERNATIONAL SYMPOSIUM ON MADISON WI, USA 04-08 JUNIO DE 2005. PISCATAWAY, NJ, EE. UU. IEEE 4 JUNIO DE 2005) , propone un sistema que aborda las deficiencias en los sistemas de memoria transaccional de soporte físico. Su sistema, denominado “memoria transaccional virtual” (VTM) , es un sistema transparente al usuario que protege al programador contra diversas limitaciones de recursos específicas a la plataforma. La VTM mantiene la ventaja de rendimiento de las transacciones en soporte físico, incurre en una baja sobrecarga en el tiempo y tiene costes modestos en soporte del soporte físico.

Breve descripción de los dibujos La presente invención, tal como se expone en las reivindicaciones independientes 1, 10 y 19, se ilustra a título de ejemplo y no se pretende que esté limitada por las figuras de los dibujos adjuntos.

La Figura 1 ilustra una realización de un sistema capaz de proporcionar una atomicidad fuerte eficiente.

La Figura 2 ilustra una realización de un sistema de memoria transaccional de soporte lógico (STM) para proporcionar una atomicidad fuerte eficiente.

La Figura 3a ilustra una realización de lógica para proporcionar una atomicidad fuerte eficiente.

La Figura 3b ilustra otra realización de lógica para proporcionar una atomicidad fuerte eficiente.

La Figura 4a ilustra una realización de un diagrama de flujo de un procedimiento para proporcionar una atomicidad fuerte eficiente.

La Figura 4b ilustra una realización del diagrama de flujo representado en la Figura 4a.

La Figura 4c ilustra otra realización del diagrama de flujo representado en la Figura 4a.

Descripción detallada En la siguiente descripción, se exponen numerosos detalles específicos, tales como ejemplos de soporte específico de soporte físico para la ejecución transaccional, procedimientos específicos de seguimiento/metadatos, tipos específicos de ubicaciones/memoria en procesadores y tipos específicos de accesos a memoria y ubicaciones, etc., para proporcionar una comprensión cabal de la presente invención. Sin embargo, será evidente para un experto en la técnica que no es preciso emplear estos detalles específicos para poner en práctica la presente invención. En otros casos, componentes o procedimientos bien conocidos, tales como la codificación de transacciones en soporte lógico, la demarcación de transacciones, arquitecturas específicas de procesadores de núcleos múltiples e hilos múltiples, soporte físico de transacciones, organizaciones de memoria tampón y detalles operacional específicos de microprocesadores, no han sido descritos con detalle para evitar hacer innecesariamente confusa la presente invención.

Un valor, según se usa en el presente documento, incluye cualquier representación conocida de un número, un estado, un estado lógico o un estado lógico binario. A menudo, el uso de niveles de lógica, valores de lógica o valores lógicos también se denomina unos y ceros, lo cual simplemente representa estados lógicos binarios. Por ejemplo, un 1 se refiere a un nivel lógico alto y 0 se refiere a un nivel lógico bajo. Sin embargo, en los sistemas de ordenadores se han usado otras representaciones de valores. Por ejemplo, el número decimal 10 también puede ser un valor binario 1010 y una letra hexadecimal A.

Además, los estados pueden ser representados por valores o porciones de valores. Por ejemplo, un estado de bloqueo puede ser representado por un primer valor en una ubicación, tal como un número impar, mientras que un número de versión, tal como un valor par, en la ubicación representa un estado sin bloqueo. Aquí puede usarse una porción de los valores primero y segundo para representar los estados, tales como los dos bits más bajos de los valores, un bit de signo asociado con los valores u otra porción de los valores. Además, las expresiones puesto a uno y puesto a cero, en una realización, se refieren a... [Seguir leyendo]

1. Un procedimiento para proporcionar mecanismos para una atomicidad fuerte en un sistema de memoria transaccional caracterizado por:

detectar una operación de carga no transaccional en una función, siendo la operación de carga no transaccional, cuando se ejecuta, para cargar desde una ubicación de memoria; insertar en la función una pluralidad de operaciones de atomicidad fuerte en respuesta a la detección de la operación de carga no transaccional en la función, siendo las operaciones de atomicidad fuerte para garantizar la validez entre accesos a memoria transaccionales y no transaccionales;

en el que las operaciones de atomicidad fuerte, cuando son ejecutadas, garantizan la validez determinando (415) si la ubicación (215) de memoria o las ubicaciones (205) de memoria han sido actualizadas por una transacción, habiendo tenido lugar dicha actualización desde el inicio de la función, en el que dicha inserción comprende:

insertar una primera operación de atomicidad fuerte en la función que, cuando es ejecutada, actualiza un registro con una copia (301b, 302b) de valor de transacción local LTV de un valor de transacción global (305) , siendo dicho valor de transacción global un valor incrementado en respuesta a la finalización de una transacción y ocurriendo dicha actualización del registro al inicio de dicha función; insertar una segunda operación de atomicidad fuerte que, cuando es ejecutada, obtiene un valor de versión asociado con la ubicación (215) de memoria; e insertar una tercera operación de atomicidad fuerte que, cuando es ejecutada, compara el valor de versión con la copia (301b, 302b) de LTV para determinar si la ubicación (215) de memoria ha sido actualizada desde el inicio de la función;

y en el que el procedimiento comprende, además, insertar (420) una pluralidad de operaciones de vía lenta que han de ser ejecutadas en respuesta a la determinación (415) de que la ubicación (215) de memoria o las ubicaciones (205) de memoria han sido actualizadas desde el inicio de la función, para resolver el conflicto entre la transacción y la operación de carga no transaccional, en el que dichas operaciones de vía lenta incluyen:

entrar en bucle o esperar en un bloqueo asociado con el valor de versión, adquirir la propiedad de los bloqueos y/o 30 volver a llevar a cabo la operación de carga no transaccional.

2. El procedimiento de la reivindicación 1 en el que la pluralidad de operaciones de atomicidad fuerte no incluye una operación de bloqueo que, cuando se ejecute, determine si un bloqueo (250) asociado con la ubicación (215) de memoria no tiene propietario.

3. El procedimiento de la reivindicación 1 en el que la determinación de si se han iniciado transacciones desde el inicio de la función para actualizar ubicaciones (205) de memoria que son objeto de acceso por la operación de carga no transaccional comprende:

insertar una primera operación alternativa de atomicidad fuerte en la función que, cuando es ejecutada, ha de copiar un valor (305) de transacción global GTV a un valor (301b, 302b) de transacción local LTV; e insertar una segunda operación alternativa de atomicidad fuerte que, cuando es ejecutada, ha de comparar el LTV (301b, 302b) con un valor (330) de transacción de inicio STV para determinar si se han iniciado transacciones que actualizan ubicaciones (205) de memoria desde el inicio de la función.

4. El procedimiento de las reivindicaciones 1 o 3 en el que la primera operación de atomicidad fuerte o la primera operación alternativa de atomicidad fuerte, respectivamente, cuando son ejecutadas, han de actualizar también un registro para contener el LTV (301b, 302b) .

45 5. El procedimiento de la reivindicación 1 en el que la segunda operación de atomicidad fuerte, que, cuando es ejecutada, obtiene el valor (251) de versión asociado con la ubicación (215) de memoria, comprende:

una primera operación de versión que, cuando es ejecutada, obtiene una dirección asociada con la ubicación (215) de memoria, y una segunda operación de versión que, cuando es ejecutada, calcula un índice a un registro (250) de 50 transacciones en una tabla (240) de registros de transacciones para obtener el valor (251) de versión.

6. El procedimiento de la reivindicación 1 en el que el registro (250) de transacciones ha de contener un valor (252) de bloqueo para indicar que la ubicación (215) de memoria tiene propietario y de contener el valor (251) de versión para indicar que la ubicación (215) de memoria no tiene propietario, y en el que el valor (252) de bloqueo incluye un uno lógico en un bit más significativo MSB del registro (250) de transacciones y el valor 55 (251) de versión incluye un cero lógico en el MSB del registro (250) de transacciones.

7. El procedimiento de la reivindicación 1 en el que la tercera operación de atomicidad fuerte, que, cuando es ejecutada, compara el valor de versión con la copia (301b, 302b) del LTV para determinar si la ubicación (215) de memoria ha sido actualizada desde el inicio de la función, comprende:

que la tercera operación de atomicidad fuerte, cuando sea ejecutada, determine (415) que la ubicación (215) de memoria ha sido actualizada desde el inicio de la función en respuesta a que el valor (251) de versión sea mayor que la copia (301b, 302b) del LTV, y determinar (415) que la ubicación (215) de memoria no ha sido actualizada desde el inicio de la función en respuesta a que el valor (251) de versión sea menor o igual a la copia (301b, 302b) del LTV.

8. El procedimiento de la reivindicación 7 en el que el valor (251) de versión es mantenido en una ubicación (240)

de los metadatos que es objeto de referencia por un valor de clave calculado de al menos una porción de una dirección asociada con la ubicación (215) de memoria.

9. El procedimiento de la reivindicación 3 en el que la determinación de si se han iniciado transacciones desde el inicio de la función para actualizar ubicaciones (205) de memoria objeto de acceso por la operación de carga no transaccional comprende, además:

que el STV contenga un valor de recuento; actualizar el valor de recuento en respuesta al inicio de cualquier transacción; comparar el LTV (301b, 302b) con el valor de recuento; determinar (415) que las transacciones no han actualizado la pluralidad de ubicaciones (205) de memoria desde el inicio de la función en respuesta a que el valor de recuento sea igual al LTV (301b, 302b) ; y determinar (415) que las transacciones han actualizado la pluralidad de ubicaciones (205) de memoria desde el inicio de la función en respuesta a que el valor de recuento sea mayor que el LTV (301b, 302b) .

10. Un sistema que comprende una memoria transaccional con mecanismos para una atomicidad fuerte caracterizado porque el sistema incluye un código de programa que proporciona:

un medio para detectar una operación de carga no transaccional en una función, siendo la operación de carga no transaccional, cuando se ejecuta, para cargar desde una ubicación de memoria; un medio para insertar una pluralidad de operaciones de atomicidad fuerte en respuesta a la detección de la operación de carga no transaccional en la función; un medio para permitir las operaciones de atomicidad fuerte para garantizar la validez entre los accesos a memoria transaccionales y no transaccionales;

en el que el medio que permite las operaciones de atomicidad fuerte para garantizar la validez comprende un medio para determinar (415) si la ubicación (215) de memoria o las ubicaciones (205) de memoria han sido actualizadas por una transacción, habiendo tenido lugar dicha actualización desde el inicio de la función, en el que el medio para dicha determinación comprende: un medio para insertar una primera operación de atomicidad fuerte en la función que, cuando es ejecutada, actualiza un registro con una copia (301b, 302b) de valor de transacción local LTV de un valor de transacción global (305) , siendo dicho valor de transacción global un valor incrementado en respuesta a la finalización de una transacción y ocurriendo dicha actualización del registro al inicio de dicha función; un medio para insertar una segunda operación de atomicidad fuerte que, cuando es ejecutada, obtiene un valor de versión asociado con la ubicación (215) de memoria; y un medio para insertar una tercera operación de atomicidad fuerte que, cuando es ejecutada, compara el valor de versión con la copia (301b, 302b) de LTV para determinar si la ubicación (215) de memoria ha sido actualizada desde el inicio de la función; y en el que el código de programa, además, proporciona: un medio para insertar (420) una pluralidad de operaciones de vía lenta que han de ser ejecutadas en respuesta a la determinación (415) de que la 45 ubicación (215) de memoria o las ubicaciones (205) de memoria han sido actualizadas desde el inicio de la función, para resolver el conflicto entre la transacción y la operación de carga no transaccional, en el que dichas operaciones de vía lenta incluyen: un medio para permitir entrar en bucle o esperar en un bloqueo asociado con el valor de versión, un medio para adquirir la propiedad de los bloqueos y/o 50 un medio para volver a llevar a cabo la operación de carga no transaccional.

11. El sistema de la reivindicación 10 en el que la pluralidad de operaciones de atomicidad fuerte no incluye una operación de bloqueo que, cuando se ejecute, determine si un bloqueo (250) asociado con la ubicación (215) de memoria no tiene propietario.

12. El sistema de la reivindicación 10 en el que el medio para determinar si se han iniciado transacciones desde el

55 inicio de la función para actualizar ubicaciones (205) de memoria que son objeto de acceso por la operación de carga no transaccional comprende:

un medio para insertar una primera operación alternativa de atomicidad fuerte en la función que, cuando es ejecutada, efectúa una copia de un valor (305) de transacción global GTV a un valor (301b, 302b) de transacción local LTV; y un medio para insertar una segunda operación alternativa de atomicidad fuerte que, cuando es ejecutada, ha de comparar el LTV (301b, 302b) con un valor (330) de transacción de inicio STV para determinar si se han iniciado transacciones que actualizan ubicaciones (205) de memoria desde el inicio de la función.

13. El sistema de las reivindicaciones 10 o 12 en el que la primera operación de atomicidad fuerte o la primera operación alternativa de atomicidad fuerte, cuando son ejecutadas, han de actualizar también un registro para contener el LTV (301b, 302b) .

14. El sistema de la reivindicación 10 en el que la segunda operación de atomicidad fuerte, que, cuando es ejecutada, obtiene el valor (251) de versión asociado con la ubicación (215) de memoria, comprende:

una primera operación de versión que, cuando es ejecutada, obtiene una dirección asociada con la ubicación (215) de memoria, y una segunda operación de versión que, cuando es ejecutada, calcula un índice a un registro (250) de transacciones en una tabla (240) de registros de transacciones para obtener el valor (251) de versión.

15. El sistema de la reivindicación 10 en el que el registro (250) de transacciones está configurado para contener un valor (252) de bloqueo para indicar que la ubicación (215) de memoria tiene propietario y está configurado, además, para contener el valor (251) de versión para indicar que la ubicación (215) de memoria no tiene propietario, y en el que el valor (252) de bloqueo comprende un uno lógico en un bit más significativo MSB del registro (250) de transacciones y el valor (251) de versión comprende un cero lógico en el MSB del registro (250) de transacciones.

16. El sistema de la reivindicación 10 en el que la tercera operación de atomicidad fuerte, que, cuando es ejecutada, compara el valor de versión con la copia (301b, 302b) del LTV para determinar si la ubicación (215) de memoria ha sido actualizada desde el inicio de la función:

está configurada para determinar (415) que la ubicación (215) de memoria ha sido actualizada desde el inicio de la función en respuesta a que el valor (251) de versión sea mayor que la copia (301b, 302b) del LTV, y está configurada para determinar (415) que la ubicación (215) de memoria no ha sido actualizada desde el inicio de la función en respuesta a que el valor (251) de versión sea menor o igual a la copia (301b, 302b)

del LTV.

17. El sistema de la reivindicación 16 que comprende una ubicación (240) en los metadatos en la que se mantiene el valor (251) de versión, estando configurada la ubicación (240) en los metadatos para ser objeto de referencia por un valor de clave calculado de al menos una porción de una dirección asociada con la ubicación (215) de memoria.

18. El sistema de la reivindicación 10 en el que el medio para determinar si ubicaciones (205) de memoria han sido actualizadas por una transacción comprende:

un medio para permitir que el STV contenga un valor de recuento; un medio para actualizar el valor de recuento en respuesta al inicio de una transacción; un medio para comparar el LTV (301b, 302b) con el valor de recuento;

un medio para determinar (415) que la transacción no ha actualizado las ubicaciones (205) de memoria desde el inicio de la función en respuesta a que el valor de recuento sea igual al LTV (301b, 302b) ; y un medio para determinar (415) que la transacción ha actualizado las ubicaciones (205) de memoria desde el inicio de la función en respuesta a que el valor de recuento sea mayor que el LTV (301b, 302b) .

19. Un soporte que porta un programa de ordenador que comprende una pluralidad de instrucciones 45 implementables por procesador para hacer que un procesador lleve a cabo un procedimiento según cualquiera de las reivindicaciones 1 a 9.