DESCRIPCIÓN DE UN ARTICULO SOBRE LA UNIDAD SIMD RECONFIGURABLES PARA EL PROCESAMIENTO DE IMAGEN

Para el lector que no esta familiarizado con las unidades SIMD, y otros aspectos que se desarrollan en el artículo, se recopiló una breve información con ejemplos, muy similares a la ejecución del desarrollo de este artículo, lo cual se encuentra posterior al desarrollo de la explicación del artículo en cuestión que sigue a continuación:

         Parte del tema de la introducción y motivación del artículo habla un poco de la reseña histórica y una breve descripción de los procesadores PowerPC, lo cual también se profundiza en este compendio, mas adelante. Para hacer la explicación mas dinámica tomaremos como referencia la siguiente figura 1.

                                                            Virtex-4 FX PowerPC

Figura 1   

        El artículo manifiesta diseñar o implementar a la medida una unidad SIMD dentro de un dispositivo lógico programable "FPGA", utilizando la familia de FPGA Virtex-4 serie FX de XILINX. ¿Cómo lo realiza?, empezaremos primero por entender esta familia de FPGA que se propone. Esta familia de FPGA posee un controlador de la Unidad de Procesamiento Auxiliar (APU), que provee una interface con alto ancho de banda entre la lógica configurable de la FPGA y el procesador PowerPC 405 integrado. Un Fabric co-processor modules (FCM), "módulo coprocesador", implementado en la FPGA, esta conectado al procesador PowerPC embebido, a través de la interface del controlador APU, para habilitar el acelerador hardware configurable, definido por el usuario. La función de estos aceleradores hardware es operar como una extensión del procesador PowerPC 405, con lo que descarga de la CPU exigentes tareas computacionales. Esta última oración es uno de los objetivos principales de la FPGA, manejar data de alto contenido de actividad computacional a altas velocidades y también es una de las razones por la que se seleccionó para el desarrollo del experimento de este artículo, tal experimento consiste en medir el rendimiento en dos procesadores PowerPC uno es el modelo 7400 y el otro 970FX, los cuales fueron denominados OSSIAN, mediante la ejecución de una aplicación de estabilización de imagen en modo "batch". Obviamente procesar una imagen en tiempo real es una tarea de alto contenido de data. Mas adelante volveremos a tocar este punto.

     El controlador APU permite extender el juego de instrucciones nativas PowerPC 405, que son ejecutadas en el FCM. Las instrucciones que soporta la APU son clasificadas en tres categorías principales:

• - Instrucciones definidas por el usuario UDI
• - Instrucciones de punto flotante del PowerPC.
• - Instrucciones de APU de carga y almacenaje (load/store).

Las instrucciones definidas por el usuario son dinámicamente programadas dentro de otro controlador a través del registro de control del procesador PowerPC 405. La unidad de punto flotante, " floating-point unit FPU, es un ejemplo de un FCM. El juego de instrucción de punto flotante del PowerPC es decodificado en el controlador APU. Mientras que el cálculo se realiza en función de la FPGA. Para soportar la FPU con diferentes complejidades, el controlador APU permite seleccionar un grupo de instrucciones de punto flotante del procesador PowerPC. Estas instrucciones son ejecutadas en el FCM mientras que otro grupo de funciones son computadas a través de la emulación del software FPU o puede ser ignorado completamente. Esto optimiza los recursos de la FPGA mientras se acelera los cálculo casi críticos con la lógica dedicada. Esto explica un poco mas la importancia de aplicar la FPGA en este desarrollo del artículo, tomando como punto de referencia que se necesita realizar multiplicaciones matriciales, del tamaño 8x8 y en tiempo real, resulta una carga computacional muy grande para un solo CPU, mientras que con esta familia de FPGA, posee como cualidad estratégica un controlador APU que no sólo sirve de interface para la comunicación con el PowerPC, sino que es el encargado de direccionar los diferentes subgrupos de instrucciones simultáneamente. Para entender un poco mas esto se realizará una secuencia paso a paso; una vez que la instrucción alcance la etapa de decodificación, ésta es simultáneamente presentada en el bloque de decodificador APU y en el CPU. Si la instrucción es detectada como una instrucción de CPU, el CPU continuará ejecutando la instrucción como lo hace normalmente, de otro modo dentro de mismo ciclo, el CPU busca una respuesta en el controlador APU, si el controlador APU reconoce la instrucción, este proveerá información necesaria para respaldar al CPU. Si el controlador APU no responde dentro del mismo ciclo, se genera una instrucción inválida por el CPU.

