UCMUCM APLICACIONES MULTIMEDIA: USO EFICIENTE DE RECURSOS PARALELOS EN ARQUITECTURAS MODERNAS LA TRANFORMADA WAVELET COMO CASO DE ESTUDIO Christian Tenllado

UCM

APLICACIONES MULTIMEDIA: USO EFICIENTE DE RECURSOS

PARALELOS EN ARQUITECTURAS MODERNAS

LA TRANFORMADA WAVELET COMO CASO DE ESTUDIO

Christian Tenllado van der Reijden.Dpto. Arquitectura de Computadores y AutomáticaUniversidad Complutense de Madrid

UCM

Quienes han participado

• Manuel Prieto• Luis Piñuel• Daniel Chaver• Carlos García• Roberto Lario• Christian Tenllado

UCM

Qué voy a contar

• JPEG2000: un vistazo al estándar.• La Transformada Wavelet Discreta• Procesadores Superescalares

– El problema de la Memoria– Procesamiento vectorial en un

superescalar: Extensiones SIMD– Nuevas estrategias de memoria para

Lifting.– Paralelismo a nivel de Thread dentro del

chip: SMT• Coprocesadores de flujos (streams): la GPU• Y... ¿hay más?

UCM

JPEG2000: un vistazo al estándar

• Nuevo estándar de compresión del Joint Photographics Expert Group.

• Sucesor del antiguo JPEG• Añade nuevas características:

– Compresión por bloques con o sin pérdidas.– Mejora tasa de compresión y calidad de imagen.– Soporta la codificación de regiones de interés.– Recuperación progresiva por nivel de detalle.

• La Transformada Wavelet: – fundamental para conseguir estos objetivos– Sustituye a la transformada del coseno del JPEG.

UCM


PreprocessingForward

IntercomponentTransfrom

Forward Intracomponent

TransfromQuantization Tier-1

EncoderTier-2

Encoder

RateControl

Original Image

CodedImage

PostprocessingInverse

IntercomponentTransfrom

InverseIntracomponent

TransfromDequantization

Tier-1Dencoder

Tier-2Dencoder

ReconstructedImage

CodedImage

Ajusta el rango dinámico de la entrada, centrándolo en ceroTransformada Wavelet Discreta (DWT):entera o realCuantización en caso de DWT realCodificación tipo EZW y SPIHTEmpaquetadoCambia de RGB a YCrCb

UCM


• Profiling Jasper: Implementación de referencia creada por miembros de JPEG

Decom% Tiempo de ejecución

Sintética Grises Color

Inter ----- ----- 2.6

IDWT 75.0 63.5 75.4

Cuant. 2.5 3.3 1.7

Tier-1 8.0 9.9 4.9

Tier-2 0.1 0.3 0.1

Comp% Tiempo de ejecución

Sintética Grises Color

Inter ----- ----- 3.1

DWT 49.1 40.0 54.8

Cuant. 2.3 3.2 2.2

Tier-1 34.5 40.9 23.6

Tier-2 0.1 0.1 0.1

Control 2.9 4.6 3.5

UCM

La Transformada Wavelet Discreta

• Surge por una doble necesidad:– Poder analizar señales no estacionarias:

resolución tiempo-frecuencia.– Aplicar diferentes resoluciones a diferentes

frecuencias: análisis de multiresolución.

• Ambas propiedades son muy útiles en compresión:– Detectamos cuantos detalles (altas

frecuencias) tiene la señal y sabemos donde (localización).

– Grandes frecuencias => más resolución. Más coeficientes que representan detalles => “Muchos ceros”.

UCM


• Dos algoritmos para implementar la 1D-DWT:– Filter-Bank: Basado en operaciones de filtrado

lineal y submuestreo con un par de filtros paso baja y paso alta (h,g).

– Lifting: Sweldens propone una reestructuración:• reduce el número de cómputos• Menor uso de memoria • Permite versión entera de la transformada• La transformada inversa es casi idéntica• Sin embargo introduce dependencias.

