Adequation Algorithme Architecture pour lareconstruction 3D en imagerie medicale TEP

Nicolas GAC

These preparee a l’Institut Polytechnique de Grenoble (INPG)

Direction : Michel DESVIGNES & Stephane MANCINILaboratoire : Gipsa-lab (Departement Images et Signal), Grenoble

17 Juillet 2008

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

2/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

1 Acceleration de la reconstruction 3D en imagerie medicale TEPImagerie medicale TEPAcceleration materielle

2 Adequation Algorithme ArchitectureStrategie d’acces memoireArchitecture 3P : Pipelinee, Prefetchee et Parallelisee

3 Performances de l’architecture 3PProtocole de mesureQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

2/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

3/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

1 Acceleration de la reconstruction 3D en imagerie medicale TEPImagerie medicale TEPAcceleration materielle

2 Adequation Algorithme Architecture

3 Performances de l’architecture 3P

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

3/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

4/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Projet ArchiTEP

Tomographie a Emission de Positons (TEP)

Imagerie fonctionnelle in vivo

Temps de reconstruction importants

γ

γ511 Kev

511 Kev

(Sinogrammes)

1

Visualisation5 Reconstruction4

2 Acquisition

3

Injection du traceur

Enregistrement des données

4/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

5/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¶ Injection du traceur

scanner

Champ de vueVolume

Détecteurs du

5/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

6/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

· Detections des paires de photons emis

scanner

Champ de vueVolume

LORs

Détecteurs du

6/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

7/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¸ Stockage des donnees dans un sinogramme

Sinogrammerho

rhoBins dusinogramme

Champ de vueVolume

phi

rho

phi

7/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

7/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¸ Stockage des donnees dans un sinogramme

rho

rhoSinogramme

rhoBins dusinogramme

Champ de vueVolume

phi

phi

7/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

7/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¸ Stockage des donnees dans un sinogramme

rho

rhoSinogramme

rhoBins dusinogramme

Champ de vueVolume

phi

phi

7/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

7/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¸ Stockage des donnees dans un sinogramme

Sinogramme

rhoBins dusinogramme

Champ de vueVolume

phi

phi

rho

7/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

8/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

¹ Reconstruction du volume : retroprojection 2D

Bins du

Champs de vue

phi

rho

sinogramme

Sommation des bins :

f ∗(xn, yn) =∑phi

bin[phi, rho(phi)]

Calcul des coordonnees :

rho = xn · cos(φ)− yn · sin(φ)= rhoe + ερ

Interpolation lineaire :

bin = (1− ερ) · bin(phi, rhoe)+

ερ · bin(phi, rhoe + 1)

8/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

9/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Acquisition 2D/3D

SINOGRAMME

4

3

2

1

0

−1

y

ESPACE IMAGE

rho

(couple d’anneaux)lambda

phi(angle transverse)

(position tangentielle)

Segment intra−anneaux

z

x

Acquisition 3D ò Meilleure qualite de reconstruction

9/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

9/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Acquisition 2D/3D

SINOGRAMME

4

3

2

1

0

−1Delta#0

(couple d’anneaux)lambda

lambda

phi(angle transverse)

phi

(position tangentielle)

(inclinaison des LORS)Delta

z

x

y

ESPACE IMAGE

x

y

rho

rho

Segment intra−anneaux

Segment inter−anneaux

z

Delta=0

Acquisition 3D ò Meilleure qualite de reconstruction9/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

MesuréSinogramme

Estimation de l’Image

Erreur dans l’espaceimage

Erreur dans l’espacede Projection

Espace Image Espace de projection

Comparaison

Sinogramme estimé

Mise à jour

Rétroprojection

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

MesuréSinogramme

Estimation de l’Image

Erreur dans l’espaceimage

Erreur dans l’espacede Projection

Espace Image Espace de projection

Comparaison

Sinogramme estimé

Mise à jour

Rétroprojection

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

Sinogramme

Estimation de l’Image

Erreur dans l’espaceimage

Erreur dans l’espacede Projection

Mesuré

Espace de projection

Comparaison

Sinogramme estimé

Espace Image

Mise à jour

Rétroprojection

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

MesuréSinogramme

Estimation de l’Image

Erreur dans l’espaceimage

Erreur dans l’espacede Projection

Espace Image Espace de projection

