Newsgroup: it.lavoro.informatica
Titolo: GPU e tomografia.


-- 
Living in Barbaropoli
http://www.barbaropoli.com


Fondamentalmente quello che dice è che solo negli USA, usando un miglior 
algoritmo/processo (e le GPU di NVidia o ATI), si potrebbe ridurre del 90% 
il rischio che per via della TAC si sviluppi un tumore e di morirne di 
conseguenza, evitando un tumore a 26 mila persone e salvando almeno 13 mila 
vite. All'anno. Soltanto negli USA. Spannometricamente saranno almeno il 
doppio in Europa, e quindi in un decennio sono poco meno di 1 milione di 
persone che si evitano un tumore e 450 mila che non ci muoiono, soltanto in 
USA ed Europa. Se ci aggiungessimo il resto del mondo, non ne parliamo.
Vien da chiedersi se è vero ...
-- 
ale
http://ale.riolo.co.uk
 

 L'avevo letta giorni fa ma mi ero dimenticato di postarla.
rilancio con questo, che e' piu' inerente al gruppo e tratta anch'esso
di ricostruzioni di tomogrammi & GPU:
http://www.ncbi.nlm.nih.gov/pubmed/17029985
interessante questo punto: "The speed gain achieved on the GPUs is in
the order of sixty (60x) to eighty (80x) times, compared to the
performance of a single central processing unit (CPU)".
Per chi non e' abbonato ad Elsevier, copio/incollo alcuni spezzoni
dell'articolo e due tabelle (formattate male, sorry) con il comparison
delle performances delle varie schede.
4. Implementation of the algorithms
In principle, both main steps of these algorithms, projection and
backprojection are straightforward to implement by standard techniques
for sparse matrix handling. Nevertheless, the implementation in a way
that lets the GPU to unfold its full potential requires some degree of
adaptation, as the GPU architecture imposes a number of limitations.
The obtained speed-up relies on the vectorized processing, that is,
the simultaneous application of a given set of instructions to all the
data-entries contained in a vector (texture in GPGPU jargon). When
applying a set of instructions to a working texture, data contained in
other textures can be accessed for read purposes, but GPU architecture
precludes writing in other textures except the working one. The image
approximants and the residuals r can be represented in the working
texture separately, and the projection and the backprojection step
have to be applied sequentially, i.e. after all values in the
projection have been calculated the backprojection can take place. ART
is per construction not vectorizable in this sense: Computing the
projection on pixel j+1 needs the correction on the image approximant
operated by pixel j to be already available, so that starting the
computations simultaneously is not possible.
The backprojection step introduces a further, distinction between SIRT
and SART. As a backprojection updates (writes into) the image
approximant, this has to be selected as the working texture. For each
pixel of the image approximant the contributing pixels in the
projections, seen by the GPU as a parameter, are located and added. In
one iteration of the SIRT algorithm, contributions to a single image
approximant pixel from all the projections are processed in the GPU
simultaneously. In SART, the contributions to this pixel will add
sequentially as the CPU controls the flow of updates from previous
projections into the GPU. In practice, the loop on all the projections
is explicitly controlled by the GPU in SIRT, and implicitly by the CPU
in SART. As this loop cannot be vectorized in SART (the working
texture has already been chosen), because between two backprojection
steps a projection has to be calculated a slight difference in the
acceleration factor should be expected.
The implementation of the algorithms was performed in Cg (Fernando and
Kilgard, 2003). This programming language has been chosen due to the
adequate documentation and the driver support from Nvidia
(
www.nvidia.com
). For programming on the GPU, the program has to be
restricted to certain profiles defined by the GPU, which are also
necessary for the compilation of the program. One of these limitations
is the instruction limit given by the GPU, meaning that a program
cannot be of arbitrary length. On a modern graphics card 65,536
instructions can be performed. This is a significant limitation for
the large EM images and reconstructions. A possible strategy to avoid
the instruction limit is the so-called “multi-passing” (Goddeke,
2005). Therefore, the data was split into smaller portions, and the
algorithm is applied multiple times on smaller portions of the data.
The problem of the instruction limit was especially difficult to deal
within the case of the projection part. Here, the limitation was
complicated by the read-only and write-only rules, so that one pixel
of the projection had to look up many pixels from the image
approximant, in the worst case approx. 1.5 the dimension of the
reconstruction. To avoid this problem, the forward projection was
split into several passes of projections of slices. This did not slow
down the projection by much, but helped greatly in avoiding the
instruction limit. A flowchart diagram of the SIRT algorithm (in this
case, for electron tomography, however, for single particles it is not
significantly different) is presented in Fig. 1 and a detailed pseudo-
code in the Appendix A.
5. Results: quality and performance
The evaluation of the performance of the implementation does not aim
to compare the weighted backprojection and various algebraic
reconstruction techniques or the quality of the GPU and the CPU
implemented algorithms. The evaluation of the algebraic reconstruction
methods has been thoroughly examined by Carazo et al., Kak and Slaney
and others (for further reading see e.g. (Carazo et al., 1999 J.M.
Carazo, C.O. Sorzano, E. Rietzel, R. Schroeder and R. Marabini,
Discrete Tomography in Electron Microscopy. In: G.T.K. Herman, Editor,
Discrete Tomography, Birkhäuser, Basel (1999).Carazo et al., 1999) or
(Kak and Slaney, 1988)). The algorithms running on the GPU should
produce identical results as on the CPU. This however is not true down
to machine precision, mainly due to the slightly different
implementation of the algorithms on the GPU but also because the GPU
does not perform double-precision operations. When comparing real data
reconstructed with double precision with reconstruction performed with
single precision, both on the CPU, the difference of the
reconstructions is zero down to single precision. This yields to the
conclusion that the GPU is not jeopardizing performance due to single
precision operations on EM data, which are typically of 10 bit depth.
Therefore a difference is not noticeable when the data are visually
inspected or in the Fourier shell correlation curves of artificial
data (Fig. 2 and Fig. 3). For the experiments presented below,
artificial as well as real data have been used for the reconstruction
of single axis tilt-series. In Fig. 2 the reconstruction of the
“Barbara” image is presented, reconstructed, with weighted
backprojection SIRT and SART on the CPU and the GPU for various
iterations. The general rule is that the larger the data set and the
more iterations are performed, the higher is the acceleration achieved
on the GPU. The reason is the slow data transfer from the CPU to the
GPU, which happens less frequently. An overview of different
processing times dependent on the hardware used as well as the
dimensions of the reconstructed slice and the iterations performed are
presented in Table 1. The most realistic cases for the day to day
reconstructions of electron tomograms, i.e. with a reconstruction size
of 512 × 512 × 512 pixels with 10 or 50 iterations of SIRT, an
acceleration in the order of 84–85 times is achieved (Table 1). The
acceleration values presented in the Table 1 and Table 2 should also
be transferable to single particle reconstructions, under the
prerequisite that the full reconstruction can be loaded into the
graphics card memory. This limits the reconstruction size to ≈ 256 ×
256 × 256 pixels, which however should be sufficient for large
macromolecular assemblies. With larger graphics card memory larger
images could be reconstructed with arbitrary geometry.
Table 1.
Comparison of different running times of the SIRT algorithm
Iterations	Dimensions	NVIDIA GeForce 6600 GT	Intel Pentium 4, 2.4 GHz
Approx. speed up factor (1)	NVIDIA QuadroFX 4500	Intel Xeon 3.4 GHz
Approx. speed up factor (2)
1	200 × 200	0:03	0:15	4.9	0:01	0:12	7.1
10	200 × 200	0:06	1:44	17.3	0:02	1:28	29.7
50	200 × 200	0:19	8:23	26.5	0:07	7:03	49.7
100	200 × 200	0:35	16:42	28.6	0:14	14:05	57.3
1	512 × 512	0:06	1:15	12.5	0:02	1:34	36
10	512 × 512	0:23	13:44	35.8	0:09	11:24	73
50	512 × 512	1:40	65:00	39	0:39	55:00	84
100	512 × 512	3:15	135:00	41.5	1:16	110:00	85
1	1024 × 1024	0:17	6:35	23.2	0:06	5:34	49
10	1024 × 1024	1:23	45:00	32.5	0:32	38:00	71
50	1024 × 1024	6:17	n/p	n/p	2:26	186:00	76
100	1024 × 1024	12:25	n/p	n/p	4:48	n/p	n/p
1	2048 × 2048	1:01	28:00	27.7	0:23	26:00	67
10	2048 × 2048	5:21	186:00	34.8	2:03	154:00	75
50	2048 × 2048	24:35	n/p	n/p	9:27	n/p	n/p
100	2048 × 2048	48:38	n/p	n/p	18:44	n/p	n/p
Table 2.
Comparison of the various computing times depending on the number of
iterations the dimension of the reconstruction image and the number of
projection angles used
Iterations	Dimensions	Angles	NVIDIA QuadroFX 4500	Intel Xeon 3.4 GHz
Approximate speed up
10	512 × 512	35	0:00:04	0:02:24	36
50	512 × 512	35	0:00:13	0:11:23	52.54
10	512 × 512	70	0:00:06	0:04:51	48.5
50	512 × 512	70	0:00:22	0:23:25	63.86
10	1024 × 1024	35	0:00:11	0:09:39	52.64
50	1024 × 1024	35	0:00:47	0:46:35	59.47
10	1024 × 1024	70	0:00:18	0:19:29	64.94
50	1024 × 1024	70	0:01:20	1:33:31	70.14

 USA ed Europa. Se ci aggiungessimo il resto del mondo, non ne parliamo.