• La extensión a 2D se realiza aplicando una 1D primero a cada fila (horizontal) y luego a cada columna (vertical). La vertical procesa el resultado de la horizontal.

UCM


• Esquema Filterbank

2H(z)

2G(z)

S(n)

Sub-banda demayor frecuencia

2H(z)

2G(z) …

Siguiente sub-banda

Detalle

Aproximación

UCM


• Características importantes:– No hay dependencias en entre iteraciones.– Requiere dos matrices.– Aproximaciones y detalles quedan contiguos pero

separados.

for( i=0; i < N; i++){

for(j=0, jj=0; j<N; j+=2,jj++){

mat2i,jj = mat1i,j-1*h0+ mat1i,j*h1 + mat1i,j+1*h0;mat2i,jj+N/2 = mat1i,j-1*g0+ mat1i,j*g1+ mat1i,j+1*g0;

}}

UCM


• Extensión 2D:– La matriz se reduce a una cuarta parte

cada vez que se desciende un nivel

L H

LLn

LHn

HLn

HHn

L H

LHn-1 HHn-1

HLn-1LLn-1

UCM


UCM

LazzyTransform NormPredict Update


• Esquema Lifting:

2

2z

S(n)A0(z)

+

B1(z)

+

Aλ-1(z)

+

Bλ(z)

+ K1

K2

A

D

UCM


• Características:– Hay dependencias en entre iteraciones.– Puede hacerse en una sola matriz– Aproximaciones y detalles quedan

entrelazados: suele requerirse una reordenación.

for( i=0; i < N; i++){for(j=0, jj=0; j<N; j+=2,jj++){

mati,j+3+= α(mati,j+2+mati,j+4);mati,j+2+= β(mati,j+1+mati,j+3);mati,j+1+= γ(mati,j +mati,j+1);mati,j += δ(mati,j-1 +mati,j+1);mati,j-1 *=ζ;mati,j-2 *= 1/ζ;

}}

UCM


• Extensión 2D:– Los datos de alta y baja frecuencia

quedan entrelazados

L L LH H

LL

LL

LL

LL

LL

LL

LL

LL LLHL HL

HL HL

HL HL

LH LH LH

LH LH LH

HH HH

HH HH

UCM

Superescalares: El problema de la memoria

• El acceso a la memoria es el principal cuello de botella.

• La DWT tiene mala localidad en uno de los dos procesos, en función del layout escogido.

• Filtrados Vertical y Horizontal no balanceados.

Un layout vertical favorece el procesamiento vertical

Datos lejanos en memoria

Datos contiguosen memoria

UCM


• Bloqueo (Aggregation)– Layout vertical: column

mayor– Filtrado horizontal: no

hay dependencias entre filas.

– Alteramos el orden de los bucles: barremos en el sentido del layout.

UCM


• Majorando la localidad espacial: layouts no lineales: 4D y Morton.

tr

0 1 2 3 4 5 6 7

8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23

24 25 26 27 28 29 30 31

32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55

56 57 58 59 60 61 62 63

tc n

m

tr

tc

tr

0 1 2 3 4 5 6 7

8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23

24 25 26 27 28 29 30 31

32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55

56 57 58 59 60 61 62 63

tc n

m

tr

tc

0 1 2 3 4 5 6 7

8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23

24 25 26 27 28 29 30 31

32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55

56 57 58 59 60 61 62 63

tc n

m

tr

tc

4D Layout

column(j)

row(i)

row(i+Tc)

column(j)

Tc

Tr

column(j)

row(i)

row(i+Tc)

column(j)

Tc

Tr

column(j)

row(i)

row(i+Tc)

column(j)column(j)

Tc

Tr

Filtrado Horizontal con 4D Layout

UCM


• Reducen significativamente los fallos de cache de L2.

• Gran impacto en los fallos por conflicto.• El algoritmo esta limitado por la L2-cache.• 4D y Morton dan resultados similares.

UCM


• Mejorando la localidad temporal: Pipeline computation

• Filtrar verticalmente tan pronto como se pueda.

• Sólo es eficiente si el orden de los cómputos es el de aggregation.