Comparaison

Sinogramme estimé

Mise à jour

Rétroprojection

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

Erreur dans l’espace

MesuréSinogramme

Estimation de l’Image

Erreur dans l’espaceimage de Projection

Espace de projectionEspace Image

Sinogramme estimé

Mise à jour

Rétroprojection

Comparaison

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

10/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Methodes iteratives

Meilleure qualite de reconstruction

Temps de reconstruction plus important

MesuréSinogramme

Estimation de l’Image

Erreur dans l’espaceimage

Erreur dans l’espacede Projection

Espace Image Espace de projection

Comparaison

Sinogramme estimé

Mise à jour

Rétroprojection

Projection

10/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

11/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Necessite d’accelerer la reconstruction

Un probleme de plus en plus complexe

Amelioration de la resolution spatiale des scannersò Volume de ' 106 voxelsò Sinogramme de ' 500 · 106 bins pour le scanner HRRTò ' 1 000 mises a jour par voxel

Utilisation de methodes iterativesò 30 a 40 iterations necessaires en EM

Reconstruction 4D en TEP dynamiqueò 30/60 frames a reconstruire

Temps de reconstruction insuffisant sur PCs

16 heures de calcul en OSEM sur un scanner HRRT

Retard technologique de 10/15 ans par rapport aux scanners

11/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

12/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Acceleration materielle

¶ Parallelisation sur machines multi-processeurs

Efficace sur machine a memoire distribuee

Inefficace sur machine a memoire centraliseeò L’acces a la memoire est un goulot d’etranglement

· Noeuds de calcul performants

Multi-Processor System on Chip (MPSoC) (Cell, GP-GPU)

System on Programmable Chip (SoPC)ò Necessite d’une strategie efficace d’acces memoire

12/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

12/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Imagerie medicale TEPAcceleration materielle

Acceleration materielle

¶ Parallelisation sur machines multi-processeurs

Efficace sur machine a memoire distribuee

Inefficace sur machine a memoire centraliseeò L’acces a la memoire est un goulot d’etranglement

· Noeuds de calcul performants

Multi-Processor System on Chip (MPSoC) (Cell, GP-GPU)

System on Programmable Chip (SoPC)ò Necessite d’une strategie efficace d’acces memoire

12/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

13/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

1 Acceleration de la reconstruction 3D en imagerie medicale TEP

2 Adequation Algorithme ArchitectureStrategie d’acces memoireArchitecture 3P : Pipelinee, Prefetchee et Parallelisee

3 Performances de l’architecture 3P

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

13/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

14/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Algorithme de retroprojection 3D

for (xn, yn, zn) in volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 do// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BI-LINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end for

14/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

14/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Algorithme de retroprojection 3D

for (xn, yn, zn) in volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 do// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BI-LINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end for

14/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

14/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Algorithme de retroprojection 3D

for (xn, yn, zn) in volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 do// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BI-LINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end for

14/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

14/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Algorithme de retroprojection 3D

for (xn, yn, zn) in volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 do// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BI-LINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end for

14/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

15/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Algorithme de retroprojection 3D

Sequence de calcul

Boucles imbriques sans dependance de donneesò Algorithme massivement parallele

Sequence simple de calcul pour la mise a jour d’un voxelò Architecture en pipeline

Acces memoire

Sinogramme de taille importante (10 Mo a 1 Go)ò Stockage du sinogramme en SDRAM

Acces a 4 bins par mise a jour de voxelò Necessite de masquer le temps d’acces en SDRAM

15/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

16/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Strategie d’acces memoire

¶ Reutilisation des donnees

Algorithme ò localite temporelle

· Mecanisme de prechargement memoire

“ad hoc” (double buffering)ò Ressources de calcul supplementairesò Mecanisme de prediction fige

generiqueAlgorithme ò localite spatio-temporelleArchitecture ò cache memoire “intelligent”

16/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

17/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Taux de reutilisation des donnees

rho

rho

phi

ESPACE IMAGE SINOGRAMME

z

y

x

lambda

17/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

17/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Taux de reutilisation des donnees

rho

rho

phi

ESPACE IMAGE SINOGRAMME

z

y

x

lambda

17/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

17/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Taux de reutilisation des donnees

rho

lambda

rho

phi

