Thursday, 29 January 2009

Programación paralela y Processor Affinity. Nunca subestimes el Scheduler de Windows Vista

 

El gran Maligno ha subido mi post sobre Parallel Computing and Processor Affinity  al blog www.windowstecnico.com, más concretamente aqui. Como en ese blog traducen todos los posts, Matias Cordero ha sido tan amable de traducir el mío al Español, así que lo incluyo también aqui por si alguien prefiere leerlo en Castellano.

Traducción por: Matías Cordero

Translated by: Matías Cordero (you can read the english version here).

Todo el mundo sabe que la paralelización es una tarea importante pero dura, y parece que no va a ser posible incrementar mucho mas las velocidades de reloj de las CPUs. El futuro es multicore! Así que toca ponerse con System.Threading ya mismo.

 

Determinar el balanceo apropiado

Cuando identificamos una tarea paralelizable, siempre es complicado encontrar el balanceo apropiado para la paralelización. ¿Es mejor abrir mas hilos o es mejor darle mas trabajo a cada hilo? La respuesta a esta pregunta depende, por supuesto, de muchas cosas, y sobre todo en la naturaleza de la tarea que gestionará cada hilo.

Es importante averiguar la cantidad de tiempo que la tarea va a estar “ociosa” en cada hilo. Si es una tarea intensiva, entonces es mejor iniciar menos hilos con mas trabajo en cada uno. Si es al contrario (una tarea que tiene muchos “parones” esperando por algo –IO, gráficos, lo que sea-), entonces es mejor abrir muchos hilos con poco trabajo, porque se distribuirán entre los núcleos físicos de la maquina cuando uno este “parado”. Por supuesto, nunca hay que abrir menos hilos que los cores físicos de la máquina.

¿Cuál es el objetivo? El mismo que en los hoteles… 100% de ocupación.

Una manera fácil de determinar la naturaleza de nuestra tarea es dejarla correr en una única CPU, y mirar el grafico de uso de la CPU del Administrador de Tareas. Esto nos dará una idea de el uso de CPU que ha realizado el proceso. Os preguntaréis ahora como forzamos a nuestra aplicación para que se ejecute en una CPU específica. La respuesta es Afinidad del Procesador o Processor Affinity (ver abajo).

 

Perder, o no perder el control. Esa es la cuestión…

Cuando comienzas por primera vez a pelearte con la paralelización, la primera idea es separar los procesos por las CPUs tu mismo. ¿Por qué no? Si tienes 10.000 operaciones, abre cuatro hilos con 25.000 operaciones cada uno. El primero para la CPU0, el segundo para la CPU1, y así sucesivamente… Yo me siento muy cómodo con esta idea. Dicho y hecho, y todo bajo control, ¿no? Bueno, no siempre es tan sencillo.

En un mundo ideal, una tarea simple, que no va a ser paralelizada más y que vive solita (no con las docenas de vecinos que un proceso tiene en un SO moderno), se gestiona mejor con una sola CPU, porque esto incrementa los aciertos de cache y elimina el consumo de la infraestructura de cambio entre hilos. Pero en la vida real, los procesos son interrumpidos por las operaciones del sistema, IO, otros procesos y muchas otras cosas. Una maquina multi-núcleo es perfecta para manejar todas esas interrupciones, porque puede repartirlas por los núcleos existentes, pero si comenzamos a fijar nuestras aplicaciones a CPUs específicas, la capacidad del sistema para evitar bloqueos y esperas se reduce considerablemente.

Como explica este gran artículo, la mayoría de las veces, es mucho mejor delegar en el Sistema Operativo para que pueda poner cada hilo donde el quiera. De todas maneras, veremos algunos resultados que avalan esta decisión mas tarde.

Processor Affinity de un proceso

En Windows, podemos forzar un proceso para que se ejecute en una CPU específica simplemente utilizando el Administrador de Tareas (botón derecho sobre el proceso y seleccionar “Establecer Afinidad”) o programáticamente utilizando el espacio de nombres System.Diagnostics. La siguiente línea cambiará la afinidad del proceso actual a la CPU1:

