Introducción

 

            Hardware Evolutivo es una nueva rama de la investigación con inspiración biológica. Nace en 1992 en una tormenta de ideas donde Hugo de Garis le pregunta a un colega de la universidad George Mason, en Virginia, acerca de la posibilidad de diseñar un circuito que pudiera ser utilizado en la evolución de una red neuronal. El ingeniero electrónico de la universidad de George Mason le contó acerca de las FPGA (Field Programmable Gate Array) y de su estructura reprogramable.

            Desde entonces ha habido mucho desarrollo e investigación entorno al tema, en parte por los bajos costos que tienen una de las plataformas de desarrollo del Hardware Evolutivo, las FPGA que en sus versiones más sencillas llegan a valer cerca de 10 dólares (Xilinx Spartan-3 XC3S50).

 

 

Qué es Hardware Evolutivo.

 

Hardware Evolutivo es un circuito electrónico reconfigurable, el cual puede ser cambiado a través de un proceso adaptivo como por ejemplo un algoritmo genético.

 

Existen en el mercado circuitos llamados FPGA (Field Programmable Gate Array) los cuales son la base de muchas investigaciones en el campo del Hardware Evolutivo. Existen muchas empresas dedicadas a producir este tipo de Hardware (Xilinx, Altera, Lattice Semiconductor, etc.).

Un circuito FPGA típico consiste en un arreglo de cientos de bloques reconfigurables, los cuales pueden implementar una gran variedad de funciones digitales lógicas, un conjunto de canales entre las entradas y salidas de éstos bloques, la forma en que están conectados estos canales con los bloques y entre sí puede ser visto como un control a través de interruptores electrónicos, cuyos estados están dados por la memoria del dispositivo. Los bloques que se encuentran en los límites del dispositivo tienen una configuración especial para los interruptores ya que éstos son la interfaz con las conexiones externas.

 

Tipos de Hardware Evolutivo.

 

            El Hardware Evolutivo puede ser dividido en 2 tipos:

Aquellos que utilizan evolución extrínseca donde el algoritmo genético es aplicado en software a una simulación del dispositivo que se está evolucionando.

Y aquellos que utilizan evolución intrínseca donde el algoritmo genético es aplicado al dispositivo mismo.

            Esta clasificación también puede ser considerada como restringida (constrained) o no restringida (unconstrained).

 

 

Hardware evolutivo restringido (Constrained).

 

            La evolución restringida es similar a los otros tipos de Hardware Evolutivo, aunque usualmente mucho más rápido. Parámetros tales como coeficientes de un filtro digital, o los pesos en una red neuronal pueden ser ‘evolucionados’. También es posible diseñar circuitos completos desde niveles de transistor o compuertas.

            Últimamente se está apuntando a crear una pieza inteligente de hardware que puede ser insertada en cualquier sistema y comience a operar sin alguna programación explícita. Sólo necesitaría una realimentación (feedback) de que tan bien está haciendo el trabajo requerido.

            Naturalmente esta técnica  es limitada a problemas en donde la función de fitness es más fácil que resolver el problema directamente.

 

 

Hardware evolutivo no-restringido (Unconstrained).

 

         Mientras la distinción entre intrínseco/extrínseco es irrelevante para evolucionar el software, las diferencias en hardware son evidentes. Con la mayoría de los artefactos de ingeniería, la evolución extrínseca es más rápida que construir varios prototipos del dispositivo,  pero la circuitería puede ser más rápida evolucionando intrínsicamente. Esto tiene el notable potencial de generar diferentes resultados; mientras que al simular, un diseño es naturalmente restringido al modelo del dispositivo realizado por el programador, la evolución intrínseca permite al diseño explotar las características naturales de un dispositivo el cual puede incluso no ser entendido por el programador.

 

 

Figura 1. Evolución Intrínseca.

 

 

            Esto es conocido como evolución no restringida. El concepto fue introducido por Adrian Thompson quién en 1996 evoluciono un discriminador de tonos, usando menos de 40 compuertas lógicas programables sin una señal de clock en una FPGA. Este diseño tan pequeño es notable para este tipo de dispositivo, y hasta ahora no se tiene un entendimiento completo de cómo el dispositivo funciona.  Por ejemplo, un grupo de compuertas no tienen conexión lógica al resto del circuito, a pesar de que este grupo es crucial para su funcionamiento. Se cree que este grupo compuertas de alguna forma modula la alimentación ó influencia las otras conexiones generando un campo magnético.

 

 

Limitaciones.

 

Como todo en la vida el Hardware Evolutivo tiene desventajas.

 

 

Futuras investigaciones.

 

Actualmente la investigación en hardware evolutivo a menudo está enfocada en el concepto biológico de crecimiento.  Esto nace de la necesidad de resolver problemas más complejos. Los problemas complejos requieren grandes circuitos, grandes circuitos requieren grandes genotipos para ser representados asociados a una pequeña probabilidad de encontrar, a través de la evolución, una que funcione. La respuesta  de la naturaleza es el crecimiento - de acuerdo a la cual la evolución diseña una pequeña célula  la cual crece hasta producir un organismo completo. El crecimiento físico del hardware es, hoy en día, imposible, pero el crecimiento de la información es posible. Un ejemplo de esto es el desarrollo del zygote, donde un número de células idénticas intercambian señales en donde la diferenciación está en cada célula realiza diferentes tareas dependiendo de su posición en el organismo.

Otra dirección de investigación es la aplicación de la técnica de la programación genética para especificar la conectividad entre los componentes, en vez de tomar el stream de bits de configuración directamente como un génoma.

