cÓmputo paralelo en el procesamiento de … · – tolerar fallas • problemas: ... deteccion,...

CÓMPUTO PARALELOEN EL PROCESAMIENTO DE SEÑALES

DOPPLER DE ULTRASONIDO

Dr. Fabián García Nocetti

DISCA - IIMASUniversidad Nacional Autónoma de México

SEMINARIO MMC 2006

CONTENIDO

• CÓMPUTO PARALELO

• PROC. DE SEÑALES DOPPLER US

• IMPLANTACIÓN

• RESULTADOS

• CONCLUSIONES

SEMINARIO MMC 2006

COMPUTO PARALELO• Cómputo Secuencial (von Neumann):

– Un procesador ejecuta instrucciones una por una– La memoria contiene instrucciones y datos

SEMINARIO MMC 2006

• Problemas para Cómputo de Alto Desempeño:– El procesador puede resultar lento– La memoria puede resultar lenta

COMPUTO PARALELO

• Cómputo Paralelo: Utiliza dos o mas procesadores concurrentemente para resolver un problema.

SEMINARIO MMC 2006

COMPUTO PARALELO

• Multiplicación Matriz vector: Ax = b– Asigna uno o varios renglones de A a cada procesador.– Asigna x a todos los procesadores.– Cada procesador realiza el cómputo de los elementos de b.

SEMINARIO MMC 2006

Procesador 1Procesador 2Procesador 3Procesador 4Procesador 5

• METAS:– Reducir el tiempo de ejecución– Manejar mayor complejidad– Tolerar fallas

• PROBLEMAS:– Cómo partir el problema en un número de

tareas?– Cuál es el tamaño adecuado de éstas?– Cómo distribuir las tareas?

COMPUTO PARALELO

SEMINARIO MMC 2006

COMPUTO PARALELO

• Modelos de Programación:

Concurrente ParaleloSEMINARIO MMC 2006

SEMINARIO MMC 2006

vesselvessel

EBREBR

t/mst/ms

VEVE

Pbackg.Pbackg.

PmaxPmax

Ultrasonido Doppler

Ultrasonido DopplerReflejantes "scatterers"

SEMINARIO MMC 2006

v = Velocidad del flujo sanguíneo (14 - 750 mm/s)

fo= frecuencia de transmisión (4 a 8 MHz)

c = Velocidad del US en la sangre (1500 m/s)

fd= Frecuencia Doppler (100 – 7600Hz)

θ = Angulo entre el haz y el flujo

Ultrasonido Doppler

0cos2 fc

vfdθ

±=

SEMINARIO MMC 2006

Ultrasonido DopplerInstrumento Doppler típico

SEMINARIO MMC 2006

Ultrasonido Doppler

SEMINARIO MMC 2006

A{t}

t / ms

time domain

Doppler Doppler FFTFFT

t/st/s

fDfD

Δt > 10msΔt > 10msPRX{fD}PRX{fD}

fDfD

frequency domainfrequency domain

Ultrasonido DopplerUltrasonido Doppler (método no invasivo)- Frec. Doppler proporcional a la velocidad de sangre

- Espectro Doppler varía con el tiempo

SEMINARIO MMC 2006

Ultrasonido DopplerUltrasonido Doppler- Evolución de distribución de velocidad

- Variación en espectro → detección de padecimientos

SEMINARIO MMC 2006

Ultrasonido Doppler- Detección y cuatificación de flujo:

+ Corazón, Arterias y Venas

- Flujo en arterias es complejo:+ Pulsátil, Sangre (fluido no homogéneo),

Arterias (material viscoelástico)

- Perfiles de velocidad variados+ Selección de técnicas de procesamiento

de señal

SEMINARIO MMC 2006

Ultrasonido DopplerProcesamiento de Señal

SEMINARIO MMC 2006

Ultrasonido DopplerProcesamiento de Señal

SEMINARIO MMC 2006

S P ECT R AL ES TIM AT ORS

F T

PARAM ETR IC

TIM E-F R EQ

B OX CA R W INDOWE D

HA NNING W INDOWE D

A R

A RMA

Y ULE W AK E R

B URG

MODIFIE D COV A RIA NCIA

LS MY WE MA Y NE FIRDOZA N