• Requerimos un buffer auxiliar: para el filtro del ejemplo un buffer de dos columnas

• Para imágenes muy grandes el buffer auxiliar puede ser un problema

Buffer Auxiliar

UCM


• Pipeline Computation + 4D layout

First tile column

Second tile column

Third tile column

H VH

H

V

HVV

.....

INITIAL STAGE FINAL STAGE

.....

MAIN STAGE

H

H

VVVVVV V

VVVVVV

First tile column

Second tile column

Third tile column

H VH

H

V

HVV

.....

INITIAL STAGE FINAL STAGE

.....

MAIN STAGE

H

H

VVVVVV V

VVVVVV

UCM


DA

Vertical filtering

12

.....

.....

.....

.....3456

7

Horizontal Filtering+

Aggregation

AB2

....

....AB3

8

......

......

.....

.....

AB1

AB2

AB3

....

....AB1

Step II

AA

DD

AD

.......

..Wavelet

coefficients

Step I

Auxiliary Buffers

DA

Vertical filtering

12

.....

.....

.....

.....3456

7

Horizontal Filtering+

Aggregation

AB2

....

....AB3

8

......

......

.....

.....

AB1

AB2

AB3

....

....AB1

Step II

AA

DD

AD

.......

..Wavelet

coefficients

Step I

Auxiliary Buffers

• Necesitamos un tamaño de buffer auxiliar de tres bloques: independiente del tamaño de la matriz.

UCM


• Algunos resultados (P-III, imagen de 8192x8192)

UCM

Procesamiento vectorial : Extensiones SIMD

• Aplicaciones multimedia pueden considerarse Streaming applications.

• Encaja con el estilo SIMD (Single Instruction Multiple Data)

• Muchos datos son cortos (8 y 16 bits) que en C son previamente convertidos a entero

• Las Extensiones Multimedia (MME) surgen inicialmente con el propósito de manejar eficientemente datos cortos (MMX en Pentium II) con un estilo SIMD.

• Ponto surge la necesidad de aplicar el mismo concepto a FP (SSE en Pentium III y SSE2 en Pentium 4)

UCM


• SSE2: MME del Pentium 4– Ampliación del ISA.– Xmm0-7: nuevos registros independientes

de los tradicionales x87-FP. Son de 128 bits.– X87-FP modelo de registros en pila. Xmm es

un modelo de registros independientes.– Pueden ser utilizados para operaciones FP

escalares.– Instrucciones que permiten al programador

modificar el comportamiento de la jerarquía de memoria: prefetching y streaming stores.

UCM


4 32-bit Integers

8 16-bit Shorts

16 8-bit Chars

xmm0-xmm7

4 32-bit single FP numbers

2 64-bit double FP numbers

128 128

Vector Unit

128

OP OP OP OP

X1(SP) X2(SP) X3(SP) X4(SP)

Y1(SP) Y2(SP) Y3(SP) Y4(SP)

Z1(SP) Z2(SP) Z3(SP) Z4(SP)

Zi= Xi OP Yi

OP

X1(SP) X2(SP) X3(SP) X4(SP)

Y1(SP) Y2(SP) Y3(SP) Y4(SP)

Z1(SP) Z2(SP) Z3(SP) Z4(SP)

Op vectorial

Op escalar

UCM


• MME vs Procesadores Vectoriales– Vectores de menor longitud – Unidades de acceso a memoria más limitadas.

• No soportan operaciones de Gather/Scatter • En muchos casos los datos deben estar alineados, o

si son no alineados el coste de la operación se eleva.

– Repertorio de instrucciones menos general y flexible.

– MME preparadas para manejar referencias a través de punteros.

UCM


• Técnicas de vectorización– Tradicional: Vectorización del filtro

• Problema con SSE: no hay operaciones de reducción en el repertorio

bi bi+1 bi+2 bi+3 bi+4

h0 h1 h2 h3

* * * *

y0 y1 y2 y3

h4

*

y4

Reducción

UCM


