Download Implementación de Shear-warp distribuido utilizando hardware gráfico

IMPLEMENTACION DE SHEAR-WARP DISTRIBUIDO
UTILIZANDO HADRWARE GRAFICO
J. Camacho(1), L. Márquez(1), R. Carmona(1), R. Rivas(2)
(1)
LCG, Escuela de Computación, Universidad Central de Venezuela, Venezuela,
[email protected], [email protected], [email protected].
(2)
CCPD, Escuela de Computación, Universidad Central de Venezuela, Venezuela,
[email protected]
RESUMEN
Se presenta una solución distribuida mediante el enfoque maestro/esclavo para realizar
visualización de volúmenes utilizando hardware gráfico. Se considera el uso de texturas 2D
mediante la factorización Shear-warp por ser más rápido que utilizar texturas 3D. El
volumen de entrada es distribuido en bricks de forma estática. Cada brick es desplegado por
separado utilizando texturas 2D para obtener su aporte individual a la imagen intermedia en
el espacio deformado. La porción en la imagen intermedia asociada a cada brick es enviada
al maestro quien se encarga de componerlas de atrás hacia delante, según la distancia del
respectivo brick al ojo, para generar la imagen intermedia final. El maestro utiliza esta
imagen como textura, para realizar el warping y el despliegue final. Este trabajo es la
primera implementación distribuida de Shear-warp que utiliza en hardware gráfico tanto
para la generación de la imagen intermedia como para la final. Se presentan mediciones de
tiempo hasta para 4 esclavos.
ABSTRACT
This paper focuses on a distributed volume rendering method based on the master-slave
approach, exploiting graphics hardware capabilities. Shear-warp factorization with 2D
texture mapping is used instead of 3D texture mapping for speed. The source volume is
distributed in bricks among the slaves. Each brick is rendered to obtain a partial
intermediate image in sheared space. Slaves send these images to the master, who
composes them for warping, also using 2D texture mapping. This work is the first
distributed hardware based Shear-warp which uses 2D texture mapping in both process:
shear and warping. We present execution time measurements up to 4 slaves.
INTRODUCCIÓN
Uno de los principales inconvenientes de la visualización volumétrica es que el tiempo
requerido para la generación de las imágenes, limita la creación de aplicaciones
interactivas. Ejemplo de ello es el tiempo requerido por la técnica de Ray Casting, y los
retardos ocasionados por los fallos de página, con la técnica de Shear-warp o texturas 2D.
Para solventar el alto costo computacional e insuficiencia de memoria de la visualización
volumétrica se han propuesto enfoques distribuidos, que permiten crear aplicaciones
interactivas, tal que proporcionen un control más natural del volumen y ayuden al sistema
visual humano a comprender mejor la estructura en estudio.
La mayoría de las implementaciones distribuidas hechas hasta la actualidad han sido
realizadas bajo software. Actualmente, existe una variedad de hardware gráfico que soporta
textura 2D y 3D que permiten realizar la visualización en tiempos muy inferiores a los
obtenidos por software. Sin embargo, la capacidad de memoria de textura de la tarjeta
continúa siendo una limitante para volúmenes que la sobrepasen en tamaño.
En este trabajo se presenta una implementación de un algoritmo de visualización de
volúmenes distribuido que explota el hardware gráfico con textura 2D en los dos procesos
de la factorización Shear-warp.
Se utiliza texturas 2D por ser en la práctica
aproximadamente 3 veces más rápidas que texturas 3D.
ANTECEDENTES
El principal objetivo de la visualización volumétrica es lograr una aproximación de la
propagación de la luz a través de un volumen [3]. El volumen por lo general está dado
como un conjunto de muestras (voxels) provenientes de una función escalar continua
s=s(x,y,z), dispuestas en una malla rectangular. Mediante una función de transferencia, a las
muestras s se le asocia un color c(s)=RGB y una opacidad α(s)=A. Se asume que los
valores R, G, B y A están en [0,1]. Por cada rayo de visualización que pasa por el ojo y un
píxel de la pantalla, y atraviesa el volumen, se calcula una integral [8]. En el caso discreto,
supongamos que las muestras requeridas a los largo del rayo son s0,…,sn; entonces por
series de Riemann la ecuación de composición volumétrica es escrita como:
n
i −1
i =0
j =0
C ≈ ∑ α ( s i ) * c( si )∏ (1 − α ( s j ))
(1)
El algoritmo de Ray Casting evalúa esta ecuación en forma directa por software. Sin
embargo, esta ecuación puede ser evaluada en orden inverso para utilizar la operación de
mezcla que provee el hardware (Eq. 2). Note que se realiza una interpolación lineal entre el
color c(si) con el color Si+1 acumulado en el buffer de color. Se puede demostrar que S0=C.
α ( si ) * c ( si )
si i = n
⎧
Si = ⎨
⎩α ( si ) * c( si ) + (1 − α ( si )) * S i +1 si i < n
(2)
Visualización de volúmenes basado en aplicación de texturas requieren geometrías
intermedias sobre los cuales desplegar los cortes. Polígonos alineados al objeto, y polígonos
alineados al viewport son las técnicas tradicionales para este proceso. La primera utiliza
texturas 2D, que es más rápida, pero genera artefactos considerables bajo ciertos ángulos.
Esta técnica requiere de tres copias del volumen en memoria (ver Fig. 1). Para la
visualización se escoge la copia más perpendicular a la dirección de visualización. La
segunda utiliza texturas 3D, cuyo rendering es mucho más lento, pero reduce
considerablemente los artefactos, debido a la interpolación trilineal.
y
A
⊥ax
⊥ay
⊥az
x
Figura 1: Almacenamiento de tres copias del volumen, una por cada eje principal. Cada copia contiene una serie de cortes
paralelos 2D del volumen. Estos cortes son tratados como texturas bidimensionales para explotar el hardware gráfico.
Otra estrategia para acelerar el tiempo de respuesta son los algoritmos paralelos y
distribuidos. Aunque hay muchos trabajos en esta área, mencionaremos lo que están
relacionados con la fatorización Shear-warp. Lacroute [3], ha diseñado un algoritmo basado
en software para un multiprocesador de memoria compartida, que básicamente, asigna a
cada nodo grupos de filas de la imagen intermedia. Alcanza 13 fps con un volumen de 2563,
implementado sobre un SGI Challenge con 16 procesadores de 150MHz. Kentaro et al.
distribuyen el volumen por slabs (cortes 2D) entre los esclavos. El shear y warping por
software se realiza el cada esclavo, y luego se compone la imagen final mediante un binaryswap [6]. Alcanzaron 16.2 fps con 32 procesadores y un volumen de 2563 muestras. El
algoritmo presentado por Lang et al. [7] paraleliza la composición de la imagen intermedia
por software. Sin embargo, el warping es realizado de manera eficiente en el hardware
gráfico que soporta textura 2D, lo cual fue demostrado en trabajos previos [2]. Sus mejores
resultados se obtuvieron con un cluster linux con 16 Pentiums 4 de 2.4GHz, y un volumen
de 256x256x110, logrando 8.4 fps. Otros autores [1] dividen la carga en el espacio
desplazado (sheared space), mediante slabs perpendiculares a los cortes. Cada procesador
calcula un conjunto de filas de la imagen intermedia, y pueden realizar el warping de forma
independiente del resto de los procesadores. El maestro ensambla la imagen final. La
desventaja es la distribución de los slabs perpendiculares, los cuales requieren cómputo y
transmisión. Lograron generar 12 frames/seg en una máquina Thinking Machine CM-5 con
128 procesadores para un volumen de 2563.
SHEAR WARP DISTRIBUIDO
Nuestra implementación distribuida del shear-warp es realizada bajo el esquema de
partición estática del objeto [5], es decir que a cada nodo le corresponde un subvolumen
fijo. La arquitectura utilizada es a memoria distribuida, y en práctica una LAN de PCs
conectadas mediante un switch de 100Mbps. El modelo distribuido es maestro/esclavo. Los
nodos esclavos se encargan del cálculo parcial de la imagen intermedia, y del envío de las
mismas al nodo maestro. El nodo maestro se encarga de la interacción con el usuario,
control de los esclavos, distribución de de la carga, composición de las imágenes
intermedias parciales, y el cálculo del warping vía texturas 2D [7].
Distribución de la carga
Para dividir el volumen se utilizó la técnica denominada Bricking [4]. En dicha técnica se
divide el volumen en pequeños bloques (bricks o blocks), los cuales se asignan a los
esclavos. La división del volumen se realiza en cada uno de los tres ejes hasta alcanzar o
sobrepasar el número de esclavos. Si hay más de 8 esclavos, entonces recursivamente se le
aplica el mismo principio a cada uno de los bricks, nivel por nivel. Si la partición arroja
más bricks que esclavos, a algunos esclavos tendrán un brick más. Así, cada esclavo puede
manejar más de un brick, no necesariamente contiguos ni del mismo tamaño.
Generación de la imagen intermedia
Por cada brick en un esclavo se compone una imagen intermedia parcial, desplegando
polígonos texturizados y desplazados con los cortes bidimensionales del brick de atrás
hacia adelante. La forma de mezclar los polígonos es especificada mediante
glBlendFunc(GL_ONE, GL_SRC_ALPHA). El rendering de cada brick es realizado offscreen mediante un p-buffer[9], ya que las máquinas esclavas no deben mostrar ninguna
imagen por pantalla. La imagen se toma del buffer de color como RGBA.
Hay que tomar ciertas consideraciones para obtener una buena interpolación entre fronteras
de bricks. Por simplicidad, consideremos un volumen de 2x4x1 pixels, como se muestra en
la Fig. 2. Al aplicar bricking para 2 esclavos se divide esa textura en dos porciones de
2x2x1 píxeles y se aplica el proceso de visualización por separado a cada una. Al unir las
imágenes de ambos esclavos, se obtienen errores (Ver Fig. 3).
Píxel
Textura 1
Textura 2
Área sin
interpolar
Textura 1
Figura 2: Volumen de 2x4 píxeles
Figura 3: Fusión de las imágenes
intermedias produce errores en bordes
Textura 2
Figura 4: Fusión utilizando borde
con interpolación.
Se puede observar en la Fig. 3 que en el área dentro de los recuadros punteados no se
realiza interpolación y la unión entre los dos bricks no presenta continuidad. Esto ocurre
debido a que los voxels de los bricks adyacentes no fueron tomados en cuenta al realizar la
interpolación. Si se añade un borde de un voxel a cada brick con los voxels adyacentes, la
interpolación bilineal resultante es correcta en la unión de las dos texturas (Ver Fig. 4).
Generación de la imagen final
Las imágenes resultantes por cada brick en los esclavos son opcionalmente comprimidas
con LZO y enviadas al maestro, quien ordena estás imágenes desde las más lejana hasta la
más cercana (según su respectivo brick en coordenadas de ojo), y las compone texturizados
polígonos para obtener la imagen intermedia final. Con esta imagen se realiza el warping
para obtener la imagen final, no sin antes enviar a los nodos esclavos los parámetros de
visualización del próximo cuadro o frame. Un pseudocódigo que resume los pasos
anteriores se muestra a continuación:
void MasterRenderingLoop()
Calcular las matrices de visualización.
Enviar las matrices de visualización a los nodos esclavos.
while (true)
Recibir todas las imágenes intermedias
Calcular la próxima matriz de visualización.
Enviar la próxima matriz de visualización.
Componer la imagen intermedia final.
Calcular y desplegar la imagen final
void SlavesRenderingLoop()
while (true)
Recibir las matrices de visualización.
for cada brick local do
Calcular la imagen intermedia.
Enviar imagen intermedia al nodo maestro.
RESULTADOS
Los experimentos fueron realizados en cinco sistemas de computación con distintas
características. La descripción de estos sistemas se muestra en la tabla 1.
Sistema
Procesador
Memoria
RAM
1
Pentium III 600 MHZ
256 MB
2
Pentium 4 de 1500 MHZ
3
4
5
Tarjeta
GeForce3
64MB
Tarjeta de Video
Bandwidth
Fill Rate
GB/sec
Texels/sec
7.36
3.2billion
GeForce FX
12.8
1.6 billion
5600 256 MB
GeForce 4 ti
Pentium IV 2.0 GHZ
1 GB
10.4
4.8 Billion
4600 128 MB
GeForce FX
Pentium III 650 MHZ
128 MB
10.4
1.3 billion
5200 128 MB
GeForce 4 ti
Pentium III 550 MHZ
192 MB
8
4 Billion
4200 128 MB
Tabla 1: Características de los sistemas utilizados
256 MB
Sistema Operativo
Windows 2000
Windows XP
Windows XP
Windows 2000
Windows 2000
La aplicación se desarrolló en VC++ 6.0, y el API gráfico OpenGL®. Para la comunicación
se utilizó sockets. Opcionalmente, la transmisión se realiza con data comprimida, ya que
mejora significativamente el rendimiento [7]. El algoritmo de compresión utilizado fue
LZO [10], que en nuestras pruebas reduce el tamaño de los paquetes en aproximadamente
un 75%. Todas las pruebas fueron realizadas con imágenes intermedias de 256x256, y la
imagen final de 512x512. Las rotaciones y acercamiento del volumen fueron las mismas en
todas las pruebas. Al reducir el viewport de las imágenes intermedias se sacrifica calidad de
imagen, pero se envía un 25% del total requerido para una imagen de 512x512.
Se decidió tomar como maestro al equipo con menor rendimiento en las pruebas locales,
para que las máquinas con mejor rendimiento gráfico (esclavas) realicen el cómputo de la
composición volumétrica de bricks. Los volúmenes utilizados para las pruebas fueron de
varias dimensiones, y obtenidos del “Visible Human Project” [11]. Los datos de los
volúmenes se muestran en la tabla 2. La Fig. 5 muestra dos imágenes obtenidas con estos
volúmenes, utilizando cuatro procesadores.
Nombre
Dimensiones
A
B
C
256x256x256
256x512x256
512x512x256
Tabla 2: Datos
Memoria mínima requerida para
almacenar las tres copias
16MB
16MB*3=48MB
32MB
32MB*3=96MB
64MB
64MB*3=192MB
de los volúmenes de entrada
Tamaño
Figura 5: volumen A y B
Los escenarios planteados para obtener los resultados fueron los siguientes: (E1) Ejecución
de la aplicación de manera local con un sólo brick, (E2) con dos bricks y (E3) con cuatro
bricks; (E4) de manera distribuida con dos esclavos, y (E5) con cuatro. Los criterios de
comparación se basaron en los fps (frames per second) y el tiempo en cambio de eje
(tiempo en generar la próxima imagen al cambiar de copia del volumen).
Pruebas Locales
Los resultados muestran que el sistema con mayor rendimiento fue el sistema 2. Este
sistema aprovecha los 256 MB que tiene en la memoria del hardware gráfico para realizar
el intercambio de las copias del volumen, redundando en menos fallos de página. En
cambio, el rendimiento del sistema 5 fue el más pobre. No soportó el experimento en los
escenarios E2 y E3. Esto se debe a los bajos recursos que tiene la máquina para realizar el
intercambio de memoria virtual (200 MB de disco, 192 de memoria RAM). En la Fig. 6, se
muestra una gráfica que ilustra el comportamiento de los distintos sistemas. Aunque se
muestra el escenario E1, los resultados con E2 y E3 son similares. El tiempo de respuesta
para C es muy pobre por los costosos fallos de página al cambiar la copia del volumen.
30,00
30
25,00
Sistema 1
20,00
25
Sistema 2
fps
15,00
Sistema 3
20
Sistema 1
Sistema 4
10,00
Sistema 5
5,00
Sistema 2
Seg.
15
Sistema 3
Sistema 4
0,00
A
B
C
Sistema 1
0,47
0,09
0,04
Sistema 2
25,61
5,24
0,28
Sistema 3
15,76
0,73
0,10
Sistema 4
5,03
0,27
Sistema 5
Figura 6: fps de los sistemas trabajando con dos bricks
localmente. Escenario 1.
Sistema 5
10
5
0
A
B
C
Figura 7: Tiempo del cambio de eje de los sistemas
utilizando dos bricks localmente. Escenario 1.
En cuanto al cambio de eje, los sistemas con mejores resultados fueron el 2 y 3 (ver Fig. 7).
El sistema 2 realiza el cambio de eje en un tiempo inferior que el sistema 3 a pesar de
contar con menos memoria de video. La razón es que este sistema tiene 1GB de RAM y no
necesita memoria virtual para realizar el intercambio de las copias del volumen.
Pruebas Distribuidas
Las pruebas fueron realizadas en una red LAN de 100MB/sec, en horas nocturnas. En los
escenarios E4 y E5 el sistema 5 se selecciona como maestro. El tiempo de respuesta
mejoró para los volúmenes B y C (ver Fig. 8), y el uso de compresión llega a reducir el
tiempo de respuesta en un 30%. El cambio de eje al realizar la prueba en E4 resultó
beneficioso comparado con E2. El peor de los casos, en E2 el cambio de eje duró
aproximadamente 27 seg, y 3 segundos en E4 (ver Fig. 7 y 9). En E5 vemos que la
compresión lzo llega a reducir el tiempo de respuesta en un 50% aproximadamente.
Además, para el volumen C se obtienen más de 10fps (ver Fig. 10), que al comparar E2
(0.28fps) obtenemos una mejora de 35 veces el tiempo de respuesta. Además, en E5 el
tiempo de cambio de eje para el volumen B ya no es significativo (ver Fig. 7,9,11).
Aceleración
Para determinar la aceleración se observó la cantidad de cuadros por segundo con cada
volumen de prueba, cuando se varía la cantidad de procesadores. Para el caso de un
procesador se decidió tomar, el sistema con mejor desempeño (sistema 2) y con la misma
cantidad de bricks según el caso distribuido con el que se este comparando (ver Fig. 12 y
13). Con los volúmenes B y C la distribución generó mejores resultados, llegando a reducir
hasta 35 veces el tiempo de respuesta (volumen C y E5).
3.5
25
3
20
15
Con Compresión
seg
fps
2.5
Sin Compresión
10
2
Con Compresión
Sin Compresión
1.5
1
5
0.5
0
0
A
B
C
A
Figura 8: Fps de los sistemas con escenario E4
C
Figura 9: Tiempo del Cambio de eje con escenario E4
20
4
18
3.5
16
3
14
C o n C o m p re s ió n
2.5
S in C o m p re s ió n
10
seg
12
fps
B
1.5
6
1
4
Con Compresión
2
8
Sin Compresión
0.5
2
0
0
A
B
A
C
Figura 10: fps utilizando con escenario E5
Local
Sin Compresión
B
C
Figura 11: Tiempo del Cambio de eje con Escenario E5
Local
Con Compresión
Sin Compresión
Con Compresión
25
30
20
25
15
fps
fps
20
15
10
10
5
5
0
0
A
B
C
Figura 12: Comparación de fps con 4 bricks, con los
escenarios E2 (local), y E4 (sin compresión y con
compresión)
A
B
C
Figura 13: Comparación de fps con 4 bricks, con los
escenarios E3 (local), y E5 (sin compresión y con
compresión)
CONCLUSIONES
Debido al poder procesamiento que la visualización de volúmenes necesita, se ha utilizado
dos niveles de optimización. El primero corresponde a la utilización del hardware gráfico.
Sin embargo, para volúmenes que sobrepasan las capacidades de memoria de este
hardware, e incluso memoria principal y/o virtual, se requiere un segundo nivel de
optimización, que consiste en el procesamiento distribuido.
Los resultados de las pruebas realizadas indican que el procesamiento local de los
volúmenes que pueden ser cargados totalmente en la memoria de textura, logra un
adecuado tiempo de respuesta. En este caso, el uso de alguna técnica distribuida resulta
contradictoria. Por otra parte, si se sobrepasan las capacidades locales de la memoria de
textura, el rendimiento decae notablemente, debido al intercambio de datos que ocurre entre
memoria RAM y memoria de video, e incluso accesos a disco. En este caso, el
procesamiento distribuido mejora el rendimiento, debido a la disminución de la latencia.
Para reducir el ancho de banda requerido por el envío de imágenes, es necesario aplicar
algunas técnicas como compresión de los datos al momento de transmitir. En este trabajo se
utiliza la librería lzo, que ofrece una compresión promedio de 75% en este tipo de datos.
Esta reducción en el tamaño de los paquetes ayuda a reducir los cuellos de botella de la
LAN, redundando en una mejora en el tiempo de respuesta total hasta en un 50%, pese al
overhead adicional causado por la compresión y descompresión de las imágenes.
BIBLIOGRAFÍA
1. Amin M. B.; Grama, A. y Singh, V. Fast Volume Rendering Using an Efficient, Scalable
Parallel Formulation of the Shear-Warp Algorithm. In Proc. Parallel Rendering
Symposium. Atlanta, pp. 7-14, 1995
2. Carmona, Rhadamés. Shear-Warp: Una implementación Eficiente. In Proc. XXVI
Conferencia Latinoamericana de Informática. Méjico, 2000
3. Lacroute, Philippe G.. Fast Volume Rendering Using Shear-Warp Factorization of the
Viewing Transformation. Reporte Técnico: CSL-TR-95-678, 1995
4. LaMar, Eric; Hamann, Bernd y Joy, Kenneth I. Multiresolution Techniques for
Interactive Texture-Based Volume Visualization. In Proc. Visualization '99. pp 355-362.
1999
5. Neumann, Ulrich. Communication Costs for Parallel Volume-Rendering Algorithms.
IEEE Computer Graphics and Applications. 1994
6. Sano, Kentaro; Kitajima, Hiroyuki; Kobayashi, Hiroaki y Nakamura Tadao. Parallel
Processing of the Shear-Warp Factorization with the Binary-Swap Method on a
Distributed-Memory Multiprocessor System. IEEE Parallel Rendering Symposium.
1997.
7. Schulze, Jürgen P. y Lang, Ulrich. The Parallelization of the Perspective Shear-Warp
Volume Rendering Algorithm. High Performance Computing Center Stuttgart (HLRS),
2002
8. Engels K., Kraus M. y Ertl T. High Quality Pre-Integrated Volume Rendering Using
Hardware-Accelerated Pixel Shading. Siggraph/Eurographics Workshop on Graphics
Hardware. 2001
9. www.opengl.org
10. LZO Data Compression Format 2002. http://oberhumer.com/opensource/lzo/
11. M. J. Ackerman. TheVisible Human Project. In Proc. IEEE, 86(3):504--511, Mar. 1998