Este artículo demuestra cómo obtener un secuenciamiento óptimo para un pipeline de datos no lineal. Esto tiene como objetivo alcanzar la máxima utilidad del pipeline (máximo throughput) cuando existen conflictos en etapas con realimentaciones negativas (retroalimentaciones).

El concepto de pipeline como técnica de paralelización de tareas fue introducido por Ransom Olds en la línea de ensamblaje del Oldsmobile Curved Dash. Luego fue perfeccionado por Henry Ford para la producción del Ford Modelo T agregando cintas transportadoras, lo cual le permitía producir un vehículo cada 93 minutos. Por esta razón generalmente se le atribuye la idea de pipeline a Henry Ford. Más allá de surgir de la industria automotriz, es un concepto genérico que puede ser aplicado a cualquier tipo de tarea.

En computación, un pipeline de datos es un conjunto de elementos de procesamiento de datos conectados en serie, donde la salida de un elemento o etapa es la entrada de la siguiente. Esto permite paralelizar una tarea subdividiéndola en etapas que se ejecutan concurrentemente. De esta forma es posible ejecutar una misma tarea sobre diferentes datos al mismo tiempo (siempre que no hayan conflictos en las etapas en las que éstos se ejecutan).



Más allá de que su uso más conocido sea en la implementación del pipeline de instrucciones de un microprocesador o CPU (lo cual permite solapar la ejecución de múltiples instrucciones en un mismo circuito electrónico), existen otros tipos de pipelines relacionados a la computación: pipelines gráficos utilizados en todas las GPUs (tarjetas gráficas) para convertir modelos 3D a imágenes 2D renderizadas; pipelines de software (utilizados en sistemas Unix para aplicar una serie de procesos en paralelo a un mismo conjunto de datos); pipelines HTTP (para realizar varias peticiones HTTP en una misma conexión TCP); etc.

En un pipeline lineal ideal, todas las etapas tienen la misma duración, y en cada ciclo ingresa una nuevo dato. Cuando las etapas tienen diferentes duraciones, el tiempo de ciclo del pipeline es el de la etapa más lenta. Por ello es importante dividir correctamente en etapas de tiempos similares al paralelizar una tarea.

Los pipelines no lineales son aquellos en los que el flujo de datos tiene realimentaciones. Este es el caso en el que una etapa debe ser atravesada dos veces. O dicho de manera correcta, un dato debe ser procesado dos veces por una misma etapa en ciclos de tiempo diferentes. Veamos un ejemplo de pipeline no lineal:

Tal como se observa, se trata de un pipeline no lineal: un dato pasa primero dos veces por la etapa 1 (S1); luego pasa por las etapas 2, 3, 4, 5 y 6; y termina pasando una vez más por la etapa 2 (S2). Ahora bien, si ingresa un dato al pipeline, ¿cuántos ciclos deben transcurrir para que ingrese el siguiente datos sin que se produzcan colisiones (que ambos datos necesiten ser procesados por una misma etapa en un mismo ciclo)?

La latencia total para procesar un dato en este pipeline es de 8 ciclos. Por ende una latencia trivial sería esperar 8 ciclos para ingresar el siguiente dato. Esto equivale al procesamiento de datos sin pipeline, hasta que no finaliza un dato no se procesa el siguiente.

Para poder aprovechar el paralelismo del pipeline evitando colisiones (es decir, ingresar datos con mayor frecuencia) es necesario analizar latencias críticas (latencias de iniciación que provoquen colisiones). A tal fin se elabora la siguiente tabla de reservación de estados, poniendo etapas en las filas y ciclos en las columnas:

Las cruces marcan en qué etapa se encuentra un dato en cada ciclo. Las latencias críticas se obtienen como la distancia en ciclos entre colisiones (uso de una misma etapa). Tener en cuenta que una misma etapa puede generar múltiples colisiones si se utiliza más de dos veces y deben analizarse todas las distancias posibles entre cruces de una misma fila.

La máxima cantidad de cruces en una misma etapa (misma fila) indica la latencia mínima teórica promedio que se podría alcanzar. En este caso, la latencia mínima teórica es 2. Esto significa que se podría iniciar, en promedio, datos cada dos ciclos. Sin embargo esto es teórico, es necesario analizar cuidadosamente las posibles colisiones y el ritmo de iniciación. Pero en definitiva la cota mínima a la latencia promedio la establece la etapa del pipeline más utilizada.

A partir de las latencias críticas encontradas se arma un vector de colisión. Se trata de un número binario donde cada bit es igual a 1 si la posición (numerando a partir de 1 en adelante y de derecha a izquierda) es una latencia crítica y 0 si no lo es. La longitud del vector es igual a la latencia crítica más grande. De esta forma el bit más significativo del vector siempre será 1. En este caso tenemos las latencias críticas 1 y 5, con lo cual queda el siguiente vector de colisiones:

