False Sharing

Actualmente todas las computadoras están formadas por varios procesadores, por esta razón el desarrollo software está evolucionando hacia el procesamiento en paralelo con la finalidad de explotar al máximo posible estas máquinas. Este tipo de procesamiento nos permite utilizar cada una de las CPUs de nuestra máquina de forma simultánea para realizar un conjunto de operaciones independientes unas de otras. Pero no siempre ejecutar una aplicación de forma concurrente significa que se vaya a ganar rendimiento de forma inmediata, incluso en ciertas ocasiones se puede perder si el procesamiento concurrente no se gestiona de forma correcta.

Una de las principales causas que provocan una disminución de rendimiento es la sincronización entre los distintos procesadores. Esto es debido a que los procesadores generalmente tienen entre dos y tres niveles (L1, L2,…) de memoria caché en los cuales se va replicando la información de la memoria del sistema cuyo acceso suele ser lento mientras que el acceso a estos tipos de memoria es mucho más rápido. La velocidad de acceso va aumentando en función del nivel de la caché, a mayor proximidad a la CPU (L1) mayor velocidad.

figure1

Cada uno de los niveles está dividido en líneas de caché, normalmente de 64 o 128 bytes (L1) cada una, siendo estas la minínima unidad de información que puede entrar o salir de la caché. Cuando uno de los procesadores modifica una variable invalida la línea entera en la que se encuentra esa variable. Para mantener consistente el estado de la información cuando uno de los procesadores invalida una línea de memoria todos los procesadores del sistema invalidan esa misma línea en sus caches.

Este proceso de invalidación de líneas de caché no sólo se produce cuando se modifica el estado de una variable que se encuentra en uso por varios procesadores si no también cuando se modifica una variable que se encuentra en la misma línea de caché que otra variable que utiliza otro procesador. Esta situación se denomina false sharing.

figure2

En el siguiente fragmento de código podemos ver como varios hilos acceden de forma concurrente a celdas contiguas de un mismo array. Cuando uno de los hilos modifica el estado de la celda que le corresponde invalida la línea entera en donde se encuentran el resto de celdas del array. Esta acción inicia el proceso de sincronización entre las caches del sistema provocando una disminución del rendimiento.

int cores = Environment.ProcessorCount;
int[] counts = new int[cores];
Parallel.For(0, cores, i =>
{
    for (int j = 0; j < 50; j++)
    {
        for (int k = 0; k < 10000000; k++)
        {
            counts[i] = counts[i] + 3;
        }
    }
});

Una forma sencilla de evitar el false sharing es usar variables locales para realizar las escrituras dentro de la ejecución de cada hilo, reduciendo así el número de escrituras en las variables globales.

A continuación podemos ver una optimización del código anterior en donde se van guardando los resultados parciales en una variable local hasta terminar el proceso que el resultado se guarda en la variable global.

int cores = Environment.ProcessorCount;
int[] counts = new int[cores];
Parallel.For(0, cores, i =>
{
    int localCount = 0;
    for (int j = 0; j < 50; j++)
    {
        for (int k = 0; k < 10000000; k++)
        {
            localCount = localCount + 3;
        }
    }
    counts[i] = localCount;
});

Aquí podemos ver los tiempos de ejecución de ambos códigos:

tablaFalseSharing

Como podemos ver, reduciendo el número de escrituras en variables globales al mínimo posible conseguimos una mejora del rendimiento del 95%. Esto es debido a que se reduce el número de invaliaciones de líneas de cache y por lo tanto disminuye el tiempo que gastan los procesadores en la sincronización de sus cachés.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s