• Nuestra Propuesta: En lugar de vectorizar el filtro, filtrar en paralelo varias filas/columnas– Sinergia con aggregation si tenemos los datos

alineados!!!– Problema: sólo se vectoriza de manera efficiente uno de

los dos filtrados (el horizontal con un layout vertical)

UCM


• ¿Cómo vectorizar con MME?– Ensamblador– Intrínsecas– Compilación: Vectorización

guiada• Desambiguación explícita de

puteros• Alineación de memoria a 16

bytes.• Simplificación de estructuras

de bucle• Indexación simple de

vectores.

float restrict* a;float restrict* b;float restrict* c;float restrict* d;

…

#pragma vector alignedfor(i=0; i< N; i++){

a[i] = b[i]*c[i]+d[i];}

UCM


• Efectos laterales:– Se reduce el número de instrucciones– Se reduce el número de loads

• Consecuencia: mejor aprovechamiento de recursos de planificación

Filter Coeficients

row(i)

row(i+3)

row(i+1)

row(i+2)

column(j)

*

+

scalar ops

* * * * * * *+

* * * * * * *+

* * * * * * *+

* * * * * * *+

Wav

ele

t Co

efic

ien

ts

Filter Coeficients

row(i)

row(i+3)

row(i+1)

row(i+2)

column(j)

*

+

scalar ops**

++

scalar ops

* * * * * * *+

** ** ** ** ** ** **+

* * * * * * *+

** ** ** ** ** ** **+

* * * * * * *+

** ** ** ** ** ** **+

* * * * * * *+

** ** ** ** ** ** **+

Wav

ele

t Co

efic

ien

ts

* * * * * * *

+

Filter Coeficients

*

+vector ops

row(i)

row(i+3)

row(i+1)

row(i+2)

column(j)

Wav

ele

t Co

efic

ien

ts* * * * * * *

+

Filter Coeficients

*

+vector ops

row(i)

row(i+3)

row(i+1)

row(i+2)

column(j)

** ** ** ** ** ** **

++

Filter Coeficients

*

+vector ops

**

++vector ops

row(i)

row(i+3)

row(i+1)

row(i+2)

column(j)

Wav

ele

t Co

efic

ien

ts

No Vectorizado Vectorizado

UCM


• Sinergia SIMD-Memoria:– Vectorización de iteraciones: sólo es eficiente

con aggregation y memoria alineada– Con 4D podemos vectorizar los dos filtrados

• Utilizamos una técnica de transposición de bloques.

A D

A

Origin Destination

Store buffer

D

A D

A

Origin Destination

Store buffer

D

UCM

Nuevas estrategias de memoria para Lifting

• Lifting puede hacerse inplace– Menos consumo de memoria y menos fallos de

cache.– Los datos quedan dispersos => sólo se puede

vectorizar el primer nivel de la transformada.

• En muchas aplicaciones es necesario un reordenamiento posterior.

• Parece interesante modificar el algoritmo para:– Vectorizar todos los niveles:– Colocar los datos finales de forma óptima para

el codificador.

UCM


• Alternativa: Mallat (propuesta por Chatterjee)• Nuestra Propuesta: Inplace-Mallat

MATRIX 1 MATRIX 2

L

L

L

L

L

L

L

L

H

H

H

H

H

H

H

H

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

LL1

LL2 LL4

LL3

HH3

HH4HH2

HH1

HL1

HL2 HL4

HL3

LH1

LH2 LH4

LH3

Column Transform

Row Transform

Transformed image (Matrix 1) LL1 LL2 LL3 LL4...

logical view

Transformed image (Matrix 2) LH2LH1 LH4LH3...HL1

MATRIX 1 MATRIX 2

L

L

L

L

L

L

L

L

H

H

H

H

H

H

H

H

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

LL1

LL2 LL4

LL3

HH3

HH4HH2

HH1

HL1

HL2 HL4

HL3

LH1

LH2 LH4

LH3

Column Transform

Row Transform

Transformed image (Matrix 1) LL1 LL2 LL3 LL4...

logical view