El procesador PowerPC y el FCM residen en dominios de reloj  separados, el módulo de sincronización del controlador APU maneja la diferencia de frecuencia de reloj, esto permite al FCM operar a mas baja frecuencia que el procesador. En esta instancia el controlador APU recibe la data resultante del coprocesador (en este caso de la unidad SIMD) y en un buen tiempo de ejecución envía los datos de vuelta al procesador.

La idea de expresar lo antes dicho es para poder entender como se comunica  la FPGA con el procesador específicamente en esta familia FX, que es la que posee el PowerPc 405, también para entender como se realiza la aceleración hardware en la FPGA. Implementar una unidad SIMD en esta FPGA tiene una gran sentido y es que ya cuentas con el procesador y el pipeline para poder trabajar con instrucciones vectoriales, ya que para el procesamiento de imagen se requiere mucho cálculos matriciales. Con la ayuda del compilador GCC se  genera código que utiliza el FCM, y al FCM se puede accesar realizando las instrucciones en código ensamblador o código C. el GCC genera el código que utiliza una unidad de punto flotante  FCM, para cálculos de operaciones de punto flotante.

Haciendo referencia a la multiplicación de matrices de los coeficientes de la transformada de wavelet de haar (se explica mas adelante), en tiempo real fue muy bien indicado por el artículo implementar la unidad SIMD en la FPGA, ya que este dispositivo programable adaptará dicha técnica a la medida y no tan sólo eso sino que permite implementar a futuro otras transformadas de tipo wavelet, sin necesidad de desmontar la FPGA y el resto de los dispositivo. Para este tipo de estudios donde la exigencia de velocidades y la carga computacional es alta, este dispositivo representa una alternativa poderosa y mas económica que la tecnología ASIC. Virtex-4 FPGA contiene tres tipos de familias LX, FX y SX, ofreciendo múltiples características de selección y combinación para todas las aplicaciones complejas. El artículo utilizó la serie FX por tener implementado no sólo el procesador PowerPC sino por la nueva tecnología de interface del controlador APU ofreciendo todas las ventajas antes nombradas y que no las tenían las otras series. Es por eso que la serie FX es para aplicaciones de plataformas embebidas. El Virtex-4 posee 960 pines de entrada/salida, soporta memorias de interface DDR y DDR-2. En este artículo el Virtex-4 FX, demostró ser una plataforma embebida capaz de implementar una unidad SIMD totalmente reconfigurable a un precio mas bajo que desarrollar una unidad SIMD (ILLIAC IV) para un objetivo específico. Para tener una cierta idea de las unidades SIMD y de otros aspectos que habla el artículo, como lo es profundizar en la carga computacional de las transformadas de wavelet en la FPGA, se desarrollo el siguiente contenido:

 

La Unidad SIMD es una técnica empleada para el manejo en paralelo de datos. Como un procesador de vector. En una arquitectura SIMD el paralelismo se logra por múltiples unidades de proceso llamados elementos de procesamiento (PE), cada una es capaz de ejecutar una operación especializada autónomamente. Esta arquitectura se caracteriza por el hecho de que la misma operación es realizada en un momento dado sobre un gran conjunto de datos en todos los (PE). Las computadoras SIMD están especialmente diseñadas para realizar cómputos vectoriales sobre matrices de datos.

Ejecución de una SIMD