System.Diagnostics.Process.GetCurrentProcess().ProcessorAffinity = (System.IntPtr)1;

La propiedad ProcessorAffinity es una máscara de bits variable. Los valores son:

 

Valor

Procesadores permitidos

0 (0000)

No permitido (significa no utilizar procesadores)

1 (0001)

Procesador 1

2 (0010)

Procesador 2

3 (0011)

Procesadores 1 y 2

4 (0100)

Procesador 3

5 (0101)

Procesadores 3 y 1

6 (0110)

Procesadores 3 y 2

7 (0111)

Procesadores 3, 2 y 1

8 (1000)

Procesador 4

 

y así sucesivamente…

Tened en cuenta que esto cambiará la afinidad del proceso actual (la aplicación completa), no del hilo actual. Cualquier hilo que se haya abierto desde este proceso heredará la misma afinidad.

Processor Affinity de un hilo.

El primer requisito para controlar como se distribuyen tus hilos entre las CPUs es ser capaz de establecer la afinidad con el procesador de un hilo (no del proceso). Hay un post interesante sobre este tema aquí, donde Tamir Khason lo explica todo. Para cambiar la afinidad de un hilo debemos utilizar la clase System.Diagnostics.ProcessThread (propiedad ProcessAffinity). El problema viene cuando tratamos de averiguar que hilo es el que estamos buscando, in la lista de los hilos del proceso actual.

1.- Primera aproximación - Obsoleta

Conseguimos la instancia del ProcessThread con el siguiente código:

ProcessThread t = Process.GetCurrentProcess().Threads.OfType<ProcessThread>().Single(pt => pt.Id == AppDomain.GetCurrentThreadId());
t.ProcessorAffinity = (IntPtr)(int)cpuID;

El problema de esta aproximación es que el método GetCurrentThreadId está obsoleto, así que mejor no utilizarlo.

2.- Segunda aproximación – No válida

Podéis estar tentados de utilizar la propiedad ManagedThreadID para buscar dentro de la colección Threads del proceso. No lo hagáis. ProcessThread.ID no tiene nada que ver con la propiedad ManagedThreadID, representan cosas diferentes. Un tipo dice aquí que ManagedThreadID es de hecho el desplazamiento dentro de la colección ProcessThread, pero no he investigado mucho más, y no os aconsejo utilizarlo hasta que no verifiquéis esta información.

3.- Tercera aproximación – Válida, pero nativa (no manejada)

La tercer aproximación hace un “dllimport” del “kernel32.dll” y utiliza algunas de sus funciones. Este método está probado y funciona correctamente:

[DllImport("kernel32.dll")] 
static extern IntPtr GetCurrentThread();

[DllImport("kernel32.dll")] 
static extern IntPtr SetThreadAffinityMask(IntPtr hThread, IntPtr dwThreadAffinityMask);

SetThreadAffinityMask(GetCurrentThread(), new IntPtr(1 << (int)cpuID));

Una nota curiosa:

Si estáis programando para la XBox360 con XNA Game Studio 3.0, tenéis un método Thread.SetProcessorAffinity listo para utilizar, sin toda la morralla de arriba. Esto se debe a que la XBox necesita especialmente aprovecharse de sus núcleos para ofrecer un rendimiento decente. No se si la presencia de este método se debe a que el rendimiento del Scheduler de la XBox es peor que el de Vista… puede ser. De todas formas podéis leer mas aquí.

 

El Test

Tarea: Generar tres tablas 2D con resultados de un test geométrico en una escena 3D, incluyendo 975.065 pruebas de colisión (ray-mesh) cada una.

Hardware: Dell XPS 630 QuadCore

Software de monitorización: Process Explorer

PARTE 1 (multihilo deshabilitado). Impacto de la afinidad del procesador

Test 1:

  • Número de hilos: 1 (hilo principal)
  • Afinidad con el procesador: CPU 1
  • Tiempo total: 2 min 57.11 seg

clip_image002

Con la afinidad con el procesador asociado a la CPU 1, todo el trabajo es obviamente gestionado por esta CPU. Los dos picos que se pueden apreciar en el gráfico se deben a operaciones de IO (guardar en disco) y marcan claramente la generación de cada tabla de datos. En esta prueba podemos observar claramente que nuestra tarea es muy intensiva y constante, porque mantiene el procesador al 100% de uso la mayoría del tiempo.