Transformed image (Matrix 2) LH2LH1 LH4LH3...HL1

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

LL1

LL2 LL4

LL3

HH3

HH4HH2

HH1

HL1

HL2 HL4

HL3

LH1

LH2 LH4

LH3

L

L

L

L

L

L

L

L

H

H

H

H

H

H

H

H

Column Transform

Row Transform

MATRIX 1 MATRIX 2

Transformed image LL1 LL2 LL3 LL4 LH2LH1 LH4LH3 ...HL1

logical view

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

LL1

LL2 LL4

LL3

HH3

HH4HH2

HH1

HL1

HL2 HL4

HL3

LH1

LH2 LH4

LH3

L

L

L

L

L

L

L

L

H

H

H

H

H

H

H

H

Column Transform

Row Transform

MATRIX 1 MATRIX 2

Transformed image LL1 LL2 LL3 LL4 LH2LH1 LH4LH3 ...HL1

logical view

Inplace-Mallat Mallat

UCM


• Todos los niveles tienen un layout column major

• Datos a procesar contiguos

• Memoria alineada• Conclusión: se pueden

vectorizar todos los niveles

• Los datos contiguos por subbandas => Orden óptimo

x

+

+

x

+

+

UCM


• Añadiendo 4D podría vectorizarse el filtrado vertical!!

409620,0

0,2

0,4

0,6

0,8

1,0

1,2

I M IM

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

819220,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

4,5

5,0

I M IMT

ime

(s

)

Post

Level 4

Level 3

Level 2

Level 1

409620,0

0,2

0,4

0,6

0,8

1,0

1,2

I M IM

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

819220,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

4,5

5,0

I M IMT

ime

(s

)

Post

Level 4

Level 3

Level 2

Level 1

409620,0

0,1

0,2

0,3

0,4

0,5

0,6

I-VEC M-VEC IM-VEC

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

819220,0

0,5

1,0

1,5

2,0

2,5

I-VEC M-VEC IM-VEC

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

409620,0

0,1

0,2

0,3

0,4

0,5

0,6

I-VEC M-VEC IM-VEC

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

819220,0

0,5

1,0

1,5

2,0

2,5

I-VEC M-VEC IM-VEC

Tim

e (

s)

Post

Level 4

Level 3

Level 2

Level 1

Versiones Escalares

Versiones Vectoriales

UCM

• Estrategias tradicionales para incrementar la eficiencia de los procesadores están llegando a su límite:– Superpipelining– Predicción de saltos– Ejecución superescalar– Ejecución fuera de orden

• Han hecho a los procesadores cada vez más complejos, con más transistores y más consumo.

• Diseñadores intentan buscar métodos de incrementar el rendimiento a una tasa mayor que el consumo de potencia y el número de transistores.

Paralelismo a nivel de Thread dentro del chip: SMT

UCM


• Las técnicas de ILP tratan de incrementar el número de instrucciones que pueden procesarse por ciclo.

• El problema es encontrar instrucciones suficientes para ejecutar.– Limitado por dependencias– Acceso a la DRAM lento.– El procesador se queda sin instrucciones

ejecutar cuando se produce un fallo de cache.• Consecuencia: doblar el número de unidades

de ejecución no va a doblar el rendimiento del procesador.

• Limitado paralelismo en el flujo de instrucciones

UCM


• Solución, extraer paralelismo de otras fuentes.

• La mayor parte del software está organizado en threads– Extraer paralelismo entre threads

• Alternativas– Chip Multiprocessing: poner dos procesadores

completos en un mismo chip.– Permitir que un procesador ejecute varios

threads alternando (switching) entre ellos.• Time-slice multithreading• Switch-on-event multithreading

– Simultaneous Multi-threading (SMT)

UCM


• Simultaneous Multi-threading.– Hace que un procesador físico aparezca como

múltiples procesadores lógicos.• Una copia de estado arquitectónico por procesador

lógico.• Recursos físicos compartidos: unidades de

ejecución, recursos de planificación, lógica de predicción, caches, …

– SO y usuarios pueden planificar procesos o threads como si fuesen procesadores físicos convencionales.

