unidad 2: segmentación segmentación no lineal docente: ing. josé díaz chow

Unidad 2: Segmentación

Segmentación No Lineal

Docente: Ing. José Díaz Chow

Explicar el concepto de segmentación no lineal

y su diferencia con la segmentación lineal.

Utilizar diferentes formas de representar y describir las funciones y operación de los cauces no lineales.

Exponer el campo de aplicación de los cauces no lineales y las diferentes implementaciones en uso hoy día.

Objetivos (1/2)

Enumerar los tipos de dependencias y sus

riesgos asociados que pueden darse en los cauces no lineales.

Conocer técnicas para tratar los riesgos por dependencias estructurales, específicamente en la prevención de colisiones y maximizar el rendimiento del cauce.

Objetivos (2/2)

2.10 Segmentación no lineal

Segmentación general o no-lineal Representaciones Implementaciones Riesgos de la Segmentación NL Planificación de recursos

Contenido

Segmentación no lineal

• Segmentación no limitada por relación de precedencia lineal entre las subtareas

T1 T2T3 T4

T1 T3T2 T4

out

in

1 2 3in out

Grafo de Precedencia Lineal Grafo de Precedencia No lineal

13

2 4

• Excención y multiplicidad de etapas

• Repetición de etapas (loops)

• Retorno a etapas anteriores (feedback)

• Multiples trayectorias (multifunción y dinámicos)



Contenido

Representación de Cauces NL

S1 S2 S3 S4 S5

• Diagramas de bloques y descripción:

• Grafo de precedencia y trayectorias:

S1 S5S4S3S2

Inicio

1

2

3 4

5

6 7'

8

Final

7

8'

Representación de Cauces NL

• Tabla de Reserva del cauce:Sj \Ti 0 1 2 3 4 5 6 7 8

1 X X

2 X X X

3 X

4 X X

5 X X



Contenido

Implementaciones

• Cauces lineales:

• Segmentados de instrucciones

• Cauces aritméticos simples

• Cauces no-lineales:

• Cauces aritméticos en P.F

• Segmentados escalares/S.E.: Multiciclos

Procesadores Multiciclo

• DLX Multiciclo

BUS D/L MEM ESC

ALUE

MULE/PF

SUMPF

DIVE/PF

Mejoras de la Técnica

Más de 1 instrucción por ciclo

• Superpipelining:

• Tiempo de etapa es una fracción (p.e. ½) del período de reloj

• Superescalar:

• Procesador con varias unidades funcionales y/o cauces de ejecución.



Contenido

Riesgos se incrementan por la no linealidad de implementación: Unidades en PF pueden hacer que instrucciones

posteriores concluyan antes. Para aprovechar la multiplicidad de unidades

funcionales, tenemos en ejecución múltiples operaciones en PF en paralelo.

Dependencias estructurales: Colisiones en Unidades funcionales o en etapas de cauces aritméticos.

Dependencias de datos: Problemas de Coherencia. Dependencias de control: Requerido garantizar la

coherencia cuando hay operaciones en PF multiciclo.

Riesgos de la Segmentación NL

En CPUs NoLineales de Instrucciones: Dependencias estructurales: Colisiones en

Unidades funcionales, cuando dos operaciones iguales:

ADDF f23, f2, f7

ADDF f18, f5, f9

Dependencias de datos: Dependencias de Datos provocan riesgos de incoherencia de resultados:

ADDF f5, f2, f7

MULF f18, f5, f9


Detección de dependencias

estructurales por el código de operación.

ADDF f23, f2, f7

ADDF f18, f5, f9

MULF f17, f4, f11

Se detiene la emisión de nuevas instrucciones del mismo tipo.

Pérdida de eficiencia Si no hay DD, se debería de

adelantar MULF: Ejecución en desorden para mayor eficiencia


BUS D/L MEM ESC

ALU E

MULE/PF

SUMPF

DIVE/PF

Dependencias de Datos:

Aplican las mismas dependencias R-D. ADDF f5, f2, f7

MULF f18, f5, f9

Posible implementación de forwarding Detección previa de Dependencia, marcaje de

registro y no emisión de MULF hasta que resultado disponible o f5 consistente.

Pueden aparecer dependencias D-R (WAR) y R-R (WAW) debido a que las operaciones duran tiempos diferentes y a la ejecución en desorden.