W IGNE R V ILLE

B ES SE L

B ORN J ORDAN

CHOI W ILL IA MS

Métodos de Estimación Espectral

Ultrasonido Doppler

SEMINARIO MMC 2006

Métodos de Estimación espectral

– Basados en Transformada de Fourier– Modelos Paramétricos

• Auto-Regressive• Moving-Average• ARMA• Others

SEMINARIO MMC 2006

FFT-based (Short-term FT) Model-based (AR-Method)

Métodos de Estimación espectral

SEMINARIO MMC 2006

Métodos de Estimación espectral

SEMINARIO MMC 2006

Métodos de Estimación espectral

SEMINARIO MMC 2006

FT Paramétrico (AR)

Métodos de Estimación espectral

SEMINARIO MMC 2006

• Desempeño de métodos – Señales estacionarias– Segmentos de tiempo cortos para

tratar señales no-estacionarias– Compromiso entre resolución de

frecuencia y tiempo.

Métodos de Estimación espectral

SEMINARIO MMC 2006

• Otros tipos de estimadores espectrales:– Distribuciones Tiempo-frecuencia

Wigner Ville, Choi Williams, Bessel, Born Jordan, Margenau Hill, Kirkwood Rihaczek, Page, Zhao Atlas Marks, Sinc, Adaptative-Q, ...etc.

Métodos de Estimación espectral

SEMINARIO MMC 2006

• The Wigner Ville Distribution

( ) ∫∞

∞−

−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ += τττω ωτdetxtxtWVD j

22, *

( ) ( ) ( )∑−

+−=

−•−=

1

1

2*2,

N

N

Nkj

eWWknDWVDτ

τπ

ττ

( ) ( )ττ −+• nxnx *

Métodos de Estimación espectral

• The Choi Williams Distribution( )

( )

∫ ∫∞

∞−

∞

∞−

−−

•= στμ

σπτω

2

2

424

1,t

etCWD

τμτμτμ ωτdedxx j−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +•

22*

( ) ( ) ( )∑−

+−=

−

⎜⎜⎝

⎛•−=

1

1

2*2,

N

N

Nkj

eWWknDCWDτ

τπ

ττ

( ) ( )⎟⎟

⎠

⎞−+++• ∑

−=

−M

Mnxnxe

μ

στμ

τμτμσπτ

*42

2

2

41

Métodos de Estimación espectral

• The Bessel Distributions( ) ∫ ∫

∞

∞−

∞

∞−

•⎟⎠⎞

⎜⎝⎛ −

⎟⎠⎞

⎜⎝⎛ −

−=ατμ

ατμ

τπαω tUttBD 0

2

12,

τμτμτμ ωτdedxx j−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +•

22*

( ) ( ) ( )∑−

+−=

−

⎜⎜⎝

⎛•−=

1

1

2*2,

N

N

Nkj

eWWknDBDτ

τπ

ττ

( ) ( )⎟⎟

⎠

⎞−+++⎟

⎠⎞

⎜⎝⎛−• ∑

−=

τα

ταμ

τμτματμ

τπα

2

2

*2

211 nxnx

Métodos de Estimación espectral

• The Born Jordan Distribution( ) ∫ ∫

∞

∞−

+

−

−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ += τμτμτμ

ταω

ατ

ατ

ωτt

t

j dedxxtBJD22

121, *

( ) ( ) ( )∑−

+−=

−

⎜⎜⎝

⎛•−=

1

1

2*2,

N

N

Nkj

eWWknDBJDτ

τπ

ττ

( ) ( )⎟⎟⎠

⎞−+++• ∑

−=

τα

ταμ

τμτμτα

2

2

*

41 nxnx

Métodos de Estimación espectral

• Desempeño de DTFs– Señales no-estacionarias– Suministran información relativa

tanto del tiempo como la frecuencia

Sin embargo:

– Mayor complejidad computacional

Métodos de Estimación espectral

SEMINARIO MMC 2006

Arquitectura para Procesamiento

SISTEMA DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

ADSP-21062 SHARC ARCHITECTURE PARTITIONING AND TASK ALLOCATION

Arquitectura para ProcesamientoSISTEMA DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

MODELO COMPUTATIONAL (FARM)