– Micro-arquitectura: las unidades funcionales estarán procesando simultáneamente instrucciones de distintos threads.

UCM


• Multiprocesador tradicional vs SMT processor

Arch StateArch State Arch StateArch State

ProcessorExecutionResources



Multiprocesador Procesador con SMT

UCM


• Implementación Intel: Hyper-threading– Se incrementan menos de un 5% el tamaño del

dado y el consumo de potencia

• Características de implementación:– Se controlan las colas de acceso a los

recursos compartidos– El progreso independiente de cada thread

se garantiza:•O bien duplicando las colas: una para cada

thread•O bien limitando el número de entradas de las

colas compartidas que puede copar un thread

UCM


• Recursos que han sido duplicados– Control de acceso a TC y a

la microcode ROM– ITLB– Cola de Streaming buffers– GBHR y Return Stack Buffer– RAT’s (tabla de

renombrado)

UCM


• Recursos compartidos– TC y microcode ROM– Tabla de historia de

patrones (PHT)– Uop Queue, la mitad

para cada uno.– ROB, load y store buffers

(como máximo cada uno puede usar la mitad)

– Colas para la etapa de scheduling (memory & general) (como máximo cada uno puede usar la mitad)

– Schedulers y las colas de schedulers (limitado el máximo número de etradas por procesador lógico)

– DTLB, L1 DC, L2 y L3 caches.

– Unidades Funcionales y Registros

UCM


• Aplicamos la idea a la DWT– Utilizamos OpenMP para la generación

de código multithread

• Dos posibles estrategias– Data Partitioning (DP)

• La mitad de los datos para cada procesador lógico (grupos de columnas).

• El trabajo de ambos procesadores lógicos es el mismo: están balanceados.

• Los dos threads compiten por recursos físicos compartidos.

• El modelo es “teóricamente escalable”.

UCM


• Dos posibles estrategias– Functional Partitioning (FP)

• Cada uno de los threads realiza una de las dos funciones principales: Filtrado Horizontal y Filtrado Vertical.

• No se compite por la cache de datos• El thread vectorizado va por delante, provocando los

fallos de cache– Puede equilibrar ambos threads– Puede haber un efecto de prefetching entre

threads• Necesidad de una correcta sincronización: sobrecarga• Modelo sólo escalable si se combinan DP y FP• Sólo puede aplicarse a versiones Inplace e Inplace-

Mallat con estrategia pipeline.

UCM


• Data Partitioning

β

αα αα

ββ

γ γ

δ δ

γ γ

β

αα αα

βββ

γ γ

δ δ

γ γ

β

δ δδ δ

ζ

1/ζ

ζ

1/ζ

ζ

1/ζ

ζ

1/ζ 1/ζ

Image Row

Horizontal Filtering using Lifting

A B C D E F G H I

Thread i-1

β

αα α

ββ

γ γ

δ δ

γ

δ

ζ ζ

1/ζ

J K L

Thread i

Pre-computation of the Horizontal Filtering

(performed by thread i)

Column Partitioning

Approximation and Details

α Stage

β Stage

γ Stage

δ Stage

NormalizationStage

β

αα αα

ββ

γ γ

δ δ

γ γ

β

αα αα

βββ

γ γ

δ δ

γ γ

β

δ δδ δ

ζ

1/ζ

ζ

1/ζ

ζ

1/ζ

ζ

1/ζ 1/ζ

Image Row

Horizontal Filtering using Lifting

A B C D E F G H I

Thread i-1

β

αα α

ββ

γ γ

δ δ

γ

δ

ζ ζ

1/ζ

J K L

Thread i

Pre-computation of the Horizontal Filtering

(performed by thread i)

Column Partitioning

Approximation and Details

α Stage

β Stage

γ Stage

δ Stage

NormalizationStage

UCM


• Data Partitioning

LLiLLi-1

αα

β

α

β

γ

C D E F

ζ

Pre-c

omput

atio

n of t

he

Horizont

al fi

lterin

g (Thr

ead i)