Los procesadores SIMD pueden manejar un único flujo de instrucciones y múltiple flujos de datos. Dado que un elemento de procesamiento no constituye una unidad de procesamiento central CPU, y que no es capaz de funcionar independientemente, el sistema es en esta caso de procesamiento paralelo y no es un sistema multiprocesador. Estos procesadores pueden tener uno o dos configuraciones ligeramente diferentes, una ha sido implementada en la muy conocida computadora ILLIAC IV cuya esquematización puede verse a continuación:

Para este caso esta computadora tiene 256 (PE) distribuidos en cuatro cuadrante de 8x8 (PE). Los PEs de un cuadrante  son controlados por una unidad de control común, como resultado de esto los PES de dicho cuadrante pueden ejecutar la misma operación simultáneamente. En la siguiente figura se muestra la comunicación entre los Pes dentro del cuadrante. Cada PE  se comunica con su vecino, la mayor distancia entre dos PEs no vecino es 8.

 

 

 

 

 

 

 

 

 

 

 

 

 

Cada PE es esencialmente una unidad aritmético y lógica (ALU) con registros de trabajos que le pertenecen y una memoria local (PEM) para el almacenamiento de datos distribuidos. La unidad de control (CU) cuenta con una memoria de para el almacenamiento de programas. En ella se cargan lo programas del usuario desde el almacenamiento principal. La función de la CU es decodificar todas las instrucciones  y determinar donde debe de ejecutarse las instrucciones decodificadas; las instrucciones escalares se ejecutan directamente dentro de la CU. Las instrucciones vectoriales se envían  a los PEs para una distribución de la ejecución a fin de alcanzar un paralelismo, gracias a la multiplicación de unidades aritméticas PEs.

Todos los elementos de procesamiento realizan la misma función sincrónicamente en forma esclava bajo el control de la CU. Los operandos vectoriales se distribuyen en la PEM antes de lanzar la ejecución paralela de los PEs.

 

En la figura anterior se muestra la estructura interna de un elemento de procesamiento.

Di indica la dirección asignada a este elemento de procesamiento

Si indica si este procesador esta o no activo para realizar ciertos cálculos.

Ii es un registro índice

Ri es el registro que apunta  a otros procesadores

Formalmente una unidad SIMD se caracteriza por el siguiente conjunto de parámetros:

C:{N,F,I,M}

N= es el número de procesadores

F= es el conjunto de funciones de ruteo de datos previsto por la red de interconexión.

I= el conjunto de instrucciones para las operaciones escalares y vectoriales, de ruteo de datos y manejo de la red.

M= conjunto de mascara que habilitan o deshabilitan a los procesadores.

Ejemplo de funcionamiento de un procesador SIMD.

Para mostrar cómo es el ruteo de datos en un procesador SIMD veremos en detalle una instrucción vectorial dentro de los N PEs.

Se desea la suma de S(k) de las primeras k componentes de un vector A para k = 0,1,.......n-1. Sea A= (A0, A1, ......An-1)

Necesitamos calcular las siguientes sumas:

Este vector de n sumas puede calcularse recursivamente realizando las n-1 iteraciones definidas como:

S(0) = A(0)

S(k) = S(k-1) + A(k) para k = 1,2, ...., n-1

Esta sumas recursivas para n = 8 se implementaron en un procesador SIMD N=8 PEs

En la implementación se utilizan tanto el ruteo de datos como el enmascaramiento de PEs. Inicialmente cada A(i) que reside en cada PEM(i) es movido al registro D(i) en cada PE(i) para i = 0,1,..., n-1 (sumiendo n=N=8).

En el primer paso A(i) es ruteado desde R(i) a R(i+1) y sumando al A(i+1). Obteniéndose la suma A(i) + A(i+1) en R(i+1) para i =0,1,...8.

Las flechas de la siguiente figura muestran las operaciones de ruteo y la notación abreviada ∑Ai a Aj se utiliza indicando la suma intermedia de A(i) + A(i+1)+....+A(j).

En el paso 2, la sumas intermedias en R(i) son ruteadas a R(i+2) para i = 0,1,...5.

En el paso final las sumas intermedias en  R(i)  son ruteadas en R(1+4) para i =0,1...,3