Inquadra il problema dell'assorbimento di radiazioni del paziente e
fornisce dei numeri per farne capire l'impatto.
Il fulcro del discorso e' l'implementazione su GPU di un algoritmo per
ricostruire tomogrammi da pinhole-CT, non il low radiation dose to the
patient (che e' da attribuirsi al pinhole-CT).

 Il fulcro del discorso e' ...
_processo_
--
ale
http://ale.riolo.co.uk

 > Il fulcro del discorso e' ...
"l'implementazione su GPU di un algoritmo per ricostruire tomogrammi
da pinhole-CT" ;-)

 performance of a single central processing unit (CPU)".
nessun commento? :-O
Sono solo io a vederci in tutto cio' l'inizio di una nuova era
nell'elaborazione real-time?
Stiamo parlando di algoritmi pre-esistenti che girano sino ad 80
(!!!!!) volte piu' veloci su GPU!!!!

 (!!!!!) volte piu' veloci su GPU!!!!
IMVHO, almeno astrattamente, molti dei poster/lurker di ILI potrebbero non 
trovarla esattamente una novità.
Dal punto di vista implementativo è un'altro discorso, io un paio di 
processi in cui scommetterei che la parallelizzazione mi potrebbe aiutare 
non poco li avrei, ma non credo di avere il tempo di poter dedicare alla 
cosa a breve.
-- 
ale
http://ale.riolo.co.uk
 

 trovarla esattamente una novità.
dici?
http://tinyurl.com/22qhlw6
Pazienza, quei "molti dei poster/lurker di ILI" esperti in GPU di cui
parli hanno perso un'altra occasione per discuterne. amen.



Il mio concetto di GPU è "roba dentro alla scheda grafica che fa cose e 
vede gente".
Non è neanche detto che tutti sappiano di cosa stai parlando.
  ngw
-- 
Nicholas Wieland (ngw)
Zooppa CTO
911 Western Avenue, Suite 420
Seattle, WA  98104  US

 vede gente".
qui concordiamo ;-) neanche a me piace ne' m'e' mai piaciuta l'idea.
Pero' stiamo parlando di algoritmi (comunemente usati da anni) che
vanno 60-80 volte piu' veloci se reimplementati su GPU!
IMHO aprono veramente le frontiere a tutte quelle applicazioni che
potrebbero essere tranquillamente esportate in real-time o in
dispositivi mobili (ad esempio per la robotica) o in campo aereo-
spaziale e tanti altri (oltre al gia' citato medico/biologico).
Se prende piede, son sicuro che GPU un po' piu' aperte ne verranno
fuori, l'idea che gia' con queste si velocizza di 80x e' come
(chesso', la sparo li') passare ad elaborare da un commodor64 a un
Pentium, a costi (relativamente) ridotti, spazi contenuti e consumo
energetico non eccessivo!!! Ovviamente non tutte le applicazioni
avranno questo guadagno, pero' alcune specifiche e critiche (come la
ricostruzione di tomogrammi) si', e' questo e' gia' IMHO veramente
tanto!

 parli hanno perso un'altra occasione per discuterne. amen.
