Propuesta para Trabajo de Grado

II - MARCO TEÓRICO

1. Marco Conceptual

1. Trabajos importantes en el área

En el área del filtrado de imágenes se han hecho importantes esfuerzos desde los años 80 [2] con distintas finalidades, como lo son el filtrado de imágenes a tiempo real, el filtrado de grandes cantidades de imágenes y el filtrado de imágenes de gran tamaño. Algunos de estos importantes esfuerzos son los siguientes:

• 
  Filtrado de imágenes 2D a tiempo real, este proceso involucra procesar rápidamente imágenes capturadas, el resultado de este proceso de filtrado no necesariamente tiene que ser el más preciso. [2]
  
• 
  Filtrado de imágenes médicas MRI (Magnetic resonance imaging) utilizando dispositivos FPGA de manera paralela. [6]
  
• 
  Filtrado de imágenes 2D basados en GPU, se ha demostrado que las soluciones basadas en GPU llevan a un aumento en el desempeño a comparación de la implementación normal en CPU. [5]
  
• 
  Filtrado de imágenes satelitales por medio de GPU (High-Pass Filter); estas imágenes presentan un desafío debido al gran tamaño que suelen tener, y ya que actualmente la adquisición de estas imágenes no es tán dificil como en épocas pasadas, la principal obstrucción en cuanto a estas investigaciones es el tiempo de procesamiento de las mismas. [4]
  
• 
  Filtrado de imágenes 2D en dispositivos móviles: en estos dispositivos es necesario implementar eficientemente cualquier tipo de software debido a las limitadas capacidades computacionales de los mismos; en cuanto a el filtrado de imágenes, se han migrado librerias de programación propias de los PC’s a estos dispositivos, y se ha logrado tener un buen rendimiento. [1]
  

2. Descripción general de la plataforma CUDA

CUDA es una plataforma de programación paralela y al mismo tiempo un modelo de programación, que aprovecha las capacidades computacionales de las tarjetas de video (GPU’s) de Nvidia. CUDA fue introducido en el 2006 [5].

CUDA es compatible con diversos lenguajes, como C++, Java, Python, entre otros, pero el ambiente que viene por defecto en el SDK es C.

1. Modelo de programación

CUDA parte de la base que el paralelismo (tanto en GPU como en CPU) es algo que se está haciendo y que se ve venir como el futuro de la computación de alto desempeño. Teniendo lo anterior en cuenta, el modelo de programación de CUDA provee abstracciones que permiten al programador no tener en cuenta la cantidad de recursos que utilizará en una tarea que utilice paralelismo.



Ilustración 1: Modelo de programación escalable
De esta manera, es posible programar una tarea paralela una vez, y que para aumentar el rendimiento de la aplicación de esta tarea baste añadir más GPU’s, o mas núcleos en los que sea posible ejecutar el código. En la ilustración 1 se aprecia un esquema de dicho modelo escalable.

1. Kernels

El kernel es la forma en la que CUDA extiende el lenguaje C, permitiendo al programador definir funciones propias. La gran diferencia es que estas funciones cuando se ejecutan, son ejecutadas N veces por N CUDA threads.

2. CUDA threads

Cada CUDA thread (de aquí en adelante solamente llamados hilos) que ejecuta un kernel definido contiene una variable única threadIdx. Esta variable es un vector de tres componentes, así que los diferentes hilos pueden ser identificados usando índices de hilos de una, dos o tres dimensiones. Esto facilita el procesar elementos en un dominio como el de un vector, una matriz o un volumen [9].

Estos hilos vienen organizados por bloques, existe un límite en el número de hilos por bloque (actualmente 1024 hilos), sin importar la dimensión del mismo. Sin embargo, es posible lanzar varios bloques con hilos dentro de sí, aumentando así el número de hilos que efectivamente se ejecutan en una tarea.

Los bloques también están organizados, esta vez entre una grilla de bloques. Esta grilla a su vez puede ser unidimensional, bidimensional o tridimensional. Cada bloque también se identifica dentro de su grilla, pero esta vez utilizando la variable blockIdx. Dentro de cada kernel es posible obtener el tamaño del bloque con la variable blockDim. En la ilustración 2 se muestra un esquema explicando toda la organización de estos hilos.