Artificial Boundary

Thread i-1Thread i

LLiLLi-1

αα

β

α

β

γ

C D E F

ζ

Pre-c

omput

atio

n of t

he

Horizont

al fi

lterin

g (Thr

ead i)αα

β

α

β

γ

C D E F

ζ

Pre-c

omput

atio

n of t

he

Horizont

al fi

lterin

g (Thr

ead i)

Artificial Boundary

Thread i-1Thread i

UCM

// Initial Stagefor( column=0; column < thread_distance; column++)

Horizontal_Filtering(matrix,column);

#pragma omp parallel private(task, more_tasks) shared(control variables){

more_tasks=true;while(more_tasks){

#pragma omp criticalScheduler.next_task(&task);

if(task.type == HTask)Horizontal_Filtering(matrix,task.column);

if(task.type == VTask)Vertical_Filtering(matrix,task.column);

#pragma omp criticalmore_tasks = Scheduler.commit_task(task);

}}


• Functional Partitioning

Secheduling Overhead

UCM


• DP vs FP:– Utilizamos la

estrategia Inplace-Mallat vectorizada

– Alcazan speedups elevados

– Para matrices pequeñas mejor DP: la imagen cabe en L3

– Para matrices grandes, mejor FP: el overhead de sincronización se hace despreciable.

• Hay que buscar estrategias mixtas

DP vs FP in 1 Processor

0,50

0,75

1,00

1,25

1,50

256² 512² 1024² 2048² 4096² 8192²

Image Size

Sp

eed

up

DP 1P && 2T

FP 1P && 2T

UCM


• Efectos sinergéticos entre SMT y SIMD– DP: reducción del nº de instrucciones del SIMD reduce la

competencia por los recursos de planificación.– FP: al vectorizar se hace efectivo el prefetching del thread

horizontal sobre el vertical

1 Processor

0,0

0,5

1,0

1,5

2,0

128² 256² 512² 1024² 2048² 4096² 8192²

Sp

ee

d-u

p

DP (VEC) 1P && 2TFP (VEC) 1P && 2TDP 1P && 2TFP 1P && 2T

UCM

Paralelismo a nivel de Thread dentro del chip: SMT• Eficiencia: SMT alcanza un speedup igual al 75% del

obtenido con un multiprocesador tradicional.– Para matrices pequeñas: el pre-cómputo limita el rendimiento– Para matrices grandes: la contención del bus limita el rendimiento

DP version

1,0

1,5

2,0

2,5

3,0

256² 512² 1024² 2048² 4096² 8192²

Sp

ee

du

p

1P && 2T

2P && 2T

2P && 4T

4P && 4T

UCM

Coprocesadores de flujos (streams): la GPU

• Stream processors: diseñados para procesar flujos de datos.– Sobre todos los datos de un flujo se aplica un programa (kernel)

idéntico– Utilizados sobre todo en empotrados para aplicaciones multimedia– Utiles si el paralelismo de la aplicación es fácil de describir en forma de

streams

CoprocessorMemory

Coprocessor Controler

ExternalMemoryInterface

StreamControl

CPU

Main Memory ALU Cluster

ALU Cluster

ALU Cluster

UCM


• La Pixel Engine de la GeForce FX 5950 puede entenderse como un Stream Coprocessor

• Los Streams son colecciones de cuatro floats que llamamos Pixels

• Para utilizarla como coprocesador:– Hay que pasarle los datos a la tarjeta.

• Se almacenarán en la memoria interna de la tarjeta gráfica.• Hay que elegir una función de mapeo de datos de la matriz al

Pixel-Buffer

– Hay que diseñar la aplicación como un conjunto de kernels que puedan ser aplicados de forma independiente sobre cada Pixel.

– Hay que darle ordenes a la tarjeta para que vaya aplicando estos kernels sobre distintas áreas del pixel Buffer.

– Al final recogemos los resultados.

UCM


• Existen tres posibles funciones de mapeo: 4x1, 1x4 y 2x2

• Escogemos el modelo 2x2 por simetría y simplicidad.

