PIPELINE
Muchos de los computadores antiguos y muchos de los minicomputadores
contemporáneos son monoprocesadores, lo cual no debe sorprendernos ya que es la
máquina más elemental para diseñar y construir.
Por otra parte, las computadoras digitales modernas de gran escala utilizan
frecuentemente el procesamiento simultáneo (concurrencia) en distintos puntos del sistema denominaremos a esta clase de computadoras Procesadores Paralelos.
Los computadores paralelos son sistemas de computadores consistentes de un
conjunto centralizado de procesadores que pueden procesar simultáneamente los datos
del programa.
El procesamiento paralelo se basa en la explotación de sucesos concurrentes
en el proceso de cómputo.
Como apuntamos en el Capítulo 1 la concurrencia implica paralelismo, simultaneidad y pipelining.
Sucesos Paralelos ocurren en múltiples recursos durante el mismo intervalo
de tiempo.
Sucesos Simultáneos ocurren en el mismo instante.
Sucesos Pipeline ocurren en lapsos superpuestos.
Se puede hablar de niveles de paralelismo, que caracterizamos de la siguiente
manera:
- Multiprogramación, Multiprocesamiento: Estas acciones se toman a nivel de
Programa o Trabajo.
- Tarea o Procedimientos: Acciones que se toman dentro de un mismo
programa, ejecutándose procesos independientes en forma simultánea.
- Interinstrucciones: Acciones a nivel de instrucción, o sea, dentro de mismo
proceso o tarea se pueden ejecutar instrucciones independientes en forma
simultánea.
- Intrainstrucciones: Acciones simultáneas que se pueden realizar para una
misma instrucción, por ejemplo vectorización de operaciones escalares dentro
de una instrucción compleja tipo DO, FOR, etc.
El paralelismo de un mayor nivel se obtiene por medio de algoritmos, los de
menor nivel con importante actividad del hardware.
Ultimamente ciertas técnicas del procesamiento distribuido son incorporadas a
arquitecturas centralizadas para conseguir mayor grado de paralelismo.
El paralelismo puede obtenerse de distintas maneras, a saber:
- Multicomputadoras: Computadoras independientes, muy a menudo una de ellas actúa como supervisor, que realizan una tarea común en una sola
ubicación (una configuración muy común, aunque ciertamente limitada, es la
minicomputadora como preprocesador de un computador mainframe).
- Multiprocesadores: Un conjunto de unidades de cómputo, cada una de las
cuales tiene sus propios conjuntos de instrucciones y datos, compartiendo una
misma memoria. Los computadores multiprocesadores consisten en un número
n mayor o igual a 2 de procesadores que operan simultáneamente sobre una
misma memoria, y están interconectados mediante canales que transmiten
comandos de control y datos. Están controlados por un único Sistema
Operativo.
- Redes de computadoras: Computadoras independientes conectadas
mediante un canal de manera tal que los recursos propios disponibles en un
punto de la red pueden estar disponibles para todos los miembros de la red.
- Procesador Pipeline: Un solo computador el cual puede realizar
simultáneamente operaciones de cálculos en determinadas secciones, con
diferentes estadios de completitud. Los procesadores pipeline se basan en el
principio de dividir los cálculos entre una cantidad de unidades funcionales que
operan simultáneamente existiendo superposición.
- Procesador Array: Un grupo de unidades de cómputo cada una de las cuales
realiza simultáneamente la misma operación sobre diferentes conjuntos de
datos. Los procesadores array operan sobre vectores. Las instrucciones del
computador vectorial son ejecutadas en serie (como en los computadores
clásicos) pero trabajan en forma paralela sobre vectores de datos.
Clasificación del FLYNN
A grandes rasgos, la ejecución de una instrucción puede verse como etapas
distintas, que realizan:
- Búsqueda de la instrucción,
- Decodificación de la instrucción,
- Búsqueda de los operandos, y
- Ejecución de la instrucción.
Las instrucciones pueden verse
como un flujo de instrucciones que se
desplazan de memoria al procesador y los
operandos como un flujo de datos que se
desplazan entre memoria y el procesador
Analizando el ciclo de una instrucción se puede diferenciar a un procesador en
dos unidades funcionales:
La unidad de control (CU): decodifica la instrucciones y envía señales a una
Unidad de Procesamiento.
La unidad de procesamiento (PU): ejecuta las instrucciones decodificadas y
envía los resultados a la unidad funcional memoria.
M. J. Flynn en 1966 realizó una clasificación del paralelismo presente en un
procesador basado en el número de Flujo de Instrucciones y de Datos simultáneos.
Combinando flujo de instrucciones y flujo de datos surgen 4 grupos de
procesadores posibles.
PROCESAMIENTO EN SERIE vs. PROCESAMIENTO EN PARALELO.
Tsé-Yun Feng (1972) sugirió la utilización del grado de paralelismo para
clasificar las distintas arquitecturas de computadoras. La cantidad máxima de bits que
pueden ser procesados dentro de una unidad de tiempo por un computador, es lo que
se denomina máximo grado de paralelismo.
Consideremos un conjunto de m
palabras de n bits cada una, llamamos un
bit-slice a una columna vertical de bits de un
conjunto de palabras en la misma posición
BALANCE DEL ANCHO DE BANDA DEL SUBSISTEMA (BANDWIDTH).
La estructura de bus común tiene el inconveniente que ofrece una
comunicación en cuello de botella.
Cada acceso a memoria de un ordenador desaprovecha accesos a millones de
bits cuando escoge unos pocos para enviar a través del bus desde la memoria a la
unidad central de proceso.
Este despilfarro se tolera por dos razones:
- Primero, porque simplifica nuestro concepto de la máquina y se adapta a
nuestra inclinación natural de hacer las cosas una a una.
- Segundo, nos suministra una sola y simple interconexión entre las distintas
partes de la máquina.
En general, la CPU es la unidad más veloz dentro de una computadora.
Mediremos su ciclo en un tiempo Tp dado en decenas de nanosegundos; el de la
memoria, en Tm dado en cientos de nanosegundos; y el del subsistema de E/S, que es
el más lento, en Td, dado en unos pocos milisegundos. Entonces:
Td > Tm > Tp
Ej: En la IBM 370/168, Td = 5 ms (discos); Tm = 320 ns y Tp = 80 ns.
Se define el ancho de banda o bandwidth de un subsistema como la cantidad
de operaciones realizadas por unidad de tiempo. Para el caso de memoria es la cantidad de palabras de memoria que pueden accederse por unidad de tiempo.
Es importante al hacer mediciones comparativas entre los anchos de banda de
los diferentes subsistemas tener bien en claro ciertos conceptos.
Cuando se mide el ancho de banda de la memoria (o equivalentemente el del subsistema de E/S) su visualización no es complicada debido a que es bastante sencillo pensar que, ya que la memoria en un dispositivo pasivo, lo que se mide es la cantidad de información (bytes, palabras, instrucciones, etc) que la memoria puede transmitir en una cierta unidad de tiempo.
En cambio hablar del ancho de banda de la CPU, que es un dispositivo activo,significa en cierta forma la capacidad de proceso de la misma, es decir más burdamente hablando, que cantidad de instrucciones puede ejecutar por unidad de tiempo.
Si lo que se desea es comparar los anchos de banda de la memoria y la CPUdebe ponerse especial cuidado en qué patrón de comparación se está utilizando. Por
ejemplo, utilizando los guarismos anteriores, si la IBM 370/168 ejecuta 50 instrucciones
en 80 ns su memoria demora 320 ns en transferir esas 50 instrucciones a la CPU.
Sea W la cantidad de palabras que se obtienen por cada ciclo de memoria Tm;
luego, el ancho de banda máximo de la memoria es:
Bm = W / Tm (Palabras o bytes)
Ej: La IBM 3033 tiene un ciclo de procesador de Tp = 57 ns. Por cada ciclo de
memoria de Tm = 456 ns pueden obtenerse 8 palabras dobles de 8 bytes c/u a partir de un sistema de memoria con 8 elementos lógicos de almacenamiento en forma intercalada (interleaved). Luego:
Bm = 8 * 8 bytes / 456 ns = 134 Mb/s
Pero debido a esta partición lógica de la memoria pueden producirse determinados conflictos al querer acceder a una posición, y por lo tanto, el ancho de banda
útil (Bmu) será menor:
Bmu ≤ Bm
Se sugiere una medida del tipo:
Bmu = Bm / M 1/2
donde M es la cantidad de módulos de memoria del sistema de memoria.
Luego, en el ejemplo anterior, se tiene:
Bmu = 134 / 8 1/2 = 47.3 Mb/s
En cuanto a dispositivos externos, el concepto de bandwidth se complica un
poco. Piense que, por ejemplo, según los tiempos de latencia y rotación, la tasa de
transferencia de una unidad de disco puede variar. En general nos referimos a la tasa
de transferencia promedio de una unidad de disco como el bandwidth Bd del disco; un
valor típico es del orden de 3 Mb/s. En una unidad de cinta el valor típico ronda los 1.5
Mb/s. Las impresoras, lectoras y terminales son mucho más lentas aún. Usando
múltiples drives estas tasas aumentan.
El bandwidth de un procesador se mide como el máximo porcentaje de
cómputo de la CPU; por ejemplo, 160 megaflops (millones de instrucciones de punto
flotante por segundo) en los computadores Cray-1, y de 12.5 MIPS (millones de instrucciones por segundo) en los computadores IBM 370/168. Estos son valores pico obtenidos de la división de 1/Tp = 1/12.5 ns y 1/80 ns respectivamente.
En la realidad, el porcentaje útil de CPU es Bpu menor o igual a Bp. Este porcentaje de utilización se calcula sobre la cantidad de resultados (o palabras) por segundo:
Bpu = Rw / Tp (palabras/s)
donde Rw es la cantidad de resultados medidos en palabras, y Tp es el tiempo
necesario para generar esos resultados Rw.
Por ejemplo, el CDC Cyber-205 tiene un porcentaje pico de 200 MFLOPs para
resultados de 32 bits, y solamente de 100 MFLOPs para resultados de 64 bits.
En las computadoras actuales se observa la siguiente relación entre los
bandwidths de los distintos subsistemas:
Bm ≥ Bmu,
Bmu ≥ Bp,
Bp ≥ Bpu, y
Bpu ≥ Bd
Esto significa que la memoria principal tiene el mayor bandwidth, ya que debe
ser accedida tanto por la CPU como por los dispositivos de E/S, es decir que del porcentaje efectivo de información transferida por unidad de tiempo por la memoria una
parte se dirige a la CPU y otra corresponde al intercambio de información con los
medios externos. Por lo tanto necesitamos igualar la potencia de procesamiento de los
tres subsistemas. A continuación describimos los dos mecanismos más usados:
Balance entre CPU y Memoria.
La diferencia de velocidad entre la CPU y la memoria puede achicarse
mediante el uso de memoria cache de alta velocidad. La cache tiene un tiempo de acceso Tc = Tp. Un bloque de palabras de memoria es movido a la cache (Por ej. bloques
de 16 palabras en la IBM 3033) de tal manera que los datos e instrucciones están disponibles inmediatamente para su uso; también puede servir como un buffer para instrucciones.
Balance entre dispositivos de E/S y Memoria.
Pueden utilizarse canales de diferentes velocidades entre los dispositivos lentos
y la memoria. Estos canales de E/S realizan funciones de bufferización y mult
plexamiento para la transferencia de datos desde muchos discos y la memoria principal
mediante el robo de ciclos a la CPU. Incluso pueden utilizarse controladores de disco
inteligentes para filtrar la información irrelevante de las pistas del disco, lo cual aliviaría
la saturación de los canales de E/S.
En el caso ideal desearemos alcanzar un balance total del sistema, en el cual el
bandwidth de la memoria coincida con la suma del bandwidth del procesador y de los
Dispositivos de E/S, es decir:
Bpu + Bd = Bmu
donde Bpu = Bp y Bmu = Bm han sido maximizados ambos.
Paralelismo con una sola CPU
Procesamiento paralelo es un término utilizado para denotar operaciones
simultáneos en la CPU con el fin de aumentar su velocidad de cómputo. En lugar de
procesar cada instrucción secuencialmente como en las arquitecturas convencionales,
un procesador paralelo realiza tareas de procesamiento de datos e instrucciones concurrentemente.
Para lograr concurrencia en un sistema con un solo procesador se utilizan
técnicas de paralelismo que se consiguen multiplicando los componentes de hardware,
o técnicas de pipelining.
Introduciremos las características básicas de los computadores paralelos, que
son aquellos sistemas que enfatizan el procesamiento en paralelo. Estos computadores
se pueden dividir en tres configuraciones según la arquitectura:
- Computadores Pipeline
- Procesadores Matriciales - Array Processors
- Sistemas Multiprocesadores
Un computador pipeline hace operaciones superpuestas para explotar el
paralelismo temporal. Un Array Processor usa ALUs múltiples sincronizadas, para
lograr paralelismo espacial. Un sistema multiprocesador logra paralelismo
asincrónico a través de un conjunto de procesadores que interactúan y comparten
recursos (periféricos, memorias, bases de datos, etc.).
El pipelining es una forma económica de hacer paralelismo temporal en computadoras. La idea es la misma que la de las líneas de montaje de las plantas industriales. Se divide la tarea en una secuencia de subtareas, cada una de las cuales se
ejecuta en una etapa de hardware especializada que trabaja concurrentemente con otra
de las etapas del pipeline. Esto permite aumentar el throughput del sistema de forma
considerable.
COMPUTADORES PIPELINE
Veamos el ejemplo de un pipeline de cuatro etapas: el proceso de ejecución de
una instrucción en un computador digital envuelve cuatro pasos principales: levantar la
instrucción de memoria (Instruction Fetch - IF); identificar la operación que debe efectuarse (Instruction Decoding - ID); levantar los operandos si son necesarios en la
ejecución (Operand Fetch - OF); y ejecutar la operación aritmético lógica que ha sido
decodificada. Antes de comenzar a ejecutar una nueva instrucción deben completarse
estos cuatro pasos.
- Principios de pipelining lineal
Las líneas de montaje de las plantas han sido utilizadas para aumentar productividad. Su forma original es una línea de flujo (pipeline) de estaciones de montaje en
donde los ítems se ensamblan continuamente.
Idealmente todas las etapas tienen que tener igual velocidad de procesamiento,
porque sino la más lenta se transforma en un cuello de botella de todo el pipe. La
subdivisión de la tarea de entrada en una secuencia apropiada de subtareas es un factor crucial para determinar la performance del pipeline.
En un pipeline de tiempo uniforme, todas las tareas tienen igual tiempo de
procesamiento en todas las estaciones. Sin embargo, en la realidad las estaciones
sucesivas tienen tardanza de tiempo distinta. La partición óptima del pipeline depende
de un número de factores, incluyendo la calidad de las unidades de trabajo (eficiencia y
capacidad), la velocidad deseada y la efectividad en costo de toda la línea.
El tiempo que se tarda en obtener resultados continuos es lo que se conoce
como "tiempo de carga del pipe".