ESPACE IMAGE SINOGRAMME

z

y

x

17/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

18/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Reconstruction par blocs de voxels

for Bloc in Volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 dofor (xn, yn, zn) in Bloc do

// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BILINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end forend for

18/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

18/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Reconstruction par blocs de voxels

for Bloc in Volume dofor delta = 0 to deltamax − 1 do

for phi = 0 to phimax − 1 dofor (xn, yn, zn) in Bloc do

// CALCUL DES COORDONNEESrho(phi) = xn · cos φ + yn · sin φlambda(phi, delta) = ...// INTERPOLATION BILINEAIREbininterp = C00 · bin00 + C01 · bin01 ...// ACCUMULATIONf ∗(xn, yn, zn) = f ∗(xn, yn, zn) + bininterp · J∆

end forend for

end forend for

18/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

19/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Estimation du taux de reutilisation des donnees

0

5

10

15

20

25

0 200 400 600 800 1000

Tau

x de

réu

tilis

atio

n

Taille du bloc (nombre de voxels)

segment 0segment 1segment 2

Moyenne

Bloc de 162 · 3 : ' 9 sans interpolation bilineaire (' 36 avec)19/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

20/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Mecanisme de prechargement memoire

@=rho+phi*RHO_MAX+z*RHO_MAX*PHI_MAX

xStockage en SDRAM

ESPACE IMAGE SINOGRAMME

lambda

rho

phiz

y

ò Sauts dans l’espace memoire non constant

20/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

20/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Mecanisme de prechargement memoire

@=rho+phi*RHO_MAX+z*RHO_MAX*PHI_MAX

xStockage en SDRAM

ESPACE IMAGE SINOGRAMME

lambda

rho

phiz

y

ò Sauts dans l’espace memoire non constant

20/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

21/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Mecanisme de prechargement memoire

ò Parcours memoire en sinusoıde 3D dans un segment

LAMBDA (COUPLE D’ANNEAUX)

DATE D’ACCES

PH

I (A

NG

LE

TR

AN

SV

ER

SE

)

RHO (POSITION TANGENTIELLE)

21/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

22/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Suivi de la sinusoıde 3D par un cache 3D-AP

DONNEES

COORDONNEES

SoPC : System on Programmable Chip

ADRESSE

DONNEES LatenceSRAM

1 cycle

(10−100 Ko)

(128 Mo−1 Go)

30 nsLatence

3DRP

3D−APCache

SDRAM

RHO (POSITION TANGENTIELLE)

LAMBDA (COUPLE D’ANNEAUX)

PH

I (A

NG

LE

TR

AN

SV

ER

SE

)

DATE D’ACCES

22/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

23/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Prediction par analyse statistique

memoire cache

rho

phi

lambda

zone de garde

zone en cachecentre du cache

Coordonnees des acces memoireprecedents

−→bin(n) =

phi(n)rho(n)

lambda(n)

Calcul de la moyenne des coordonnees

Filtre IIR de premier ordre

23/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

24/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Suivi de la sinusoıde 3D

Mise a jour du cache

Mise à jour effective du cache

Dépassement de la zone de garde 80

100

120

140

160

180

200

0 10000 20000 30000 40000 50000 60000 70000

rho

sequence d’acces memoire

requetes au cachemoyenne estimee

centre du cachezone en cachezone de garde

Mise à jour effective du cache

Dépassement de la zone de garde

Requetes au cacheMoyenne estiméeCentre du cache

Zone en cacheZone de garde

rho

séquence d’accès mémoire

Moyenne estimée

24/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

24/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Suivi de la sinusoıde 3D

Traitement des defauts

80

100

120

140

160

180

200

0 10000 20000 30000 40000 50000 60000 70000

rho

sequence d’acces memoire

requetes au cachemoyenne estimee

centre du cachezone en cachezone de garde

Requetes au cacheMoyenne estiméeCentre du cache

Zone en cacheZone de garde

rho

séquence d’accès mémoire

Défauts de cache

24/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

25/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Pipeline de retroprojection 3D + Cache 3D-AP

Objectif : 1 cycle par mise a jour de voxel

Flot de controle

RAM

Voxel reconstruitBin

CoordoneesFlot de données

FIFO

INTERFACEMEMOIRE

CACHE

3D−AP

FSM

f(x,y,z)