• El problema de la división del algoritmo en kernels está en las dependencias de datos– Versión Filter-Bank

• Necesita dos matrices: no hay posibilidad de azares RAW

• No hay dependencias entre iteraciones: no hay posibilidad de que se produzcan azares WAR

– Versión Lifting• La implementación inplace conlleva riesgos RAW:

necesitamos dos matrices• Hay dependencias entre iteraciones: hay riesgos WAR

UCM


• La implementación Filter-Bank no es compleja

left

_bo

un

da

ry_

fir9

rig

ht_

bo

un

da

ry_

fir9

ce

ntr

al_

fir9

left

_b

ou

nd

ary

_fi

r7

rig

ht_

bo

un

da

ry_

fir7

ce

ntr

al_

fir7

2 pixel = 4 image positions

1 pixel = 2 image positions

Input

Output

fra

gm

en

t pro

gra

m(f

p)

fp_l

eft

_bo

und

ary

_fir

9

fp_

righ

t_b

oun

da

ry_

fir9

fp_

cen

tra

l_fir

9

fragment program sequential order

filter 7 (detail)filter 9 (approach)

filter 7 (detail)filter 9 (approach)

initial image

fp_

left

_bo

und

ary

_fir

7

fp_

righ

t_b

oun

da

ry_

fir7

fp_

cen

tra

l_fir

7

UCM


• Las dependencias de datos en lifting hace que en principio haya que dividir en cinco etapas distintas el algoritmo

α

γ

β

fra

gme

nt s

equ

entia

l ord

er

ai,j-2 ai,j-1 ai,j ai,j+1 ai,j+2 ai,j+3 ai,j+4ai,j-3

1 pixel

δ

normalization

α 1 αα 1 α

β 1 ββ 1 β

γ 1 γγ 1 γ

δ 1 δδ 1 δnormalization

α 1 αα 1 α

β 1 ββ 1 β

γ 1 γγ 1 γ

δ 1 δδ 1 δnormalization

ai,j-4

jj-1

ai,j+1 =ai,j+1+ α(ai,j+ai,j+2)

UCM


• ¿Y si retrasamos las operaciones “problemáticas” a la siguiente etapa?

• Reducimos el algoritmo a sólo tres etapas.

α 1 αα 1 α

β 1 ββ 1 β

γ 1 γγ 1 γ

δ 1 δδ 1 δ

α 1 α

β 1 β

γ 1 γ

δ 1 δ

α 1 αα 1 α

β 1 ββ 1 β

γ 1 γγ 1 γ

δ 1 δδ 1 δ

αβ

normalization

γδ

fra

gme

nt

sequ

entia

l ord

er

ai-2 ai-1 ai ai+1 ai+2 ai+3 ai+4ai-3 ai-2 ai-1 ai ai+1 ai+2 ai+3 ai+4ai-3

1 pixel

UCM


• Algunos resultados: – la técnica

funciona!!– Los tiempos

son excelentes1.68

4.081.51

4.73

16.77

64.56 64.59

16.71

4.69 1.63

14.14

54.42

0

10

20

30

40

50

60

70

2048 1024 512 256

image size

Exe

cuti

on

Tim

e (m

s)

Filter-Bank Lifting Extended Lifting

UCM

Y... ¿Hay más?

• Superescalares:– Analizar las estrategias de memoria en SMT– 4D más vectorización más SMT– Combinar FD y DP en SMT y Multiprocesadores con

SMT– Aplicar SMT a los algoritmos de Filter-Bank– Sintonización de los algoritmos y las técnicas

estudiados según la arquitectura de forma automática: generación automática del código.

– Modificar el estándar JPEG2000 => ZZ_JPEG2000

• GPU– Estudio de distintas funciones de mapeo– Micro-Benchmarking

Documents

UCMUCM APLICACIONES MULTIMEDIA: USO EFICIENTE DE RECURSOS PARALELOS EN ARQUITECTURAS MODERNAS LA TRANFORMADA WAVELET COMO CASO DE ESTUDIO Christian Tenllado