Consiguientemente el PE(k) tiene el valor final de S(k) para k =0,1,...7.

Cuanto más lejos se extienden las operaciones de ruteo cada vez menos PEs son los intervinientes. Nótese que en el paso 1 PE(7) recibe pero no transmite; en el paso 2 son los PE(6) y PE(7), en tanto que en el paso 3 son los PE(4), PE(5), PE(6) y PE(7) los que reciben solamente.

Estos PEs que se desean que se transmitan son enmascarados durante el paso correpondiente.

Los PEs que son enmascarados en cada paso dependen de la operación (ruteo de datos o suma aritmética) que se realice. Aun así los patrones de enmascaramiento varían en los diferentes ciclos de operación.

 Un arreglo de PEs es una unidad aritmética pasiva esperando ser invocada para las tareas de cómputo paralelo.

Procesamiento pipeline/paralelo

El multiprocesamiento es una consecuencia natural de las actividades que están viajando simultáneamente en distintos elementos de procesamiento de la red. El pipeline puede pensarse como una forma de multiprocesamiento que optimiza la utilización de recursos y saca ventaja de las dependencias entre los cálculos.

 

Filosofía de diseño de los procesadores  RISC

Antes de la aparición de los procesadores RISC (Reduced Instruction Set Computer), la filosofía de diseño de los procesadores se basaba en aumentar la potencia de proceso agregando mayor capacidad de almacenamiento en forma de registros. Este hecho condujo a un problema y es que los registros se implementan en los procesadores usando transistores en el propio dado del procesador, además de que incrementan en gran medida la complejidad de las CPUs, pues todas sus unidades funcionales han de estar "cableadas" con todos los registros. En este sentido, la utilización de la memoria principal simplificaba el diseño y lo abarataba, por lo que los microprocesadores limitan el número de registros que implementan en su interior.

Para poder usar la memoria principal para almacenar la información de las unidades funcionales de la CPU, se intentó implementar las instrucciones de manera que ofrecieran varias versiones en función de la posición de los operandos de las mismas, ya sea en registros internos o memoria principal, y simplificar la programación. Este concepto se conoce como ortogonalidad. Hace que un menor número de instrucciones permitan realizar las mismas operaciones, pues la misma instrucción puede ser configurada para diferentes modos de direccionamiento.

Breve reseña histórica de la arquitectura PowerPC.

La filosofía RISC fue introducida por John Cocke en los años 70. La primera implementación de un procesador RISC llegaría con el proyecto 801 de IBM, dedicado especialmente a computación empotrada. Ofreció un rendimiento bastante malo, por lo que IBM emprendió el Proyecto América, creando el primer procesador de la arquitectura POWER [3], incluido en el RISC System/6000 a principios de los 90.

En 1991, IBM se dio cuenta de las posibilidades de su diseño y se creó la alianza AIM (Apple, IBM & Motorola, actualmente Freescale), con el objetivo de terminar con el domino del tándem Microsoft-Intel que ofrecía sistemas basados en 80386 y 80486 y tenía al Pentium en desarrollo. Para Motorola supuso una salida al poco éxito que estaba teniendo su serie 88000, por lo que requirió que la nueva solución fuera compatible con el bus del 88000 a nivel de hardware.

El resultado de estos requerimientos fue la arquitectura PowerPC (Performance Optimization With Enhanced RISC Performance Computing).

La primera implementación de un procesador PowerPC llegó en 1993 con el PowerPC 601 de IBM.

Ejemplos de implementaciones de sobremesa fueron los procesadores 750 (G3), 7400 (G4), 7450 (G4e) y sus múltiples versiones (7447, 7447a y 7448) y el 970 (G5) y sus derivaciones: 970FX, 970MP y 970GX.

La ISA (Instruction Set Architecture) de PowerPC se describió originalmente en tres libros [6] que contemplaban las instrucciones de nivel de usuario, el entorno virtual y el entorno operativo.

 

Modos de direccionamiento a memoria