VOXELS

RAM DES

phi

(x,y,z)(n,phi)

(n,phi)

ACCUMULATION

CALCUL DESCOORDONNEES

(rho,phi,lambda)

bin(phi,x,y,z)(n,phi)

INTERPOLATION

BU

S M

EM

OIR

E

COS

FIFO pleine

n

stop

cos(phi)

défaut

25/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

26/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Parallelisation

Donnees communes entre blocs adjacents

ò non reutilisees avec une architecture parallele simple

������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

BUS MEMOIRE

3D−BPFSM

CACHES

y

x

z

3D−BPUnité 2Unité 1 Unité 3

3D−BPUnité 4

3D−BP 3D−BP

26/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

26/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Algorithme de retroprojection 3DStrategie d’acces memoirePipeline + Cache 3D-APParallelisation

Parallelisation

Donnees communes entre blocs adjacents

ò reutilisees grace a une hierarchie memoire

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

CACHES FEUILLES

BUS MEMOIRE

CACHE RACINE

3D−BPFSM

y

x

z

Unité 23D−BPUnité 3Unité 1

3D−BPUnité 4

3D−BP 3D−BP

26/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

27/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

1 Acceleration de la reconstruction 3D en imagerie medicale TEP

2 Adequation Algorithme Architecture

3 Performances de l’architecture 3PProtocole de mesureQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

27/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

28/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Protocole de mesure

Etude en simulation

Premiers “calibrages” du cache

Impossibilite de traiter des donnees de taille “reelle”

Prototypage de l’architecture 3P

Implementation sur un SoPC

Simulateur du bus memoireò Parametrage de la latence et du debit memoire

Donnees utilisees

Sinogrammes correspondant au scanner HR+ de Siemens

Precorrections sur STIR (filtrage, correction en arc ...)

28/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

29/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Mesures effectues sur la carte

¶ Comportement du cache 3D-AP

ηdefaut : taux de defaut de cache

ηcache : taux de reutilisation des donnees mises en cache

· Efficacite de reconstruction

Nombre de cycles d’horloge par mise a jour de voxels

¸ Qualite de reconstruction

EAMr : Erreur Absolue Moyenne relative

29/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

30/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Plateforme SoPC utilisee pour le prototypage

RétroPPC DOCM

BRAMSDRAMCtl

SRAMCtl

InteruptCtl

UART

PontPCI

SDRAMSRAM

Switch

IOCM

32

Virtex II Pro

PCI Carte de developpement Avnet

3D

Cache3D−AP

3D−AP 3D−APCache Cache

PLB

3DRétro

OPB PLB6432

32

Rétro 3D

3D−AP Cache

30/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

31/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Ressources materielles utilisees sur un Virtex 2 Pro

1 unite 4 unites 9 unitesRetro 3D slices CLB 573 1 817 3 924

Multiplieurs 12 48 108

Cache 3D-AP slices CLB 672 2 830 4 804RAMs 2 Ko 24 Ko 36 Ko

Retro 3D + slices CLB 1 245 4 637 8 728Cache 3D-AP (9.1%) (32.9%) (63.7%)

Xilinx 2VP30 (13 696 slices, 136 multiplieurs, 306 Ko RAMs)

13 unites sur un Virtex 4 FX60

ò limitation due au nombre de multiplieurs

31/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

31/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Ressources materielles utilisees sur un Virtex 2 Pro

1 unite 4 unites 9 unitesRetro 3D slices CLB 573 1 817 3 924

Multiplieurs 12 48 108

Cache 3D-AP slices CLB 672 2 830 4 804RAMs 2 Ko 24 Ko 36 Ko

Retro 3D + slices CLB 1 245 4 637 8 728Cache 3D-AP (9.1%) (32.9%) (63.7%)

Xilinx 2VP30 (13 696 slices, 136 multiplieurs, 306 Ko RAMs)

13 unites sur un Virtex 4 FX60

ò limitation due au nombre de multiplieurs

31/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

32/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Comportement du cache 3D-AP

Le cache suit correctement la sinusoıde 3D

ηdefaut ' 0.1 % pour un cache non hierarchique

ηdefaut ' 0.2 % pour un cache hierachique avec 8 unites

Difficulte a suivre “au plus pres” une courbe 3D

ηcache feuille ' 10 (' 36 idealement)