Il thread che citi mostra appunto che un discreto campione di poster
ILI sono a conoscenza delle promesse e delle possibilità della
tecnologia in questione, anche se qualcuno rimane scettico (o almeno
era scettico quasi 1 anno fa, che in termini informatici può benissimo
equivalere ad una era geologica).
--
ale
http://ale.riolo.co.uk

 equivalere ad una era geologica).
A mio parere bisogna valutare con molta attenzione  l'obiettivo che ci
si pone, il GPGPU è molto interessante ma non è sicuramente un
"acceleratore" così automatico e semplice da usare.
Che poi è lo stesso, in parte, per quanto riguarda le CPU multicore,
non di rado va riscritto completamente l'algoritmo per usarle al
meglio. Cosa che non succedeva quando si aumentava semplicemente la
frequenza di lavoro, oppure del bus, ed altri parametri trasparenti
alle applicazioni.

 vanno 60-80 volte piu' veloci se reimplementati su GPU!
Ciao,
    ero io ad averne parlato,ed ho l'interesse massimo ad approfondire.
Quello che dici alla fine è giustissimo, da "reimplmentare", ma aggiungo 
che molte cose andando avanti si fanno più chiare, anche nell'ottica di 
una consapevole realtà legata al fatto che non è sempre 
facile/conveniente/utile reimpletare tutto per le GPU.
In particolare di recente ho anche letto alcune cose un po' contrarie 
alle GPU e in effetti un po' mi hanno fatto pensare.
In sostanza dice bene questo signore:
http://www.informit.com/articles/article.aspx?p=1606232&WT
e in particolare:
"In theory, you could run any program on a GPU, just as you can run a 
complete OpenGL stack on the CPU. It might not run fast, however, 
because both the CPU and GPU are heavily optimized toward a certain kind 
of instruction stream. CPUs expect a lot of integer computations and a 
lot of branches. The code that runs on a CPU expects a branch around 
every seven instructions, on average. In contrast, a GPU expects very 
few branches and a lot of floating-point arithmetic."
Dove per "branch" si intendono in pratica gli "if".
Questo sostanzialmente cosa significa?
Significa che il codice in cui ci sono parecchi "if" sulle GPU non 
guadagnano molta velocità rispetto alle CPU, anzi ne perdono parecchia.
Le GPU vanno bene per calcoli massivi, continuativi in cui non ci si 
chiede spesso "se è così faccio questo altrimenti faccio quest'altro", 
insomma sono macchine "macina calcoli", che è del resto il motivo per 
cui sono nate!!
Nella vita reale, nel business immagino accadrà qualcosa del tipo che 
Intel prova a rendere le sue CPU quanto più veloci possibile per quello 
stesso tipo di esecuzione con pochi "if" in modo da non farsi fare 
concorrenza da Nvidia e AMD, d'altro canto Nvidia prova a trasformare le 
sue GPU in processori quanto più capaci possibili anche con gli "if". 
AMD invece punta a fusion, ossia a fondere in un unico processore sia 
GPU che CPU, quindi utilizzare ambedue le tecnologie.
E' tutto ancora all'inizio, insomma, e per quanto questo possa farmi 
dispiacere parecchio ho letto in giro che alcuni stanno iniziando un po' 
a disilludersi sulle GPU, proprio per esempio nel campo del raytracing.
In sostanza loro dicono "con le GPU hai molta velocità in più, ma solo 
se vuoi implementare gli algoritmi più semplici, non appena vuoi fare 
qualcosa di più sofisticato la CPU ritorna a essere la strada più 
"conveniente" (per vari motivi) anche per velocità di esecuzione".
http://ompf.org/forum/viewtopic.php?f=8&t=1793&start=0
Little dummy wrote:How about cooperating with Dade and the Lux team for 
a GPU accelerated Mitsuba 0.0.2?
Overall, individual rendering techniques are free to do stuff on the GPU 
(for example, row-column sampling is something that could be implemented 
based on the GL backend), but there are currently no plans to switch 
everything to OpenCL/CUDA. I feel that this really constrains the kinds 
of things you can do, and it would be too limiting for some of the 
fancier rendering techniques, especially MLT.
saluti

 saluti
ciao!