Las CPUs PowerPC direccionan al byte y sólo es posible el acceso a memoria mediante las instrucciones LOAD y STORE, que copiarán a los registros del procesador los valores de la memoria principal o los transferirán a ésta.

Para generar las direcciones se sumará el contenido de un registro base a un índice proporcionado en la propia instrucción o en un registro índice. PowerPC permite actualizar el registro base con la última dirección generada para, por ejemplo, procesar elementos consecutivos.

Conjunto de registros

La arquitectura define 32 registros de propósito general y otros 32 registros de coma flotante de 64 bits. En función del modo de operación, los registros de propósito general tendrán un ancho de 32 ó 64 bits.

Las implementaciones que incorporan el motor vectorial AltiVec [9] (también llamado VMX por IBM o Velocity Engine por Apple) incorporan 32 registros adicionales de 128 bits.

Motor de cálculo vectorial

Además de los 32 registros vectoriales, los procesadores PowerPC que implementen el motor AltiVec implementan instrucciones de control de caché para evitar sobrecargar el uso de la memoria caché y producir un descenso del rendimiento.

Como ocurre con las extensiones SSEx de los procesadores x86, operan en paquetes de datos usando los registros especiales definidos a tal efecto. La diferencia radica en que PowerPC define 32 frente a 8 registros de x86 (AMD64 amplía esta cifra hasta 16) y que ejecuta las instrucciones vectoriales de forma independiente en un ciclo y sin requerir un cambio de modo [9], cosa que no se ha conseguido en los procesadores x86 hasta 2006 con la introducción de la microarquitectura Core de Intel.

AltiVec fue desarrollado entre 1996 y 1998 y la primera implementación se produjo en el MPC7400 de Motorola (G4) que Apple usó para optimizar parte del código de su nuevo sistema operativo, Mac OS X. Recientemente, se ha incluido el motor VMX en los procesadores de la línea POWER de IBM con el futuro POWER6.

A continuación se describe solamente los procesadores que se hace referencia al articulo.

PowerPC 7447

Tras las implementaciones de la serie 6XX, llegó la serie 7XX, denominada por Apple como G3, que permitió superar el rendimiento de la serie 6XX, pero que tuvo una importante carencia: el motor vectorial, que ya tenían sus competidores x86. El motor vectorial llegaría con el 7400 de Motorola, que sería básicamente un 750 con el añadido de las extensiones AltiVec.

En 2001 presenta el 7450, que supondría un rediseño completo de la anterior versión. Con un pipeline un poco más largo (7 etapas frente a las 4 del 7400) pudo alcanzar frecuencias mayores, desde los 667 MHz en 2001 a los 2 GHz en la actualidad. La última revisión, el MPC7448 está fabricada en 90 nm y ofrece cotas de rendimiento por vatio de entre las mejores del mercado.

El PowerPC 7447 es una pequeña evolución del 7450, con el cual comparte filosofía arquitectónica. También tiene un pipeline de 7 etapas, está fabricado con tecnología de 130 nm e implementado con 58 millones de transistores. El 7447 implementa las extensiones AltiVec, que añaden 162 nuevas instrucciones a la ISA Power y tiene 4 unidades de ejecución vectoriales, permutación de vectores, operaciones de enteros simples, operaciones de enteros complejos y operaciones de coma flotante, además de los 32 registros de 128 bits estándar.

 

PowerPC 970

La filosofía de diseño del PowerPC 970 varió respecto a la del 7450, en este caso se usó un pipeline bastante  largo, de 14 etapas en el caso de operaciones con enteros, frente a las 7 del 7450. Esto permite tener hasta 200 instrucciones al vuelo pendientes de confirmar (lo que incrementa el número de registros de renombrado necesarios), además de escalar mejor frecuencia. Estas características, combinadas con un consumo relativamente reducido (el 970 de 1,8 GHz consume 42 W frente a los 69 del Pentium 4 a 2,8 GHz y los escasos 30 W del 7450 a 1,2 GHz), hicieron que se convirtiera en un chip muy popular.