Hierarchie memoire utile a partir de 8 unites

ηcache racine ' 1.1 pour 4 unites (' 3.5 idealement)

ηcache racine ' 1.7 pour 8 unites (' 5 idealement)

32/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

33/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Cycles/op en fonction des segments reconstruits

0.9

0.95

1

1.05

1.1

1.15

1.2

1.25

1.3

1.35

1.4

0 5 10 15 20 25 30

Effi

caci

té d

e re

cons

truc

tion

(cyc

les/

Op)

Latence mémoire (cycles)

segment −2segment −1

segment 0segment +1segment +2

Efficacité optimale L’architecture 3P est efficace

1.05 cycles/op(latence de 30 ns @200 Mhz)

Legere sensibilite

a la latence memoire

a la courbure 3D de la sinusoıdeò Mise a jour du cache plus longò Les defauts bloquent le pipeline

33/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

34/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Cycles/op en fonction du debit memoire

0.8

1

1.2

1.4

1.6

1.8

2

2.2

0 5 10 15 20 25 30

Effi

caci

té d

e re

cons

truc

tion

(cyc

les/

Op)

Latence mémoire (cycles)

d_mem = 8 octets/cycled_mem = 4 octets/cycled_mem = 2 octets/cycled_mem = 1 octet/cycle

d_mem = 0.5 octet/cycled_mem = 0.25 octet/cycle

Efficacité optimale

Robustesse face a la degradation dudebit memoire

Seulement 25 % moins efficaceavec un debit 32 fois moinsimportant

34/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

35/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Cycles/op/unite pour 1, 4 et 8 unites

0.5

1

1.5

2

2.5

3

3.5

0 5 10 15 20 25 30

Effi

caci

té d

e re

cons

truc

tion

par

Uni

té d

e T

raite

men

t (C

ycle

s/O

p/U

T)

Latence mémoire (cycles)

1 pipeline4 pipelines8 pipelines

Efficacité optimale

Facteurs d’acceleration

3.2 pour 4 unites

4.5 pour 8 unites

Conflits d’acces au cache racine

������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

���������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

ò Duplication de lamemoire racineò Desynchronisationdes calculs

35/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

36/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Volume Shepp Logan reconstruit en logiciel (“bit true”)

(a) STIR

(b) 3PA-PET

Abscisse x

STIROriginal

3PA−PET

Inte

nsité

du

volu

me

Comparaison des profils (a) et (b)

