Download Divisor de Frecuencias en Hardware Evolutivo

Divisor de Frecuencias en Hardware Evolutivo
Christian José Devia1
[email protected]
José Marcio Luna2
[email protected]
Alvaro Betancourt MIng, MSc3
[email protected]
RESUMEN
En el presente articulo se describe el desarrollo de una plataforma experimental en hardware evolutivo (Evolvable Hardware, EHW) dentro del proyecto DEEP (Development of an Experimental Evolvable Hardware Platform).
Se expone el análisis de los primeros resultados obtenidos durante la evaluación de la plataforma a través de la implementación de un divisor de frecuencias evolutivo.
Palabras Claves
Hardware Evolutivo, Algoritmos Genéticos, Divisor de Frecuencia, FPGA.
1 Estudiante. Universidad Distrital. Facultad de Ingeniería. Miembro Grupo LAMIC
2 Estudiante. Universidad Distrital. Facultad de Ingeniería. Miembro Grupo LAMIC
3 Profesor. Universidad Distrital. Facultad de Ingeniería. Director Grupo LAMIC
ABSTRACT
This abstract is aimed at describing the development of an experimental platform within Evolvable Hardware (EHW) along the DEEP (Development of an Experimental Evolvable Hardware Platform) project, as well as presenting the analysis of the outcomes reached from the platform evaluation through the implementation of an evolvable frequency divider.
Key Words
Evolvable Hardware, Genetic Algorithms, Frequency Divider, FPGA.
I. INTRODUCCIÓN
En los últimos años, las estrategias bioinspiradas han tomado fuerza en el campo de la ingeniería. Es así como surgen ramas de estudio como la computación evolutiva [1,2,3,4] que imita operadores naturales como la selección, el cruce y la mutación de criaturas para resolver complejos problemas multivariables de forma heurística. Esto, complementado con los últimos desarrollos en dispositivos lógicos programables como las FPGAs (Field Programmable Gate Array) han dado lugar a una novedosa disciplina llamada Hardware Evolutivo (Evolvable Hardware, EHW) [5,6,7]. El EHW es un acercamiento moderno al diseño de circuitos complejos y a la construcción de hardware adaptativo. Varias de las dimensiones del EHW están en pleno proceso de exploración. El proyecto DEEP (Development of an Experimental Evolvable Hardware Platform), se presenta como una propuesta que da comienzo a la experimentación en este novedoso campo dentro de la Universidad Distrital, con el fin de realizar pruebas de tipo académico que permitan examinar su aplicabilidad en el entorno local.
El presente artículo se organiza como sigue: La sección 2, ilustra la metodología utilizada en el desarrollo de la plataforma experimental en EHW, se describen los dos procesos paralelos de diseño que implican un desarrollo de una celda evolutiva sobre FPGA y una librería de instrumentos virtuales que implementan los algoritmos genéticos. En la sección 3 se expone el modo como dichos procesos operan conjuntamente. En la sección 4 se evalúa el desempeño de la plataforma frente al problema concreto de un divisor de frecuencias evolutivo. Se desarrollan una serie de ejemplos cuya finalidad es exponer la incidencia de los operadores genéticos sobre la arquitectura hardware adoptada en la plataforma. Finalmente en la sección 5 se presentan las conclusiones.
II. METODOLOGÍA
Para llevar a cabo el experimento sobre la FPGA, se hizo necesario el diseño de una plataforma experimental en EHW. Dicho diseño se compone de dos partes fundamentales:
•
Desarrollo de una librería de instrumentos virtuales (Virtual Instruments, VI) orientada al diseño, ejecución y evaluación de algoritmos genéticos (AG) bajo el lenguaje de programación gráfica Labview.
•
Diseño de una matriz de celdas evolutivas adecuada para la FPGA, que facilite el monitoreo de la evolución y las conexiones físicas al interior del dispositivo.
2.1. Librería de Instrumentos Virtuales para Algoritmos Genéticos: La librería presenta operadores específicos, seleccionados entre las principales estrategias evolutivas reportadas y aplicadas en problemas de ingeniería [2, 4], por lo tanto, se cuenta con una variedad de soluciones que abarcan una buena cantidad de problemas mediante la combinación de diferentes VIs, y por ende de diferentes estrategias de evolución.
En el VI de generación de población inicial se determinan parámetros de codificación de los individuos, la cual, puede ser de tipo binaria, octal, hexadecimal o decimal, facilitando el proceso de experimentación con diversos tipos de cadenas [4]. Asimismo, los operadores de selección (por ruleta y por muestreo estocástico), cruce (con puntos de cruce variable) y mutación (uniforme y no uniforme) [1,2,4], poseen muchas prestaciones, de tal forma que el usuario accede a diversas opciones para diseñar el AG que mejor se acomode a sus necesidades.
Esta librería ha sido puesta a prueba en la solución de algunos problemas de evolución de software como maximización en funciones bidimensionales con funciones senoidales moduladas, minimización de la función de Ackley y coincidencia de palabras [4], donde se han obtenido buenos resultados en cuanto a precisión en las respuestas, tiempos de convergencia y facilidades de operación hacia el usuario. Esto último se refleja en la interfaz gráfica que dadas las prestaciones de Labview, conducen a que sea muy amigable para el operador y además permite realizar cambios de parámetros fácilmente.
2.2. Diseño de una Matriz de Celdas Evolutivas sobre FPGA.
El circuito evolutivo fue especificado mediante lenguaje de descripción de hardware, VHDL y programado en una FPGA XC4000 de Xilinx [8, 9, 10]. Consiste en una matriz de cuatro celdas y una memoria RAM que contiene las palabras de programación e interconexión de las celdas como se puede observar en la figura 1.
La arquitectura de celda se diseñó de tal forma que mediante un gran número de operaciones lógicas, el proceso evolutivo se lleva a cabo de forma fácil al interior del dispositivo hardware. Cada celda cuenta con tres unidades lógicas, un flip­flop tipo T y un conjunto de multiplexores. Una celda lógica puede realizar 16 operaciones diferentes, determinadas por la palabra de control proveniente de la RAM. Para su programación se requieren 16 bits, lo cual lleva a que el circuito evolutivo quede determinado por una palabra de programación de 64 bits. La figura 2 ilustra el diagrama de la celda propuesta.
Figura 1. Diagrama esquemático del circuito evolutivo. La tabla 1 muestra las operaciones de la unidad lógica :
Tabla 1.
Tabla de operaciones de la Unidad Lógica.
La figura 3 ilustra las conexiones internas finales dentro de la FPGA.
Figura 2.
Diagrama esquemático de una celda.
Figura 3.
Esquema de conexiones internas dentro de la FPGA.
2.3. Funcionamiento Conjunto de la Plataforma
Los módulos de hardware y software descritos anteriormente, trabajan en forma conjunta permitiendo así la evolución intrínseca de hardware mediante la utilización de un AG.
El AG maneja una población fija de individuos de 64 bits, codificados en cadenas hexadecimales, los cuales, son descargados a la FPGA por puerto paralelo [11], para ello se implementó un protocolo de nivel físico que garantiza la sincronía en la transferencia de datos en las dos direcciones del puerto. De esta forma, cada individuo modifica el comportamiento del circuito evolutivo produciendo una salida específica, la cual es realimentada hacia el computador para su posterior análisis en el AG.
Dependiendo del problema planteado se diseña un VI de aptitud, cuya función es tomar la señal de salida de la FPGA y determinar que tan apto resulta el individuo de acuerdo con la solución que aporte su fenotipo. Es decir, dentro de la FPGA se decodifica del genotipo del individuo en su fenotipo. Este dato de aptitud, permite escoger de manera probabilística, a qué individuos durante cada generación le serán aplicados los diversos operadores evolutivos y genéticos.
III. IMPLEMENTACIÓN DE UN DIVISOR DE FRECUENCIAS EVOLUTIVO
La primera propuesta de prueba, para la plataforma experimental en EHW, consiste en llevar a cabo la evolución de un divisor de frecuencias, que partiendo de un tren de pulsos de referencia en la entrada del sistema, permita conseguir arquitecturas digitales que resulten en señales de salida con frecuencias múltiplos de la original. Dichos múltiplos, por tratarse de un divisor de frecuencias, deben encontrarse en un rango comprendido entre 0 y 1. Para todos los experimentos llevados a cabo la señal de entrada consiste en un tren de pulsos a 60 Hz generado dentro de la FPGA. 3.1. Divisor de Frecuencias a ½ de la frecuencia de entrada
Para este caso se busca obtener la arquitectura necesaria para originar una señal de 30 Hz a partir de la señal de 60 Hz de entrada al sistema. Dado que el espacio solución del problema en este caso es grande, se puede concluir que la respuesta deseada puede darse a través de varios individuos, por lo que el problema puede tener muchas soluciones.
Figura 4
Curva de error, Evolución divisor de frecuencias con factor 1/2.
Los parámetros (Factor (de frecuencia) = 0.5, Población (Número de individuos) = 5, Mutación (probabilidad) = 10­0%, Cruce (probabilidad) = 25%) del algoritmo genético y los resultados de la evolución se muestran en la figura 4.
De estos resultados se observa que a partir de la generación 20, la función de error del mejor individuo alcanza el mínimo, conduciendo al resto de la población hacia la optimización de sus valores de aptitud (que en este caso es inversamente proporcional a la función error), como lo demuestra la curva evolutiva promedio de la población y la curva del individuo menos apto.
Para esta prueba el porcentaje de mutación disminuye conforme se avanza en la evolución. A este tipo de mutación se le conoce como mutación no uniforme y se sigue de la ecuación:
(1) donde:
Porcentaje de mutación en la generación t
Porcentaje de mutación inicial
Generación en curso
Número total de Generaciones a evolucionar
Factor de linealidad de la función (para este ejemplo particular su valor es b=1)
Obsérvese la rápida convergencia de este primer experimento. Esto se debe, a que como se había afirmado antes, el espacio solución es amplio, es decir, muchos individuos pueden llevar a la solución de 0,5 veces la frecuencia de entrada. La secuencia numérica hexadecimal que conforma el genotipo del mejor individuo, la señal obtenida y el circuito equivalente interno evolucionado se ilustran en la figura 5: Genotipo = 384C871E51CB4D46h
(a)
(b)
Figura 5
a) Señal obtenida. b)Circuito equivalente del divisor de frecuencias con factor 1/2
Como puede notarse, el circuito no es óptimo, pues para estas pruebas la función de aptitud es independiente de los recursos utilizados dentro de la FPGA
Puede apreciarse que la presencia del flip­flop tipo T con su entrada T en alto y la señal de 60Hz a la entrada de reloj, es la base principal para la división de frecuencias a la mitad.
3.2. Divisor de Frecuencias a ¼ de la frecuencia de entrada
Se presenta un problema de mucha mayor complejidad que el divisor de frecuencias a ½ de la frecuencia de entrada, ya que el espacio solución es muy reducido frente al espacio de exploración del algoritmo, es decir, que existe un menor número de soluciones posibles que satisfagan el problema, y sin embargo, el algoritmo tiene el mismo número de alternativas para explorar. En este caso se procede basándonos en [12] a ejecutar solo los operadores de selección, mutación y reproducción (dejando de lado el operador cruce), para examinar la conducta del proceso evolutivo. Los valores de los parámetros del algoritmo se muestran en la figura 6, con el comportamiento temporal del mismo:
Figura 6
Curva de error, evolución divisor de frecuencias con factor 1/4
Obsérvese como la evolución tarda cerca de 235 generaciones en converger a una respuesta cuando la población es pequeña (5 individuos), puesto que los individuos carecen de variedad.
Se puede notar un “ruido” latente a lo largo de la curva de la función de error promedio, debido a la ausencia de cruce, puesto que el cruce contribuye a la explotación de soluciones [4]. Esto, probablemente puede resultar perjudicial para la convergencia del algoritmo ya que el mejor individuo está propenso a mutar de tal forma que se pierda la solución que brinda su genotipo.
La secuencia numérica hexadecimal que conforma el genotipo del mejor individuo, la señal obtenida y el circuito equivalente interno evolucionado se ilustran en la figura 7:
Genotipo=CFC8DDE955600FD5h
Figura 7
a) Señal obtenida. b)Circuito equivalente del divisor de frecuencias con factor 1/4
Como era de esperarse, la división a ¼ de frecuencia ha encontrado una arquitectura consistente en dos flip­flops consecutivos, que para los propósitos del experimento resultan en un circuito que utiliza menor cantidad de recursos, y corresponde a una de las arquitecturas de división de frecuencias más sencillas que se pueden emplear.
Posteriormente, se obtuvo una mejoría dividiendo frecuencias a ¼ en el desempeño de la plataforma, incrementando el tamaño de la población a 15 individuos e introduciendo el operador cruce. Esto se puede visualizar en la figura 8:
Figura 8
Curva de error, evolución divisor de frecuencias con factor 1/4.
Se tiene una notable mejoría en la convergencia del algoritmo. Nótese que nuevamente la mutación obedece a la ecuación (1), pero esta vez, el factor de linealidad es b=2, lo que ayuda a preservar la solución obtenida en la generación 14, al reducir de manera cuadrática la probabilidad de mutación conforme transcurren las generaciones. A su vez debe observarse cómo la convergencia se logra mucho antes (generación 14 frente a generación 235), ya que la heterogeneidad y número de la población inicial incrementa la capacidad de exploración del algoritmo.
La secuencia numérica hexadecimal que conforma el genotipo del mejor individuo, la señal obtenida y el circuito equivalente interno evolucionado se ilustran en la figura 9:
Genotipo=A4CECAA47996C7D8h
Figura 9
a) Señal obtenida. b)Circuito equivalente del divisor de frecuencias con factor 1/4
Debe notarse en el fenotipo que el ciclo útil de la señal de salida en este caso no corresponde al ciclo útil de la señal de entrada. Esto ocurre porque el algoritmo genético únicamente trabaja en función de la frecuencia requerida en la señal de salida, pero no tiene en cuenta el ciclo útil de la misma con respecto a la de entrada. Sin embargo, aunque el procedimiento de mutación del ejemplo anterior haya dado con una solución con un ciclo útil del 50%, que se asemeja más a la señal de entrada, se debe tener en cuenta que la evolución con el ciclo útil del 25% fue mucho más estable y veloz en su convergencia.
También puede observarse la complejidad del circuito obtenido en comparación con el caso anterior, puesto que recursos tales como, el número de flip­flops y compuertas lógicas es mucho mayor en este caso.
3.3. Divisor de Frecuencias a 1/3 de la frecuencia de entrada
En un circuito digital secuencial como es el caso de las celdas lógicas diseñadas, se esperaría intuitivamente que las frecuencias de las señales de salida fuesen la mitad para el caso, en que la señal de entrada se conectara a la entrada de reloj de un flip­flop tipo T con su entrada T en alto. Asimismo, se esperaría una cuarta parte de la frecuencia en caso de que la señal de salida de un primer flip­flop se conectara al reloj de otro flip­flop tipo T con su entrada T en alto. Así sucesivamente si se conectan n flip­flops en cascada se tendría una fracción de frecuencia final de. La meta en este ejemplo es evolucionar con la arquitectura de celdas planteada a un divisor de frecuencias con factor 1/3. El desempeño de la evolución y sus parámetros se muestran en la figura 10.
Figura 10
Curva de error, evolución divisor de frecuencias con factor 1/3.
Debe notarse que la convergencia del individuo más apto presentó problemas, dadas las difíciles condiciones para que este múltiplo de frecuencia se alcance. Esto ocurre, porque el cambio de algún término de la cadena resulta crítico para mantener el error minimizado. Por lo tanto, es posible aseverar que este caso es el ejemplo más crítico de todos los presentados hasta ahora en la medida en que posee el conjunto solución más pequeño de todos.
Sin embargo, ejecutando una estrategia de EHW que contenga mutación no uniforme con b=2 y con una probabilidad de cruce del 25%, la plataforma resuelve el problema.
La secuencia numérica hexadecimal que conforma el genotipo del mejor individuo, la señal obtenida y el circuito equivalente interno evolucionado se ilustran en la figura 11:
Genotipo=1C5C9E0D319CC730h
Figura 11
a) Señal obtenida. b)Circuito equivalente del divisor de frecuencias con factor 1/3
Nótese que nuevamente el ciclo útil de la señal de salida (66%) es diferente del de la señal de entrada (50%), puesto que como se había explicado, la función de aptitud no depende de este factor.
Una de las hipótesis planteadas para explicar el funcionamiento del circuito mostrado, es que el flip­flop tipo T realimentado con la compuerta NOT, posiblemente se comporta como un oscilador, ya que aunque parezca que posee un estado estable cuando la salida Q se encuentra en 1 y la entrada de reloj permanece en 0, se tiene que durante los cambios de nivel en dichas conexiones se pueden producir pulsos espurios que ponen nuevamente un nivel bajo en la salida Q, resultando en una oscilación permanente a través de la realimentación. Luego, las operaciones lógicas se llevan a cabo entre señales de frecuencias diferentes, y probablemente desfasadas, que concluyen en la obtención de la señal de 20 Hz.a la salida del circuito.
IV. DISCUSIÓN Y CONCLUSIONES
Se han presentado varios experimentos que evalúan el desempeño de una plataforma experimental en EHW haciendo evolución de circuitos digitales en FPGA. Para este caso específico, se evalúa el desempeño de un divisor de frecuencias evolutivo. Como la función de aptitud, no depende del número de recursos a utilizar dentro del dispositivo reconfigurable (FPGA XC4000 de xilinx), los circuitos pueden llegar a ser muy complejos. Para evitar lo anterior, se propone a futuro emplear funciones de penalización proporcionales al número de recursos que cada individuo emplee dentro de la FPGA, es decir, que cada individuo deberá pagar un pequeño valor de su aptitud en la medida en que utilice más compuertas lógicas o registros.
Vale la pena resaltar que en los experimentos de hardware, la búsqueda aleatoria puede conducir a individuos muy aptos, que aporten soluciones apropiadas al problema planteado, pero solo en el caso en que el espacio solución sea lo suficientemente grande para converger y no perder de vista la solución. Inclusive, se pueden obtener muy buenos resultados proponiendo probabilidades de cruce nulas en el AG.
Por último, en experimentos de mayor exigencia como en el último caso, se consiguieron resultados interesantes, que se basan en Albert [7], y se comprueba que la naturaleza ofrece soluciones de ingeniería, planteadas sobre un modelo sistemático de diseño evolutivo que está fuera de los paradigmas y modelos conceptuales humanos, y que son mucho más generalizados, es decir, que dentro de los sistemas científicos tradicionales el espacio solución propuesto por los métodos clásicos de optimización, es más reducido que el propuesto por una metodología basada en estrategias bioinspiradas.
REFERENCIAS BIBLIOGRAFICAS
[1]MARTINEZ José, ROJAS Sergio. “Introducción a la Informática Evolutiva”. Ed Universidad Nacional de Colombia. 1999. 186p
[2]CERROLAZA Miguel. “Algoritmos de Optimización Estructural Basados en Simulación Genética”, Ed. Universidad Central de Venezuela. Caracas. 1996. 163p
[3]FALKENAUER Emanuel. “Genetic Algorithms and Engrouping Problems”. Ed. John Wiley. 1998. 220p
[4]MITSUO Gen. “Genetic Algorithms and Engineering Problems”. Ed John Wiley. 1997. 411p
[5]YAO Xin, HIGUCHI Tetsuya. “Promises and Challenges of Evolvable Hardware”. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews. 1999
[6]TIMOTHY G.W. GORDON, Peter, BENTLEY, J. “On Evolvable Hardware”. 2002
[7]ALBERT David. “Evolutionary Hardware Overview”. 1997
[8] XC4000E and XC4000X Series Field Programmable Gate Arrays May 14, 1999 (Version 1.6) Product Specification Rev. 1 Second Quarter 2000DataSource CD­
ROM.
[9]XC4000E and XC4000X Series Field Programmable Gate Arrays XC4000XL Electrical Specification. Rev. 1 Second Quarter 2000 DataSource CD­ROM
[10]XC4000XLA/XV Field Programmable Gate Arrays DS015 (v1.3) October 18, 1999 Product Specification. Rev. 1 Second Quarter 2000DataSource CD­ROM.
[11]PEACOCK, Craig. “Interfacing the Standard Parallel Port”. http://www.senet.com.au/~cpeacock
[12]KROHLING, R. ZHOU, Y.TYRRELL, M. “Evolving FPGA­based robot controllers using an evolutionary algorithm”.