Hardware Evolutivo puede ser considerado como una rama de la ingeniería bio-inspirada,  un amplio campo el cual aplica conceptos biológicos  tales como evolución, crecimiento, sistemas inmunes entre otros.

 

 

Algoritmos Genéticos.

 

Como funcionan los Algoritmos Genéticos.

            Se tiene una población inicial de individuos, P(t)={X1,….., Xn}, donde cada individuo representa una solución potencial al problema, que se evalúan según una función de adaptación llamada función de fitness.

            En la iteración t+1 se forma una nueva población seleccionando los individuos mejor adaptados, y modificándolos mediante operadores genéticos para formar nuevas soluciones.

 

Algoritmo:

           

            Comenzar

            t=0

            inicializar P(t)

            evaluar P(t)

            mientras (condición de término) hacer:

                        t= t+1

                        seleccionar P(t) de P(t-1)

                        modificar P(t)

                        evaluar P(t)

            fin

            fin

           

 

            Generalmente los individuos son representados mediante vectores binarios. La selección de estos se puede realizar a través de varios métodos, algunos de ellos son:

 

- Selección Proporcional (Roulette Wheel).

- Selección por Ranking con SUS (Stochastic Universal Sampling).

- Selección por Torneo.

 

 

Estos métodos de selección son elitistas, es decir, los individuos mejores adaptados reemplazan a los peores, pero en la selección con Ranking con SUS es la más utilizada por que permite tener una mayor diversidad de individuos, en un principio, evitando generar una población con copias del mejor individuo lo cual hace que el algoritmo se estanque.

 

 

Los operadores genéticos más utilizados son Crossover o recombinación genética  y  Mutación.

El algoritmo del Crossover es:

 

1.      Escoger dos individuos A y B, aleatoriamente de la población de padres generada por el operador de selección.

2.      Escoger uno o más punto de cruce.

3.      Intercambiar segmentos entre padres y producir descendencia C y D.

A                                                                            B

 

 

 

 

 

 

 

                        C                                                                            D

 

 

 

 

 

 

 

La Mutación consiste en cambiar de 0 a 1 ó de 1 a 0 alguna componente del individuo, este proceso generalmente se hace para cada elemento pero la mutación se lleva a cabo con un probabilidad bajísima, p = 0.1.

 

 

0

 

 

 

 

1

 

 

 

 

FPGA (Field Programmable Gate Array)

 

Un FPGA es un dispositivo semiconductor usado para procesar información digital, similar a un microprocesador. Utiliza un arreglo de compuertas lógicas que pueden ser reprogramadas después de su fabricación.

 

Los FPGAs son generalmente más lentos que su contraparte Circuito Integrado de Aplicación Específica (ASIC), y son menos eficientes en el consumo de energía.

 

Muchos de los FPGAs actuales tienen la capacidad de ser reprogramados en tiempo de ejecución, y esto es la idea de la computación reconfigurable o los sistemas reconfigurables.

 

Arquitectura.

La arquitectura consiste en un arreglo bloques lógicos configurables (CLB) y caminos entre éstas. Dos conectores I/O por cada columna y fila de bloques. Cada camino tiene el mismo número de canales (cada canal tiene una cierta cantidad de cables).

 

Figura 2. Esquema de un FPGA.

 

En la figura 3 se muestra un bloque típico de un FPGA. Consiste en 4 entradas de una LUT (Lookup Table) y un flip-flop.

 

Figura 3. Bloque básico de un FPGA.

 

 

 

La ubicación de los pines de un bloque del FPGA se muestra en la figura 4.

 

Figura 4. Ubicación de los pines del bloque lógico.

 

Las entradas son accesibles por un costado del bloque, mientras que la salida puede ser conectada tanto a los canales que están a la derecha como los que están por debajo del bloque.

 

Cada salida puede ser conectada a cualquier segmento de cable del canal que este adyacente al bloque, tal como lo muestra la figura 5.

 

 

Figura 5. Posibles conexiones de un pin del bloque con algún cable del canal.

 

 

El encaminamiento de la información es segmentada. Esto es, cada segmento de cable abarca sólo un bloque lógico antes de llegar a un bloque interruptor (Switch Box). Activando algunos de los interruptores programables dentro del Switch Box se puede construir un camino más largo.

 

Figura 6. Cableado segmentado entre bloques lógicos.

 

En cada intersección de un camino vertical con uno horizontal, hay un Switch Box. En esta arquitectura, cuando un cable entra a un Switch Box, hay 3 interruptores programables que permiten conectarlo a otros 3 cables del segmento adyacente. La topología de los interruptores de esta arquitectura es la llamada planar.  En esta topología del Switch Box, un cable del canal uno sólo puede ser conectado con alguno de los cables del canal uno del camino adyacente. En la figura 7 se ilustra las conexiones en el Switch Box.

 

Figura 7. Conexiones dentro del Switch Box.

 

 

 

Diseño y Programación del FPGA.

Para definir el comportamiento del FPGA el usuario utiliza un lenguaje llamado HDL (hardware description language) o de un diseño esquemático. Comúnmente los HDL utilizados son VHDL y Verilog. Luego, usando una herramienta de diseño electrónica automatizada, se genera la lista de los bloques y conexiones que se debe utilizar. Esta lista es adecuada a la arquitectura del FPGA usando un proceso llamado called-and-route, usualmente implementado en software por la compañía de la FPGA. El usuario luego valida el mapa, a través de simulaciones y otras metodologías. Una vez que el proceso de diseño y validación están completos, es generado un archivo binario (también, usualmente con un software de la compañía del FPGA) el cual es utilizado para (re)configurar el FPGA.