Reconstruction de qualite satisfaisante (EAMr ' 1 %)36/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

37/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Volumes reconstruits sur la carte

original logiciel (virgule fixe)

carte (1 unite) carte (8 unites)

37/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

38/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Implementation sur CPUs

Caracteristiques du Pentium 4 et du bi-Xeon dual core

Puissance de calcul : 3.2 GFlops (P4), 12 GFlops (bi-Xeon)

Caches set associatifs (L1 : 16/32 Ko, L2 : 2 Mo)

Optimisations sur CPU

Introduction localite spatiale et temporelleò acceleration d’un facteur 3

Reduction du nombre d’operations par mutualisation descalculsò acceleration d’un facteur 7

Parallelisation avec la librairie pthread sur 4 coeurs (bi-Xeon)

38/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

39/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Architecture des GPUs 8800 de Nvidia

Caracteristiques du GTS 8800

Puissance de calcul : 260 GFlops (8*12 PEs)

Caches 2D de texture (8 Ko)

39/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

40/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Optimisations sur GPU

Parallelisation conservant la localite spatio-temporelle

Reconstruction par blocs de voxels

Reconstruction “en parallele” des voxels adjacents danschaque bloc de voxels

Reduction du nombre d’operations par mutualisation des calculs

ò Acceleration d’un facteur 2

40/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

41/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Temps de Reconstruction sur CPU/GPU/FPGA

Hardware Nb Unites de Temps Cycles/OpTraitement /UT total

Pentium 4 1 2.5 s 16 16CPU (3.2 Ghz, 6.4 Go/s)

bi-Xeon dual core 4 294 ms 7,12 1,78(3 Ghz, 10.6 Go/s)

GPU GTS8800 96 50 ms 12.9 0.135(1.2 Ghz, 64 Go/s)

FPGA Virtex 4 8 526 ms 1,7 0,21(200 Mhz, 0,8 Go/s)

ASIC 5*3PA-PET 40 27 ms 2.62 0,065(1.2 Ghz, 24 Go/s)

41/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

41/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Protocole de mesureComportement du cache 3D-APQualite et efficacite de reconstructionEtude comparative sur CPU/GPU/FPGA

Temps de Reconstruction sur CPU/GPU/FPGA

Hardware Nb Unites de Temps Cycles/OpTraitement /UT total

Pentium 4 1 2.5 s 16 16CPU (3.2 Ghz, 6.4 Go/s)

bi-Xeon dual core 4 294 ms 7,12 1,78(3 Ghz, 10.6 Go/s)

GPU GTS8800 96 50 ms 12.9 0.135(1.2 Ghz, 64 Go/s)

FPGA Virtex 4 8 526 ms 1,7 0,21(200 Mhz, 0,8 Go/s)

ASIC 5*3PA-PET 40 27 ms 2.62 0,065(1.2 Ghz, 24 Go/s)

41/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

42/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Paire materielle de projection/retroprojectionQualite et efficacite de reconstruction

1 Acceleration de la reconstruction 3D en imagerie medicale TEP

2 Adequation Algorithme Architecture

3 Performances de l’architecture 3P

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

42/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

43/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Paire materielle de projection/retroprojectionQualite et efficacite de reconstruction

Algorithme 3D-RP et 3D-EM

Algorithme 3D-RP

Algorithme analytique

Etape de projection utilisee afin d’utiliser les segmentsinter-anneaux

Algorithme 3D-EM

Algorithme iteratif bayesien

Etape de projection fait partie integrante du processus iteratif

Paire materielle de projection/retroprojection

Retroprojecteur “voxel-driven” avec interpolation bi-lineaire

Projecteur par lancer de rayon [Mancini07]

43/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

44/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Paire materielle de projection/retroprojectionQualite et efficacite de reconstruction

Qualite de reconstruction

Reconstruction des volumes PET-SORTEO [Reilhac05]

STIR ArchiTEP STIR ArchiTEP(3D-RP) (3D-RP) (3D-EM) (3D-EM)

Quantification de l’ecart de reconstruction avec STIR

' 1% pour l’algorithme 3D-RP

' 3% pour l’algorithme 3D-EM

44/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

45/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

Paire materielle de projection/retroprojectionQualite et efficacite de reconstruction

Efficacite de reconstruction

Virtex 4 (200 Mhz) vs Pentium 4 (3.2 Ghz)

Acceleration Gain en efficacitepar rapport a STIR par rapport a STIRProj. Retro. Total Proj. Retro. Total

3D-RP 6 17.5 7.5 95 300 1203D-EM 3 12 3.5 50 200 60

45/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

46/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

ConclusionPerspectives

1 Acceleration de la reconstruction 3D en imagerie medicale TEP

2 Adequation Algorithme Architecture

3 Performances de l’architecture 3P

4 Vers une reconstruction de meilleure qualite

5 Conclusion et Perspectives

46/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

47/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

ConclusionPerspectives

Conclusion

Demarche d’Adequation Algorithme Architecture

Lever du verrou technologique constitue par le “mur memoire”ò Parcours memoire en sinusoıde 3D + Cache 3D-AP

Genericite de la strategie memoire adoptee

Acceleration de la retroprojection 3D sur CPU/GPU/FPGA

Fort impact fort de la localite spatio-temporelle

GPU plus rapide mais architecture 3P plus efficace

Vers une reconstruction de meilleure qualite

ò algorithmes 3D-RP et 3D-EM

47/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

48/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

ConclusionPerspectives

Perspectives

Amelioration de la parallelisation des calculs

Parallelisation sur une puce SoC

Parallelisation sur carte multi SoPCsò carte du projet ArchiTEP : 1+6 Virtex 4

Accelerations Algorithmiques

OSEM, sous echantillonage, methodes “divide and conquer”

Tomographie CT

Retroprojection a faisceaux coniques

48/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008

49/49

Acceleration de la reconstruction 3DAdequation Algorithme Architecture

Performances de l’architecture 3PVers une reconstruction de meilleure qualite

ConclusionPerspectives

Merci de votre attention !

49/49

tel-0

0330

365,

ver

sion

1 -

14 O

ct 2

008