PARMasterPAR i=0 FOR N

Worker

SISTEMA DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

WORKER PROCESS

PARSwitch(MoreWork,

FPrev,ToNext,Work)Feedback(ToPrev,Fnext,

WorkDone)Application(Mwork,Work,

WorkDone)

COMPUTATIONAL MODEL (FARM)

SISTEMA DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

4 Data-Segment on 4 processors

MODELO COMPUTATIONAL (FARM)

SISTEMA DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

Analiticsignal’s 1st

segment

Analiticsignal’s pth

segment

Processor 1t

Processor pt

Processor p+1t

Autocorrelationfunction’s 1th

segment

TFD’s 1th

segment

Processor p+qt

Autocorrelationfunction’s qth

segment

TFD’s rthsegment

Processor p+q+1t

Processor nt TFDi(t,w)

xi(t) Xi+1(t)

TFDi-1(t,w)

Cómputo Paralelo (TFD)

Intrinsic/Algorithm Parallelism

xi(t),i=1,2, ... ,N

SequentialTFD of x1(t)

SequentialTFD of x2(t)

SequentialTFD of xN(t)

TFDi(t,w),i=1,2, ... ,N t

Processor 1

tProcessor 2

tProcessor n

Data Parallelism

Cómputo Paralelo (TFD)

.

SHARC Implementation 1 processor

0

5

10

15

20

Exec

. tim

e (m

s)

4 0.5316 1.0532 2.0964 4.18286 0.8929 1.7874 3.5761 7.15378 1.3324 2.6956 5.422 10.874810 1.8438 3.7717 7.6277 15.3398

64 128 256 512p

p : model order ; N: data length

N

SHARC Implementation 2 processors

02

46

810

Exec

. tim

e (m

s)

4 0.3002 0.5955 1.1859 2.36686 0.4809 0.9626 1.9258 3.85238 0.7006 1.4167 2.8487 5.712810 0.9563 1.9547 3.9516 7.9453

64 128 256 512p

p : model order ; N: data length

N

SHARC Implementation 3 processors

0

2

4

6

Exec

. tim

e (m

s)

4 0.2154 0.4276 0.8518 1.70036 0.3359 0.6723 1.345 2.69068 0.4824 0.975 1.9603 3.930910 0.6528 1.3337 2.6956 5.4193

64 128 256 512p

p : model order ; N: data length

N

SHARC Implementation 4 processors

012

345

Exec

. tim

e (m

s)

4 0.1731 0.3436 0.6848 1.36716 0.2634 0.5272 1.0547 2.10978 0.3732 0.7542 1.5162 3.041110 0.5011 1.0233 2.0676 4.1563

64 128 256 512p

p: model order ; N: data length

N

RESULTADOS (MC)

SEMINARIO MMC 2006

TFD Performance on single DSP SHARC Architecture

0.0

2.0

4.0

6.0

8.0

10.0

12.0

14.0

16.0

15 31 63 127 255 511 1023data-segment

Tim

e [m

s]

Wigner Ville Born Jordan Bessel Choi Williams STFT

Resultados (TFD)

0.00

1.00

2.00

3.00

4.00

5.00

15 31 63 127 255

Signal's length

Tim

e

Wigner, Pipeline Wigner, Farm

Bessel, Pipeline Bessel, Farm

TFD Performance on 4 DSP SHARC: Wigner & BesselIntrinsic/Algorithm Parallelism

Resultados (TFD)

0.0000

1.0000

2.0000

3.0000

4.0000

5.0000

6.0000

15 31 63 127 255 511

Window length

Elap

sed

time

[ms]

1 Proc. 2 Proc.3 Proc. 4 Proc.

TFD Performance on 1 to 4 Sharc DSPs: WignerData Parallelism

Resultados (TFD)

0.0000

1.0000

2.0000

3.0000

4.0000

5.0000

6.0000

15 31 63 127 255 511

Window length

Elap

sed

time

[ms]

1 Proc. 2 Proc. 3 Proc. 4 Proc.

TFD Performance on 1 to 4 Sharc DSPs: BesselData Parallelism

Resultados (TFD)

• Sistema Doppler Bidireccional

SISTEMAS DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

