Vectorización

lunes, 13 diciembre 2010 @ 10:58 -0600

En 1966 un profesor de la Universidad de Stanford, Michael J. Flynn propuso una clasificación para la arquitectura de computadoras conocida como la Taxonomía de Flynn [1].

Esta clasificación está basada en el número concurrente de instrucciones y en los flujos de datos disponibles en la arquitectura:

	Single Instruction	Multiple Instruction
Single Data	SISD	MISD
Multiple Data	SIMD	MIMD

De manera general los ordenadores personales pueden considerarse como SISD: Single Instruction, Single Data. Estos procesadores solamente pueden hacer una operación sobre un valor a la vez.

Sin embargo, con la llegada del procesamiento multimedia, el mercado de los ordenadores personales comenzó a ejercer presión sobre los fabricantes de chips para proveer de hardware más potente capaz de reproducir audio y vídeo (actividad muy demandante de poder de cómputo), sin afectar la sensación de desempeño en las demás tareas.

Esta demanda significaba, en gran medida, dotar de procesamiento paralelo a los baratos procesadores de la computación personal, ya que para reproducir multimedia mientras se realizan otras tareas, la arquitectura SISD, por más velocidad de procesamiento que adquiriera, jamás lograría el objetivo.

La respuesta a esto, a mitad de la década de 1990, fue que las compañías de hardware introdujeron extensiones al conjunto de instrucciones nativas de sus procesadores. Estas extensiones son la implementación de la arquitectura SIMD dentro de sus CPUs SISD. Ejemplos de estas extensiones son la SSE [2] de Intel, la 3DNow! [3] de AMD y NEON en ARM [4].

En otras palabras, el advenimiento de la arquitectura SIMD en los ordenadores personales implicó la llegada de la computación paralela al público masivo.

Como su nombre lo indica, la arquitectura SIMD es la forma de paralelización más básica y simple que existe, en donde la misma operación se realiza en un conjunto de datos a la vez.

Supongamos que tenemos el siguiente pseudocódigo:

for (i = 0; i < N; i++) {
  a[i] = a[i] + b[i];
}

sobre los vectores

a = { 2, 4, 6, 8 };
b = { 1, 3, 5, 7 };

En la arquitectura SISD el número de operaciones a realizar serían cuatro:

    op(2) -> 3
    op(4) -> 7
    op(6) -> 11
    op(8) -> 15

No obstante, en la arquitectura SIMD solamente se realizaría una operación:

    vop(2,4,6,8) -> { 3, 7, 11, 15 }

La misma operación se realiza simultáneamente sobre todo el vector de datos, siendo, en este caso, cuatro veces más rápido la ejecución del algoritmo.

En computación paralela, a este tipo de paralelización se le conoce como vectorización, debido a que su ámbito de optimización es sobre operaciones vectoriales, y por ende, en matriciales.

El procesamiento de audio y vídeo se basa casi exclusivamente en operaciones matriciales, como la transformada discreta de Fourier [5], y es por esto que la extensiones SIMD en los procesadores de los ordenadores personales satisfacen las demandas de multimedia del mercado.

Como normalmente sucede, el hardware va varios pasos adelante de software, lo que provoca que los sistemas de cómputo en el mercado no explotan todas las capacidades del hardware disponible. Además que la mayoría de los programadores pocas veces van más allá de lo que sus compiladores y entornos de desarrollo les proveen.

En la actualidad, un área de investigación importante en el desarrollo de compiladores, es el uso automático de las extensiones SIMD, o también conocida como “vectorización automática”. De esta manera el programador no tendría que emplear una lógica distinta y una sintaxis especifica en su código; el compilador detectaría aquellas porciones de código secuencial susceptibles a vectorizar (vea, por ejemplo, el wiki sobre vectorización en GCC [6]).

Lamentablemente la vectorización automática no garantiza que el código sea 100% optimizado para las extensiones disponibles, sino únicamente se limita a garantizar que la dependencia y precisión de los datos no se corrompa. Si realmente deseamos sacarle todo el jugo a la vectorización, el programador deberá ensuciarse las manos con las instrucciones de bajo nivel (vea, por ejemplo, el conjunto de instrucciones de NEON para GCC [7]).

Pero al haber distintos conjuntos de instrucciones para los distintos procesadores que el mercado maneja, aprender y utilizar cada uno de ellos implica un impacto en el coste del desarrollo de software. Imaginen si tiene que escribir la misma lógica optimizada para cada CPU objetivo ¡qué tremenda tontería!

Una de las alternativas para solucionar este problema, sobre todo si las porciones de código a vectorizar son muy específicas y claramente identificadas, es ORC [8].

ORC es un compilador que, de manera diferente a lo acostumbrado, opera a través de una biblioteca de software. El lenguaje que este compilador procesa es un tipo de lenguaje ensamblador genérico que opera sobre arreglos de datos (nuestros vectores famosos).

Como indica Eric Raymond en su libro Art of the Unix Programming [9], una de las reglas de la programación es la “regla de la generación”: escribe programas que escriban programas [10], ORC es una herramienta para seguir este principio.

Nuestro programa generará, en tiempo de ejecución, el código en el ensamblador de ORC. Luego, utilizando la biblioteca de ORC, le indicamos que compile dicho código auto-generado ¡también en tiempo de ejecución! y finalmente lo ejecute.

De esta manera, nuestro código podrá funcionar de manera optimizada para todas las extensiones SIMD soportadas por ORC, aunque nosotros solamente hayamos aprendido el lenguaje genérico de ORC.

Varios elementos de GStreamer, por ejemplo, utilizan ORC para optimizar sus operaciones, como por ejemplo el re-escalado de vídeo y el re-muestreo de audio.

Grupo Linuxero del Bajío