Requerido garantizar secuencia

correcta de los cálculos. Necesario mecanismo de control que

trate las dependencias estructurales y de datos integralmente.

Dos enfoques se han empleado: Uso del marcador (Scoreboard) Algoritmo de Tomasulo


Scoreboad o Marcador:

Estructura de datos y control centralizada. D/L se divide en dos etapas:

Decodificar y detectar Dependencias estructurales

Detectar Dependencias de Datos y Leer Operandos

Cada instrucción pasa por el marcador que lleva un tablero de DD

Emite la instrucción si no hay dependencias Controla la escritura ordenada de resultados


Tomasulo:

Estructura de datos y control distribuida (estaciones de reserva).

Carga de instrucciones en una cola y se emiten si hay estaciones de reserva disponibles.

Estaciones de reserva controlan cada unidad de ejecución. Llevan copia de las operaciones y los datos

Estructura de datos de control de los registros y DD

Implementa forwarding para mejorar la eficiencia


Tomasulo:


Tomasulo:

Emisión en orden Control entre estaciones de reserva

(Tabla de datos) Ejecución en orden pero finalización

puede ser en desorden. Escrituras en orden.


En Cauces Aritméticos: Dependencias Estructurales en etapas del

cauce: Provocan riesgos de Colisión.

Detección en Tabla de reserva Etapas utilizadas más de una vez por función.

Implementación de un Mecanismo de bloqueo. Vector de Colisiones. Mejora de la eficiencia: Planificación de recursos




Contenido

Planificación de recursos en cauces

aritméticos: Basada en mecanismo de bloqueo de

colisiones. Permite detectar las secuencias de

inicializaciones más provechosas. Minimiza las penalizaciones mejor

desempeño del Cauce.

Planificación de Recursos

Uso de vector de colisiones para bloquear las

inicializaciones de nuevas tareas en latencias prohibidas (aquellas latencias o pulsos de reloj en las cuales, si se inicia, habrá una colisión).

El vector de colisiones se implementa como un registro binario de desplazamiento: En cada pulso de reloj el registro desplaza una posición a

la derecha. Se verifica si bit desplazado es 1 ó 0. Si es 1 se bloquea la inicialización y si es 0 se permite.

Cuando se permite la inicialización, se hace un OR del registro con el valor del vector de colisiones original a fin de reservar las prohibiciones que la nueva inicialización va a generar.

Mecanismo de bloqueo

Algoritmo de Planificación.

• (P1) Análisis de colisiones en tabla de reservas:

• Lista de latencias prohibidas F (y libres F’).

Sj \Ti 0 1 2 3 4 5 6 7 8

1 X X

2 X X X

3 X

4 X X

5 X X

F = { 1, 5, 6, 8 } F’ = { 2, 3, 4, 7 }


• (P2) Vector de colisiones (Elemento de bloqueo)

• (P3) Diagrama de estados (Base de la estrategia)

C = (Cn . . . C1) | Ci = 1 i F Ci = 0 i F’

C = ( 10110001)

- Primer estado es C.

- Se simula cada nuevo estado del registro de bloqueo luego de cada posible inicialización (latencias libres): A cada estado existente se desplaza i ciclos a la derecha i F’ y se aplica OR con C. Si el resultado es diferente de algún estado existente, es un nuevo estado.


En base los estados generados a partir de las transiciones en las diferentes latencias libres posibles, creamos un diagrama de estados que caracteriza el funcionamiento del cauce en todos sus estados posibles.


10110001

10110111 10111101

10111011 10111111

7+

37+

7+

7+

7+

4 2

243

1

23

54

Diagrama de Estados del cauce


• (P4) Determinar ciclos simples (lm, mlm, ca)

• (P5) Estrategia: Secuencia que favorecen los ciclos avariciosos

Ciclo simple Latencia media (lm)

¿Es Avaricioso?

( 7 ) 7 ( 3, 7 ) 5 ( 3, 4 ) 3.5 SI, y tiene la mlm( 4, 3, 7 ) 4.6 ( 4, 7 ) 5.5 ( 2, 7 ) 4.5 ( 2, 2, 7 ) 3.6 SI( 3, 4, 7 ) 4.6

unidad 2: segmentación segmentación no lineal docente: ing. josé díaz chow

Documents