Ilustración 2: Organización CUDA threads

3. Organización de memoria

Cada hilo puede acceder a varios espacios de memoria durante su ejecución (Ilustración 3). Cada hilo tiene memoria local privada, cada bloque tiene memoria compartida visible por todos los hilos del bloque (durante el periodo de vida del mismo). Por último, todos los hilos tienen acceso a memoria global siempre.



Ilustración 3: Diferentes espacios de memoria
Aunque existen más espacios de memoria a los que los hilos pueden acceder, solamente se utilizan los aquí descritos para CUDAlicious.

4. Computación heterogenea

En la sección anterior se describe los diferentes espacios de memoria accesibles por un hilo de CUDA, pero todos estos espacios son memoria físicamente ubicada dentro de la GPU.

El modelo de programación de CUDA asume que todos los CUDA threads se ejecutan en un dispositivo físicamente separado, que opera como co-procesador al procesador anfitrión. De igual manera, se asume que tanto el anfitrión como el dispositivo CUDA mantienen espacios de memoria separados. De esta manera, la única forma de gestionar los espacios de memoria descritos en la sección Organización de memoria es a través de llamadas a CUDA runtime [9]. En la ilustración 4 se muestra el esquema de un ejemplo en el que el código del dispositivo anfitrión es serial y escrito en C, y el código del dispositivo está compuesto de varios kernels que se ejecutan en la GPU de manera paralela.

Ilustración 4: Ejemplo computación heterogénea

2. Interface de programación

El lenguaje por defecto para programar en CUDA es CUDA C, este lenguaje consiste en extensiones hechas al lenguaje C para acomodarlo al modelo de programación previamente descrito.

Cualquier código que utilice estas extensiones, se compila utilizando NVCC. NVCC soporta no solo código especifico para la GPU (kernels) sino también puede ser una mezcla de código del anfitrión y del dispositivo.

1. CUDA Runtime

Esta implementada en la librería cudart, que se enlaza a cualquier aplicación CUDA de forma bien sea estática (uso de librería .lib) o dinámica (.dll).

En general provee utilidades a la hora de ejecutar el código CUDA, entre ellas, las más importantes son:

• 
  Manejo de memoria local
  
• 
  Manejo de memoria compartida [9]
  
• 
  Chequeo de errores
  
• 
  Interoperabilidad con SLI [10]
  

En CUDA runtime se encuentran muchas de las funciones más utilizadas en el proceso de comunicación con la GPU. La tabla 1 muestra algunas de estas funciones y una breve descripción de su utilidad.

Nombre Función	Descripción
cudaMalloc()	Reserva memoria en el espacio de memoria del dispositivo.
cudaFree()	Libera la memoria previamente reservada de memoria del dispositivo.
cudaMemcpy()	Transfiere memoria entre anfitrión y dispositivo, de ida y vuelta.
cudaDeviceSynchronize()	Es llamada para esperar todos los procesos asíncronos. Usualmente usada antes de comprobar errores.
cudaPeekAtLastError()	Devuelve el último error, se llama desde código de anfitrión.

Tabla 1: Funciones CUDA

En la tabla 1 se aprecia que CUDA C se maneja de manera similar a C, teniendo en cuenta las claras diferencias entre los dos lenguajes, pero en general mantiene incluso el mismo orden de parámetros dentro de las funciones.

3. Descripción general de la plataforma ITK

ITK significa “Insight Segmentation and Registration Toolkit” [11].

Es una plataforma para el desarrollo de aplicaciones de registro y segmentación de imágenes. Segmentación es el proceso de identificar y clasificar datos que se encuentran en una representación digitalmente muestreada. El registro es el proceso de alinear o desarrollar correspondencias entre estos datos. [11]

1. Arquitectura

ITK está organizado alrededor de una arquitectura de paso de datos. Esto quiere decir que los datos están representados por data objects, que a su vez son procesados por process objects (filtros).