El PowerPC 970 es un microprocesador superescalar con modos de operación de 32 y 64 bits que desciende directamente del POWER4 de IBM e implementa el motor vectorial VMX (AltiVec).

Comparado con el PowerPC 7450, el 970 tiene un rendimiento general mayor, pero el tener muchas más etapas de segmentación hace que cuando es necesario vaciar el pipeline, la penalización de rendimiento sea también mayor. Por este motivo, el 970 tiene una caché de instrucciones el doble de grande que la del 7450 (64 KiB frente a 32 KiB), además de que ha de incorporar técnicas avanzadas de predicción de saltos para minimizar los fallos de pipeline, penalizando el rendimiento [12].

Para mantener el pipeline lleno de instrucciones en todo momento, se leen de memoria ocho instrucciones por ciclo. Estas instrucciones se decodifican y dividen en una especie de micro operaciones llamadas IOPs, que se ejecutarán fuera de orden.

Pero la mayor mejora de rendimiento del 970 es el bus frontal que incorpora. Éste está compuesto por dos canales unidireccionales de 32 bits de ancho que pueden funcionar hasta a la mitad de la frecuencia de la CPU, es decir, ésta última tiene un multiplicador de 2x. Los comandos de control se multiplexan en bus junto con los datos, lo que hace que se pierda una pequeña cantidad de ancho de banda (en torno a un 10%), aunque sigue manteniendo una tasa de transferencia bastante alta (para un FSB de 900 MHz se llega a los 6,4 GiB/s).

Para concluir, es necesario mencionar que el 970 posee dos unidades de enteros asimétricas, una unidad de coma flotante que permite ejecutar operaciones en doble y simple precisión a la misma velocidad y que tiene 80 registros disponibles (32 de la ISA PowerPC y 48 de renombrado) y una implementación total de las extensiones AltiVec, con unidades de aritmética en coma flotante y entera, lógica y permuta de vectores [13]. En la figura 8 de aprecian todos los bloques constitutivos del PowerPC 970.

PowerPC 401

El PowerPC 401 es un chip contemporáneo al PowerPC 601. Fue diseñado para entornos empotrados, como microcontroladores, elementos de redes (routers, switches...), etc. Para reducir el coste, consumo y tamaño se eliminaron elementos como la unidad de gestión de memoria (desparece la paginación) y las unidades de coma flotante, lo que permitió un consumo de tan sólo 0,1 W en su versión de 100 MHz (1996). Fue implementado usando únicamente 85.000 transistores. Sólo puede emitir una instrucción por ciclo y posee un pipeline de tres etapas.

Lo antes dicho complementa la información suministrada en la introducción y motivación del  artículo en cuestión.  Básicamente la idea del artículo es implementar los elementos de procesamientos PE dentro de la lógica de la FPGA y a su vez tener comunicación con el procesador PowerPC a través de la unidad de control CU, o de la APU (unidad de procesamiento auxiliar) como lo identifica el artículo, con la gran diferencia con respecto a la Altivec o SSE, de poder ser reconfigurable en a la medida que se desee; dado que el módulo se puede redefinir mediante un lenguaje de descripción de hardware VHDL.

METODOLOGÍA DE TRABAJO DEL ARTÍCULO 

En la metodología del artículo se explica la acción de reescribir el código de bucles (escalar) en formato vectorial, es decir aplicar  el proceso de vectorización.  En el siguiente cuadro se representa una tabla de referencia para convertir de vectorial a escalar.

 

 Y un ejemplo de esta conversión de vectorial a escalar sería:

 

Luego de escalar a vectorial se cumple conciertas reglas como:

Y tomando como ejemplo la figura B del código de escalar se convertirá a vectorial de la siguiente forma:

El compilador GCC 4.x viene con un vectorizador que implementa ciertas aproximaciones basadas en bucle, lo que significa que no tiene en cuenta el código directo. Por lo tanto el artículo informa que aparte de la vectorización automática (por el compilador GCC), se puede realizar también en forma manual tomando en cuenta como referencia los ejemplos antes nombrados.

RESULTADOS PRELIMINARES

