¿Cómo poner mi variable de estructura en cachés de CPU para eliminar el tiempo de acceso a la página de memoria principal? Opciones

Question

Está claro que no hay una manera explícita o ciertas llamadas al sistema que ayudan a los programadores a poner una variable en la memoria caché de la CPU.

Pero creo que un cierto estilo de programación o bien diseñado algoritmo puede hacer posible aumentar las posibilidades de que la variable se pueda almacenar en caché en las memorias caché de la CPU.

Aquí está mi ejemplo:

Quiero añadir una estructura de 8 bytes al final de una matriz que consiste del mismo tipo de estructuras, declarada en la región de la memoria principal global.

Este proceso se repite continuamente para 4 millones de operaciones. Este proceso toma 6 segundos, 1.5 us para cada operación. Creo que este resultado dice que las dos áreas de memoria no han sido almacenadas en caché.

Tengo algunas pistas de un cache-oblivious algorithm, así que probé varias formas de para mejorar esto. Hasta ahora, sin mejora.

Creo que algunos códigos inteligentes pueden reducir el tiempo transcurrido, hasta 10 a 100 veces. Por favor muéstrame el camino.

------------------------------------------------------------------------- 

adjuntas (2011-04-01)

Damon ~ gracias por tu comentario!

Después de leer su comentario, analicé mi código nuevamente, y encontré varias cosas que me perdí. El siguiente código que adjunté es la versión abreviada de mi código original.

Para medir con precisión el tiempo de ejecución de cada operación (en el código original, hay varios tipos diferentes de operaciones), inserté el código de medición de tiempo usando la función clock_gettime(). Pensé que si mido el tiempo de ejecución de cada operación y las acumulo, se puede evitar el costo adicional por el ciclo principal.

En el código original, el código de medición del tiempo estaba oculto por una función de macro, por lo que me olvidé completamente de él.

El tiempo de ejecución de este código es de casi 6 segundos. Pero si elimino la función de medición de tiempo en el ciclo principal, se convierte en 0.1 segundos.

Dado que la función clock_gettime() es compatible con una precisión muy alta (hasta que 1 nano segundo), ejecutado sobre la base de un hilo independiente, y también requiere muy grande estructura, Creo que la función hizo que el caché de salida de la memoria principal área donde se realizan las inserciones consecutivas.

Gracias de nuevo por su comentario. Para una mayor mejora, cualquier sugerencia será muy útil para mí para optimizar mi código.

Creo que la variable de estructura definida de forma jerárquica podría ocasionar un costo de tiempo innecesario, , pero primero quiero saber cuánto sería, antes de cambiarlo al código de estilo C.

---

typedef struct t_ptr { 
    uint32 isleaf :1, isNextLeaf :1, ptr :30; 
    t_ptr(void) { 
     isleaf = false; 
     isNextLeaf = false; 
     ptr = NIL; 
    } 
} PTR; 

typedef struct t_key { 
    uint32 op :1, key :31; 
    t_key(void) { 
     op = OP_INS; 
     key = 0; 
    } 
} KEY; 

typedef struct t_key_pair { 
    KEY key; 
    PTR ptr; 
    t_key_pair() { 
    } 

    t_key_pair(KEY k, PTR p) { 
     key = k; 
     ptr = p; 
    } 
} KeyPair; 

typedef struct t_op { 
    KeyPair keyPair; 
    uint seq; 
    t_op() { 
     seq = 0; 
    } 
} OP; 

#define MAX_OP_LEN 4000000 
typedef struct t_opq { 
    OP ops[MAX_OP_LEN]; 
    int freeOffset; 
    int globalSeq; 
    bool queueOp(register KeyPair keyPair); 
} OpQueue; 

bool OpQueue::queueOp(register KeyPair keyPair) { 
    bool isFull = false; 
    if (freeOffset == (int) (MAX_OP_LEN - 1)) { 
     isFull = true; 
    } 
    ops[freeOffset].keyPair = keyPair; 
    ops[freeOffset].seq = globalSeq++; 
    freeOffset++; 
} 

OpQueue opQueue; 
#include <sys/time.h> 
int main() { 
    struct timespec startTime, endTime, totalTime; 
    for(int i = 0; i < 4000000; i++) { 
     clock_gettime(CLOCK_REALTIME, &startTime); 
     opQueue.queueOp(KeyPair()); 
     clock_gettime(CLOCK_REALTIME, &endTime); 
     totalTime.tv_sec += (endTime.tv_sec - startTime.tv_sec); 
     totalTime.tv_nsec += (endTime.tv_nsec - startTime.tv_nsec); 
    } 
    printf("\n elapsed time: %ld", totalTime.tv_sec * 1000000LL + totalTime.tv_nsec/1000L); 
} 

Answer 1

no he sido capaz de forzar el almacenamiento en caché, pero puede forzar la memoria para ser uncache factible. Si tiene otras grandes estructuras de datos, puede excluirlas para que no contaminen sus cachés. Esto se puede hacer especificando PAGE_NOCACHE para las funciones de Windows VirutalAllocXXX.

http://msdn.microsoft.com/en-us/library/windows/desktop/aa366786(v=vs.85).aspx

Answer 2

no poner la estructura en cualquier caché. La CPU lo hace automáticamente por ti. La CPU es aún más inteligente que eso; si accede a la memoria secuencial, comenzará a poner cosas de la memoria en el caché antes de que las lea.

Y realmente, debería ser de sentido común que para un código tan simple como este, el tiempo que pasa midiendo es diez veces más que el tiempo para ejecutar el código (aparentemente 60 veces en su caso).

Dado que confía tanto en clock_gettime(): sugiero que lo llame cinco veces seguidas y almacene los resultados, luego imprima las diferencias. Hay resolución, hay precisión, y hay cuánto tiempo lleva devolver la hora actual, que es bastante larga.