Estos dos (data objects y process objects) son conectados entre sí para formar pipelines [11], un ejemplo está en la ilustración 5.

Ilustración 5: Ejemplo pipeline ITK

2. Recursos utilizados

Esta plataforma fue necesaria para el desarrollo de CUDAlicious por la capacidad de leer una gran cantidad de formatos de imágenes de varias dimensiones. Realmente no se utiliza ningún otro recurso de esta plataforma.

Se utilizan las factorías definidas en la tabla 2, estas funciones manejan tipo de datos Image de ITK; Image de ITK es básicamente una grilla que contiene todos los datos de la imagen, con todas sus dimensiones [11].

ImageFileReader	Lee los datos de la imagen de un solo archivo [16].
ImageFileWriter	Escribe los datos de la imagen a un solo archivo [17].

Para leer de una serie de archivos se puede utilizar la factoría ImageSeriesReader, CUDAlicious actualmente solo lee datos de un solo archivo.

4. Convolución

   1. MATEMÁTICAMENTE

Es una operación matemática entre dos funciones (f y g), que produce una tercera función, que típicamente es vista como una versión modificada de una de las dos funciones iniciales.

La convolución de f y g es escrita como f ∗ g, y está definida en la ilustración siguiente.

Ilustración 6: Definición convolución

2. IMPLEMENTACIONES ACTUALES

Existen varias formas de implementar la convolución en tarjetas gráficas Nvidia actualmente, se analizaron las más relevantes actualmente.

Todas estas implementaciones requieren una información básica de entrada:

• 
  Tamaño del filtro
  
• 
  Valores del filtro
  
• 
  Tamaño de la imagen
  

1. Trivial

En el contexto de procesamiento de imágenes, un filtro por convolución es el producto escalar de los valores del filtro (kernel) con los puntos de la imagen dentro de una ventana que rodea cada uno de los puntos de salida [12].



Ilustración 7: Descripción general de la convolución
En la ilustración 7 se explica este proceso, que consta de los siguientes pasos por cada uno de los puntos de la imagen de salida:

1. 
   Multiplicar cada uno de los valores del filtro por los valores de la imagen de entrada (dentro de la ventana / tamaño delimitado por el filtro)
   
2. 
   Sumar estos valores
   
3. 
   En la imagen de salida asignar el valor de la suma al punto de la imagen de salida correspondiente
   

Este método de convolución es el trivial, y aunque también es altamente paralelizable, su complejidad algorítmica depende en gran manera de los tamaños tanto de la imagen como del kernel.

2. FFT

Es posible también resolver la convolución utilizando la transformada rápida de Fourier (FFT), utilizando la definición expuesta en la ilustración 8, en donde ◦ representa multiplicación punto a punto.


Ilustración 8: Convolución resuelta usando FFT, tomada de [13]

Varios trabajos alrededor de la convolución en GPU se han enfocado en utilizar este teorema, dejando claras sus ventajas y desventajas, que se enumeran a continuación [13].

Ventajas

• 
  Toma el mismo tiempo para todos los filtros
  
• 
  No hay restricciones de hardware con respecto al tamaño del filtro
  
• 
  Sirve con todos los filtros de frecuencia
  

Desventajas

• 
  FFT toma bastante tiempo
  
• 
  Maneja bien solamente imágenes con dimensiones potencias de 2
  

3. Separable

Generalmente, la convolución trivial en dos dimensiones requiere n*m multiplicaciones para cada pixel de salida, donde n y m son el ancho y el alto del filtro. Los filtros separables son un tipo especial de filtro que puede ser expresado como la composición de dos filtros unidimensionales, uno aplicado a las filas de la imagen y el otro aplicado a las columnas, de esta manera solo se requieren n+m multiplicaciones por cada pixel de salida [13].



Ilustración 9: Filtro de detección de bordes de Sobel
De esta manera, el filtro de dos dimensiones mostrado en la ilustración 9 se puede aplicar de la misma manera aplicando los dos otros filtros unidimensionales uno después del otro.