En los resultados preliminares el artículo nombró su sistema OSSIAN, basados en procesadores  PowerPC 7400 y la PowerPC 970, el sistema OSSIAN consiste en el dispositivo Virtex-4 modelo XC4FX12.

La  medición de rendimiento se realizó mediante la ejecución de una aplicación de estabilización de imagen en modo "batch", es decir en modo de procesamiento de imagen en bloque, estas se leen y se almacena su resultado en la memoria. Cuando el artículo expresa que el algoritmo se realiza con la transformada de wavelet se trata de los siguiente:

La Transformada Wavelet Discreta (DWT) esta siendo muy utilizada en el campo del procesado de imágenes gracias a su flexibilidad en la representación de señales no estacionarias y sus buenas características de adaptabilidad a la visión humana. La DWT está relacionada con el análisis multiresolución y la descomposición en subbandas, lo cual se utiliza en el procesado de imágenes. Este método de transformación que fue desarrollado por Mallat [7], ofrece ortogonalidad y la posibilidad de representación tiempo-frecuencia.

La transformada Wavelet discreta (DWT) descompone recurrentemente una señal de entrada, So(n), en dos subseñales de menor resolución consideradas como aproximación y detalle. Las señales Si(n) y Wi(n) son la aproximación y el detalle respectivamente de la señal en el nivel i. la aproximación de la señal en el nivel i+1 se puede calcular como:

Si+1(n) = ∑g(k)Si(2n-k)

El detalle de la señal en el nivel i+1 se puede calcular como:

Wi+1(n) = ∑h(k)Si(2n-k)

Es decir la señal original pasa por dos filtros un pasa bajo y pasa alto.

Y se vuelve a mostrar la forma de obtener los coefienciente de wavelet de haar realiando downsampling, como se ve en el ejemplo siguiente:

Estos coeficientes es  a lo que nos referimos como los detalles de la señal y es lo que se necesita para formar la matriz coeficientes de wavelet de haar. Se puede formar tres matrices de coeficientes de haar dependiendo del número de niveles que se tome, mientras mayor sea el nivel mayor será el número de coeficientes de haar.

 

Down-Sampler

 Hacer un down-sampling de un factor entero M>1 consiste en guardar uno de cada M valores muestreados y eliminando los M-1 muestreos intermedios, generando una señal de salida xd[n] de acuerdo con la siguiente relación: xd[n]=x[nM]. Al igual que la operación de up-sampling, el downsampling es lineal pero es variante en el tiempo. Disminuir la frecuencia puede tener implicaciones a la hora de cumplir el teorema del muestreo, por lo que se explica la razón por la que va después del filtro pasobajo o pasaalto, para evitar que sea variante en el tiempo.

        (↓2)y=(...,y(-4),y(-2),y(0),y(2),y(4),......)

El símbolo (↓2) indica downsampling o decimacion, para compensar la pérdida de componentes durante el downsampling, es necesario multiplicar y(2n) por raiz de 2, este factor se incluye de una vez en el filtro, es decir el filto pasa bajo por ejemplo: Ho(w) cambia C(w) = raiz(2)Ho(w), por lo tanto los coeficientes del filtro "C", en los filtros  promedios los coeficientes se incrementan en raiz(2)/2; por lo tanto :

c(o)=c(1)=  raiz(2)/2   el cual es 1/raiz(2)

por lo tanto la matriz de downsampling para el filtro pasa bajo será:

por lo tanto la matriz de downsampling para el filtro pasa alto será:

 

Luego se habla de una matriz de correlación que se puede definir de la siguiente manera:

Donde I es la función de entrada y h es el operador filtro (templete).

Se realizará un ejemplo para entender mejor como funciona este filtro de correlación:

Para calcular la correlación en el pixel (2,4) de la imagen se siguen los siguientes pasos:

• 1- Se desliza el filtro de manera que su pixel central quede alineado con el pixel (2,4) de la imagen.
• 2- Se multiplica cada peso del filtro por los elementos de la imagen que se encuentran abajo.
• 3- Se suman los productos individuales calculados en el paso 2.

