Implementación de Fista en una FPGA para la resolución de problemas QP

Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería Electrónica Robótica y Mecatrónica Implementación de Fista en una FPGA para la resolución de problemas QP Autor: Andreu Morro Gallego Tutores: Juan Moreno Nadales y Pablo Krupa Dpto. Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo Fin de Grado Ingeniería Electrónica Robótica y Mecatrónica Implementación de Fista en una FPGA para la resolución de problemas QP Autor: Andreu Morro Gallego Tutores: Juan Moreno Nadales Pablo Krupa Dpto. Ingeniería de sistemas y automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo Fin de Grado: Implementación de Fista en una FPGA para la resolución de problemas QP Autor: Andreu Morro Gallego Tutores: Juan Moreno Nadales y Pablo Krupa El tribunal nombrado para juzgar el Trabajo arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2020 El Secretario del Tribunal Agradecimientos Con este trabajo pongo fin a mis estudios en el grado de GIERM en la Escuela Técnica Superior de Ingeniería de Sevilla, y me gustaría aprovechar esta sección para agradecer a todas aquellas personas que me han acompañado estos años. A mi familia, por todo el apoyo y amor que me han dado, y por no haber dudado nunca de mí, incluso en aquellos momentos en los que ni yo mismo me veía capaz. A mis compañeros y amigos, porque todo es más fácil con personas como vosotros. A mis profesores, no solo por enseñarnos lo correspondiente a sus asignaturas, sino también, por habernos hecho crecer como personas durante sus clases, y en especial a mis tutores Juan y Pablo por haberme ayudado y atendido siempre que se lo he pedido. Gracias a todos, desde lo más profundo de mi corazón. Andreu Morro Gallego Sevilla, 2020 Resumen El objetivo de este trabajo es implementar un algoritmo de resolución de problemas de programación cuadrática, llamado FISTA, e implementarlo en una FPGA utilizando síntesis de alto nivel. Para ello veremos que son los problemas de programación cuadrática y una explicación sobre el algoritmo FISTA. Después tendremos una introducción sobre las FPGAs y sus ventajas sobre otros procesadores, para finalizar con una introducción a la síntesis de alto nivel y las ventajas que ofrece este tipo de técnica de diseño. Una vez vistos los dos bloques teóricos veremos todos los pasos de implementación seguidos, empezando por diseñar el algoritmo en MATLAB, para después pasarlo a C y finalmente utilizando Vivado HLS sintetizarlo. Una vez hecho se implementará en la FPGA. Finalizaremos el proyecto con un análisis de los resultados obtenidos en las diferentes etapas de implementación y observaremos la correcta implementación del algoritmo en la FPGA. Figura 4-27 Resumen de la creación del proyecto 36 Figura 4-28 Menú principal de Vivado 37 Figura 4-29 creación de nuevo bloque 37 Figura 4-30 Añadir repositorio 38 Figura 4-31 Selección de carpeta 38 Figura 4-32 Localización del repositorio 39 Figura 4-33 selección del módulo IP 39 Figura 4-34 Añadir módulo IP 40 Figura 4-35 Módulo IP añadido 40 Figura 4-36 conexión del procesador con el módulo IP 41 Figura 4-37 Conexión realizada 41 Figura 4-38 Validación del diseño 42 Figura 4-39 Creación de HDL Wrapper 42 Figura 4-40 selección de HDL Wrapper 43 Figura 4-41 Generación del Bitstream 43 Figura 4-42 selección de opciones Bitstream 43 Figura 5-1 Comparación salidas del algoritmo 46 Figura 5-2 Resultados de la cosimulación 47 Figura 5-4 Estimación uso de la placa 47 Figura 5-5 Finalización del Bitstream 48 Figura 5-6 Conexiones realizadas en la FPGA 48 Figura 5-7 Nivel de conexiones en puertas lógicas 49 Figura 5-9 Análisis de consumo de Energía de la FPGA 50 Figura 5-10 Análisis de consumo de recursos 50 1 1 INTRODUCCIÓN Este TFC trata la resolución de problemas de Programación cuadrática (QP) utilizando el algoritmo FISTA 1 [1] (Fast Iterative Shrinking-Threshold Algorithm) e implementado en una FPGA (Field-Programmable Gate Array). Empezamos respondiendo a dos preguntas: ¿Por qué resolución de problemas QP? Y ¿Por qué implementarlo en una FPGA? Problemas QPs La programación cuadrática (QP) es el nombre que se le da a un procedimiento que minimiza un problema de optimización convexo sujeto a restricciones lineales de igualdad y desigualdad cuya función objetivo es una función cuadrática. La importancia de la programación cuadrática es debida a que un gran número de problemas aparecen de forma natural como cuadráticos, por ejemplo, optimización por mínimos cuadrados, pero además es importante porque aparece como un subproblema frecuentemente para resolver problemas no lineales más complicados [2]. Las técnicas propuestas para solucionar los problemas cuadráticos tienen mucha similitud con la programación lineal. En concreto, en el ámbito de control muchos MPC (model predictive control) se resuelven resolviendo problemas QP, en concreto, los MPC basados en un modelo lineal [3]. Los algoritmos de control basados en MPC requieren resolver problemas de optimización en tiempo real, por lo que resulta de interés el desarrollo de algoritmos de optimización eficientes y su implementación en sistemas embebidos capaces de resolverlos en tiempos suficientemente pequeños. FPGA Los sistemas embebidos 2 constan de componentes de hardware y software diseñados para realizar una función específica y a menudo tienen restricciones de tiempo real o fiabilidad que van mucho más allá de la computación estándar. Para satisfacer estas demandas a nivel de hardware, los sistemas embebidos tradicionales suelen incorporar microcontroladores, procesadores de señales digitales (DSP) o arrays programables de puertas lógicas (FPGA). Respecto al software, tradicionalmente hacen falta varios lenguajes o herramientas para programar o configurar cada elemento de hardware. Como resultado, los equipos de diseño embebido tradicional requieren miembros con numerosos conocimientos en diseño de hardware y software capaces de integrar el hardware y el software en sistemas embebidos típicos. Las FPGAs son chips programables que implementan funcionalidad de hardware personalizado. La llegada de herramientas de diseño de un nivel superior ha permitido a los usuarios que tienen amplia experiencia con el diseño de hardware digital aprovechar la tecnología FPGA. Las ventajas de FPGA son la fiabilidad y el determinismo del hardware sin el coste inicial y la rigidez del diseño de circuitos integrados de aplicación específica (ASIC). Además, las FPGA son más ventajosas que los procesadores multinúcleo que ejecutan muchas menos instrucciones en paralelo que lo que consiguen las FPGA existentes y que requieren pilas de software y controladores más sofisticados, lo que disminuye la fiabilidad en comparación con las FPGAs. Por lo tanto, estas ventajas convierten las FPGAs en el elemento de hardware ideal para la creación rápida de prototipos y para conseguir un alto rendimiento en el diseño embebido. La tecnología FPGA ofrece a los diseñadores una vía más rápida al mercado con menor coste. Además, la capacidad de cargar nueva lógica y redefinir las conexiones en el tejido de la FPGA permite tener en cuenta usos futuros de diseños y beneficiarse 1 FISTA es un algoritmo de resolución de QPs que se explicará en detalle en el bloque 2-Programación cuadrática, concretamente en el apartado 2.7. Algoritmo FISTA 2 Un sistema embebido o empotrado es un sistema de computación diseñado para realizar una o algunas funciones dedicadas. 1 Introducción 2 de actualizaciones más robustas sin necesidad de modificar sustancialmente el hardware. Dentro de los algoritmos de resolución de QPs se ha elegido FISTA porque es un método rápido de primer orden muy utilizado [4]. Por estas razones en este TFC se ha optado por realizar esta implementación. Para implementar el algoritmo en una FPGA primero se ha diseñado en MATLAB, después se ha pasado a C, se ha implementado y simulado en el microprocesador de la placa y finalmente utilizando síntesis de alto nivel (HLS) con la herramienta Vivado HLS se ha creado un módulo de propiedad intelectual (IP) y se ha implementado en la FPGA. Figura 1-1 Proceso de Implementación del algoritmo FISTA El trabajo está dividido en dos bloques teóricos. En el primero llamado 2-Programación Cuadrática veremos primeramente el origen de este, los diferentes métodos de resolución de los problemas QPs y finalmente una explicación del algoritmo FISTA. En el segundo bloque llamada 3-FPGAs veremos una pequeña introducción a lo que son las FPGAs y su arquitectura básica, después comentaremos las principales ventajas que ofrecen las FPGAs frente a otras plataformas y finalmente explicaremos que es la síntesis de alto nivel (HLS) y las ventajas que ofrece. Después en el capítulo 4-Programacion e implementación del algoritmo veremos el diseño del algoritmo tanto en MATLAB como en C, después veremos cómo se ha utilizado Vivado HLS para la síntesis de alto nivel y finalmente implementarlo en la FPGA. Finalmente, en el capítulo 5-Resultados y conclusiones veremos los resultados obtenidos de dicha implementación. Matlab C Verilog 3 2 PROGRAMACIÓN CUADRÁTICA Para comprender mejor la programación cuadrática (QP), vamos a ver primero lo que son los problemas de optimización, puesto que los problemas QP son un tipo de problemas de optimización, para después poder ver en detalle el problema QP que se ha resuelto utilizando el algoritmo FISTA. 2.1. Historia Durante la segunda guerra mundial, la administración militar de Reino Unido llamó a un grupo de científicos de diferentes disciplinas científicas para usar su conocimiento y proveer asistencia tanto en problemas estratégicos, como tácticos de la guerra. Estos resultados obtenidos por los científicos británicos, motivaron a E.E.U.U a empezar actividades similares. La metodología aplicada por estos científicos para alcanzar sus objetivos se llamó O.R. (Operational Research). La investigación operativa, conocida popularmente como O.R. es una adición reciente a un largo listado de herramientas científicas que brindan una nueva perspectiva a muchos problemas de gestión. La investigación operativa agrega mayor sofisticación hacia la resolución de problemas de gestión. Busca la determinación del mejor curso de acción (óptimo) de un problema de decisión bajo el factor limitante de recursos limitados. En consecuencia, O.R. se ha convertido en una herramienta versátil en el campo de gestión y su potencial para uso futuro es muy sustancial. O.R. demuestra una técnica científica eficaz para resolver tales problemas de toma de decisiones de industria y negocios modernos [5]. 2.2. Problema de optimización Una palabra clave asociada con O.R. es “optimización”. Optimización significa determinar el mejor curso de acción entre las diferentes alternativas disponibles en un problema de toma de decisiones. Puede considerarse como un proceso de encontrar el valor óptimo de una función (generalmente llamada función objetivo) bajo un conjunto dado de circunstancias (a menudo llamado “restricciones”). Los problemas de optimización se pueden encontrar en casi todos los ámbitos de actividad humana. Esto ocurre en casi todas las ingenierías como Civil, Mecánica, Eléctrica, Telecomunicación, Química etc. Esto también ocurre en la industria económica y negocios. De hecho, el desarrollo de técnicas de optimización está siendo aplicado en todos los ámbitos donde las decisiones deben ser tomadas en una situación compleja que puede ser representada por un modelo matemático [5]. 2.3. Solución a problemas de optimización La solución de un problema de optimización generalmente implica tres fases: i) fase de modelado, ii) solución del modelo matemático, y iii) validación de los resultados y su implementación. De estos tres, la primera fase es la más importante. Un modelo incorrecto produce una solución incorrecta. Sin embargo, las otras dos fases también son igualmente importantes puesto que proporcionan la base para obtener la solución óptima y su implementación. En la mayoría de los casos, el problema de optimización que nace de una descripción tiene que transformarse en un modelo matemático, a la que una o más de las técnicas disponibles de optimización pueden ser aplicadas [14]. Antiguamente, debido a la disponibilidad limitada de recursos, la tendencia era introducir aproximaciones y supuestos en el modelo matemático, para que pudieran resolverse convenientemente utilizando algunas técnicas de optimización. Sin embargo, la solución de éste no era precisa y el modelo matemático simplificado Programación cuadrática 4 a menudo no cumplía con las especificaciones del usuario. Ésta fue una de las principales razones por las que inicialmente estos métodos no eran muy utilizados. Sin embargo, con la disponibilidad de recursos informáticos en forma de ordenadores personales, y al mismo tiempo el desarrollo de técnicas computacionales más robustas y eficientes de optimización, el escenario ahora ha cambiado [5]. En concreto, en el ámbito de resolución de problemas QP, existen una gran variedad de metodologías de resolución entre las que destacan: • El Método del Punto Interior [6]. • Conjunto Activo [7]. • Lagrangiana Aumentada [8]. • Gradiente Conjugado [9]. • Gradiente proyectado [10]. • Extensiones del algoritmo simplex [7]. 2.4. Descripción del problema QP Consideramos el siguiente problema QP: min 𝑧 1 2𝑧𝑇𝐻𝑧+𝑞𝑇𝑧 (2-1a) 𝑠.𝑎.𝑧∈𝑍 (2-1b) 𝐺𝑧=𝑏 (2-1c) Donde: • 𝑧 ∈ ℝ𝑛𝑧 son las variables de decisión • 𝐺 ∈ ℝ𝑚𝑧𝑥𝑛𝑧. • 𝑏 es un vector real m-dimensional • 𝑞 es un vector real n-dimensional Con las siguientes asunciones realizadas: • La matriz hessiana H ∈ ℝ𝑚𝑧×𝑛𝑧 es diagonal y definida positiva. • 𝑍={𝑧 ∈ ℝ𝑛𝑧 | 𝑧≤𝑧≤𝑧} define un conjunto de restricciones en caja. • 𝑛𝑍>𝑚𝑧 y el rango de G =𝑚𝑧. • Existe 𝑧 ∈𝑟𝑖(𝑍) tal que 𝐺𝑧=𝑏, donde 𝑟𝑖(∙) representa un interior relativo. • Dejando que 𝐽(𝑧)=1 2𝑧𝑡𝐻𝑧+𝑞𝑇𝑧 y 𝑧∗sean la función de coste y solución óptima de las ecuaciones (2-1), respectivamente. Denotamos el coste óptimo 𝐽∗=𝐽(𝑧∗). 5 Implementación de Fista en una FPGA para la resolución de problemas QP 2.5. Algoritmo FISTA Esta sección está basada en el artículo [11]. El algoritmo FISTA es un algoritmo de resolución de QPs perteneciente a la clasificación del gradiente conjugado y basado en el método de Nesterov [1]. Para comprender como funciona el algoritmo FISTA, primeramente, es necesario explicar lo que es la formulación dual. 2.5.1. Formulación Dual Considerando el problema QP expuesto en (2-1) con las asunciones realizadas anteriormente. La función lagrangiana 𝐿∶ ℝ𝑛𝑧×ℝ𝑚𝑧→ℝ, la función dual Ψ∶ ℝ𝑚𝑧→ℝ, y 𝑧(𝜆) se pueden definir como 𝐿(𝑧,𝜆)=1 2𝑧𝑇𝐻𝑧+𝑞𝑇𝑧−𝜆𝑇(𝐺𝑧−𝑏) (2-2) 𝜓(𝜆)=inf 𝑧∈𝑍𝐿(𝑧,𝜆) (2-3) 𝑧(𝜆)=𝑎𝑟𝑔𝑚𝑖𝑛𝑧∈𝑍𝐿(𝑧,𝜆) (2-4) Donde 𝜆 ∈ ℝ𝑚𝑧 es la variable dual. Debido a las asunciones realizadas, se cumplen las condiciones de Slater [12], por lo que se da la dualidad fuerte, es decir, 𝐽∗=𝜓(𝜆∗) y 𝑧∗=𝑧(𝜆∗) con 𝜆∗=𝑎𝑟𝑔𝑚𝑎𝑥 𝜆𝜓(𝜆) (2-5) Definición 1: Dado el problema QP descrito en (2-1) con matriz hessiana 𝐻 ∈𝐷+ 𝑛𝑧 y matriz de restricción de igualdad 𝐺∈ ℝ𝑚𝑧×𝑛𝑧, denotamos 𝑊𝐻 como 𝑊𝐻=𝐺𝐻−1𝐺𝑇 ∈ ℝ𝑚𝑧×𝑚𝑧 (2-6) Con las asunciones realizadas en (2-1) y [13, Lemma 3.1], tenemos que 𝜓(∙) es una función fuertemenete suave, por lo tanto, es continuamente diferenciable con un gradiente Lipschitz. Además, se puede demostrar que el parámetro de suavidad viene dado por la matriz 𝑊𝐻 dada en la definición 1, es decir, que 𝜓(∙) satisface, 𝜓(𝜆+∆𝜆)≥𝜓(𝜆)−∆𝜆𝑇(𝐺𝑧(𝜆)−𝑏)−1 2𝜆𝑇𝑊𝐻∆𝜆 (2-7) Por lo tanto, dado a 𝜆𝑘 un valor de 𝜆𝑘+1 =𝜆𝑘+∆𝜆𝑘 tal que 𝜓(𝜆𝑘+1)≥𝜓(𝜆𝑘) puede ser obtenido tomando ∆𝜆 como solución de ∆𝜆𝑘=argmax ∆λ −∆𝜆𝑇(𝐺(𝑧𝑘)−𝑏)−1 2𝜆𝑇𝑊𝐻∆𝜆 (2-8) Programación cuadrática 6 Cuya solución puede ser obtenida resolviendo el siguiente sistema de ecuaciones 𝑊𝐻∆𝜆𝑘=−(𝐺𝑧(𝜆𝑘)−𝑏) (2-9) El 𝜓(𝜆∗) óptimo es alcanzado cuando 𝜓(𝜆𝑘+1)=𝜓(𝜆𝑘)=𝜓(𝜆∗), que ocurre cuando ∆𝜆=0, O, equivalentemente cuando 𝐺𝑧(𝜆𝑘)−𝑏=0. Pero dado que esta condición no se da en la práctica, tomamos la solución subóptima 𝑧𝑘 que satisface ‖𝐺𝑧(𝜆𝑘)−𝑏‖≤𝜖 (2-10) Siendo 𝜖>0 un parámetro de exactitud y ‖∙‖ cualquier norma. Cabe remarcar que si se mantienen las asunciones realizadas en el aparado (2-1), los elementos de 𝑧(𝜆), llamados como 𝑧(𝜆)𝑖 𝑝𝑎𝑟𝑎 𝑖=1,……𝑛𝑧, se puede calcular resolviendo los siguientes problemas de optimización, ya que no hay acoplamiento de variables 𝑧(𝜆)𝑖: 𝑧(𝜆)𝑖=argmin 𝑧∈ℝ 1 2𝐻𝑖,𝑖𝑧2+(𝑞𝑖−∑𝐺𝑗,𝑖𝜆𝑗)𝑧 𝑚𝑧 𝑗=1 (2-11a) s.a. 𝑧𝑖≤𝑧≤𝑧𝑖 (2-11b) El cual tiene la siguiente solución explicita: 𝑧(𝜆)𝑖=max{min{−(𝑞𝑖−∑𝐺𝑖,𝑗𝜆𝑗 𝑚𝑧 𝑗=1 ) 𝐻𝑖,𝑖 ,𝑧𝑖},𝑧𝑖} (2-17) 2.5.2 Algoritmo Fista Finalmente procedemos a explicar el algoritmo paso a paso: Paso 0: definir 𝜆𝑜, normalmente, 𝜆𝑜=0. Paso 1: inicializar las variables 𝑘=0,𝜂𝑜=𝜆𝑜,𝑡𝑜=1. Paso 2: Repetir. Paso 3: Incrementamos k, 𝑘=𝑘+1. Paso 4: obtener 𝑧(𝜆𝑘−1) utilizando la ecuación (2-17). Paso 5: obtener ∆𝜆𝑘−1. Resolviendo el sistema de ecuaciones (2-9) Paso 6: calcular 𝜂𝑘=𝜆𝑘−1+∆𝜆𝑘−1. Paso 7: Calcular 𝑡𝑘=1 2(1+√1+4𝑡𝑘−1 2). 7 Implementación de Fista en una FPGA para la resolución de problemas QP Paso 8: Calcular 𝜆𝑘=𝜂𝑘+𝑡𝑘−1−1 𝑡𝑘(𝜂𝑘−𝜂𝑘−1). Paso 9: Calcular el residuo Γ=𝐺𝑧(𝜆𝑘)−𝑏. Paso 10: Hasta que ‖Γ‖<𝜖. Salida: 𝑧∗=𝑧(𝜆𝑘). 9 3 FPGA Las FPGAs fueron introducidas hace casi dos décadas y media. Desde entonces han experimentado un rápido crecimiento y se han convertido en un medio de implementación popular para circuitos digitales. Los grandes avances tecnológicos han permitido una mejora en la capacidad lógica de las FPGAs y las ha convertido en un método alternativo de implementación para diseños grandes y complejos. Además, la naturaleza programable de sus recursos lógicos y de enrutamiento ha tenido un gran impacto en la calidad del área, la velocidad y el consumo de energía del dispositivo [14]. 3.1. Introducción Las FPGAs son dispositivos fabricados con silicio que pueden ser programados eléctricamente para convertirse en casi cualquier tipo de circuito digital o sistema. Para producciones de bajo a medio volumen, las FPGAs proveen soluciones más baratas y en menor tiempo que los circuitos integrados de aplicación específica (ASIC) los cuales normalmente requieren muchos recursos tanto de dinero como de tiempo para obtener el primer dispositivo. Mientras que las FPGAs toman menos tiempo para programarse que por ejemplo un ASIC y su precio oscila entre unos cientos o unos miles de dólares. También para variaciones de requerimientos las FPGAs pueden ser parcialmente reconfiguradas, mientras el resto de FPGA sigue ejecutándose. La mayor ventaja que presentas las FPGAs frente a su contraparte los ASICs es la flexibilidad. Esto provoca que las FPGAs sean más grandes y consuman más energía que los ASICs. Estas desventajas surgen en gran parte por la interconexión de enrutamiento que presentan las FPGAs que corresponde casi el 90% del área total de ésta [14]. 3.2. Conceptos básicos sobre las FPGAs Normalmente las FPGAs se componen de: • Bloques de lógica programable (CLB) donde se implementan las funciones lógicas. • Enrutamiento programable que conecta estas funciones lógicas • Bloques de entrada/salida (I/O) que están conectados a estos bloques lógicos a través del enrutamiento interconectado hechos fueran del chip. Un ejemplo de esto puede ver en la figura 3-1, donde las celdas lógicas están interconectadas mediante las fuentes de enrutamiento programable. Los bloques entrada/salida están situados en las periferias de la celda y también están interconectadas mediante las fuentes de enrutamiento. El término “programable/reconfigurable” en las FPGAs hace referencia a la habilidad de implementar nuevas funciones en el chip después de que su fabricación sea completa [15]. Figura 3-1 Esquema de la arquitectura FPGA. FPGA 16 • Asignación: La asignación define el tipo y el número de recursos hardware (por ejemplo, unidades funcionales, componentes de almacenamiento o conectividad) necesarios para satisfacer las limitaciones de diseño. Según la herramienta que se utilice para la síntesis de alto nivel, se pueden agregar algunos componentes durante las etapas de planificación y vinculación. Por ejemplo, los componentes de conectividad. Los componentes son seleccionados de la librería RTL. Es importante seleccionar, al menos una vez, un componente para cada operación en la especificación del modelo. La librería debe incluir las características de los componentes (como área, retraso y potencia). • Planificación: Todas las operaciones requeridas en la especificación del modelo deben programarse en ciclos. Dependiendo del componente funcional al que la operación está mapeada, las operaciones se pueden programar dentro de un ciclo de reloj o para varios ciclos. Las operaciones se pueden encadenar (la salida de una operación alimenta directamente una entrada de otra operación). Las operaciones pueden programarse para ejecutarse en paralelo siempre que no haya dependencias de datos entre ellos y hay recursos suficientes disponible al mismo tiempo. • Vinculación: Cada operación definida en las especificaciones del modelo debe estar vinculada a una de las unidades funcionales capaces de ejecutar la operación. • Generación: Una vez tomadas las decisiones en la etapa de vinculación, planificación y asignación, el objetivo del paso de generación de la arquitectura RTL es aplicar todas las decisiones de diseño tomadas y generar un RTL del modelo sintetizado. 3.7. Vivado HLS Para realizar la síntesis de alto nivel se ha utilizado la herramienta de Xilinx Vivado HLS. Vivado HLS, es la modificación y personalización realizada por Xilinx de las herramientas de SAN AutoESL AutoPilot que a su vez se deriva del entorno XPilot de la Universidad de California Los Ángeles [22][23]. Vivado HLS sintetiza el modelo algorítmico en C/C++ y SystemC generando un bloque de propiedad intelectual (IP) o exportando el código RTL en VHDL/Verilog para síntesis e implementación en una FPGA de Xilinx (figura 3-6). Utiliza el entorno de compilación de código abierto LLVM [24] y se aprovecha de sus continuas optimizaciones. Vivado HLS soporta C, C++ y SystemC, lo que permite realizar la simulación del código C realizando un mínimo conjunto de modificaciones. Vivado HLS realiza la síntesis del algoritmo, donde se produce la transformación de las funciones en la arquitectura RTL, incluyendo las tareas de planificación, asignación y enlazado de unidades funcionales. Estas operaciones afectan a la síntesis de las interfaces y son afectadas a su vez por esta. La síntesis de las interfaces realiza la transformación de los argumentos y parámetros de las funciones en puertos RTL con el protocolo de comunicación elegido para la comunicación con otros bloques del diseño. Afecta a variables globales, argumentos de las funciones de mayor nivel de jerarquía y valores retornados por las funciones. Las principales técnicas de optimización usadas por Vivado HLS son las siguientes: • Optimización del flujo de datos o entre funciones (Dataflow pipelining) • Segmentación de las funciones • Optimización de latencias • Enrollado y desenrollado de bucles • Segmentación de bucles • Modificación de los intervalos de iniciación • Mapeado de arrays a memorias • Limitación o compartición de recursos 17 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 3-6 Flujo de diseño en Vivado FPGA 18 19 4 DISEÑO E IMPLEMENTACIÓN DEL ALGORITMO Tal como se ha explicado en la introducción, el diseño del algoritmo ha pasado por varias etapas antes de poder ser implementando en la placa. A continuación, se van a comentar las características principales del código para cada etapa. 4.1. Programación en MATLAB y C Debido a que tanto el código en C como en MATLAB son muy parecidos se van a explicar juntos en la misma sección comentando las principales diferencias entre ellos. Para evitar la confusión entre los símbolos matemáticos descritos en el apartado 2.6.2 Algoritmo FISTA y el programa en MATLAB y C se ha hecho una tabla de equivalencias entre los símbolos y las variables: Símbolo Matemático Nombre en MATLAB y C 𝜆𝑜 Lambda_k 𝜂𝑜 eta_k 𝑡𝑜 t_k 𝑧(𝜆𝑘−1) z_ka ∆𝜆𝑘−1 deltalambda_ka Γ residuo 𝜖 epsilon 𝑧∗ z_salida 𝑧 UB 𝑧 LB Tabla 4-1 Correspondencia símbolos con programa Para evitar colocar muchas líneas de código se van a comentar las características principales de cada paso del algoritmo. El código completo puede consultarse en el anexo A y en el anexo B siendo los códigos en MATLAB y en C respectivamente. Las variables de entrada del algoritmo son matriz G, matriz H, vector q, vector b, vector UB y vector LB. Los pasos seguidos para el algoritmo FISTA están explicados en el apartado 2.5.2. • El paso 1 es idéntico para los dos códigos y consiste en inicializar las variables lambda_k, k, eta_k y t_k. • Para el paso 2 se ha utilizado un bucle while 3 para los dos códigos. Para MATLAB se ha utilizado la condición de que la norma del residuo sea mayor que la variable épsilon, es decir mientras que la norma 3 El bucle while es un ciclo repetitivo basado en los resultados de una expresión lógica. Diseño e implementación del algoritmo 20 20 del residuo es mayor que el valor de épsilon dado el bucle while se mantiene activo: while(norm(residuo) > epsilon) Para el codigo en C se ha utilizado un bucle while, pero se ha añadido la condición de que el bucle solo se ejecute una serie limitada de veces con la variable kmax. Es el algoritmo puede salir del bucle while de dos maneras diferentes, la primera igual que en MATLAB si la norma del residuo es mayor que la variable epsilon o si se ha alcanzado el número máximo de repeticiones. while((norma > epsilon) && (k < kmax)) • El paso tres simplemente consiste en incrementar la variable k para ambos códigos. k=k+1; • Para el paso cuatro se ha utilizado un doble bucle for 4 en los dos códigos para calcular z_ka como se indica en la ecuación (2-17). La diferencia reside en que en a la hora de calcular el máximo y mínimo en MATLAB se han utilizado las funciones max y min respectivamente, mientras que en C al no contar con estas funciones se ha utilizado el condicional if-else 5 . • El paso cinco consiste en calcular deltalambda_ka resolviendo la ecuación (2-9). En Matlab: Wh=(G/H)*G'; deltalambda_ka=(inv(Wh))*(-(G*z_ka'-b)); Mientras que en C se deben utilizar dobles bucles for para las operaciones matriciales, como puede verse en el anexo B • El paso seis consiste en calcular eta_k y es idéntico para ambos códigos con la salvedad que en C se requiere un bucle for para sumar los dos vectores lambda_ka y deltalambda_ka eta_k=lambda_ka+deltalambda_ka; • El paso siete es idéntico para ambos códigos y consiste en calcular la variable t_k. t_k=(1+sqrt(1+4*t_ka^2))/2; • En el paso ocho calculamos el vector lambda_ka y como en el paso seis en MATLAB es inmediato, mientras que en C requerimos de bucles for. lambda_k=eta_k+((t_ka-1)/t_k)*(eta_k-eta_ka); • El paso nueve consiste en calcular el residuo en MATLAB es inmediato y en C se requieren bucles for para los productos matriciales residuo=G*z_k'-b; • Y finalmente el paso diez consiste en calcular la norma del residuo, para continuar o salir del bucle while, en MATLAB se calcula dentro de la propia condición del bucle con la función norm, mientras que en C se calcula con un bucle for. for(int i=0;i<120;i++){ aux6=aux6+(residuo[i]*residuo[i]); } norma=sqrt(aux6); Si finalmente no se cumplen alguna de las condiciones del bucle while copiamos los valores de z_k al vector z_salida. 4 El bucle for es un bucle que repite un bloque de instrucciones dadas un número predeterminado de veces. 5 El condicional if-else es una estructura que nos posibilita definir las acciones que se deben llevar a cabo si se cumple cierta condición y también determinar las acciones que se deben ejecutar si no se cumple. 21 Implementación de Fista en una FPGA para la resolución de problemas QP 4.2 Implementación utilizando HLS Como se ha comentado anteriormente para realizar la síntesis de alto nivel se ha utilizado la herramienta de Xilinx Vivado HLS y se han seguido las siguientes etapas: • Simulación en el procesador de la placa. • Una vez nos aseguramos que el código en C implementado en el procesador de la placa nos da el mismo resultado que en C procedemos a realizar la cosimulación C/RTL. • Finalmente, una vez hecha la cosimulación y el resultado ha sido satisfactorio procedemos a realizar la síntesis y exportación del módulo IP. 4.2.1 Simulación en el procesador Primeramente, nos dirigimos a la aplicación Vivado HLS en este caso se ha utilizado la versión 2019.2. Pulsamos el botón “create new proyect” como se muestra en la figura 4-1. Figura 4-1 Selección de nuevo proyecto Una vez apretado el botón nos aparecerá una ventana para seleccionar el nombre del proyecto y la localización de este como se muestra en la figura 4-2. Diseño e implementación del algoritmo 22 22 Figura 4-2 Selección de nombre del proyecto y localización Una vez nombrado y localizado nos preguntara si queremos agregar algún archivo. En esta ventana podríamos añadir nuestros archivos de C, pero se ha optado por no añadir ningún archivo y añadirlos más tarde como se explicará a continuación. 23 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 4-3 añadir ficheros Ahora nos aparecerá una ventana (figura 4-4) que nos pregunta que nombre queremos darle a la solución de la síntesis de alto nivel y además podremos seleccionar la placa que queramos apretando en el botón de los tres puntos. Diseño e implementación del algoritmo 24 24 Figura 4-4 selección de nombre de solución HLS Y procedemos a seleccionar la placa explicada en el apartado 3.3. como se muestra en la figura 4-5. Figura 4-5 Selección de la placa Una vez seguidos los pasos correctamente nos aparecerá una ventana (figura 4-6). 25 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 4-6 Pantalla principal Ahora procedemos a crear los archivos de programación para ello arriba en la izquierda en “source” damos clic derecho con el ratón y seleccionamos “new file” y nos preguntará el nombre y la localización del archivo nuevo. Es importante escribir el terminal .cpp después del nombre y guardarlo en el mismo directorio que el proyecto. Repetimos lo mismo para “Test Bench”. Una vez hecho esto hay que explicar la modificación que se han hecho del código en C descrito en el anexo B. Para poder probar la simulación el código se ha dividido en dos, el apartado source contiene el código del algoritmo llamado “Fista.cpp” exactamente igual que en C, el código completo puede consultarse en el anexo C. Las únicas dos diferencias son que el algoritmo FISTA se ha convertido en una función que será llamada en el archivo de Test Bench, proporcionándole las entradas descritas en la sección 4.1 añadiendo épsilon y kmax. void fista_puntofijo(fix_t epsilon, int kmax, fix_t G[filas][columnas], fix_t H[columnas], fix_t UB[filas], fix_t LB[columnas], fix_t b[filas], fix_t q[columnas], fix_t Wh_inv[filas][filas]) y los datos tienen formato de punto fijo. 4.2.1.1 Punto Fijo Las FPGAs utilizan el formato de punto fijo porque reduce el nivel de carga computacional respecto a otros formatos, como por ejemplo el punto flotante. En la figura 4-7 se puede ver cómo está formado un número en punto fijo Diseño e implementación del algoritmo 32 32 Una vez realizada esta tarea podemos seleccionar el botón llamado “Run C Synthesis” en la pantalla principal tal como se muestra en la figura 4-18. Figura 4-18 Ejecutar Síntesis Al terminar la síntesis se nos abrirá una ventana con información de los resultados de la síntesis, que se comentarán en el capítulo 5-resultados, y a la izquierda la solución de la síntesis que contiene los códigos en verilog. Figura 4-19 Resultados de la síntesis Finalmente, si la simulación ha resultado exitosa podemos proceder a exportar el algoritmo y crear el módulo 33 Implementación de Fista en una FPGA para la resolución de problemas QP IP, para ello vamos al icono llamada “export RTL” en el menú principal. Como se muestra en la figura 4-20. Figura 4-20 Exportación RTL Se nos abrirá una ventana (figura 4-21) y debemos seleccionar IP Catalog y el lenguaje verilog Figura 4-21 Selección parámetros exportación Y si se han realizado todos los pasos correctamente ya tenemos nuestro módulo IP lista para implementar en la placa. 4.3. Implementación del módulo IP en la placa y generación del Bitsream Primero de todo nos dirigimos a la aplicación Vivado en este caso la versión Vivado 2019.2 y creamos un nuevo proyecto como en la figura 4-22. Diseño e implementación del algoritmo 34 34 Figura 4-22 Creación de un nuevo proyecto Una vez hecho nos aparecerá una pantalla de presentación, pulsamos en el botón “next” y nos aparecerá una pantalla (figura 4-23) donde debemos nombrar y localizar nuestro nuevo proyecto. Figura 4-23 selección de nombre y ruta del proyecto Apretamos “Next” y nos aparecerá una nueva ventana en la que debemos seleccionar la primera opción RTL_proyect (figura 4-24). 35 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 4-24 Selección RTL_project Apretamos “Next” en las dos siguientes ventanas porque no queremos añadir fuentes ni restricciones (figura 4- 25). Figura 4-25 Selección de fuentes y restricciones Y finalmente tal y como se hizo en Vivado HLS seleccionamos la placa zybo z20 y apretamos “Next” (figura 4-26). Diseño e implementación del algoritmo 36 36 Figura 4-26 selección de la placa Nos aparecerá una ventana con un resumen y si todo es correcto apretamos en “Finish” (figura 4-27). Figura 4-27 Resumen de la creación del proyecto 37 Implementación de Fista en una FPGA para la resolución de problemas QP Finalmente, nos aparecerá una ventana principal (figura 4-28). Figura 4-28 Menú principal de Vivado Ahora procedemos a implementar el módulo IP que creamos anteriormente, primero como se muestra en la figura 4-29 seleccionamos Create block Design. Figura 4-29 creación de nuevo bloque Nos aparecerá una ventana emergente y apretamos “Ok” Y en la ventana de la derecha damos clic derecho con el ratón a “Add Repositoy” (figura 4-30). Diseño e implementación del algoritmo 38 38 Figura 4-30 Añadir repositorio Seleccionamos la carpeta donde guardamos la exportación realizada en Vivado HLS (figura 4-31). Figura 4-31 Selección de carpeta Y el programa nos debería detectar automáticamente el repositorio como se muestra en la figura 4-32. 39 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 4-32 Localización del repositorio Ahora ya podemos buscar y seleccionar nuestro IP como en la figura 4-33. Figura 4-33 selección del módulo IP Ahora en la ventana diagram ya podemos agregar nuestro módulo IP (figura 4-34). Diseño e implementación del algoritmo 40 40 Figura 4-34 Añadir módulo IP Ahora ya tenemos el módulo IP agregado (figura 4-35). Figura 4-35 Módulo IP añadido En el siguiente paso debemos conectar nuestro módulo IP con el procesador zynq de la placa, para ello repetimos el paso anterior. Y seleccionamos la opción “Run Connection Automation” (figura 4-36). 41 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 4-36 conexión del procesador con el módulo IP En la figura 4-37 podemos ver la conexión realizada. Figura 4-37 Conexión realizada Ahora repetimos el mismo proceso para la opción “Run Block Automation”. Una vez hecho validamos el diseño como se muestra en la figura 4-38. resultados y conclusiones 48 48 Figura 5-5 Finalización del Bitstream Se abrirá una ventana en la que podemos ver las conexiones realizadas en el interior de la placa (figura 5-6). Figura 5-6 Conexiones realizadas en la FPGA Si hacemos zoom lo suficiente se pueden llegar a ver las conexiones a nivel de puertas lógicas. 49 Implementación de Fista en una FPGA para la resolución de problemas QP Figura 5-7 Nivel de conexiones en puertas lógicas En la sección “IMPLEMENTATION” de la izquierda podemos ver diferentes análisis realizados tras la implementación en la FPGA. Vamos a destacar dos principalmente que son “Report Power” y “Report utilization” (figura 5-8). Figura 5-8 Características principales tras la implementación En el análisis de consumo de energía podemos ver datos interesantes como son la temperatura máxima que alcanza el chip de la FPGA, o el consumo de energía de esta (Figura 5-9). resultados y conclusiones 50 50 Figura 5-9 Análisis de consumo de Energía de la FPGA Y en el análisis de recursos podemos ver cuanta memoria de la FPGA consume el algoritmo (figura 5-10). Figura 5-10 Análisis de consumo de recursos Como podemos ver hay algunas diferencias con los resultados obtenidos tras la síntesis en Vivado HLS, esto se debe a que en Vivado HLS son estimaciones, mientras que estas son las reales. 5.4 Conclusiones finales Se ha comprobado el correcto funcionamiento del algoritmo tanto en el código de MATLAB y en C y finalmente de la simulación C. Y después se ha comprobado que el diseño RTL ha ofrecido el mismo resultado, finalmente 51 Implementación de Fista en una FPGA para la resolución de problemas QP se ha comprobado que tras la implementación en la FPGA no ha habido problemas de consumo ni de utilización de recurso, por lo tanto, podemos concluir que el algoritmo funciona y se puede implementar sin problemas en la placa real Zybo z20. resultados y conclusiones 52 52 53 Implementación de Fista en una FPGA para la resolución de problemas QP 6 REFERENCIAS [1] BECK, Amir; TEBOULLE, Marc. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2009, vol. 2, no 1, p. 183-202. [2] BADER, B. W. Constrained and unconstrained optimization. 2009. [3] CAMACHO, Eduardo F.; ALBA, Carlos Bordons. Model predictive control. Springer Science & Business Media, 2013. [4] KIM, Donghwan; FESSLER, Jeffrey A. Another look at the fast iterative shrinkage/thresholding algorithm (FISTA). SIAM Journal on Optimization, 2018, vol. 28, no 1, p. 223-250. [5] KHAN, Ashfaq Ahmad. Stochastic Quadratic Programming. 2011. Tesis Doctoral. Aligarh Muslim University. [6] KIM, Seung-Jean, et al. An interior-point method for large-scale l_1-regularized least squares. IEEE journal of selected topics in signal processing, 2007, vol. 1, no 4, p. 606-617. [7] MURTY, Katta G.; YU, Feng-Tien. Linear complementarity, linear and nonlinear programming. Berlin: Heldermann, 1988. [8] DELBOS, Frédéric; GILBERT, Jean Charles. Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems. 2003. [9] DAI, Yu‐Hong. Nonlinear conjugate gradient methods. Wiley Encyclopedia of Operations Research and Management Science, 2010. [10] ROSEN, Jo Bo. The gradient projection method for nonlinear programming. Part I. Linear constraints. Journal of the society for industrial and applied mathematics, 1960, vol. 8, no 1, p. 181-217. [11] KRUPA, Pablo; LIMON, Daniel; ALAMO, Teodoro. Implementation of Model Predictive Control in Programmable Logic Controllers. IEEE Transactions on Control Systems Technology, 2020. [12] BERTSEKAS, Dimitri P. Convex optimization theory. Belmont: Athena Scientific, 2009. [13] BECK, Amir; TEBOULLE, Marc. A fast dual proximal gradient algorithm for convex minimization and applications. Operations Research Letters, 2014, vol. 42, no 1, p. 1-6. [14] FAROOQ, Umer; MARRAKCHI, Zied; MEHREZ, Habib. Tree-based heterogeneous FPGA architectures: application specific exploration and optimization. Springer Science & Business Media, 2012. [15] PANG, Aiken; MEMBREY, Peter. Beginning FPGA: Programming Metal. Apress, 2016. [16] https://reference.digilentinc.com/reference/programmable-logic/zybo-z7/start [17] APARICIO OLMEDO, Aldo Alejandro; PONLUISA MARCALLA, Neiser Fernando. Estudio comparativo de los lenguajes HDL y su aplicación en la implementación del Laboratorio de Sistemas Digitales Avanzados mediante FPGAS en la EIE-CRI. 2014. Tesis de Licenciatura. [18] COUSSY, Philippe; MORAWIEC, Adam (ed.). High-level synthesis: from algorithm to digital circuit. Springer Science & Business Media, 2008. [19] HENDRIKS, Johan, et al. High Level Synthesis: Performance analysis and code optimization. Master thesis of Eindhoven University of Technology, 2012. [20] FINGEROFF, Michael. High-level synthesis: blue book. Xlibris Corporation, 2010. [21] COUSSY, Philippe, et al. An introduction to high-level synthesis. IEEE Design & Test of Computers, 2009, vol. 26, no 4, p. 8-17. [22] CONG, Jason, et al. Platform-based behavior-level and system-level synthesis. En 2006 IEEE International SoC Conference. IEEE, 2006. p. 199-202. [23] CHEN, Deming, et al. xpilot: A platform-based behavioral synthesis system. SRC TechCon, 2005, vol. 5. Referencias 54 54 [24] P CARBALLO, Pedro. Aportaciones a la metodología de diseño basada en Síntesis de Alto Nivel. Aportaciones al diseño de IPs para procesado de eventos complejos y codificación de vídeo. 2016. Tesis Doctoral. 55 Implementación de Fista en una FPGA para la resolución de problemas QP 7 ANEXOS 8.1. Anexo A código del Algoritmo FISTA en MATLAB %Algoritmo FISTA clear all load('QPejemplo.mat') % salida----->valor óptimo de la variable Z %Tambien calcular la variable lambda epsilon=1e-4; %%valores que necesito calcular mz, lambda, mz=rank(G); [m,n]=size(G); %%inicio del algoritmo %paso 1: inicialización de variables lambda_k(1:m)=0; lambda_k=lambda_k'; k=0; eta_k=lambda_k; t_k=1; residuo=1; %%para eliminar warnings z_ka(1:n)=0; z_k=z_ka; %% paso 2:repetir hasta while(norm(residuo) > epsilon) %paso 3 incrementar k k=k+1; lambda_ka=lambda_k; eta_ka=eta_k; t_ka=t_k; %paso 4 obtener z(lambda(k-1)) for i=1:n sum=0; for j=1:1:mz sum=sum+G(j,i)*lambda_ka(j); %z_ka(i)= max(min((-(q(i)-G(j,i)*lambda_ka(j))/H(i,i)),UB(i)),LB(i)); end z_ka(i)= max(min((-(q(i)-sum)/H(i,i)),UB(i)),LB(i)); end Anexos 56 56 %paso 5 obtener deltalambda(k-1) Wh=(G/H)*G'; deltalambda_ka=(inv(Wh))*(-(G*z_ka'-b)); %paso 6 obtener eta(k) eta_k=lambda_ka+deltalambda_ka; %paso 7 calcular t(k) t_k=(1+sqrt(1+4*t_ka^2))/2; %paso 8 calcular lambda(k) lambda_k=eta_k+((t_ka-1)/t_k)*(eta_k-eta_ka); %paso 9 residuo for i=1:n sum=0; for j=1:1:mz sum=sum+G(j,i)*lambda_k(j); %z_k(i)= max(min((-(q(i)-G(j,i)*lambda_k(j))/H(i,i)),UB(i)),LB(i)); end z_k(i)= max(min((-(q(i)-sum)/H(i,i)),UB(i)),LB(i)); end residuo=G*z_k'-b; % paso 10 repetir hasta que norma residuo<=epsilon end z_salida=z_k'; 57 Implementación de Fista en una FPGA para la resolución de problemas QP 8.2. Anexo B Programación en C #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define filas 120 #define columnas 180 float epsilon = 0.0001; int kmax= 25; int main(){ //matriz lambda_k float lambda_k[filas]; float lambda_ka[filas]; float deltalambda_ka[filas]; int k=0; //matriz eta float eta_k[filas]; float eta_ka[filas]; float t_k = 1; float t_ka; float residuo[filas]; float z_k[columnas]; float z_ka[columnas]; float z_salida[columnas]; float norma = 1; float aux; float minimo; // paso 1 inicializacion de variables for(int i=0;i<filas;i++){ lambda_k[i]=0; eta_k[i]=0; } //inicio del algoritmo //paso 2 while((norma > epsilon) && (k < kmax)){ //paso 3 incrementar k k = k+1; printf("k: %d \n",k); //copiamos matrices for(int i=0;i<filas;i++){ Anexos 64 64 sum2=sum2+G[j][i]*lambda_k[j]; } //z_k(i)= max(min((-(q(i)-G(j,i)*lambda_k(j))/H(i,i)),UB(i)),LB(i)); aux=(-(q[i]-sum2))*H[i]; //calculo del minimo y maximo if(aux>UB[i]){ minimo = UB[i]; } else{ minimo = aux; } if(minimo>LB[i]){ z_k[i]=minimo; } else{ z_k[i]=LB[i]; } } //multiplicacion G*z_k' //residuo=G*z_k'-b; fix_t producto5[120]; // Dentro recorremos las filas de la primera (A) for (int i = 0; i < 120; i++) { fix_t aux10 = 0; // Y cada columna de la primera (A) for (int j = 0; j < 180; j++) { // Multiplicamos y sumamos resultado aux10 += G[i][j] * z_k[j]; } // Lo acomodamos dentro del producto producto5[i] = aux10; } for(int i=0;i<120;i++){ residuo[i]=producto5[i]-b[i]; } //paso 9 repetir hasta que norma residuo<=epsilon //printf("empezamos paso 9\n"); fix_t aux6=0; for(int i=0;i<120;i++){ aux6=aux6+(residuo[i]*residuo[i]); } norma=sqrt((float)aux6); //norma =(fix_t) norma; //printf("\n norma: %f \n\n",norma); } 65 Implementación de Fista en una FPGA para la resolución de problemas QP for(int i=0;i<180;i++){ z_salida[i]=z_k[i]; } if(k==kmax){ printf("Numero de iteraciones maximas alcanzadas\n"); } else{ printf("residuo menor que epsilon\n"); } printf("imprimiendo valor de k: %d",k); for(int i=0;i<180;i++){ printf("\n %f",(float)z_salida[i]); } return; } 8.4 Anexo D Código de Fista_TB.cpp #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<ap_fixed.h> #define filas 120 #define columnas 180 typedef ap_fixed<32,9> fix_t; int main() { fista_puntofijo(epsilon,kmax,G,H,UB,LB,b,q,Wh_inv); return 0; }