Story Transcript
Contenido 1. Definición del problema 2. Caracterización 3. Modelado 4. Técnicas de partición Hw-Sw 5. Revisión de trabajos clásicos 6. Nuevos enfoques 7. Conclusiones
PARTICIÓN Hardware-Software: Modelado y técnicas
Mª Luisa López Vallejo Diseño de Circuitos Electrónicos Heterogéneos
Dpto. Ingeniería Electrónica-UPM
M. L. López Vallejo
2
M. L. López Vallejo
1. Definición del problema
1.1 Co-diseño Hw-Sw
¿Por qué Co-diseño?
n ió ac al c i f ci ion pe nc Es F u
Time-to-market
Ventajas 9 9 9 9 9
Se explota el sinergismo Hw-Sw Mejores prestaciones Compromiso coste-prestaciones Tiempo de diseño menor Propiedad intelectual
I/O
Partición Hw-Sw: Impacto crítico 9
Hw
Memoria
Hw
...
Sistema
M. L. López Vallejo
1.2 Flujo de Co-diseño
4
1.3 Problemas de Co-diseño
Transformaciones
Formato Intermedio
Síntesis de ASIPs: Diseño y generación de un microprocesador
Partició ón HW-SW
Generació ón de có ódigo
Procesador
Arquitectura destino 3
M. L. López Vallejo
Hw
Memoria
Características coste-prestaciones
Especificació ón
Procesador
Interfaz
Diseño de Sistemas en un chip (SoC)
Aceleración de ejecución: Máquinas con FPGAs
ASICs con cores de procesadores Sííntesis Hardware
Prototipado Integració ón
Prototipado
M. L. López Vallejo
Diseño de Sistemas empotrados Sistemas heterogéneos propiamente dichos
Verificació ón Cosimulació ón
5
M. L. López Vallejo
6
1
1.4 Qué es Partición Hw-Sw
Tarea clave en el ciclo de Co-diseño
Interfaz de Usuario
9
Asigna bloques a unidades de procesamiento Hw/Sw 9 Planificación del sistema
9 9
Entrada
MODELO DE SISTEMA
Basada en estimaciones Considera restricciones: Cotas impuestas por recursos: área, memoria... Límites impuestos por las prestaciones
Algoritmo
Salida
Estimadores
Técnicas: 9
Procedimientos generales de optimización Adaptación de algoritmos clásicos de partición 9 Métodos más sofisticados 9
Funció ón de coste
7
M. L. López Vallejo
M. L. López Vallejo
8
1.5 Diferentes problemas
9 9
2.1 Tipo de especificación 2.2 Granularidad 2.3 Arquitectura destino 2.4 Tipo de aplicación
Sistemas Empotrados Sistemas en un Chip
División en conjunto de instrucciones 9
1. Definición del problema 2. Caracterización
Distribución física de funcionalidad entre unidades de procesamiento diferentes
3. Modelado 4. Técnicas de partición Hw-Sw 5. Revisión 6. Nuevos enfoques
Síntesis ASIPs
Mapping o Mapping + partición 9
Máquinas aceleradoras basadas en FPGAs
7. Conclusiones M. L. López Vallejo
9
M. L. López Vallejo
2. Caracterización del problema
2.1 Tipo de Especificación
Identificación de aspectos clave: 9
Tipo de especificación
9
Granularidad Arquitectura destino Tipo de aplicación
9 9
10
Lenguaje único 9
HDL: Verilog, VHDL... Lenguaje de programación: C, C++, Ada... 9 Técnica de descripción formal: Lotos, STL,… 9
Diferentes lenguajes: 9
Más real Mejor adecuación 9 Contrario a la idea inicial 9
Objetivos 9 9
Fundamentos para implementación Clasificación Estudio de los antecedentes
M. L. López Vallejo
¡Condiciona la representación interna!
11
M. L. López Vallejo
12
2
2.2 Granularidad Tamaño de los objetos manipulados 9
Gruesa:
9
Fina
Tareas Funciones Bloques
I/O
Instrucciones Operaciones
Medida relativa
Múltiples granularidades 9
Procesador
Interfaz
2.3 Arquitectura destino
Hw
Memoria
Definida de forma dinámica
Genérica 13
M. L. López Vallejo
14
M. L. López Vallejo
2.5 Tipo de aplicación Auto-contenidos
Sistemas empotrados
Procesado informació ón
Consumidor
Ordenadores Emuladores Prototipado
1. Definición del problema
Control en transporte
Control de planta
Redes
Electrodomé ésticos
Automó óviles
Fabricació ón
Telé éfono
Juegos
Quíím ica
Defensa
Aviones
HiFi
Barcos
Concentrados
Trenes
2. Caracterización 3. Modelado 3.1 Modelo de sistema 3.2 Modelo de la arquitectura 3.3 Extensiones 3.4 Referencias de calidad
Centrales
Distribuidos localmente
Distribuidos
4. Técnicas de partición Hw-Sw 5. Revisión
Clasificación de Prof. De Micheli
6. Conclusiones 15
M. L. López Vallejo
16
M. L. López Vallejo
3. Modelado del problema
3.1 Modelo de sistema
Resolución de un problema Definición de un modelo Aspectos involucrados
Fundamento de implementaciones posteriores Puntos básicos: 9 9 9 9
M. L. López Vallejo
Abstracción de la funcionalidad
Define los objetos básicos de la partición
Base de la estructura de datos
Fundamentado en un modelo de computación
Información asociada fundamental
Modelo de sistema Modelo de arquitectura Extensiones Formulación de la función de coste 17
M. L. López Vallejo
18
3
3.1.1 Modelos de Computación
3.1.2 Grafos de flujo
Tipo de grafo: dirigido
Formulación matemática Ö verificación
9 9
Formalismos más utilizados 9 9 9 9
Granularidad: 9
Grafo de flujo de ejecución (DFG y CDFG) Redes de petri Máquinas de estados finitos Otros
9
19
M. L. López Vallejo
Acíclico: DFG, Grafos de tareas Cíclico: CDFG gruesa (tareas) fina (operadores) ARCO: ttransf (vi, vj ) wi j ni j
NODO: hai hti ssi sti ni
20
M. L. López Vallejo
3.1.2 Ejemplo de grafo de flujo
3.1.3 Redes de Petri
Orig
T4
T7
Vértice i T0
ha i ht i ss i st i ni
T3
Lugares (places) Transiciones Fichas (tokens) P4
P2
T6
T1 5
T5
Arco (i,j)
T2
t transf(v ,v ) i
T4
j
wij nij
T8
T2
P1
T5
T6 P5 5
T1
T3 M. L. López Vallejo
21
End
3.2 Modelo de arquitectura
RAM
ROM
Modelado a dos niveles de abstracción: 9
Nivel RTL
9
Nivel funcional
Tres modelos básicos: 9 9 9
M. L. López Vallejo
22
(Sistema)
BUS (datos / direcciones / control)
COPRO1
P6
3.2.1 Bases del modelo de arquitectura
Estructura clásica: procesador-bus-coprocesador MICRO PROCESADOR
P3
M. L. López Vallejo
Procesador Co-procesador Interfaz
COPRO2
23
M. L. López Vallejo
24
4
3.2.2 Modelos integrantes
Procesador 9 9 9
Cache/ memory
Arquitectura load-store RISC ...
3.2.2 Modelo Co-procesador Hardware Datapath
Decode and issue unit
Fetch Unit
Multiple instruction
FU
FU
FU
FU
FU
Controlador
Abstracciones matemáticas Representación de la información, funciones booleanas
Abstracciones matemáticas: Máquinas de estados finitos (FSM)
Componentes principales • Puertas Lógicas & Flip-Flops •Componentes RTL
Componentes principales • Puertas Lógicas & Flip-Flops • Registros de Estado y componentes para Estado Siguiente
Input
FU
Input Status
Datapath
Register file
Controller
Register file
Control 25
M. L. López Vallejo
3.2.2 Modelo de interfaz
M. L. López Vallejo
Basada en bus
9
Memory-mapped
9
Protocolo asíncrono mediante interrupciones
9 9
External Memory Interface
AHB DMA bus Master
B R I D G E
Latencia, Tp Área hardware, Ap Espacio en memoria, Mp
Restricciones 9 Modelo
Serial interface
de sistema:
– Máxima latencia, T 9 Modelo
Timer 27
3.4 Referencias de calidad
de arquitectura:
– Máxima área hardware, A – Máximo espacio en memoria, M – Velocidad de transferencia del bus, B – Anchura del bus, W
APB
M. L. López Vallejo
M. L. López Vallejo
9
ESPECIFICACIÓN
Implementación todo-software 9
TRANSFORM. SW
MaxM MaxT
9
9 9 M. L. López Vallejo
SIMULACIÓN SISTEMA
ni
ss i ,st i
Hw-Sw
Procesos SW
TRANSFORM. HW
ESTIMACIÓN HW
hai ,ht i
PARTICIÓN
MaxA MinT
Siempre se cumple: 9
GRAFO
ESTIMACIÓN SW (PROFILING)
Implementación todo-hardware 9
28
Todo junto: Flujo de información
Implementaciones extremas
26
Atributos de calidad de la partición 9
ARM Processor
HW CoProcessor
Output
3.3 Extensiones a los modelos básicos
9
Output
tcomm,i,j
A, T, M Procesos HW
CO-ESTIMACIÓN HW-SW
Ap ≤ MaxA Mp ≤ MaxM MinT ≤ Tp ≤ MaxT
CO-SIMULACIÓN HW-SW
PROTOTIPADO
29
M. L. López Vallejo
30
5
4. Técnicas de Partición Hw-Sw 1. Definición del problema 2. Caracterización 3. Modelado 4. Técnicas de partición Hw-Sw
Métodos de optimización general 9 9 9
4.1 Métodos de optimización general
4.2 Adaptación de heurísticos
Adaptación de heurísticos
4.3 Técnicas especiales 4.4 Comparativa
5. Revisión 6. Nuevos enfoques 7. Conclusiones
9
Min-cut
9
Agrupamiento
Técnicas especiales 9
31
M. L. López Vallejo
Recocido simulado Programación lineal Algoritmos genéticos
Sistemas basados en conocimiento
4.1 Métodos de optimización general
4.1.1 Función de coste
Problema de optimización combinatoria 9 Medida de calidad Î Función de coste 9 Espacio de soluciones Î Restricciones
¡Sin conocimiento del problema!
Métodos: 9 9 9 9
9
9
Recocido simulado Programación lineal Algoritmos genéticos Otros
A
+ kT ×
T
+ kM ×
Mp M
+ kC ×
Cp C
[
Métodos de penalización, barrera o minimización del error cuadrático medio
Ventajas de la formulación propuesta: 9 9 9 9
A
+ kT ×
Tp T
+ kM ×
Mp M
+ kC ×
Cp C
34
M. L. López Vallejo
]
Generalidad Eficiencia y sencillez Evita la alteración de algoritmos clásicos Permite adaptar el método al problema particular Fácilmente extensible
M. L. López Vallejo
Ap
Funciones de penalización
+ k p × r 2 ( Ap , A) + r 2 (Tp , T ) + r 2 ( M p , M )
9
Restricciones impuestas a los atributos de calidad
kA ×
33
Tp
Atributos de calidad de la partición:
– A, T, M y C
Términos de corrección Ap
Guía los métodos de optimización Permite adaptar el algoritmo al problema Ha de considerar: – Ap, Tp, Mp y Cp
M. L. López Vallejo
kA ×
32
M. L. López Vallejo
A
35
M. L. López Vallejo
T 36
6
Minimización del error cuadrático medio
80
2
60
1.5
Fp(Ap,Tp)
Fp(Ap,Tp)
Funciones barrera
40 20
1 0.5 0 10
0 4A 2 Ap
2
T4
A5
2 0
0
Ap
Tp 37
M. L. López Vallejo
9 9 9
Soluciones del problema Coste Mínimo global Movimiento
Proceso físico de recocido 9 Estados del sistema 9 Energía 9 Cristalización 9 Perturbación
Sistema en equilibrio térmico
Los estados se ocupan siguiendo la distribución de Boltzmann −E
prob (estado Energía E ) α e kT
39
E E
Más probables Menos probables 40
M. L. López Vallejo
Fundamentos (y II)
Seudo-código
Test de Metropolis: Sistema en equilibrio térmico
T = T∞ = calienta(); actual_P = inicial_P; coste = funcion_coste(actual_P); WHILE (no congelado) { WHILE (no equilibrio) { genera_movimiento(); ∆E = incr_coste(); IF (acepta_metropolis(∆E)) actual_P = haz_movimiento(); coste = funcion_coste(actual_P); } } T = enfria(T); }
Perturbar sistema ligeramente Calcular ∆E If (∆E < 0) Aceptar // configuración menor energía else // configuración mayor energía Aceptar con Prob(∆E, T) = exp(- ∆E/kT)
Repetido a diferentes temperaturas decrecientes: Recocido Simulado M. L. López Vallejo
Tp
38
Estados Estados M. L. López Vallejo
0
Fundamentos
Basado en una analogía:
9
0
M. L. López Vallejo
4.1.2 Recocido simulado
Problema de optimización combinatoria
T1
41
M. L. López Vallejo
42
7
Evolución (mínimos)
Elementos clave
Coste
Búsqueda local
9
Recocido
9
9
puede
poco probable
siempre
quizás
siempre
M. L. López Vallejo
9
T ↑↑
T ↓↓
43
Esquema de enfriamiento
Temperatura inicial: T∞
Temperatura inicial: T∞
Criterio de equilibrio
Solución aleatoria (gran aceptación)
Criterio de equilibrio: equilibrio Velocidad de enfriamiento: enfria(T)
¿Cómo reducir temperatura?
44
M. L. López Vallejo
¿Cuándo hay equilibrio térmico?
Decisivo para una buena implementación Experimentales vs. Dinámicos
Esquema de enfriamiento (ejemplo)
¿Cuándo he alcanzado T∞?
Configuraciones Movimientos
Esquema de enfriamiento 9
nunca
Que refleje perfectamente la calidad de una solución ¿Evaluación incremental?
Conjunto de movimientos 9
Soluciones casi siempre bastante probable
Función de coste
9
nº estados aceptados > un orden de magnitud n
9
nº estados generado > dos órdenes de magnitud n
Velocidad de enfriamiento: enfria(T) 9
T
Tnew = Told * 0.9
Criterio de parada: congelado ¿Cuándo se ha parado el sistema?
Criterio de parada 9
45
M. L. López Vallejo
3 bucles consecutivos sin mejora 46
M. L. López Vallejo
Ejemplo de funcionamiento
Análisis
Cost Function
800
Polémico: ¡No es la panacea!
600 400
200
9
0 1
51
101
151
201
251
301
351
9
401
40000
Temperature
Ventajas Escapa de mínimos locales Independiente de la solución inicial
Inconvenientes
30000
9
Tiempos de ejecución elevadísimos
20000
9
10000
9
Múltiples parámetros Î Difícil de ajustar No garantiza mínimo global
0 1
M. L. López Vallejo
51
101
151
201
251
301
351
401
47
M. L. López Vallejo
48
8
4.1.2 Programación lineal
Aplicación a partición Hw-Sw
Formulación matemática de un problema de optimización combinatoria “LP solvers” Se reduce a formular inecuaciones Formulación: x Variables 9 9
Maximizar (min) Cumpliendo
c Tx
Ax ≤ a x≥0
Variables: implementación de cada objeto xhi ∈ { 0 , 1 } xsi ∈ { 0 , 1 }
Inecuaciones: Σhai xhi ≤ A Σssixsi ≤ M
Coste Restricciones
Coste y restricciones lineales respecto a x
Variables enteras Î ILP
Σstixsi + Σhtixhi ≤ T
¡Atención!!!
xsi + xhi =1 ...
Objetivo: ????
49
M. L. López Vallejo
4.1.3 Algoritmos genéticos
Seudo-código
Analogía: proceso de evolución en la naturaleza Población de posibles soluciones Codificada en cromosomas Objetivo: nueva generación Proceso de selección 9 9
9
Sobrevive el mejor 010010 110 Cruces 001001 010 Mutaciones 001011000
010010 010 001001 110
51
M. L. López Vallejo
FOR (i=0; i < pop_size; i++) Pop ← Pop U random_cromosoma(); REPEAT { new_pop ← ∅; FOR (i=0; i < num_cruces; i++) { padre1 = select(pop); padre2 = select(pop); cruce (padre1, padre2, hijo1, hijo2, crit); new_pop ← new_pop U {hijo1, hijo2}; } FOR (i=0; i < num_mut; i++) { mutante = select(pop); muta (mutante); new_pop ← new_pop U {mutante}; } new_pop ← new_pop U select_mejores(); pop = new_pop; UNTIL stop(); Selecciona_mejor() } M. L. López Vallejo
Búsqueda tabú 9 9 9 9
Hill-climbing Se mueve al vecino menos costoso Lista tabú: para evitar ciclos Más rápido que recocido
Heurístico Î conocimiento del problema
¿Adaptación o redefinición? 9 9 9
Problema de la mochila (knap-sac) Etc.
9
9
53
Se utilizan unidades de ejecución heterogéneas Medida de calidad más compleja Dificultad en la evaluación incremental ¡Reestructuración completa del algoritmo!!!
Algoritmos más conocidos: 9
M. L. López Vallejo
52
4.2 Adaptación de heurísticos de partición de circuitos
4.1.4 Otros
50
M. L. López Vallejo
Migración de grupos Agrupamiento (clustering)
M. L. López Vallejo
54
9
4.2.1 Migración de grupos
9 9
B
A
Búsqueda local mejorada Se puede escapar de algún mínimo local Procedimiento 9
K&L: funcionamiento B
A
coste
Odenación de nodos por ganancias Intercambia todos los nodos en cada pasada Guarda registro de los mejores movimientos y los realiza
B
A
Dos versiones: 9 9
Kernighan & Lin, implementación básica Fiduccia & Mattheyses: mejora estructura de datos
nuevo coste
55
M. L. López Vallejo
56
M. L. López Vallejo
Seudo-código
F&M: Estructura de datos max
REPEAT { actual_P = mejor_P = Pi; WHILE (hay_nodos_libres(actual_P)){ Obj = SelectMov(actual_P); actual_P = mueve_y_fija(actual_P, Obj); ActualizaCostes(actual_P, Obj); mejor_P = MenorCoste(actual_P,mejor_P); } } UNTIL (Coste(mejor_P) > coste(actual_P));
C
vé értice
v min
1
v
vé értice
2
v
3
v
n
C
Bucket array 57
M. L. López Vallejo
M. L. López Vallejo
Adaptación
Análisis de migración de grupos
Esquema de control: se conserva
Ventajas 9
Aspectos de nivel de sistema
n M. L. López Vallejo
9
Estructura de datos
Función de coste
Clave
Dato
0.345
Nodo7
0.914
Nodo11
…
…
1.467
Nodo4
58
MAPAS: - emulan el bucket array - claves reales - acceso rápido
59
Inconvenientes 9
9
Tiempos de ejecución bajos Escapa de algunos mínimos locales
Muy dependiente de la solución inicial Irregular No garantiza mínimo global
Aplicación: Refinamiento de otras técnicas
M. L. López Vallejo
60
10
4.2.2 Técnicas de agrupamiento
Algoritmo constructivo Elementos clave: 9
9
Fundamentos
Semilla
A 10
B
5
Función de proximidad: métrica que sirve para agrupar objetos Matriz de proximidad
C
3
AB CDE A B 10 C 57D 03 7E 30 0 8-
de corte 3
7
b) Matriz de proximidad
D
Árbol de agrupaciones: representación del proceso
Líínea
7
A
B
D
C
E
8
9
Línea de corte: determina el resultado final
E a) Objetos y proximidades originales
61
M. L. López Vallejo
62
M. L. López Vallejo
Seudo-código
Modificaciones
G: grafo, G = (V,A) C: matriz de proximidad, C = {cij | 1 T ?
Posible Solució ón
∑ st n + ∑ st m
v n ∈ pi
¿Ap > A ?
SI
NO
vm ∈ p j
¿Mp > M ?
ht k = max{ ht n with vn ∈ pi ∪ p j }
SI
HwP1 A1
<
HwP2 A2
<
HwP3 A3
Sw
NO
ht k = max{ t end (vn )} − min{ t start (vn )} − tidle SOLUCIÓ ÓN
67
M. L. López Vallejo
Funcionamiento
Area y latencia normalizadas
Análisis de agrupamiento
Area Latencia Restricciones
1.6
68
M. L. López Vallejo
Ventajas 9
Tiempos de ejecución muy bajos
1.4
1.2
Inconvenientes 9
1
Muy dependiente de las restricciones
Irregular
0.8
0.6
Aplicación: partición inicial de calidad
0.4 0.2
¡Agrupamiento + Migración de grupos!
0 0
5
10 Nºde iteraciones
15
20
M. L. López Vallejo
69
M. L. López Vallejo
4.3 Técnicas de Inteligencia Artificial
70
Qué es un Sistema Experto
Fundamentos: 9
• Sistema basado en el conocimiento (experto)
Sistema basado en conocimiento – Emula la forma de pensar de un experto – Se aprovecha el conocimiento adquirido por otros – Trabajo al nivel del conocimiento
9
• El conocimiento se puede estructurar mediante reglas algorítmicas: if A then B
Lógica borrosa
• Componentes principales:
– Interfaz con humanos. Lenguaje del experto – Modelado de parámetros imprecisos – Control de matices 9
9 9
y
Metodología CommonKADS
Motor de Inferencia Base de conocimiento
Ejemplo: CLIPS
– Soporte para el diseño y construcción del sistema experto – Librería de PSMs M. L. López Vallejo
71
M. L. López Vallejo
72
12
Sistema Experto: estructura
¿Por qué Lógica borrosa?
El diseñador experto utiliza expresiones en lenguaje natural utilidad de las variables lingüísticas.
Se manejan magnitudes imprecisas, vagas, inciertas ambiguas o inexactas: estimaciones, tendencias, etc.
M. L. López Vallejo
73
Simplicidad y efectividad probada.
M. L. López Vallejo
Lógica borrosa: Fundamentos Conjunto borroso: A = {(x, µ A(x)) / x ∈ X} µ A(x) ∈ [0,1] Función de pertenencia X: Universo de discurso
Variable lingüística: (W,T(W), X, G, M), con 9W nombre de la variable 9 T(W) conjunto de valores lingüísticos 9U universo de discurso 9G regla sintáctica para T(W) 9M regla semántica
Ejemplo: variable lingüística edad 9 W edad 9 T(W) = { niño, joven, maduro, viejo... } 9 U = [0,100] 1,0 0,8
Á(x)
Lógica borrosa: Fundamentos
Niño Joven Maduro Anciano
0,6 0,4 0,2 0,0
0
20
40
60
80
100
Edad (a±os) M. L. López Vallejo
Lógica borrosa: Fundamentos
Relaciones borrosas: representan el grado de presencia o ausencia de interacción entre los elementos de dos conjuntos borrosos mediante una función de pertenencia.
M. L. López Vallejo
Particionado Hw-Sw: planteamiento
Entradas: 9
Composición: AND, OR, NOT...
Reglas IF THEN borrosas: inferencia de mínimo o de producto
Ejemplo: IF área es pequeña AND mejora en tiempo es grande THEN es buen candidato
M. L. López Vallejo
Grafo del sistema con anotaciones: – Estimaciones de tareas (área y tiempo HW, tamaño y tiempo SW, nº medio de ejecuciones, etc). – Estimación de comunicaciones: tiempos de transferencia, frecuencias de comunicaciones, etc.
Ejemplo: x está (muy) cerca de y
76
9
Bases de conocimiento: – Clasificación – Restricciones – Tentativas
Salida: 9
Grafo anotado con implementaciones
M. L. López Vallejo
13
5.3 Aquitectura del Sistema Experto
SHAPES: Módulo clasificador µ(Area) 1,0
Clasificador
Ejemplo:
BC Clasif
0,8 0,6
Pequeña Media Grande
0,4 0,2
Asignador
Evaluador
NO
1,0
Implementación
BC Restricc.
BC Comunic.
Estrategia BC Tentativas
Si
Procesos SW Procesos HW
0,0 0
σ /2
σ
3σ/2
0,6 Umbral 0,43
0,4
Salida
0,2
Solución
Area(%)
0,8
0,0
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15 P16 P17 P18 P19 P20 P21 P22 P23
Procesos 79
M. L. López Vallejo
M. L. López Vallejo
4.4 Comparativa
6.1 Calidad de la solución 25
PRUEBAS: 9
Evaluar los métodos considerando: Coste de la solución
– Calidad de la solución – Tiempo de cálculo 9
Recocido simulado Kernighan&Lin Agrupamiento Sistema experto
20
Tres tipos de ejemplos – Casos de estudio – Universidad de Cincinnati – Generados
15
10
5
9
Influencias: – Función de coste: tipo y parámetros de control – Variantes de los algoritmos
0 REG
81
M. L. López Vallejo
LU
Mean
Laplace
FFT
Ejemplos con sus restricciones
82
M. L. López Vallejo
6.2 Tiempo de CPU
6.3 Comparativa
40
Método
Límite
Grano
Ventajas
Inconvenientes
Aplicación
50
Grueso
Calidad Regularidad
Lento
Referencia
Kernighan & Lin
100
Indiferente
Rápido
Irregular
Agrupamiento
500
Fino
Rápido
Irregular
Preprocesado
75
Grueso
Calidad Regularidad
Interpretado
Partición Hw-Sw Interacción
35
Tiempo de CPU (s)
30
Recocido simulado (x 1/15) Kernighan&Lin
Recocido Simulado
Agrupamiento Sistema experto
25
20
Refinamiento
15
10
5
Sistema experto
0
REG
M. L. López Vallejo
LU
Mean Complejidad
Laplace
Información
FFT
83
M. L. López Vallejo
84
14
5. Revisión de trabajos clásicos Entorno Especificación
1. Definición del problema
HardwareC
Vulcan
2. Caracterización 3. Modelado 4. Técnicas de partición Hw-Sw 5. Revisió Revisión de trabajos clá clásicos 6. Nuevos enfoques
Aplicación Grano Datos
Cosyma Subconjunto C
Datos
Ptolemy Silage
Tiempo Real
SpechCharts
Vahid
C extendido
Castle
Control -
7. Conclusiones CADLab VHDL
85
M. L. López Vallejo
Control
Fino
Algoritmo Mejora
(Instruc.) Iterativa
Formato Intermed. DFGs
Fino
Recocido
Árbol
(BSB)
Simulado
Sintáctico
Grueso
GCLP
(tareas)
(constr.)
Grueso (tareas) Grueso
Heurísticos Program.
(función) Posibilística Grueso
CDFG
Arquitectura Estándar Estándar Sistema empotrado
SLIF
Estándar
-
Estándar
Rec. Simul.
Grafo de
(función) Búsq. Tabú
Procesos
Estándar
86
M. L. López Vallejo
5. Revisión de trabajos clásicos (cont.) Entorno Especificación
Aplicación Grano
Algoritmo
DDEL
C y VHDL
Datos
Grueso (tareas)
Wolf
Orientada a objetos
Tiempo Real
Grueso (tareas)
Polis
Esterel
Sistemas Reactivos
Grueso (bloque)
Tiempo Real
Fino Manual (instruc.)
Telecomunicación
Fino Manual (instruc.)
Genético Heurístico
Formato
Arquitectura
1. Definición del problema
DAG
Estándar
2. Caracterización
Grafo de Tareas
Escalable
CFSM
Estándar
3. Modelado 4. Técnicas de partición Hw-Sw 5. Revisión de trabajos clásicos
-
Sistema Empotrado
6. Nuevos enfoques
-
Sistema Empotrado
7. Conclusiones
Intermed.
Sin partición automática
Chinook Verilog IMEC
VHDL y C++
Manual
87
M. L. López Vallejo
6.1 Dynamic HW-SW partitioning: a first approach
6. Nuevos enfoques 1. Dynamic HW-SW partitioning: a first approach G.M. Stitt, R. Lysecky F. Vahid. DAC’03
Motivación 9
Department of Computer Science and Engineering University of California, Riverside
Optimizaciones dinámicas cada vez más en uso – Optimizaciones dinámicas de software – Transmeta Crusoe:
2. Physically-aware HW-SW Partitioning For Reconfigurable Architectures with Partial Dynamic Reconfiguration
z
Dynamic code morphing
– Compilación “Just In Time” (lenguajes interpretados)
S. Banerjee, E. Bozorgzadeh, N. Dutt Center for Embedded Computer Systems (CECS) University of California, Irvine
Ventajas 9
Optimizaciones transparentes – Sin esfuerzo del diseñador – Sin restricciones de herramientas
3. Co-síntesis de sistemas empotrados: FLECOS
9
J.M. Moya Fernández UPM M. L. López Vallejo
88
M. L. López Vallejo
89
Se adapta al uso actual
M. L. López Vallejo
90
15
Introducción
Introducción
Desventajas de las optimizaciones dinámicas actuales 9
Se limitan a optimizaciones software – Aceleración limitada (1.1x a 1.3x)
Idealmente, se puede realizar partición HW-SW dinámicamente:
Como alternativa, se puede realizar hw/sw partitioning
9
9
Se consiguen elevadas aceleraciones (2x a 10x) 9 Sin embargo, optimizaciones dinámicas no existían hasta ahora
– Soporta todos los lenguajes/herramientas – La mayoría de enfoques previos incluyen flujos complejos de herramientas
Sw
Profiler
______ ______ ______
Partición transparente
9
Se consiguen mejores resultados que con optimizaciones software
9
Se adapta al uso actual
Critical Regions
– >2x aceleración, ahorro energético Sw
______ ______ ______
Hw
______ ______ ______
Es necesario una arquitectura apropiada 9
Processor
Con un procesador y lógica reconfigurable
ASIC/FPGA
91
M. L. López Vallejo
Arquitectura destino
Ideas básicas
Plataformas con Microprocesador/FPGA integrado 9
El binario se analiza (profiling) y se identifican candidatos hardware 9 Las regiones identificadas se “decompilan” en CDFG 9 CDFG se sintetiza a hardware 9 El binario se actualiza para utilizar el hardware
Ejemplos 9
Xilinx Virtex II Pro, Triscend E5/A7, Altera Excalibur, Atmel FPSLIC
La partición dinámica se hace más factible 9
Sin embargo, la partición se debe realizar a nivel binario
Processor
Processor
FPGA
FPGA
1990s
2003
M. L. López Vallejo
93
Partición Hw/Sw dinámica: Funcionamiento add add add MicroMicroadd processor processor add add MicroMicroadd add processor processor add add add add Dynamic add add Partitioning add Module add add add add add add Memory SW add add add
Binary
Profiling
Binary Updater
Decompilation
Ventajas frente a partición de código fuente 9
Soporta cualquier lenguaje/compilador
9
Mejor estimación de prestaciones y tamaño de código software
Permite la partición HW-SW dinámica
Hw Exploration
Behavioral Synthesis Updated Binary
Processor
Netlist
FPGA
94
M. L. López Vallejo
Partición Hw/Sw dinámica: Funcionamiento beq beq beq MicroMicrobeq processor processor beq beq MicroMicrobeq beq processor processor beq beq beq beq Dynamic beq beq Partitioning beq Module beq beq beq beq beq beq Memory SW beq beq beq
Configurable Logic
SW
Configurable Logic
SW
_________ _________ _________
M. L. López Vallejo
Partición hw/sw a nivel binario 9
Comunicación más eficiente, menor tamaño – Mayores prestaciones, bajo consumo
92
M. L. López Vallejo
_________ _________ _________
95
M. L. López Vallejo
96
16
Partición Hw/Sw dinámica: Funcionamiento add add add MicroMicroadd processor processor add add MicroMicroadd add processor processor add add add add Dynamic add addadd add Partitioning add Module add add add add add add Memory SW add add add
Partición Hw/Sw dinámica: Funcionamiento beq beq beq MicroMicrobeq processor processor beq beq MicroMicrobeq beq processor processor beq beq beq beq Dynamic beq beqbeq beq Partitioning beq Module beq beq beq beq beq beq Memory SW beq beq beq
Configurable Logic
SW
SW
_________ _________ _________
_________ _________ _________
97
M. L. López Vallejo
98
M. L. López Vallejo
Partición Hw/Sw dinámica: Funcionamiento
Partición Hw/Sw dinámica: Funcionamiento
MicroMicroprocessor processor
MicroMicroprocessor processor
MicroMicroprocessor processor
MicroMicroprocessor processor
Dynamic Partitioning Module
SW SW SW SW
Configurable Logic
Dynamic Partitioning Module
HW HHW WHHW WHHW W
SW Memory SW
SW SW SW
Configurable Logic
Frequent Loops
Memory SW
SW
_________ _________ _________
Configurable Logic
SW
_________ _________ _________
Frequent Loops
99
M. L. López Vallejo
Módulo de Partición Dinámica
MicroMicroprocessor processor MicroMicroprocessor processor
Implementa las herramientas de partición “on chip” 9
Configurable Logic
Dynamic Partitioning Module
SW HW/SW
80
20
Memory SW
Profiler, compilador de partición, síntesis, place&route SW Source
MicroMicroprocessor processor
Profiler
MicroMicroprocessor processor
60 40
Frequent Loops
100
M. L. López Vallejo
Partición Hw/Sw dinámica: Funcionamiento
100
Frequent Loops
0
Time
Partitioning Compiler
Energy
SW Binary
Synthesis
Dynamic Partitioning Module
Configurable Logic
Place&Route
SW
_________ _________ _________
M. L. López Vallejo
HW
Frequent Loops
101
M. L. López Vallejo
Memory
102
17
Módulo de Partición Dinámica
Arquitectura del sistema
Herramientas de síntesis y P&R on-chip
Microprocesador(s)
9
Normalmente se ejecutan en estaciones de trabajo 9 Idea que “horripila” a la mayoría de los investigadores
Sin embargo, la partición dinámica sólo trabaja con regiones de código pequeñas 9
9
Por lo tanto, podemos desarrollar herramientas ligeras que trabajen específicamente en estos bucles pequeños El overhead de área no es crítico por la tendencia actual (Ley de Moore)
103
M. L. López Vallejo
MicroMicroprocessor processor Configurable Logic
Dynamic Partitioning Module
Memory
104
M. L. López Vallejo
Módulo de Partición Dinámica
MicroMicroprocessor processor
Memoria on-chip Lógica Configurable Módulo de partición dinámica
Caso típico: bucles internos de pequeño tamaño
MIPS (puede haber varios)
Lógica configurable
Detecta dinámicamente bucles activos y los reimplementa en hardware sobre lógica configurable Componentes arquitecturales
Muy simplificada para permitir herramienta P&R ligeras DMA se usa para acceder a memoria Dos registros 9
9
Profiler 9 Procesador y memoria (adicionales)
9
– SOCs pueden tener muchos en cualquier caso – Alternativa: compartir el procesador principal
R0_Input almacena datos desde memoria R1_InOut almacenamiento temporal de datos & retorno a memoria
Configurable Logic Fabric 9 9
Proporciona lógica combinacional Impone ejecución de bucles en un solo ciclo (restricción temporal)
Profiler
DMA
R0_Input
R1_InOut
Memory Configurable Logic Fabric
Partitioning Co-Processor
105
M. L. López Vallejo
Configurable Logic Fabric
Binary
3-input 2-output LUTS rodeadas de matrices de interconexión
Small, Frequent Loops
SM
Switch Matrix
LUT
RT and Logic Synthesis
SM M
M. L. López Vallejo
0 1 2 3
SM
LUT T
LUT UT SM M
SM SM ...
Inputs ...
3 2 1 0
De-compilación Modificación de binario
DMA Configuration
Configurable Logic Fabric
SM M
9
Decompilation
3-input (8 word) 2-output SRAM
Configurable Logic Fabric
El flujo de diseño es diferente del del partición convencional 9
Conecta cables en el mismo canal y distinto lado
LUT 9
Loop Profiling
Matriz de interconexión 9
Herramienta: descripción general
Fabric 9
106
M. L. López Vallejo
3 2 1 0
Inputs
Tech. Mapping Place & Route
SRAM
(8x2)
Binary Modification
Bitfile Creation Updated Binary
0 1 2 3
Outputs
107
HW M. L. López Vallejo
108
18
Profiling de bucles
Non-intrusive profiler 9
Des-compilación recupera información de alto nivel Crea CDFG optimizado
Monitoriza el bus de instrucciones
Overhead muy pequeño 9
Des-compilación
9
Pequeña cache (~16 entradas) y 2,300 puertas lógicas
Menos del 1% overhead en consumo
Partición de binarios ha demostrado resultados similares que partición a nivel de código fuente en muchas aplicaciones [Greg Stitt, Frank Vahid, ICCAD 2002]
To L1 Memory
rd/wr rd/wr Microprocessor
addr
Frequent Loop Cache Controller
addr
data
Se eliminan todas las ineficiencias del conjunto de instrucciones
Frequent Loop Cache
saturation
sbb
data
++
data
109
M. L. López Vallejo
110
M. L. López Vallejo
Configuración DMA
Síntesis RT
Mapping de accesos a memoria en la arquitectura DMA
Mapping operaciones del DFG a componentes de librería hw
Crea expresión booleana para cada bit de salida en el DFG reemplazando componentes hw con las correspondientes expresiones
9
9
Reads/writes Incrementa/decrementa actualización de direcciones 9 Modos de petición single/block 9
Optimiza DFG para DMA 9 9
Sumadores, Comparadores, Multiplexores, Shifters
Elimina cálculo de direcciones Elimina condiciones de contadores/salidas de bucle
1
• Memory Read
r1 +
DMA Read
• Increment Address Read
r1
r2
• Block Request
r1 32-bit adder
r2
+ r3
+
r4
r5
32-bit comparator
……. M. L. López Vallejo
Síntesis lógica
8 <
r4[1]=(r1[1] xor r2[1]) xor carry[0], carry[1]= …….
111
M. L. López Vallejo
112
Technology Mapping
Optimiza ecuaciones booleanas desde nivel RT 9
r3
r4[0]=r1[0] xor r2[0], carry[0]=r1[0] and r2[0]
r3
r2 +
Gran oportunidad para la minimización lógica por la utilización de valores inmediatos en el binario
Mapping de operaciones lógica a LUTs de 3-input, 2-output
Simple minimización lógica de 2-niveles 9
Lysecky/Vahid DAC’03 r1
4 +
r2
r2[0] = r1[0] xor 0 xor 0 r2[1] = r1[1] xor 0 xor carry[0] r2[2] = r1[2] xor 1 xor carry[1] r2[3] = r1[3] xor 0 xor carry[2] … M. L. López Vallejo
r2[0] = r1[0] r2[1] = r1[1] xor carry[0] r2[2] = r1[2]’ xor carry[1] r2[3] = r1[3] xor carry[2] …
3-input, 2-output LUTs
113
M. L. López Vallejo
114
19
Placement
Routing
Nodos en el camino crítico se colocan en una fila horizontal única Se construyen dependencias entre los nodos restantes nodes y se colocan 9
2.
Coloca los nodos por encima o debajo de los nodos ya colocados LUT
LUT
LUT
LUT
LUT
LUT
LUT
LUT
LUT
LUT
LUT
LUT
3.
115
M. L. López Vallejo
Algoritmo Greedy 1.
Para cada matriz de interconexión, elegir la dirección que rutar Continuar rutando hasta alcanzar la matriz de interconexión en uso actual Backtrack a la matriz previa, y probar otra dirección
P&R es la tarea más compleja;
Creación del bitfile
Modificación del binario
Combina descripción hardware del P&R con la configuración del DMA en el fichero bitfile 9
116
M. L. López Vallejo
Actualiza el binario de la aplicación para utilizar todo el nuevo hardware 9
Utilizado para inicializar lógica configurable
9
Se reemplaza el bucle por salto código inicialización hw Wisconsin Architectural Research Tool Set (WARTS)
9
Se asume que la memoria es RAM o ROM programable
– EEL (Executable Editing Library) DMA Configuration
HW Netlist
Bitfile Creation
DMA
Bitfile
R0_Input
R1_InOut
Configurable Logic Fabric
loop:
loop:
hw_init:
Load r2, 0(r1)
Jump hw_init
1.
Initialize HW registers
Add r1, r1, 1
..
2.
Enable HW
Add r3, r3, r2
after_loop:
3.
Blt r1, 8, loop
…..
after_loop: …..
117
M. L. López Vallejo
Ejecutada en SimpleScalar
M. L. López Vallejo
452
0.05
4,695
88
360
1.04
118
Información de Benchmarks Powerstone (Brev, g3fax1&2) NetBench (url) 9 Kernel de minimización lógica (logmin)
Resultados 9
55% de tiempo total en bucles que se llevan a hardware Aceleración ideal de 2.8 9 Estos bucles eran sólo 2.4% del tamaño de la aplicación original 9
Code Binary Data Size size size Time (Lines) (Kbytes) (Kbytes) (s) 125
Jump to after_loop
9
– Tiempo total de ejecución: 1.09 segundos – Requiere menos de ½ megabyte de RAM – Tamaño de código mucho más pequeño que herramientas estándar de síntesis
7,203
5.
9
Resultados
Tool Decom pilation DMA Config. RT Synthes is Logic Synthes is Tech. Mapping Place & Route
Store any results
Resultados Experimentales
– Similar al conjunto de instrucciones de MIPS – Usa reloj de 60 MHz (como el dispositivo A7 de Triscend)
Woken up by HW interrupt
4.
M. L. López Vallejo
Pruebas de la herramienta
Shutdown processor •
Exam ple brev g3fax1 g3fax2 url logm in 119
M. L. López Vallejo
Total Loop Loop Loop Ideal Ins Ins Tim e% Size% Speedup 992 104 70.0% 10.5% 3.3 1094 6 31.4% 0.5% 1.5 1094 6 31.2% 0.5% 1.5 13526 17 79.9% 0.1% 5.0 8968 38 63.8% 0.4% 2.8 Avg: 55.3% 2.4% 2.8
120
20
Resultados Experimentales (cont.)
Análisis de este enfoque
Resultados
9
Cosigue aceleración media de 2.6, cerca del ideal 2.8 9 Bucles hardware 20X más rápidos que bucles software
9
Transparente al usuario Los diseñadores consiguen aceleración sólo con escribir software 9 Menor calidad que otros enfoques, por lo que sólo se recomienda para cuando la transparencia es crítica (¡muy a menudo!) 9
Incluso con arquitecturas y herramientas sencillas se consiguen aceleraciones
Ex a m ple brev g3fax1 g3fax2 url logmin
Sw Hw Loop Loop Sw /Hw Spe e d Tim e Tim e Tim e up 0.03 0.001 0.02 3.1 7.35 0.82 16.98 1.4 7.39 1.49 17.61 1.3 303.74 13.29 89.45 4.2 10.42 0.21 6.12 2.7 65.78 3.16 26.03 2.6
Sw Tim e 0.05 23.50 23.50 379.90 16.32 Avg:
Desventajas 9
Coste en área muy elevado Arquitectura destino muy poco real (muchas limitaciones) 9 Simplificaciones excesivas (no concurrencia, patrones de acceso a memoria limitados, ...) 9 Aspectos no muy claros (des-compilación, P&R,...) 9
121
M. L. López Vallejo
Ventajas de la partición hardware/software dinámica
6.2 Physically-aware HW-SW Partitioning For Reconfigurable Architectures with Partial RTR
Planteamiento (cont.)
Design Specification Partial Dynamic Reconfiguration (RTR)
T1
T2
T4
T3
T6
HW
….
HW
(Partial RTR)
Objetivo:
Flujo de CoCodiseñ diseño
Communication
SW
T5
Reuso hardware Î Mejores prestaciones M
Shared M
M
HW
I/f
P
Plataforma HW-SW
Task Dependency graph
Partitioning
SW
122
M. L. López Vallejo
Minimizar el tiempo de ejecución de la aplicación (schedule length) (Mapping de cada tarea a Hardware o Software) 123
M. L. López Vallejo
Arquitectura reconfigurable dinámicamente
124
M. L. López Vallejo
Placement de línea crítico: ejemplo
Off-chip memory
T1
Width C1
C2
C3
C4
Execution time
Height
Contexto sencillo Basado en columnas
T1
T2
T4
On-chip shared memory CLB
T3
T3 T2 t2 T4
Partial RTR Simple example of infeasibility
Tj Task Ti M. L. López Vallejo
Width 125
M. L. López Vallejo
126
21
Placement de línea crítico: ejemplo detallado
Placement de línea crítico: ejemplo Width
1
C2
C3
T1
C4
C2
C1
T3 T2 t2
Execution time
Execution time
C1
C1 C2 C3 C4 C5 C6 C7 C8 C9
Width C3
C4
2 3 4
T1
5 6 7 8
T3 T2
t2
T4
Imposible
T4
9 10
Posible
Planificación y placement simultáneospara garantizar feasibility 127
M. L. López Vallejo
Forma de resolverlo z Formulación exacta (ILP: integer linear programming)
Puntos clave en partición HW-SW
Variables clave:
~
Considerar restricciones físicas (colocación de tareas en columnas) como parte integrante del problema
~
xi,j,k , ri,j,k : Tarea i planificada (reconfigurada) en el time-step j,
Hacer prefetch de configuración para ocultar el overhead de reconfiguración ~ Considerar múltiples puntos de implementación de tareas ~
colocada en la FPGA empezando en la columna k Restricciones:
~
optimizaciones del compilador, heterogeneidad Recursos dedicados
(HW-SW partitioning tradicional + contiguous linear placement
(multiplicadores buitl-in)
+ prefetch configuración)
Feasible, solucionesde alta calidad (short schedule length) ~ Para cada tarea, se determina : El punto de implementación adecuado
9
El tiempo de ejecución inicial
9
Ubicación espacial
M. L. López Vallejo
~
~ 129
~
Múltiples puntos de implementación
Basado en KLFM 130
M. L. López Vallejo
Physically-aware List-scheduling z Cada tarea limitada a un punto de implementación
Consideraciones adicionales: Placement en línea
Implementación en CPLEX- extremadamente lenta
z Formulación heurística
KLFM para HW-SW partitioning con RTR parcial ~
128
M. L. López Vallejo
Descripción detallada del problema
9
T10
z Prioridad de tareas HW baseda en consideraciones físicas List-scheduling kernel para selección de siguiente tarea
kernel KLFM modificado para partial RTR
for each schedulable task,
while (more unlocked nodes)
// all parent dependencies satisfied
compute EST (earliest start time of computation)
for each unlocked node
EFT (earliest finish time) = EFT + task execution time
for each non-current implementation point of node
Choose task that maximizes
Calculate makespan by physically-aware list-scheduling
f (EST, path length, width, EFT)
best Node = SELECT NODE
z El cálculo de EST incluye restricciones físicas y de arquitectura
MOVE AND LOCK (best Node, implementation point) UPDATE NEIGHBOURS (best Node) endwhile M. L. López Vallejo
f = - A * width - B * EST + C * (path length) - D * EFT 131
M. L. López Vallejo
132
22
Cálculo de EST: Ejemplo T1
Time C1
T6
T2
C2
C3
Cálculo de EST: aproximación
C5 C6
C4
Proc
1
T4
2 EXECUTE
T3
3
Task 1
E1 R4
5
Task HW time 1 5 2 2 3 2 4 3 5 2 6 3
SW time 23 9 11 14 10 7
HW area 3 3 2 1 2 4
7
R5
RECONFIG Task 5
E4
Gap E3
10
C3
C4
First-fit placement
E2 E1
4
R3
5
Gap E3
7
C65
HW-SW comm (6,5) E5
T2
T1
C5 C6
T3
R4
Buscar la primera tarea que se puede colocar Buscar el primer slot reconfig. sin control (y con espacio disponible)
E4
If (reconfig. finish time < parent finish) EST = parent finish time
6
8 9
C2
1
3
PREFETCH gap
6
Time C1
2
P6
R3
4
T5
Task 6 on SW
E2
(overhead hidden- possible gap)
8 Else 9
133
M. L. López Vallejo
EST = reconfig finish time
134
M. L. López Vallejo
Consideraciones de heterogeneidad
Arquitectura heterogénea Off-chip memory
z A menudo, más eficientes
Height
*** Síntesis de DCT 2-dimensiones en Virtex-II, XC2V2000 On-chip shared memory
*** Placement de línea y restricciones de rutado: CLB
~
Implementación homogénea:
64 MHz
~
Implementación heterogénea:
88 MHz
Heterogénea
multiplicadores built-in (MULTX18) + memoria empotrada (BRAM)
Contexto sencillo
z Recursos limitados, sólo en columnas fijas
Basado en columnas
z La solución se debe ampliar para tratar heterogeneidad
Partial RTR Embedded multipliers, memory M. L. López Vallejo
~
Modificación básica: placement de tareas
~
Enfoque sencillo: añadir descriptor de tipo a cada columna
Width 135
Resultados experimentales
Pruebas de feasibility
z Application graph structures, and, large set of problem instances generated with TGFF ~
Varying Graph size
~
Varying In-degree/Out-degree
~
Varying area constraints
Placement-unaware
(Dick et al, CODES ’98)
Design space TGFF Graph size
20
z Detailed JPEG case study ~
40
60
80
100
(Indegree, Outdegree)
Multiple implementation points, Heterogeneity
(3,4) Area constraint
(5,5)
8 12 16 20 M. L. López Vallejo
(6,7)
136
M. L. López Vallejo
area
Topt
Feasibility
Topt
tg1
10
Y
10
11
tg5
25
NO
26
26
21
Y
21
21
tg7
20
Y
20
20
tg10
27
NO
28
29
FFT
25
Y
25
25
tg11
36
38
41
tg12
14
NO NO
15
18
27
Y
27
27
area
8 12 16 20 137
Theu
Mean-value
4-band eq
(5,5)
Placement-aware
Test
Topt
Exact schedule length with area consideration
Topt
Exact schedule length with columnar placement (new ILP)
M. L. López Vallejo
138
23
Calidad del heurístico
Calidad del heurístico Quality =
Placement-unaware (LPF) Placement-aware
Graph type
Schedule length
LPF: nodes on Longest Path First
8
12
16
20
8
12
16
20
Test 2
Test 1
Experimentos para grafos con 60 nodos 139
M. L. López Vallejo
v20
Execution time (s)
4.75%
4.71%
7.83%
v60
4.93%
8.80%
6.86%
v80
4.09%
10.57%
7.33%
v100
8.96%
11.92%
10.44%
Avg gain
4.30%
9.34%
Aumenta la ganancia al aumentar la restricción de área Aumenta la ganancia con el tamaño del grafo 140
M. L. López Vallejo
Ventajas 9 9 9
90
9
45
100
9 9 9 9
Medido sobre: SunOS 5.8 con procesador sparcv9 502 MHz 141
Partición HW-SW comprensiva que incluye RTR parcial Partición, planificación, placement en línea Múltiples puntos del espacio de diseño en HW Tiempo de ejecución razonable (o(minutos))
Inconvenientes
Graph size (number of vertices)
M. L. López Vallejo
Avg gain
1.68%
180
50
More columns (16, 20) 7.60%
Análisis de este enfoque
O(minutOs) para grafos con 100 nodos, 20 columnas
20
Few columns (8, 12) 1.83%
v40
Tiempo de ejecución
10
(Tlpf – Theu)/Theu * 100
Representación naif del problema Placement muy limitado Calidad del heurístico Puntos oscuros (reconfiguración, múltiples implementaciones, etc.)
M. L. López Vallejo
142
6.3 Co-síntesis de sistemas empotrados: FLECOS
6.3 Flecos
Basado en la idea de compilación HW-SW 9 9
Compilador HW-SW transforma comportamiento en operaciones del procesador virtual Programa = control de la(s) ruta(s) de datos. – Control jerárquico. – Ruta de datos repartida en subsistemas. – Sincronización incluída en operaciones.
9
M. L. López Vallejo
143
Optimizador define la correspondencia entre comportamiento y operaciones de la ruta de datos, con los criterios definidos por el usuario.
M. L. López Vallejo
144
24
Recursos homogéneos
Recursos homogéneos
145
M. L. López Vallejo
146
M. L. López Vallejo
Recursos homogéneos
Co-Síntesis: análisis
Ventajas 9
Flexibilidad en la especificación Reutilización 9 Trabajo en grupo 9
9 9
Interfaces homogéneas a los recursos Desacoplo de aspectos por dominios de conocimiento
Limitaciones procesador virtual 9
Cambios obligan a recompilar Composición limitada 9 No escala bien 9
M. L. López Vallejo
147
Limitaciones procesador virtual
148
M. L. López Vallejo
Proceso de diseño
Limitaciones procesador virtual 9
Cambios obligan a recompilar Composición limitada 9 No escala bien 9
Solución: 9
Definición de “Cajas” (boxes) que cumplen la misma función que el Sistema Operativo
M. L. López Vallejo
149
M. L. López Vallejo
150
25
Co-Síntesis: Análisis
7. Conclusiones
Unificación del diseño de sistemas HW y SW 9
Interfaz homogénea: procesador virtual y sistema operativo HW-SW 9 Especificación y compilación conjunta de HW y SW
Análisis de partición Hw-Sw: conocimiento
Formulación del problema: base 9
Ortogonalización por dominios de conocimiento
9
9
“Comportamiento + arquitectura + optimizador”: frente a refinado iterativo 9 “Aplicación + abstracciones + sistema operativo”: frente a “computación + comunicación”
Escalabilidad
Modelado Función de coste
Implementaciones clásicas y más innovadoras
Es un problema aún abierto
9
Composición de unidades arquitecturales con procesadores virtuales. 9 Composición funcional de recursos con sistema operativo.
151
M. L. López Vallejo
Vahid: On-chip Logic Minimization
Dynamic Hardware/Software Partitioning
JIT compilation for FPGAs 9
1 Initialize
Minimizer
I$
Proc.
MEM
D$
2 Execute
9
Minimizer
3
Indicate Completion
ARM7
152
M. L. López Vallejo
Detecta dinámicamente bucles ejecutados frequentemente y re-implementa los bucles software usando lógica configurable on-chip Requiere herramientas de síntesis lógica para sistemas empotrados Profiler
DMA Warp Processor
Dynamic Partitioning Module
MEM On-chip Minimizer
Warp Processor
System-On-Chip
153
M. L. López Vallejo
1,4
Codesign ROCM Results
(Execution Time)
(Energy Consumption)
HW/SW (200/75 MHz)
1,0 0,8 0,6 0,4 0,2
M. L. López Vallejo
154
• Average energy reduction of 59.2%
SW (75 MHz)
IP Routing Table ACL Reduction Reduction (32) (128)
D$
Configurable Logic
Codesign ROCM Results
1,2
0,0
Warp Processor
I$
Warp Processor
Energy Consumption (mJ)
Execution Time (s)
1,6
MIPS/ ARM
M. L. López Vallejo
• Average speedup of 7.8
1,8
Warp Warp Processor Processor
90 HW/SW (200/75 MHz)
70 60 50 40 30 20 10 0
Logic Synthesis (128)
155
SW (75 MHz)
80
M. L. López Vallejo
IP Routing Table ACL Reduction Reduction (32) (128)
Logic Synthesis (128)
156
26