Test 2:

  • Número de hilos: 1 (hilo principal)
  • Afinidad con el procesador: Ninguna (cualquier procesador)
  • Tiempo total: 2 min 29.45 seg

clip_image004

La mayoría del trabajo se ha gestionado por la CPU2 pero el resto de los núcleos también han trabajado en el proceso (comprobado en Process Explorer que todas las líneas verdes pertenecen al proceso que se está midiendo). Está claro que forzar el proceso a trabajar únicamente en la CPU1 solamente introdujo bloqueos y periodos de espera, probablemente debido a interrupciones que venían de otros programas que también necesitaban la CPU1.

Ganador de la parte 1 ………  Windows Scheduler !

PARTE 2 (multihilo habilitado 1)

Test 1:

  • Número de hilos: 2 (hilo principal + 1 hilo de cálculo)
  • Afinidad con el procesador:
    • Hilo principal: Cualquiera
    • Hilo de cálculo: CPU 1
  • Tiempo total: 2 min 18.14 seg

clip_image006

Los resultados que obtenemos aquí son muy lógicos. El cambio principal en esta prueba es que estamos separando el cálculo de la actualización de la interfaz y el guardado en disco. Podéis apreciar los picos bajos en el primer gráfico y sus equivalentes en los núcleos 2 y 3 (donde se ejecuta la operación de guardado). Es muy interesante notar que separar las operaciones de salvado a núcleos diferentes no ahorra mucho tiempo, porque esperamos a que se completen antes de continuar con la siguiente tabla de datos. Por este motivo los picos bajos en el primer gráfico son mucho mas notorios. Hemos movido el procesamiento de un núcleo a otro, pero no hemos paralelizado nada.

De todas maneras notamos una leve mejora en el rendimiento, mayormente porque la actualización de la interfaz (que incluye manipulación de mapas de bits) se hace en los núcleos 2 y 3.

Test 2:

  • Número de hilos: 2 (hilo principal + 1 hilo de cálculo)
  • Afinidad con el procesador: Ninguna
  • Tiempo total: 2 min 14.86 seg

clip_image008

Esta vez podemos apreciar de nuevo que el trabajo se distribuye en todos los núcleos, con una más que remarcable presencia de la CPU2. De nuevo el scheduler de Windows gana la carrera.

Ganador de la parte 2 ………  Windows Scheduler !

PARTE 3 (multihilo habilitado 2)

Test 1:

  • Número de hilos: 3 (hilo principal + 2 hilos de cálculo)
  • Afinidad con el procesador:
    • Hilo principal: Cualquiera
    • Hilos de cálculo: CPUs 1 y 2
  • Tiempo total: 1 min 18.66 seg

clip_image010

Empezamos a ver una gran mejora en el rendimiento. El doble de poder computacional, casi el doble de rápido. Parece muy realista.

Test 2:

  • Número de hilos: 3 (hilo principal + 2 hilos de cálculo)
  • Afinidad con el procesador: Ninguna
  • Tiempo total: 1 min 16.59 seg

clip_image012

Otra victoria para el scheduler de Windows. obviamente cuando el tiempo total se acorta, las diferencias también lo hacen, pero el SO vuelve a ganar.

Ganador de la parte 3 ………  Windows Scheduler !

PARTE 4 (multihilo habilitado 3)

Test 1:

  • Número de hilos: 5 (hilo principal + 4 hilos de cálculo)
  • Afinidad con el procesador:
    • Hilo principal: Cualquiera
    • Hilos de cálculo: CPUs 1, 2, 3 y 4
  • Tiempo total: 41.76 seg

clip_image014

Ahora viene el gran aumento del rendimiento. Con 4 hilos de cálculo, el tiempo total se reduce a 41 segundos! Veamos  como se comporta el SO con 5 hilos.

Test 2:

  • Número de hilos: 5 (hilo principal + 4 hilos de cálculo)
  • Afinidad con el procesador: Ninguna
  • Tiempo total: 42.05 seg

