Prefetching

José Luis Santillán

Pamela Mena

Martin Navarro

Tema:

Hardware vs Software prefetching

Objetivo General:

Analizar técnicas de prefetching en hardware y software.

Objetivos específicos:

-Describir ventajas y desventajas de hardware y software prefetching.

-Implementar software prefetching en diferentes dispositivos.

-Comparar el rendimiento y tiempos de ejecución de los programas cuando tienen técnicas de prefetching implementadas.

¿Qué es prefetching?

Es una técnica -> mínimiza errores de cache -> obtención de información rápida

Es una especulación sobre futuros accesos de datos y almacenarlos en memoria cache.

Utiliza recursos de ejecución del procesador.
Image

Efectividad del Prefetching

3 aspectos:

-Precisión: # prefetchs utiles/ # prefetchs

-Cobertura: # prefetchs utiles/ # cache misses sin prefetching

-Tiempo: tiempo que demora un prefetch en ejecutar

Software Prefetching

El software prefetching depende de que el programador o el compilador coloque explícitamente una instrucción de prefetching en la aplicación o programa.

Tipos

-Array Prefetching: Los programas que emplean array prefetching, presentan una ventaja, los patrones de acceso a la memoria caché se identifican de manera precisa cuando se compila el código. Siempre y cuando se conozca la dimensión del arreglo.

Image

-Jump Pointer Prefetching (Queue Jumping): Los punteros de salto se utilizan para reducir la latencia de la memoria durante el proceso de prefetching. Queue Jumping se aplica a estructuras sencillas “backbone” que contiene un solo tipo de nodos que se conectan (como un árbol o una lista). En los saltos de cola cada puntero se añade a un nodo que son utilizados para obtener la estructura completa.

Image

Implementacion Array prefetching

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>

void delay(int milliseconds)
{
    long pause;
    clock_t now,then;

    pause = milliseconds*(CLOCKS_PER_SEC/1000);
    now = then = clock();
    while( (now-then) < pause )
        now = clock();
}


int main(void) {
  srand(time(NULL));  
  struct timeval t1, t2;
  double elapsedTime;
  struct timeval t3, t4;
  double elapsedTime2;
  int number = 1000;
  int a[number];
  int b[number];

  for (int i = 0; i < number; i++){
    a[i] = rand(); 
    b[i] = rand();
  }
  gettimeofday(&t1, NULL);
  for (int i = 0; i < number; i++){
    a[i] = a[i] + b[i];
    delay(5);
    
  }
  gettimeofday(&t2, NULL);
  elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; 
  elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0;
  printf("%f ms.\n", elapsedTime);
  
  
  gettimeofday(&t3, NULL);
  for (int i = 0; i < number; i++){
    __builtin_prefetch (&a[i+4],1,1);
    __builtin_prefetch (&b[i+4],0,1);
    a[i] = a[i] + b[i];
    delay(5);
    
  }
  gettimeofday(&t4, NULL);
  elapsedTime2 = (t4.tv_sec - t3.tv_sec) * 1000.0; 
  elapsedTime2 += (t4.tv_usec - t3.tv_usec) / 1000.0;
  printf("%f ms.\n", elapsedTime2);
}

Gráficos

Ryzen 7 series 4000

Image Image

Intel core i7(10th)

Image Image

Intel core i5(10th)

Image Image

Intel core i7(10th) Ubuntu

Image Image

Hardware

El hardware prefetching usa mecanismos de hardware específicos para predecir datos que se necesitarán en un futuro próximo. Para estas técnicas, no es necesaria la intervención del compilador o del programador.

Tipos

-Sequential prefetching: Este método utiliza el principio de localidad espacial. Esto quiere decir que los datos que se acceden juntos son más probables que se almacenen juntos.

El cache prefecthing se realiza normalmente en bloques para aprovechar esta técnica.
Es decir, que se realiza un prefetch del bloque A+1, cuando el bloque A es accesado.

-Strided prefetching: En este caso analiza y monitorea las diferencias entre las direcciones de los accesos a memoria, buscando patrones (regulares o irregulares).

- Regulares: Los accesos de memoria están 𝑠 direcciones aparte. Es decir que, el prefetcher calcula 𝑠, y usa para calcular la dirección de memoria para realizar el prefetching.

- Irregulares: Para este caso, el acceso es variable, pero de todas formas el prefetcher intenta buscar un patrón.

Implementacion Hardware

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>


int main(void){
    struct timeval t1, t2;
    double elapsedTime;
    gettimeofday(&t1, NULL);
    
    int N = 1000;
    int array[N*N];
    //Accesses an array sequentially in rowMajor 
    for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                array[i*N+j]+=j;
            }
        }
        
    gettimeofday(&t2, NULL);
    elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; 
    elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0;
    printf("%f ms.\n", elapsedTime);
    
    struct timeval t3, t4;
    double elapsedTime2;
    gettimeofday(&t3, NULL);
    
    //Accesses an array randomly (Strided) 
    for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++) {
                array[j * N + rand() % N]+=j;
            }
    }
    gettimeofday(&t4, NULL);
    elapsedTime2 = (t4.tv_sec - t3.tv_sec) * 1000.0; 
    elapsedTime2 += (t4.tv_usec - t3.tv_usec) / 1000.0;
    printf("%f ms.\n", elapsedTime2);
    
    
}

Gráficos

Strided Prefetching

Image

Hardware Prefetching

Image

Ventajas y Desventajas

Hardware

Ventajas

Desventajas

Software

Ventajas

Desventajas

Conclusiones

Referencias