Cada vez que ingresa un nuevo dato al pipeline, los conflictos introducidos por el mismo se suman a los conflictos ya existentes (introducidos por datos ingresados previamente). Con este vector es posible confeccionar un grafo simulando el ingreso de nuevos datos según las diferentes combinaciones de latencias permitidas. en cada estado del pipe. Esto es lo que permite establecer el ritmo de iniciaciones.

El nodo raíz del grafo corresponde con el vector de colisiones. Por cada 0 (latencia permitida) de cada nodo se origina un nuevo arco que llevará a un nodo con un nuevo estado. Este próximo estado se calcula como la suma del vector de colisiones (conflictos introducidos por el nuevo dato ingresado) con el estado previo desplazado por la latencia del arco (conflictos introducidos por datos iniciados anteriormente). Sin embargo, no se trata de una suma binaria sino de un or binario bit a bit. Más que una "suma" es una agregación de conflictos.

Entonces, en el inicio ingresa un dato y se introducen los conflictos determinados por el vector de colisión 10001. A partir de aquí hay 4 latencias posibles: 2, 3, 4 y 6 (más de 6 no tiene sentido porque sería desperdiciar ciclos en vano). Por ejemplo, si se ingresa un nuevo dato luego de 2 ciclos (latencia 2 permitida), el estado cambia a 00100 (transcurridos 2 ciclos el vector de colisión cambia de 10001 a 100, es decir la anterior latencia prohibida 5 es ahora 3). Pero a su vez se deben agregar los conflictos del nuevo dato (determinados siempre por el vector de colisión):

  
   10001
or   100
   -----
   10101

El nuevo nodo desde el arco con latencia 2 es 10101:

Las otras latencias permitidas desde el nodo inicial son 3 y 4:

  
   10001       10001
or    10    or     1
   -----       -----
   10011       10001

Con latencia 3 resulta en un nuevo estado 10011 y con latencia 4 queda en el mismo estado.

Desde el nodo 10101 las latencias permitidas son 2 y 4:

  
   10001       10001
or   101    or     1
   -----       -----
   10101       10001

Desde el nodo 10011 las latencias permitidas son 3 y 4:

  
   10001       10001
or    10    or     1
   -----       -----
   10011       10001

Al finalizar, se obtiene el siguiente grafo:

El mismo contiene las diferentes iniciaciones posibles de acuerdo al estado del pipeline. Con latencia 6 obviamente se vuelve al nodo inicial, pues se esté deshaciendo de todo conflicto (6 shifts).

Para obtener la latencia promedio mínima que permita lograr el máximo throughput alcanzable en la práctica, es necesario encontrar los ciclos greedy. Estos son aquellos ciclos cerrados (sin repetir nodos) que tienen la característica de que los arcos que los conforman utilizan las latencias mínimas posibles. Teniendo en cuenta que cada nodo tiene una única latencia mínima de salida, las posibilidades no son muchas.

En nuestro ejemplo los nodos 10001 y 10101 tienen latencia mínima 2, mientras que el nodo 10011 tiene latencia mínima 3. Por lo tanto, los ciclos greedy del grafo son:

Las latencias bajo el arco indican cuáles conforman el ciclo en sí mismo, mientras que las restantes indican el camino para llegar al ciclo desde el nodo inicial.

En este ejemplo ambos greedy resultan ser de un solo arco, sin embargo es común que el ciclo esté conformado por más de un arco, lo cual marcará el ritmo de iniciación del pipeline.

Tal como se observa, existen muchos ciclos en el grafo, incluso algunos de ellos sin repetir nodos. Sin embargo, sólo los que están marcados en azul son greedy. Por ejemplo, el ciclo formado por los arcos 2 y 4 no es greedy porque 4 no es la latencia mínima disponible desde el nodo 10101.

La latencia promedio del primer ciclo es 2 y se calcula como la suma de las latencias del ciclo dividido la cantidad de arcos (en este caso es trivial: 2/1 = 2). En el segundo ciclo greedy la latencia promedio es 3.

Se observa que el primer ciclo alcanza la latencia promedio mínima teórica, con lo cual es un ciclo óptimo y significa que las etapas más utilizadas (S1 y S2) estarán 100% ocupadas una vez que el pipeline entre en régimen (se llene). Con lo cual se ha alcanzado el máximo throughput posible para este pipeline (0,5 datos por ciclo).

Es posible comprobar que no hay colisiones analizando la evolución de los primeros 6 datos representados con las letras A, B, C, D, E y F respectivamente:

Se observa que una vez alcanzado el régimen, ambas etapas más utilizadas permanecen 100% ocupadas. El tiempo de llenado y vaciado del pipeline merma su rendimiento. Pero, con la cantidad suficiente de datos a procesar, resulta despreciable. En este ejemplo, procesar sólo 6 datos en el pipeline llevó un total de 18 ciclos. Esto significa que en la práctica se completó un dato cada 3 ciclos (en lugar 2). Por ende el throughput alcanzado para 6 datos se redujo a 0,33 a causa de los ciclos perdidos en el llenado y vaciado del pipeline.

Referencias


Tal vez pueda interesarte


Compartí este artículo