SISTEMAS DOPPLER DE ULTRASONIDO

BLOQUE DE ALIMENTACION Y CARGABLOQUE DE ALIMENTACION Y CARGA

Reg. 5V Cargador Batería Reg. 2.5V

+V

Cargando Batería Baja

Batería Lista

BLOQUE DE ALIMENTACION Y CARGABLOQUE DE ALIMENTACION Y CARGA

Reg. 5VReg. 5V Cargador Batería

Cargador Batería Reg. 2.5VReg. 2.5V

+V

Cargando Batería Baja

Batería Lista

Reg. 5V Charger

Battery

MONITOR

Auto-stop

(2 min)

Reg.

2.5V

Doppler

Detector

PB

BAT

Low Bat

Bat. Ready

Charge

BAT. NiMH

3.6V--1300 mAh

DETALLE DEL BLOQUE DE ALIMENTACION

DETALLE DEL BLOQUE DE ALIMENTACION

100mA

Reg. 5V Charger

Battery

MONITOR

Auto-stop

(2 min)

Reg.

2.5V

Doppler

Detector

PB

BAT

Low Bat

Bat. Ready

Charge

BAT. NiMH

3.6V--1300 mAh

DETALLE DEL BLOQUE DE ALIMENTACION

DETALLE DEL BLOQUE DE ALIMENTACION

100mA

OSC

SEN X

COS X

DIVISORES

A

Transductor

RF

125 KHz

62.5 KHz

(1 – 6 mm)

RF

Tx

4 useg

Rx

12 useg

DRIVER DEL TRANSDUCTORDRIVER DEL TRANSDUCTOR

8MHz8MHz

20 ohms

Graft =>1-3 mm

Tx

Tx/Rx

OSCOSC

SEN X

COS X

DIVISORESDIVISORES

AA

Transductor

RFRF

125 KHz

62.5 KHz

(1 – 6 mm)

RFRF

Tx

4 useg

Rx

12 useg

Tx

4 useg

Rx

12 useg

DRIVER DEL TRANSDUCTORDRIVER DEL TRANSDUCTOR

8MHz8MHz

20 ohms

Graft =>1-3 mm

Tx

Tx/Rx

RF

MIXER

X

X

MIXER

SEN X

COS X

A1

A1

60 – 7000 Hz

60 – 7000 Hz

A2

A2

100 ohms

100 ohms

I

Q

DETECCION, FILTRADO Y AMPLIFICACIONDETECCION, FILTRADO Y AMPLIFICACION

5mV

Vout = 500mV

A1 x A2 = 40dB = 100

Doppler signal

5o. Ord

5o. Ord

RFRF

MIXER

X

MIXER

XX

X

MIXER

XX

MIXER

SEN X

COS X

A1A1

A1A1

60 – 7000 Hz

60 – 7000 Hz

A2A2A2

A2A2A2

100 ohms

100 ohms

III

QQQ

DETECCION, FILTRADO Y AMPLIFICACIONDETECCION, FILTRADO Y AMPLIFICACION

5mV

Vout = 500mV

A1 x A2 = 40dB = 100

Doppler signal

5o. Ord

5o. Ord

SEMINARIO MMC 2006

• Sensores (UNAM-ICIMAF-USC)

SISTEMAS DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

• Sistema Doppler Bidireccional

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1 Señal Directa

Tiempo [s]

Am

plitu

d [V

]

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1Señal Inversa

Tiempo [s]

Am

plitu

d [V

]

2

4

6

8

10

12

Tiempo [s]

Frec

uenc

ia [H

z]

Espectrograma del Flujo Directo

0 0.2 0.4 0.6 0.8

-2500

-2000

-1500

-1000

-500

0

500

1000

1500

20002

4

6

8

10

12

Tiempo [s]

Frec

uenc

ia [H

z]

Espectrograma del Flujo Inverso

0 0.2 0.4 0.6 0.8

-2500

-2000

-1500

-1000

-500

0

500

1000

1500

2000

2

4

6

8

10

12

Tiempo [s]

Frec

uenc

ia [H

z]

Espectrograma

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

-2500

-2000

-1500

-1000

-500

0

500

1000

1500

2000

SISTEMAS DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

• Procesamiento de Señales Doppler

S/W: GRAMFFT

PROCESAMIENTO FFT

ARTERIA: CUBITAL

TRANSDUCTOR: 8 MHz

FREC. DE MUESTREO: 22 KHz

RESOLUCIÓN BITS: 16

FILTRO P-BANDA:300–5000 Hz

RANGO DINÁMICO: 22 dB

SISTEMAS DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

• Procesamiento de Señales Doppler

S/W: GRAMCV4

PROCESAMIENTO COV. MOD.

ORDEN: 4

ARTERIA: CUBITAL

TRANSDUCTOR: 8 MHz

FREC. DE MUESTREO: 22 KHz

RESOLUCIÓN BITS: 16

FILTRO P-BANDA:300–5000 Hz

RANGO DINÁMICO: 22 dB

SISTEMAS DOPPLER DE ULTRASONIDO

SEMINARIO MMC 2006

Poner Qmedia, PI, Qmax, Qmin, y HR(ECG)

Opciones Cardiologia:

•1) Sonograma + curva maxima

•2) Curva instantánea media + running average (Default)

8 MHz, 10 MHz y 20 MHz, que despierte con 8

Agregar ventana para ECG

(Siempre Aparece)

SEMINARIO MMC 2006

Velocidad y Gasto, por default GASTO

Dejarlo así mismo

dejarlo

Agregar botones de:

• SALVAR

• CARGAR

• IMPRIMIR

• BASE DE DATOS

SEMINARIO MMC 2006

Default: 45

Colores sobre fondo negro: VERDE, ROJO, AMARILLO, CYAN, BLANCO

Control de ganancia en esta pantalla. Pendiente cual nivel por default

Rango dinamico por default de 12 dB

Default: Toverlap de 5ms, curvas interpoladas,

Nseg: 512 y Fs : 22050 HzAgregar: Boton de ImpresiónSEMINARIO MMC 2006

Tomógrafo Ultrasónico

IMAGENOLOGÍA ULTRASÓNICA

Tomógrafo Ultrasónico

IMAGENOLOGÍA ULTRASÓNICA

Beam Focusing and steering

Beam Focusing Beam Steering

Beam Re-forming

Tomógrafo Ultrasónico

IMAGENOLOGÍA ULTRASÓNICA

Tomógrafo Ultrasónico

IMAGENOLOGÍA ULTRASÓNICA

Procesamiento

Enfque

Adquisición

Amplifica Sensor

CUADRATIC SPLINESCUADRATIC SPLINES CUBIC CONVOLUTIONCUBIC CONVOLUTIONORIGINALORIGINAL

IMAGENOLOGÍA ULTRASÓNICA

Plataforma Experimental (CINVESTAV)

IMAGENOLOGÍA ULTRASÓNICA

Construcción de Imágenes

Tamaño 2500x100 Paso lateral del transductor 1 mm

Transductor de 2 Mhz5 mm de diametro

IMAGENOLOGÍA ULTRASÓNICA

Construcción de Imágenes

Tamaño 2500x1000Paso lateral del transductor 1 mm

Transductor de 2 Mhz5 mm de diametro

IMAGENOLOGÍA ULTRASÓNICA

Construcción de Imágenes

Tamaño 2500x1000Paso lateral del transductor 1 mm

Transductor de 2 Mhz5 mm de diametro

IMAGENOLOGÍA ULTRASÓNICA

Construcción de Imágenes

Tamaño 2500x1000Paso lateral del transductor 1 mm

Transductor de 2 Mhz5 mm de diametro

• CÓMPUTO PARALELO EN PROC. DE SEÑALES E IMÁGENES

• IMPLANTACIÓN EFICIENTE

• OPCIÓN FLEXIBLE Y ESCALABLE

• ABIERTO A NUEVAS TECNOLOGÍAS Y DESARROLLOS

CONCLUSIONES

SEMINARIO MMC 2006

CONCLUSIONES

• 8 pacientes(abril-julio)• 17 puentes evaluados• 16 permeables de

entrada,1 corregido o revisado en el salon

• No complicaciones relacionadas con revascularizacion

• 2 pacientes con CT-Heli a los 60 dias con permeabilidad(coincidencia 100%)

CONCLUSIONES