Por lo tanto la salida del pixel (2,4) después de la correlación será:

1x8 + 8x1 + 15x6  + 7x3 + 14x5 +  16x7  +  13x4  +  20x9  + 22x2  = 585

En el artículo utilizan una ventana de seguimiento de 41x41 pixeles y la máscara o filtro de correlación es de 8x8 pixeles. Los elementos de esta máscara al solaparse con la ventana de seguimiento será la manera de seguir los puntos en las aproximidades, este solapamiento  implica una multiplicación matricial tal como se observó en el ejemplo anterior, por lo tanto es una tarea destinada a la unidad SIMD, que será un multiplicador matricial.

NOTA: cuando se habla de pixel es importante entender que en el mismo se toma en cuenta la profundidad, esto no es mas que la suma de la combinación de la matriz de color rojo, verde y azul, donde se obtienen 8 combinaciones de colores, al definir mas elementos de la matriz de color se incrementa también en número de combinaciones, para aproximarse a los colores reales.

El proceso de realizar esta multiplicación de matrices lo realiza la unidad SIMD, implementada en la FPGA virtex-4 modelo XC4FX12. Este modelo consta de 64x24 bloques lógicos de control (CLB), 5472 silicios, 10944 LUTs, 86Kb como máxima distribución de RAM y 10944 fliflops. Cada CLB contiene 4 silicios, 8 LUTs, 8 flipflops, 8 MULT_ANDs, 2 cadenas de acarreo y aritmético, 64 bits para la distribución de RAM, registros de 64 bits.

El modelo XC4VFX12 contiene 16 entrada de reloj, los cuales pueden ser configurados por los pines de entrada/salida del dispositivo.

 REFERENCIAS

http://cpdsi-fich.wikidot.com/local--files/teorias/teoria1b.pdf

http://www.depi.itchihuahua.edu.mx/electro/archivo/electro2001/mem2001/articulos/dsp3.pdf

http://www.cudi.edu.mx/primavera_2004/presentaciones/Ricardo_Fuentes2.pdf

http://www.atc.us.es/descargas/Tecnologias_para_la_adquision_de_imagenes_(Bloque2).pdf

http://catarina.udlap.mx/u_dl_a/tales/documentos/lep/hernandez_g_d/capitulo5.pdf

http://www.iberchip.org/iberchip2007/articulos/3/a/paper/2-Arquitectura_Hibrida_FPGA.pdf

http://www.mathworks.com/access/helpdesk/help/pdf_doc/wavelet/wavelet_ug.pdf

http://www-2.dc.uba.ar/materias/so/datos/cap05.pdf

http://en.wikipedia.org/wiki/SIMD

http://www.tecnun.com/asignaturas/tratamiento%20digital/tema11.pdf 

http://www.xilinx.com/bvdocs/ipcenter/data_sheet/apu_fpu.pdf

http://cpdsi-fich.wikidot.com/local--files/teorias/teoria1b.pdf

http://www.depi.itchihuahua.edu.mx/electro/archivo/electro2001/mem2001/articulos/dsp3.pdf

http://www.cudi.edu.mx/primavera_2004/presentaciones/Ricardo_Fuentes2.pdf

http://www.atc.us.es/descargas/Tecnologias_para_la_adquision_de_imagenes_(Bloque2).pdf

http://www.xilinx.com/products/silicon_solutions/fpgas/virtex/virtex4/

[1] Alexandre E. Eichenberger, Peng Wu, Kevin O'Brien, Vectorization for SIMD Architectures with Alignment Constraints, IBM T.J. Watson Research Center Yorktown Heights, NY

[2] Ricardo José Colom†, Rafael Gadea†, Angel Sebastia†, Marcos Martínez†, Francisco allester†,

Vicente Herrero, Implementación de la Transformada Wavelet Discreta 2-D con filtros no Separables, Universidad Politécnica de Valencia. Departamento de Ingeniería Electrónica. Camino de Vera s/n 46022 Valencia