clip_image016

Wow… Ha estado muy cerca! Esta vez el SO pierde.

Ganador de la parte 4 ………  Afinidad con el procesador! (estuvo cerca)

PARTE 5 (multihilo habilitado 4)

Test 1:

  • Número de hilos: 9 (hilo principal + 8 hilos de cálculo)
  • Afinidad con el procesador:
    • Hilo principal: Cualquiera
    • Hilos de cálculo 1..4: CPUs 1..4
    • Hilos de cálculo 5..8: CPUs 1..4
  • Tiempo total: 41.07 seg

clip_image018

Test 2:

  • Número de hilos: 9 (hilo principal + 8 hilos de cálculo)
  • Afinidad con el procesador: Ninguna
  • Tiempo total: 38.24 seg

clip_image020

Wow… ese es mi chico! 38 segundos !!!

De todas maneras, estos son resultados esperados. Si establecemos más hilos que núcleos físicos, es obvio que debemos hacer alguna programación de hilos. Forzando los hilos a trabajar en una CPU concreta simplemente reduce la paralelización. Como se puede ver no obtenemos beneficio alguno cuando usamos 8 hilos de cálculo  en lugar de 4 (con la afinidad habilitada). Por lo tanto queda claro que dejarle libertad a Windows en este caso, simplemente hacer su trabajo, es de lejos la mejor opción.

Ganador de la parte 5 ………  Windows Scheduler !

Resultados

clip_image021

Test

Vista Scheduler (seg)

Processor Affinity (seg)

Parte 1

149.45

177.11

Parte 2

134.86

138.14

Parte 3

76.59

78.66

Parte 4

42.05

41.76

Parte 5

38.24

41.07

 

A sí que ¿cuál es el número óptimo de hilos para mi tarea?

¿Continuará esta tendencia (cuantos mas hilos, mas rendimiento) para siempre? La respuesta es, obviamente, no.

En una tarea ideal, intensiva al 100% y constante, el número optimo de hilos sería el número de núcleos físicos, pero en la vida real, esa tarea tan intensiva es muy dificil de encontrar. La mayoría de los algoritmos de computación tienen tiempos de parada, esperando por una paginación de memoria, o similar. Así que, el número de hilos que te darán el mejor rendimiento dependerá de lo intensiva y constante que sea tu aplicación.

He medido algunos tiempos adicionales (para el scheduler del SO solamente):

    • 16 hilos –> 37.89 seg.
    • 18 hilos –> 37.44 seg.
    • 24 hilos –> 38.03 seg.

Así, para esta tarea parece que acaba en 18 hilos. Deberéis hacer vuestros propios tests para encontrar el número optimo de hilos de vuestros algoritmos. De cualquier modo, hemos probado que incluso en una tarea intensiva como esta, el número optimo de hilos, parece estar en torno a 18 para una máquina de cuatro núcleos, que significa 4 veces el número de núcleos fisicos!

 

Conclusiones

1.- El Windows Scheduler hace un GRAN trabajo (especialmente en vista). Bate una configuración manual en la mayoría de los casos, y en los que pierde, es por muy poco.

2.- Incluso si el SO fuera un poco peor en todos los casos, sería aconsejable utilizarlo, mayormente porque es automático y o tenemos que preocuparnos de la situación de los hilos.

3.- La afinidad con el procesador es uno de los mas importantes obstáculos en el paralelismo, así que utilizadlo sólo si lo necesitáis, no porque sois mas listos que Vista. En otras palabras: no reinventéis la rueda.  Confiad en el sistema operativo.

4.- Windows Vista Scheduler Rocks ! (esto no lo traduzco)

 

¿Para que se ha utilizado toda esta información?

Casi un millón de intersecciones de ray-mesh testeadas, y ¿a que se debe todo esto? La gente en España suele decir que si es blanco y viene en una botella, probablemente sea leche (nota del traductor: blanco y en botella).

Test masivos de intersecciones Ray-Mesh + Resultados almacenados como tabla 2D = Probablemente cálculos de luces.

Estos son los resultados, espero que os gusten.

clip_image022

Cuidaros!

No comments: