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

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)


SEMINARIO MMC 2006


SEMINARIO MMC 2006

FT Paramétrico (AR)


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.


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.


SEMINARIO MMC 2006

• The Wigner Ville Distribution

( ) ∫∞

∞−

−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

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

22, *

( ) ( ) ( )∑−

+−=

−•−=

1

1

2*2,

N

N

Nkj

eWWknDWVDτ

τπ

ττ

( ) ( )ττ −+• nxnx *


• 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


• The Bessel Distributions( ) ∫ ∫

∞

∞−

∞

∞−

•⎟⎠⎞

⎜⎝⎛ −

⎟⎠⎞

⎜⎝⎛ −

−=ατμ

ατμ

τπαω tUttBD 0

2

12,

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

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ +•

22*

( ) ( ) ( )∑−

+−=

−

⎜⎜⎝

⎛•−=

1

1

2*2,

N

N

Nkj

eWWknDBDτ

τπ

ττ

( ) ( )⎟⎟

⎠

⎞−+++⎟

⎠⎞

⎜⎝⎛−• ∑

−=

τα

ταμ

τμτματμ

τπα

2

2

*2

211 nxnx


• The Born Jordan Distribution( ) ∫ ∫

∞

∞−

+

−

−⎟⎠⎞

⎜⎝⎛ −⎟

⎠⎞

⎜⎝⎛ += τμτμτμ

ταω

ατ

ατ

ωτt

t

j dedxxtBJD22

121, *

( ) ( ) ( )∑−

+−=

−

⎜⎜⎝

⎛•−=

1

1

2*2,

N

N

Nkj

eWWknDBJDτ

τπ

ττ

( ) ( )⎟⎟⎠

⎞−+++• ∑

−=

τα

ταμ

τμτμτα

2

2

*

41 nxnx


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

tanto del tiempo como la frecuencia

Sin embargo:

– Mayor complejidad computacional


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


SEMINARIO MMC 2006

WORKER PROCESS

PARSwitch(MoreWork,

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

WorkDone)Application(Mwork,Work,

WorkDone)

COMPUTATIONAL MODEL (FARM)


SEMINARIO MMC 2006

4 Data-Segment on 4 processors

MODELO COMPUTATIONAL (FARM)


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


N


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


N


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


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


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



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)


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


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


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


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



Beam Focusing and steering

Beam Focusing Beam Steering

Beam Re-forming



Procesamiento

Enfque

Adquisición

Amplifica Sensor

CUADRATIC SPLINESCUADRATIC SPLINES CUBIC CONVOLUTIONCUBIC CONVOLUTIONORIGINALORIGINAL


Plataforma Experimental (CINVESTAV)


Construcción de Imágenes

Tamaño 2500x100 Paso lateral del transductor 1 mm

Transductor de 2 Mhz5 mm de diametro


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

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

Documents