Download - Apuntes Procesamiento Vectorial
PROCESAMIENTO VECTORIAL
ÍNDICE
INTRODUCCIÓN ................................................................................. 3
1. PROCESAMIENTO VECTORIAL ................................................. 5
1. TAXONOMÍA DE FLYNN...................................................... 7
2. SEGMENTACIÓN Y PROCESADORES VECTORIALES ............ 9
3. ARQUITECTURA DE LOS PROCESADORES VECTORIALES 11
4. RENDIMIENTO DE LOS PROCESADORES VECTORIALES ... 12
5. COMPILADORES DE LOS PROCESADORES VECTORIALES 15
6. EJEMPLOS DE COMPUTADORES VECTORIALES ................. 16
CONCLUSIONES............................................................................... 19
BIBLIOGRAFÍA .................................................................................. 20
ANEXOS ............................................................................................ 22
3
INTRODUCCIÓN
Día a día las computadoras están más involucradas en las actividades
humanas, están presentes en todas nuestras tareas cotidianas, permitiendo
ejecutarlas de una manera más rápida y eficiente.
De la misma forma, muchas actividades industriales, económicas,
militares y de investigación, requieren procesar grandes volúmenes de datos
a través de numerosos y complejos cálculos, y obtener resultados en lapsos
de tiempo razonables. El análisis estructural, predicción meteorológica,
investigaciones nucleares y de alta energía, diagnóstico médico,
simulaciones en aerodinámica o hidrodinámica, inteligencia artificial y
sistemas expertos, navegación y detección, defensa, ingeniería química y
genética, son algunos campos que se puede mencionar, en los que la
necesidad de manejar volúmenes de datos cada vez mayores, de manera
rápida y precisa, puede sobrepasar las capacidades de los computadores
disponibles. Esta necesidad es el principal impulsor de computadores cada
vez más poderosos y de mayores prestaciones.
Una gran cantidad de los problemas planteados en áreas como las
mencionados anteriormente, se pueden expresar mediante la utilización de
modelos que son expresados en matrices y vectores. Esto hace posible
utilizar al máximo un tipo de arquitectura específica para esta clase de datos,
y es la de los procesadores vectoriales.
Los primeros procesadores vectoriales aparecieron en la década de
los 70. Su evolución tuvo un mayor auge en los siguientes veinte años,
declinando tras las mejoras en los procesadores escalares, particularmente
en los microprocesadores.
4
Actualmente la mayoría de las CPU implementan arquitecturas que
tienen instrucciones características de algunos procesadores vectoriales.
También muchas consolas de videojuegos y el hardware para gráficos de
computadora actuales, utilizan procesamiento vectorial en sus arquitecturas.
El amplio espectro de uso, la importancia de su desarrollo y el ser la
base de la mayoría de las supercomputadoras, hacen su estudio un tópico
muy interesante para el estudiante de la asignatura Arquitectura del
Computador, de la Universidad Nacional Abierta.
5
1. PROCESAMIENTO VECTORIAL
Un procesador vectorial es, básicamente, una unidad central de
proceso (CPU) que tiene la capacidad de implementar un conjunto de
instrucciones que operan en arreglos unidimensionales de datos. Estos
arreglos son llamados vectores.
Esto lo convierte en un diseño de CPU que puede ejecutar
operaciones matemáticas sobre múltiples datos de forma simultánea. Así, el
término Procesamiento Vectorial toma muchos significados. En general,
“Procesos que operan sobre muchas señales a la vez, las cuales están
combinadas como un vector” (Vega, p. 3).
Figura 1. Procesamiento Vectorial de una sola señal. Fuente: Vega, 2011.
6
Si las muestras se derivan de una misma señal, tenemos la situación
de procesamiento de bloques o segmentos que se ilustra en la figura anterior
(Figura 1).
En un enfoque más general, el Procesamiento Vectorial consiste en
operar sobre múltiples muestras provenientes de varias señales que llegan
simultáneamente. Este proceso puede producirse en dos formas:
Señales en modo flujo: En este esquema se ejecutan todos los cálculos
relacionados con una muestra de entrada, y la muestra es descartada
antes de que llegue la siguiente muestra de datos (Figura 2).
Señales en modo bloque: En este tipo de procesamiento, se almacena en
memoria un bloque de muestras, luego son procesadas y se produce la
muestra de salida (Figura 3).
Figura 2. Procesamiento Vectorial en Modo Flujo. Fuente: Vega, 2011.
7
Figura 3. Procesamiento Vectorial en Modo Bloque. Fuente: Vega, 2011.
1. TAXONOMÍA DE FLYNN
Michael Flynn propuso en 1972, una clasificación compuesta por
cuatro (4) categorías, establecidas en función de la multiplicidad de los flujos
de datos y de instrucciones que se conjugan en la ejecución de estos
sistemas, las cuales son:
SISD (Simple flujo de inst.-simple flujo de datos): Incluye a todos los
sistemas de un solo CPU. Las ejecuciones se ejecutan de forma
secuencial pero puede haber segmentación. Ejemplos de esta categoría
son los computadores viejos IBM 370 e IBM 7090, el VAX y el Intel 8086.
SIMD (Simple flujo inst.-multiples flujos de datos): Comprende una gran
diversidad de procesadores paralelos que ejecutan una misma instrucción
sobre un conjunto de datos al unísono o solapadamente.
MISD (Múltiples flujos inst.-simple flujo de datos): Este modelo propone la
existencia de n unidades procesadoras; cada una recibe distintas
8
instrucciones que operan sobre el mismo flujo de datos. La salida de un
procesador pasa a ser la entrada del siguiente.
MIMD (Múltiples flujos inst-multiples flujos de datos): Incluye a todos los
sistemas paralelos que constan de múltiples procesadores autónomos
trabajando cooperativa y coordinadamente en la solución de uno o más
problemas de forma simultánea.
Los procesadores vectoriales representan una tendencia hacia el
aprovechamiento del paralelismo de datos presente en las aplicaciones y por
lo tanto implementan un paralelismo SIMD (Single Instruction, Multiple Data).
Esta técnica permite procesar un conjunto de datos con una sola instrucción,
de manera síncrona.
Las CPUs vectoriales consiguen esto usando áreas de memoria
especialmente diseñadas para este propósito, denominadas registros
vectoriales. Los registros vectoriales pueden ser rellenados por las
instrucciones vectoriales, devolviendo resultados mucho más rápidos que los
tradicionales procesadores escalares. Las aplicaciones de cálculo científico y
aquellas de tratamiento de imagen, son las más beneficiadas por esta
arquitectura.
Según Lanchares (s/f), desde el punto de vista arquitectónico la
utilización de operaciones vectoriales presenta las siguientes propiedades:
El cálculo sobre cada componente es independiente del cálculo de los demás.
Una instrucción vectorial puede desplazar a un bucle de operaciones escalares sobre los elementos de un vector. De esta manera se reduce el número de instrucciones que es necesario buscar en memoria para ejecutar un cálculo.
Cuando los elementos de un vector están en posiciones consecutivas de la memoria, el acceso a los elementos de este vector es secuencial y conocido. Esto facilita la utilización de memorias entrelazadas para acelerar los procesos (p. 28).
9
De lo anterior se desprende en primer término, que al ser cada
resultado independiente de los demás, el procesador puede efectuar los
cálculos simultáneamente; en segundo lugar hay una economía en cantidad
de instrucciones al reemplazar operaciones escalares con operaciones
vectoriales y por último, al realizar los accesos secuencialmente a las
instrucciones vectoriales contenidas en los registros vectoriales, aumenta la
eficiencia; por todas estas razones la velocidad del procesamiento se
incrementa.
En la búsqueda del mejoramiento de las prestaciones
computacionales, se han implementado muchas técnicas y alcanzado
mejoras importantes desde la aparición del primer computador hasta
nuestros días, algunas de estas técnicas están relacionadas con la
tecnología y otras con la arquitectura; en el camino recorrido, el mayor
beneficio se obtiene cuando interaccionan la tecnología y la arquitectura,
especialmente la reducción en la escala de integración, que ha conducido a
dispositivos más rápidos integrados en superficies cada vez más pequeñas.
2. SEGMENTACIÓN Y PROCESADORES VECTORIALES
En la ejecución de aplicaciones, cuando existen instrucciones que
pueden realizarse en cualquier orden sin que se modifique el resultado final,
éstas se podrían hacer al mismo tiempo, y se estaría en presencia del
proceso denominado paralelismo a nivel de instrucción. Uno de los métodos
para obtener este paralelismo es la segmentación.
La segmentación consiste en descomponer la ejecución de cada
instrucción en varias etapas para poder empezar a procesar una instrucción
diferente en cada una de ellas y trabajar con varias simultáneamente. Cada
una de estas etapas de la instrucción usa en exclusiva un hardware
10
determinado del procesador, de tal forma que la ejecución de cada una de
las etapas en principio no interfiere en la ejecución del resto.
A nivel de ejecución de instrucciones o lenguaje de máquina, la
técnica de segmentación permite la ejecución de varias instrucciones
concurrentemente, esto da lugar a los procesadores escalares segmentados.
En el caso de que el procesador no pudiese ejecutar las instrucciones
en etapas segmentadas, la ejecución de la siguiente instrucción sólo se
podría llevar a cabo tras la finalización de la primera. El control podría
implementarse en este caso a través del uso de semáforos, de manera que
los procesos no produzcan errores. Por el contrario, en un procesador
segmentado, respetando excepciones de dependencias de datos o uso de
unidades funcionales, la siguiente instrucción podría iniciar su ejecución tras
acabar la primera etapa de la instrucción actual.
El problema de la dependencia de datos y de control en la
segmentación, ha sido resuelto mediante la aplicación de varias técnicas,
como la anticipación y la planificación de operaciones para el caso de
dependencia de datos, y la predicción o el retardo de saltos para el caso de
dependencias de control.
La segmentación mejora el rendimiento de una máquina sin alterar el
tiempo básico de ciclo, lo cual indica que esta técnica arquitectónica es una
buena alternativa si el número de compuertas lógicas que se pueden integrar
aumenta más rápidamente que la velocidad de las puertas lógicas.
Aunque a finales de los años ochenta casi todas las arquitecturas
incluían segmentación, el primer computador segmentado fue el IBM 7030,
que apareció a finales de los años 50, en 1964 surgió el CDC 6600
(considerado el primer supercomputador) el primero que tuvo en cuenta la
11
relación entre repertorio de instrucciones y la segmentación, posteriormente,
apareció el IBM 360/9, que introdujo muchas de las técnicas utilizadas hoy
en día para aumentar el rendimiento de la segmentación.
3. ARQUITECTURA DE LOS PROCESADORES VECTORIALES
Las máquinas vectoriales permiten la ejecución de un ciclo completo
de instrucciones mediante la realización de iteraciones realizadas sobre cada
componente de un vector. Para aprovechar al máximo esta capacidad de
trabajar con vectores, es necesario un tipo específico de arquitectura que
permitan implementar las instrucciones vectoriales.
Al respecto, Hennessy y Patterson (2002) acotan que:
… las operaciones vectoriales pueden hacerse más rápidas que una secuencia de operaciones escalares sobre el mismo número de elementos de datos, y los diseñadores están motivados para incluir unidades vectoriales si el conjunto de las aplicaciones las puede usar frecuentemente (p.p. 378-379).
Los mismos autores acotan que los procesadores vectoriales
segmentan las operaciones sobre los elementos de un vector, y que esto no
incluye sólo las operaciones aritméticas, sino también los accesos a memoria
y el cálculo de direcciones efectivas.
Una máquina vectorial comúnmente consta de una unidad escalar
segmentada y una unidad vectorial. Hay dos tipos de principales de
arquitectura de maquinas vectoriales:
1. Con registros vectoriales. En estas, casi todas las operaciones
vectoriales, funcionan con vectores almacenados en los registros, con
instrucciones para cargarlos y/o almacenarlos desde o hacia la
memoria.
12
Ventajas: Si se reutilizan los operandos vectoriales, sólo se sufre una
vez el acceso a memoria. Los resultados vectoriales temporales no
sufren el acceso a memoria.
Inconvenientes: El tamaño de los registros vectoriales limita el tamaño
de los operandos vectoriales.
2. Memoria-memoria. En éstas todas las operaciones vectoriales son de
memoria a memoria.
Ventajas: Tamaño de los operandos vectoriales ilimitado.
Inconvenientes: Todas las instrucciones sufren el acceso a memoria.
4. RENDIMIENTO DE LOS PROCESADORES VECTORIALES
Las razones para evaluar el rendimiento de un computador son muy
diversas: para los diseñadores porque son herramientas o medidas que
permiten escoger la más adecuada entre múltiples alternativas de diseño;
para los fabricantes y departamento de ventas, porque tienen la necesidad
de comparar y diferenciar su producto del de la competencia, para ofrecer
sus bondades; y para la demanda, porque deben poseer una herramienta
que les apoye en la decisión que van a tomar al adquirir un equipo.
La medida del rendimiento de mayor interés en un computador es el
tiempo. Usualmente, se toma como la medida más adecuada al tiempo de
ejecución t de un programa por parte del CPU. En el mismo contexto, se
necesita establecer métricas que permitan estandarizar las medidas
escogidas. Las métricas constituyen un criterio para evaluar el desempeño
de un sistema computacional; así mediante la medida de una métrica se
puede compara dos sistemas distintos.
13
Las métricas mas usadas, son: Latencia o tiempo de respuesta,
Productividad, Disponibilidad y Utilización.
La latencia es una medida del tiempo (t) que el sistema tarda en
producir resultados. Se puede utilizar en distintas medidas según el contexto
en que se aplique, como por ejemplo, en la evaluación del desempeño del
CPU, se puede ver como los ciclos de reloj requeridos para completar un
programa, el ancho del pulso o período del reloj del CPU y el tiempo total de
ejecución de un programa; si por el contrario, se trata de la evaluación del
rendimiento de la memoria, se refiere entonces, al tiempo de acceso a una
celda.
La productividad o throughput (), se refiere a la cantidad de trabajos
o tareas completadas por unidad de tiempo, y depende de diferentes factores
externos y circunstanciales (acceso a disco, algoritmo de scheduling, entre
otros) y sirve para medir un rendimiento más global del sistema.
La disponibilidad (d) mide cuánto tiempo un sistema se mantiene en
operación normal del tiempo total requerido.
La utilización (), según Díaz (2012, p. 3) es el fragmento de tiempo
que un componente del sistema está activo para su utilización o contribuye al
trabajo. La utilización se mide como porcentaje, o como razón entre 0 y 1. La
productividad máxima de un sistema se alcanza cuando el componente más
ocupado logra una utilización de 1 ó 100%.
El mismo autor, expone que se han propuesto un conjunto de métricas
con la intención de estandarizar las medidas de rendimiento con la finalidad
de comparar dos computadores cualesquiera, entre las métricas más
populares se encuentran:
14
Velocidad o frecuencia de ejecución de instrucciones: es una métrica
del tipo productividad que frecuentemente se expresa en millones de
instrucciones por segundo o MIPS, se define como la cantidad total de
instrucciones ejecutadas sobre el tiempo total de ejecución. Esto
indica que a mayor MIPS más rápidas son las máquinas. Sui principal
desventaja radica en que debe ser aplicado en máquinas similares.
MIPS Relativos: se trata de comparar los MIPS de una máquina con
los de una máquina de referencia, mediante la aplicación de un
programa en especial, así se intentaba resolver el problema de
aplicación solo en máquinas similares, sin embargo, este método
presentaba la desventaja adicional de encontrar la máquina de
referencia adecuada.
MFLOPS: En informática, las operaciones de coma flotante por
segundo, FLOPS (floating point operations per second), son una
medida del rendimiento de una computadora, especialmente en
cálculos científicos que requieren un gran uso de operaciones de
coma flotante. Los MFLOPS son más consistentes que los MIPS por
cuanto la cantidad de operaciones no cambia de máquina a máquina.
Como desventaja de esta métrica, los conjuntos de operaciones en
punto flotante disponibles de máquina a máquina no son estándares y
por tanto algunas operaciones se deben implementar en función de
otras, y además, algunas operaciones en punto flotante son de rápida
ejecución y otras muy lentas.
MFLOPS Normalizados. Según Díaz (2012), este método concede
pesos relativos a cada tipo de operación en punto flotante y permite
además considerar las operaciones enteras. De esta manera, como
las operaciones complejas tienen pesos mayores, se normaliza la
diferencia de velocidades, haciendo la comparación mas adecuada.
15
En el caso de los procesadores vectoriales, Maestro (2012) indica que
las medidas de rendimiento vectorial son:
R: Tasa de MFLOPS considerando vectores de longitud infinita.
N1/2: Longitud de vector necesaria para conseguir un rendimiento igual a
la mitad de R.
Nv: Longitud de vector necesaria para que el modo de operación vectorial
produzca un mejor rendimiento que el modo escalar
5. COMPILADORES DE LOS PROCESADORES VECTORIALES
El objetivo de un compilador es la traducción eficiente de un lenguaje
de alto nivel al lenguaje máquina, representando con precisión al primero. El
proceso de compilación debe realizar una serie de fases fácilmente
identificables, a saber:
Fase de precompilación o preprocesamiento, donde se realiza cierta
manipulación textual sencilla del código fuente. El paso de
preprocesamiento puede procesar o incluir archivos, así como realizar
substituciones sencillas de cadenas de texto a lo largo del código.
La fase de análisis lexicográfico, es la que descompone las sentencias de
código fuente entrantes en cadenas de caracteres (tokens) tales como
variables, constantes, comentarios o elementos del lenguaje.
La fase de análisis sintáctico, es la encargada de comprobar la sintaxis de
la entrada, y el compilador traduce el programa entrante a un lenguaje
intermedio que está listo para su optimización.
Fase de optimización, donde se realizan una o más pasadas de
optimización al lenguaje intermedio.
16
Fase de generación de código objeto, es la última etapa, en la que el
compilador traduce el lenguaje intermedio a código ensamblador,
tomando en consideración los detalles arquitectónicos particulares del
procesador que se esté utilizando.
Un compilador con vectorización analiza si las instrucciones situadas
dentro de los bucles pueden ser ejecutadas en paralelo y genera código
objeto con instrucciones vectoriales. Sin embargo, cuando se vectoriza un
código surgen dificultades relacionadas con dependencia de datos,
indexación indirectas e instrucciones de control, las cuales sólo pueden ser
resueltas en la ejecución.
La eficacia de las técnicas de vectorización depende de dos variables:
La primera es la estructura del programa, es decir, de los algoritmos
escogidos y la forma de codificación; y la segunda es la capacidad del
compilador. Por ello un buen compilador para máquinas vectoriales deberá
vectorizar bucles, generar código de seccionamiento y asignar registros
vectoriales.
La disponibilidad de compiladores para la extracción automática del
paralelismo que aprovecha el procesador vectorial ha sido decisiva en la
extensión de las arquitecturas vectoriales.
6. EJEMPLOS DE COMPUTADORES VECTORIALES
La evolución de los computadores dio un salto impresionante con la
llegada de los computadores vectoriales. El CDC Star 100 (1972) puede
considerarse como el primer computador vectorial, junto con el ASC de
Texas Instruments.
17
En cuanto a procesadores vectoriales paralelos (PVP), el primer
computador aparece en 1982, el CRAY X-MP con dos procesadores
vectoriales (en 1984 se amplia a 4 procesadores), con el que se diseña un
sistema de acceso a memoria que proporciona un ancho de banda
suficientemente elevado para utilizar varios procesadores.
Posteriormente nacen el CRAY-2 con 4 procesadores y una velocidad
pico de 2 GFLOPS y el CRAY Y-MP (1988) con 8 procesadores. El ETA-10
de CDC tenía 8 procesadores vectoriales con memoria compartida y
memoria locales para cada procesador (Ver Cuadro 1).
Los sistemas PVP fueron usados satisfactoriamente durante la década
de los 80 y 90 para optimizar los procesos de fabricación y resolver
problemas de ingeniería e investigación.
Hasta principios de los 90, cuando las arquitecturas de tipo
multiprocesador masivamente paralelos (MPP) alcanzaron la madurez
necesaria para igualar o superar a los multiprocesadores vectoriales, el
término supercomputador era prácticamente sinónimo de procesador
vectorial.
Los supercomputadores con procesadores vectoriales dominaron la
década de los 80 y principios de los 90. A partir de entonces, gracias al
incremento de las prestaciones y del diseño de las CPUs escalares y la
tendencia hacia el paralelismo masivo gracias a la memoria distribuida, el
mercado de los procesadores vectoriales fue perdiendo terreno.
Últimamente están tomando un nuevo auge los procesadores
vectoriales; ejemplo de esto es el procesador Cell de siete (7) núcleos
diseñado por de IBM y Toshiba, incluido en la PlayStation 3. Las empresas
18
Intel y AMD, también han incluido los procesadores vectoriales en su
producción (Intel MMX, AMD 3DNow, Intel Core i3, entre otros.)
Cuadro Nº 1.Ejemplos de computadores Vectoriales. (Maestro, 2011)
19
CONCLUSIONES
Las máquinas vectoriales se caracterizan por proporcionar
operaciones de muy alto nivel que trabajan sobre vectores. La mayoría de los
supercomputadores están diseñados para realizar computaciones vectoriales
o matriciales de gran escala en múltiples áreas de interés científico.
En sus inicios, debido a sus altos costos, el uso de computadores
vectoriales estaba restringido a aplicaciones científicas especificas que
trabajan con grandes colecciones de datos, tales como las señales de ecos
sísmicos producidas a consecuencia de la emisión de una onda sónica de
choque contra el terreno (en 1979 se procesaron 1015 bits de datos sísmicos
en los Estados Unidos), el procesamiento de señales de radar y sonar para
la detección de blancos en el espacio y bajo el agua, la detección remota
para la exploración de recursos terrestres, en los experimentos
computacionales de túneles de viento, en las predicciones meteorológicas y
en muchas aplicaciones de tiempo real. Sin embargo, La utilización de
procesadores vectoriales cada día tiende a ser menos onerosa que en el
pasado, ya que los costos de producción han disminuido en relación con los
procesadores matriciales.
La independencia de cálculo de cada elemento del resultado y el
volumen de trabajo que puede ser realizado con cada instrucción vectorial,
sí como la reducción de los riesgos de control en la ejecución de los
programas, son ventajas considerables que motivan a los diseñadores a usar
cada vez mas esta arquitectura.
20
BIBLIOGRAFÍA
Bernal, Luis. (s/f). Arquitectura de Computadores. [Documento en línea].
Disponible en: http://www.luisbernal.es/descargas/k/INFarqcom.pdf
Díaz Chow, José. (2012). Paralelismo y Arquitecturas Avanzadas. [Documento en línea].
Disponible en: http://www.snip.gob.ni/xdc/amc3/Folleto.pdf
Figueira, Carlos. (1996). Arquitecturas Paralelas. [Documento en línea]. Disponible en:
http://ldc.usb.ve/~figueira/Cursos/ci6842/ArqParalelas.pdf
Hennessy, J. y D. Patterson. (2002). Arquitectura de Computadores. Un Enfoque
Cuantitativo. McGraw-Hill. Madrid, España.
Lanchares, Juan. (s/f). Apuntes de Estructura de Computadores.
[Documento en línea]. Disponible en: http://www.dacya.ucm.es/lanchares/
documentos/2.9.5%20Apuntes%20de%20Estructura%20de%20Comp
utadores.pdf
Maestro, Juan A. (2011). Procesadores Vectoriales. [Documento en línea].
Disponible en: http://www.nebrija.es/~jmaestro/AT5118/Vectorial.pdf
Universidad de Valladolid. Departamento de Informática. Procesadores
Vectoriales. [Documento en línea]. Disponible en:
http://www.infor.uva.es/~bastida/Arquitecturas%20Avanzadas/Vectoriales.pdf
Universidad del Rey Juan Carlos. División de Arquitectura de Computadores.
Estructura y tecnología de Computadores III. Capítulo 7. [Documento
en línea]. Disponible en: http://dac.escet.urjc.es/~lrincon/uned/etc3/Etc3-07.PDF
21
Vega, Javier. (s/f). Procesamiento Vectorial. [Documento en línea].
Disponible en: http://cursos.itchihuahua.edu.mx/file.php/548/
PROCESAMIENTO_VECTORIAL.pdf
ANEXOS