Universitatea Tehnică “Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare
2010
Procesare grafică în sisteme de calcul de mare
performanŃă
Simona (Aruştei) CARAIMAN
- REZUMATUL TEZEI DE DOCTORAT -
Conducător ştiinŃific:
prof. dr. ing. Vasile Ion MANTA
Cuprinsul tezei
Cuprins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Index figuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Index tabele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Index algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
I Introducere 1 (1)
I.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
I.2 Structura tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.3 Diseminarea rezultatelor . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
II Sisteme de calcul de mare performanta 9 (6)
II.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
II.2 Sisteme Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
II.2.1 Aspecte generale . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
II.2.1.1 Arhitectura sistemelor Grid . . . . . . . . . . . . . . . . 14
II.2.1.2 Cerinte pentru sisteme Grid . . . . . . . . . . . . . . . . 15
II.2.2 Standarde Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
II.2.2.1 OGSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
II.2.2.2 OGSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
II.2.2.3 WSRF . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
II.2.2.4 OGSA-DAI . . . . . . . . . . . . . . . . . . . . . . . . 22
II.2.2.5 GridFTP . . . . . . . . . . . . . . . . . . . . . . . . . . 23
II.2.2.6 Standarde specifice serviciilor Web . . . . . . . . . . . . 23
II.2.3 Middleware Grid - Proiectul Globus Toolkit . . . . . . . . . . . . . 23
II.2.3.1 Aspecte generale privind GT4 . . . . . . . . . . . . . . . 24
II.2.3.2 Arhitectura GT4 . . . . . . . . . . . . . . . . . . . . . . 24
II.2.3.3 Servicii Grid Globus Toolkit 4 . . . . . . . . . . . . . . 30
II.2.4 Aplicatii Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
II.2.4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . 36
II.2.4.2 Platforma generica pentru integrarea dinamica de ser-
vicii Grid . . . . . . . . . . . . . . . . . . . . . . . . . . 37
II.2.4.3 Discutie . . . . . . . . . . . . . . . . . . . . . . . . . . 42
II.2.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
iii
iv Cuprinsul tezei
II.3 Calculatoare cuantice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
II.3.1 Aspecte generale . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
II.3.2 Concepte de baza ın calculul cuantic . . . . . . . . . . . . . . . . . 45
II.3.2.1 Principiile calculului cuantic . . . . . . . . . . . . . . . 47
II.3.2.2 Modele de calcul cuantic . . . . . . . . . . . . . . . . . 48
II.3.2.3 Porti cuantice pe un qubit . . . . . . . . . . . . . . . . . 50
II.3.2.4 Porti cuantice pe mai multi qubiti . . . . . . . . . . . . . 51
II.3.2.5 Copierea informatiei cuantice - teorema de Non-Clonare . 52
II.3.2.6 Algoritmi cuantici . . . . . . . . . . . . . . . . . . . . . 53
II.3.3 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
III Procesare grafica ın sisteme cluster si Grid 58 (16)
III.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
III.2 Seturi de date de mari dimensiuni - nori de puncte . . . . . . . . . . . . . . 61
III.2.1 Achizitia norilor de puncte - scanere laser 3D . . . . . . . . . . . . 61
III.2.2 Randarea pe baza de puncte . . . . . . . . . . . . . . . . . . . . . 63
III.3 Simplificarea seturilor de date de mari dimensiuni . . . . . . . . . . . . . . 66
III.3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
III.3.2 Randarea eficienta a norilor de puncte folosind o reprezentare hibrida 68
III.3.3 Detectia planelor ın nori de puncte . . . . . . . . . . . . . . . . . 70
III.3.3.1 Algoritmul RANSAC secvential . . . . . . . . . . . . . 70
III.3.3.2 Algoritmul RANSAC paralel (PRANSAC) . . . . . . . . 72
III.3.4 Implementare si rezultate . . . . . . . . . . . . . . . . . . . . . . . 74
III.3.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
III.4 Vizualizarea seturilor de date de mari dimensiuni ın sisteme Grid . . . . . . 79
III.4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
III.4.2 Metode de randare paralela . . . . . . . . . . . . . . . . . . . . . . 81
III.4.2.1 Paralelismul ın procesul de randare . . . . . . . . . . . . 82
III.4.2.2 Probleme uzuale ale algoritmilor paraleli de randare . . . 86
III.4.2.3 Randarea paralela - o problema de ”sortare” . . . . . . . 87
III.4.2.4 Vizualizarea ın sisteme cluster . . . . . . . . . . . . . . 90
III.4.3 Vizualizarea norilor de puncte proveniti de la scanere laser 3D . . . 91
III.4.3.1 Serviciu grid de vizualizare folosind randarea paralela . . 91
III.4.3.2 Rezultate experimentale . . . . . . . . . . . . . . . . . . 94
III.4.3.3 Discutie . . . . . . . . . . . . . . . . . . . . . . . . . . 96
III.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
IV Procesare grafica ın sisteme cuantice 100 (23)
IV.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
IV.2 Abordarea cuantica a problemei cautarii . . . . . . . . . . . . . . . . . . . 102
IV.2.1 Algoritmul de cautare al lui Grover . . . . . . . . . . . . . . . . . 102
IV.2.1.1 Descrierea algoritmului . . . . . . . . . . . . . . . . . . 102
Cuprinsul tezei v
IV.2.1.2 Iteratia Grover . . . . . . . . . . . . . . . . . . . . . . . 104
IV.2.2 Solutii multiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
IV.2.2.1 Extragerea solutiilor multiple prin protocolul de semi-
clonare . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
IV.2.2.2 Numararea aproximativa a solutiilor folosind estimarea
amplitudinii . . . . . . . . . . . . . . . . . . . . . . . . 111
IV.2.3 Extensii ale algoritmului lui Grover: determinarea maximului . . . 113
IV.3 Aplicatii ale algoritmilor cuantici ın procesarea grafica . . . . . . . . . . . 115
IV.3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
IV.3.2 Problema randarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
IV.3.2.1 Determinarea vizibilitatii primitivelor geometrice . . . . 116
IV.3.2.2 Modele de iluminare globala . . . . . . . . . . . . . . . 119
IV.3.2.3 Managementul nivelurilor de detaliu . . . . . . . . . . . 127
IV.3.3 Geometrie computationala cuantica . . . . . . . . . . . . . . . . . 128
IV.3.4 Algoritmul RANSAC cuantic - QRANSAC . . . . . . . . . . . . . 129
IV.3.4.1 Algoritmul RANSAC clasic . . . . . . . . . . . . . . . . 129
IV.3.4.2 QRANSAC . . . . . . . . . . . . . . . . . . . . . . . . 130
IV.3.4.3 Aplicatii ale algoritmului QRANSAC - algoritm cuan-
tic pentru identificarea structurilor planare ıntr-un nor de
puncte . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
IV.4 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
V Simularea calculelor cuantice 136 (37)
V.1 Justificare - necesitatea simularii . . . . . . . . . . . . . . . . . . . . . . . 136
V.2 Clasificarea simulatoarelor cuantice . . . . . . . . . . . . . . . . . . . . . 137
V.3 Limbaje de programare cuantica . . . . . . . . . . . . . . . . . . . . . . . 140
V.4 Limbajul QCL (Quantum Computation Language) . . . . . . . . . . . . . 142
V.4.1 Caracteristicile limbajului QCL . . . . . . . . . . . . . . . . . . . 142
V.4.2 Quantum Computer Simulator Library (QC-lib) . . . . . . . . . . . 143
V.4.3 Simularea problemei Bernstein-Vazirani . . . . . . . . . . . . . . . 144
V.4.3.1 Definirea problemei . . . . . . . . . . . . . . . . . . . . 144
V.4.3.2 Analiza problemei utililizand formalismul portilor cuantice145
V.4.3.3 Exemplu . . . . . . . . . . . . . . . . . . . . . . . . . . 146
V.4.3.4 Implementarea algoritmului ın QCL . . . . . . . . . . . 147
V.4.4 Simularea algoritmului lui Grover . . . . . . . . . . . . . . . . . . 148
V.4.4.1 Formularea unei interogari . . . . . . . . . . . . . . . . 148
V.4.4.2 Spatiul de cautare . . . . . . . . . . . . . . . . . . . . . 148
V.4.4.3 Iteratia Grover . . . . . . . . . . . . . . . . . . . . . . . 149
V.4.5 Simularea algoritmului de numarare aproximativa a solutiilor . . . 150
V.4.6 Simularea algoritmului pentru determinarea valorii maxime . . . . 153
V.5 Simularea calculelor cuantice ın sisteme Grid . . . . . . . . . . . . . . . . 155
V.5.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
vi Cuprinsul tezei
V.5.2 GQCL - Serviciu Grid pentru QCL . . . . . . . . . . . . . . . . . 156
V.5.2.1 Arhitectura serviciului . . . . . . . . . . . . . . . . . . . 156
V.5.2.2 Implementarea paralela a bibliotecii QC-lib . . . . . . . 158
V.5.3 Rezultate experimentale . . . . . . . . . . . . . . . . . . . . . . . 163
V.5.3.1 Transformata Hadamard . . . . . . . . . . . . . . . . . . 163
V.5.3.2 Problema Bernstein-Vazirani . . . . . . . . . . . . . . . 166
V.5.3.3 Problema cautarii . . . . . . . . . . . . . . . . . . . . . 167
V.6 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
VI Concluzii finale, contributii si directii viitoare de cercetare 169 (46)
VI.1 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
VI.2 Contributii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
VI.3 Directii viitoare de cercetare . . . . . . . . . . . . . . . . . . . . . . . . . 173
Bibliografie 176
Capitolul I
Introducere
Primul capitol al acestei lucrari justifica abordarea temei si puncteaza principalele obiective
atinse, precum si modul ın care contributiile aduse temei au fost validate prin publicarea rezul-
tatelor obtinute.
Motivatie
De-a lungul timpului, toate formularile destinate sa caracterizeze calculul de mare performanta
au provenit din natura revolutionara a sistemelor construite la momentul respectiv. Indiferent
de modalitatea de caracterizare a sistemelor de calcul de mare performanta, orizonturile oferite
de Legea lui Moore ne determina sa trasam doua directii importante de-a lungul carora trebuie
urmarita dezvoltarea sistemelor de calcul de mare performanta: sistemele Grid si calculatoarele
cuantice. Calculul heterogen, ce poate fi implementat prin intermediul sistemelor Grid, prezinta
un potential imens pentru accelerarea aplicatiilor, mai mult decat ne-am putea astepta de la Legea
lui Moore, odata cu depasirea multor bariere ce limiteaza arhitecturile conventionale. Pe de alta
parte, la scara foarte mica, natura este descrisa de legile fizicii cuantice si nu de cele ale fizicii cla-
sice. Daca miniaturizarea va atinge ın curand scara subatomica, fenomenele cuantice vor influenta
drastic comportamentul semiconductorilor si a microchip-urilor.
Indiferent de solutia de calcul abordata si de modul de generare a informatiilor, o necesitate
importanta o reprezinta vizualizarea grafica a acestora. Aceste informatii pot fi date, procese,
relatii sau concepte. Intelegerea informatiilor poate presupune detectia, masurarea si compararea,
si este realizata prin intermediul tehnicilor interactive si a prezentarii informatiilor provenind din
mai multe puncte de observare si prin mai multe tehnici. In prezent exista o varietate de resurse
computationale disponibile pentru vizualizare. In timp ce un numar foarte mare de utilizatori sunt
multumiti de capabilitatile de vizualizare disponibile prin intermediul PC-urilor moderne si a accel-
eratoarelor grafice 3D, multi altii se bazeaza pe calculul de mare performanta pentru vizualizarea
seturilor de date de mari dimensiuni sau pentru a obtine performante corespunzatoare randarii ın
timp real pentru vizualizari complexe.
Consideram astfel ca necesitatea abordarii calculului de mare performanta ın procesarea grafica
provine, ın mare parte, chiar din raspandirea utilizarii acestor sisteme de generare a informatiilor.
1
Capitolul I: Introducere 2
Aceste informatii sunt generate ın cantitati impresionante, iar ıntelegerea lor presupune dezvoltarea
de noi tehnici de procesare si vizualizare care sa utilizeze la randul lor calculul de mare performanta.
In dezvoltarea acestor noi tehnici de vizualizare au aparut doua directii de abordare pentru re-
zolvarea problemei seturilor de date de mari dimensiuni. Pe de o parte, au fost investigate metode
de simplificare a modelelor exprimate de aceste seturi de date, iar pe de alta parte, s-au dezvoltat
diverse tehnici de procesare ın paralel a acestora.
Desi aceste abordari utilizate ın procesarea si vizualizarea seturilor de date de mari dimensiuni
au produs rezultate semnificative, ıncurajatoare, integrarea si utilizarea lor ın sistemele de calcul
de mare performanta de ultima generatie presupune noi provocari pentru care nu au fost formulate
ınca solutii complete, satisfacatoare.
In acest context, lucrarea de fata ısi propune investigarea tehnicilor existente de procesare a
informatiilor pentru reprezentarea vizuala a acestora si formularea de noi solutii algoritmice pen-
tru astfel de probleme precum si investigarea modalitatilor de integrare si utilizare a acestora ın
contextul actual de dezvoltare a sistemelor de calcul de mare performanta. Tendintele ınregistrate
ın domeniul calculului de mare performanta au impus analizarea problemelor de procesare grafica
ın raport cu proliferarea sistemelor Grid si cu emergenta calculatoarelor cuantice.
Desi de la sfarsitul anilor ’90 la nivel mondial se depun eforturi considerabile, atat de cerc-
etare cat si economice, sistemele Grid nu si-au atins ınca potentialul promis datorita complexitatii
conceptelor implicate. Vizualizarea informatiilor ın astfel de sisteme reprezinta o componenta in-
dispensabila iar implementarea ei trebuie sa tina cont de toate cerintele necesare pentru dezvoltarea
acestor sisteme. Aceasta presupune atat adaptarea la aceste noi cerinte a solutiilor formulate deja
pentru procesarea grafica ın sisteme paralele si distribuite, precum si dezvoltarea de noi solutii
specifice. Astfel, unul din obiectivele cercetarilor care au produs aceasta lucrare a fost dezvoltarea
unor metode de integrare facila ın sisteme Grid a solutiilor existente pentru procesare grafica. S-a
ıncercat dezvoltarea unei platforme generice pentru integrarea dinamica de servicii Grid, care sa
furnizeze accesul la un sistem Grid la un nivel mai ınalt, prin abstractizarea detaliilor middleware-
ului Grid fata de utilizatorul final. Acest utilizator poate fi un specialist ın probleme de procesare
grafica care doreste expunerea pe Grid a unor aplicatii existente. Sarcina de a dezvolta aplicatii
noi sau de a porta aplicatii existente ın sisteme Grid este una dificila, cauzand o lipsa evidenta
de utilizatori ın aceste sisteme. Un astfel de instrument care sa permita generarea mai simpla si
mai usoara de servicii Grid specifice, spre exemplu domeniului procesarii grafice, ar promova im-
plicarea cercetatorilor din mai multe domenii ın atingerea obiectivelor sistemelor Grid. Validarea
acestui instrument este realizata prin ilustrarea dezvoltarii unor servicii Grid de procesare grafica,
precum servicii pentru vizualizarea seturilor de date de mari dimensiuni prin utilizarea tehnicilor
de randare paralela, sau servicii pentru procesare si afisare ın paralel a imaginilor vectoriale de
mari dimensiuni.
In ceea ce priveste furnizarea de solutii noi pentru procesarea seturilor de date de mari di-
mensiuni, s-a ıncercat formularea unei noi metode de simplificare a acestora care sa faca uz de
resursele de calcul paralel si distribuit. Tehnicile de simplificare a modelelor dezvoltate pana ın
prezent au fost motivate de necesitatea reducerii continutului de informatie pentru crearea de mod-
ele multirezolutie si accelerarea randarii. Cerintele de performanta impuse acestor tehnici au de-
terminat mentinerea unui echilibru ıntre calitatea modelului obtinut, timpul de procesare si spatiul
Capitolul I: Introducere 3
ocupat de acesta, indiferent daca este vorba de tehnici offline sau tehnici de timp real. In functie
de scopul aplicatiilor, s-au dezvoltat tehnici pentru care balanta s-a ınclinat ın favoarea uneia sau a
cel mult doua din aceste cerinte. Din acest motiv consideram necesara inspectarea modalitatilor de
exploatare a calculului paralel si distribuit ın vederea obtinerii de performante crescute din toate
cele trei puncte de vedere. Seturile de date de mari dimensiuni reprezentate prin nori de puncte au
devenit din ce in ce mai frecvente datorita raspandirii sistemelor de achizitie prin scanare laser 3D.
Pentru vizualizarea acestor date propunem folosirea unei reprezentari hibride a norilor de puncte
compusa din structuri planare texturate si din puncte, obtinuta prin procesarea paralela a setului de
date initial. Aceasta tehnica asigura performante crescute din toate punctele de vedere mentionate.
Cu toate ca cercetarile ın domeniul implementarii fizice a calculatoarelor cuantice au produs
pana ın prezent doar rezultate ın cadrul laboratoarelor de cercetare, interesul pentru dezvoltarea
de solutii algoritmice pentru probleme specifice informaticii cuantice este ın continua crestere.
Potentialul imens al acestor sisteme de calcul a fost demonstrat atat la nivel teoretic, cat si la nivel
practic, desi la o scara destul de redusa. Exploatarea acestui potential, demonstrarea practicalitatii
acestor sisteme si justificarea construirii lor impun ınsa gasirea de solutii cuantice pentru majori-
tatea problemelor ce pot fi rezolvate folosind sisteme de calcul clasice, precum si pentru probleme
a caror rezolvare nici nu a putut fi ınchipuita folosind sistemele conventionale de calcul. In acest
context, domeniul procesarii grafice este un domeniu aflat ıntr-un stadiu incipient, dar pentru care
este absolut necesara formularea cel putin a solutiilor problemelor fundamentale. Potentialul de
cercetare al acestui domeniu este de asemenea imens, deoarece, ın momentul actual, cercetarile se
afla abia ın stadiu de tendinte. In consecinta, asa cum s-a remarcat ın cadrul unei conferinte de
prestigiu la care au fost prezentate cateva din rezultatele continute ın lucrarea de fata, cei implicati
ın formularea de algoritmi si dezvoltarea de software pentru calcul cuantic ”are playing God: they
define the Universe and the laws of the Universe, on which wonderful computing devices emerge.
It is not possible to fail using this strategy.”1. Cu toate acestea, formularea de astfel de solutii
algoritmice este o sarcina foarte complexa deoarece, pe langa dificultatea exploatarii eficiente a
avantajelor sistemelor cuantice, intervine dificultatea eliminarii acelor deficiente, efecte nedorite,
introduse de caracteristicile calculului cuantic. Lucrarea de fata ısi propune descrierea unor prob-
leme fundamentale de procesare grafica ın termeni cuantici. Vom prezenta astfel, algoritmi cuantici
pentru problema randarii (determinarea vizibilitatii primitivelor geometrice, modele de iluminare
globala, managementul nivelurilor de detaliu), dar si pentru tehnici avansate de simplificare a mod-
elelor de mari dimensiuni.
Validarea acestor solutii algoritmice nu se poate realiza ın prezent folosind hardware cuantic,
datorita accesului foarte limitat la astfel de implementari. Din acest motiv au aparut simulatoarele
pentru calcul cuantic ce permit o implementare a algoritmilor cuantici descrisi la nivel teoretic.
Aceste simulari ale calculului cuantic folosind sisteme de calcul clasice prezinta vadite limitari
ın ceea ce priveste performantele timpului de executie dar si dimensiunea problemelor ce pot fi
simulate. In acest context consideram oportuna utilizarea sistemelor Grid pentru realizarea de ast-
fel de simulari. Dezvoltarea unui simulator cuantic ce exploateaza calculul paralel si distribuit si
expunerea ın sisteme Grid a unei astfel de functionalitatii fac parte astfel din cercetarile efectuate
1este vorba despre una din remarcile transmise odata cu recenzia lucrarii [Caraiman 09c]
Capitolul I: Introducere 4
ın contextul acestei lucrari.
Diseminarea rezultatelor
Articolele stiintifice ce stau la baza acestei lucrari au fost publicate ın reviste (5) si volume
(3) de specialitate sau prezentate la conferinte internationale (7) si sunt indexate ın baze de date
bibliografice recunoscute: Thomson ISI (3), IEEE (1), ACM (1), DBLP (3). Contributiile aduse
ın cadrul temei ”Procesare grafica ın sisteme de calcul de mare performanta” s-au conturat ın jurul
urmatoarelor directii de cercetare:
• dezvoltarea de sisteme si servicii Grid si formularea de solutii bazate pe calcul paralel si
distribuit pentru probleme de procesare grafica
S. (Caraiman) Arustei, A. Archip, and C.M. Amarandei. Parallel RANSAC
for Plane Detection in Point Clouds. Buletinul Institutului Politehnic din Iasi,
Automatic Control and Computer Science Section, LIII(LVII):139–150, 2007.
S. (Caraiman) Arustei, M. Craus, and A. Archip. Towards a Generic Framework
for Deploying Applications as Grid Services. In Marten van Sinderen, editor,
Proceedings of 2nd International Workshop ACT4SOC held in conjunction with
3rd International Conference on Software and Data Technologies, 5-8 JUL, 2008
Porto PORTUGAL, pages 17-26, Setubal, Portugal, 2008. INSTICC Press. (ISI)
S. (Caraiman) Arustei, A. Archip and C.M. Amarandei. Grid Based Visual-
ization Using Sort-Last Parallel Rendering. In H.N. Teodorescu and M. Craus,
editors, Scientific and Educational Grid Applications, pages 101–109, Iasi, Ro-
mania, 2008. Politehnium.
A. Archip, M. Craus, and S. (Caraiman) Arustei. Efficient Grid Service Design
to Integrate Parallel Applications. In Marten van Sinderen, editor, Proceedings of
2nd International Workshop ACT4SOC held in conjunction with 3rd International
Conference on Software and Data Technologies, 5-8 JUL, 2008 Porto PORTU-
GAL, pages 7-16, Setubal, Portugal, 2008. INSTICC Press. (ISI)
A. Archip, C.M. Amarandei, S. (Caraiman) Arustei, and M. Craus. Optimiz-
ing Association Rule Mining Algorithms Using C++ STL Templates. Bulet-
inul Institutului Politehnic din Iasi, Automatic Control and Computer Science
Section,LIII(LVII):123-132, 2007.
C.M. Amarandei, A. Archip, and S. (Caraiman) Arustei. Performance Study for
MySql Database Access Within Parallel Applications. Buletinul Institutului Po-
litehnic din Iasi, Automatic Control and Computer Science Section, LII(LVI):127–
134, 2006.
Capitolul I: Introducere 5
A. Archip, S. (Caraiman) Arustei, C.M. Amarandei and A. Rusan. On the de-
sign of Higher Order Components to integrate MPI applications in Grid Services.
In H.N. Teodorescu and M. Craus, editors, Scientific and Educational Grid Ap-
plications, pages 25–35, Iasi, Romania, 2008. Politehnium.
C.M. Amarandei, A. Rusan, A. Archip and S. (Caraiman) Arustei. On the De-
velopment of a GRID Infrastructure. In H.N. Teodorescu and M. Craus, editors,
Scientific and Educational Grid Applications, pages 13–23, Iasi, Romania, 2008.
Politehnium.
• formularea de solutii algoritmice pentru probleme de procesare grafica ın sisteme cuantice
S. (Arustei) Caraiman and V. Manta. New Applications of Quantum Algorithms
to Computer Graphics: the Quantum Random Sample Consensus Algorithm. In
CF ’09: Proceedings of the 6th ACM Conference on Computing frontiers, pages
81–88, New York, NY, USA, 2009. ACM.
S. (Arustei) Caraiman and V. Manta. A Quantum Random Sample Consensus
Algorithm for Point Cloud Simplification. In B.H.V. Topping and P. Ivanyi, edi-
tors, Proc. of the First International Conference on Parallel, Distributed and Grid
Computing for Engineering, Stirlingshire, UK, 2009. Civil-Comp Press. (ISI)
• simularea algoritmilor cuantici folosind limbaje de programare cuantica si simularea calcu-
lului cuantic folosind resurse ale sistemelor Grid
S. (Caraiman) Arustei and V. Manta. QCL Implementation of the Bernstein-
Vazirani Algorithm. Buletinul Institutului Politehnic din Iasi, Automatic Control
and Computer Science Section, LIV(LVIII):35–44, 2008.
S. (Arustei) Caraiman, A. Archip, and V. Manta. A Grid Enabled Quantum
Computer Simulator. In SYNASC’09: Proceedings of the 11th International Sym-
posium on Symbolic and Numeric Algorithms for Scientific Computing, 2009 (to
be published by IEEE Computer Society Press).
S. (Arustei) Caraiman and V. Manta. Grid Enabling QC-lib Quantum Computer
Simulator Library. In CSCS17: Proceedings of the 17th International Conference
on Control Systems and Computer Science, pages 531-538, 2009.
S. (Arustei) Caraiman and V. Manta. Paralel Simulation of Quantum Search.
Submitted at International Conference on Computers, Communications and Con-
trol (ICCCC), Oradea, Romania, May 12-16, 2010 (extended abstract accepted).
S. (Arustei) Caraiman. QCL Implementation of Quantum Search Algorithms.
Buletinul Institutului Politehnic din Iasi, Automatic Control and Computer Sci-
ence Section, LVI(LX), 2010.
Capitolul II
Sisteme de calcul de mare performanta
Acest capitol este rezervat definirii si clasificarii sistemelor de calcul de mare performanta,
atentia fiind concentrata asupra sistemelor Grid si a calculatoarelor cuantice.
Puterea impresionanta de procesare generata de producatorii de calculatoare nu a reusit ınca
sa multumeasca setea de viteza si de capacitate de calcul. In 1947, Howard Aiken, inginer ın
domeniul calculatoarelor, prezicea ca doar sase calculatoare electronice digitale ar fi suficiente sa
satisfaca necesitatea de calcul a Statelor Unite. Si altii au facut astfel de predictii eronate ın ceea
ce priveste puterea de procesare ce ar suporta nevoile tehnologice ın continua crestere. Desigur ei
nu au luat ın considerare cantitatile imense de date generate de cercetarea stiintifica, proliferarea
calculatoarelor personale sau aparitia Internetului. O problema stringenta este daca vom dispune
vreodata de puterea de procesare de care avem nevoie sau pe care ne-o dorim. Daca numarul
de tranzistori dintr-un microprocesor continua sa se dubleze o data la fiecare 18 luni, conform
Legii lui Moore, atunci ın 2020 sau 2030 circuitele unui microprocesor vor fi masurate la scara
sub-atomica. Aceasta observatie a determinat dezvoltarea cercetarii ın directii care sa permita
depasirea barierelor impuse de arhitecturile conventionale. Astfel, dezvoltarea sistemelor de cal-
cul de mare performanta (High Performance Computing systems) devine o necesitate, de aici si
motivatia abordarii acestei teme ın lucrarea de fata. Doua din directiile principale de dezvoltare
ce se impun sub aceste considerente sunt calculul paralel si distribuit si calculatoarele cuantice.
Prima solutie, si cea mai dezvoltata pana ın prezent, se bazeaza pe procesarea paralela. In loc
de a utiliza calculatoare din ce ın ce mai puternice pentru solutionarea unei probleme, se ımparte
rezolvarea acesteia ıntre mai multe calculatoare. Deoarece tendinta ın domeniul retelelor de calcu-
latoare este ca traficul ın retea sa se dubleze o data la 12 luni, ın timp ce preturile procesoarelor ce
pot oferi o putere mare de calcul scad, este evidenta necesitatea abordarii calculului distribuit. Un
alt considerent pentru dezvoltarea acestei paradigme este acela ca din ce ın ce mai multe tipuri de
dispozitive de calcul, de la servere, telefoane mobile si pana la automobile vor fi conectate ın retea.
O alta abordare o reprezinta calculatoarele cuantice. Cercetarile recente realizate ın domeniul cal-
culului cuantic au demonstrat potentialul imens prezentat de aceste sisteme pentru rezolvarea unor
probleme considerate ın mod traditional de nerezolvat din punct de vedere al efortului de calcul.
Spre exemplu, problema plierii proteinelor ilustreaza o slabiciune inerenta a calculului von Neu-
mann. Cu toate acestea, natura rezolva aceasta problema ın cateva secunde. Eficienta ”anormala”
6
Capitolul II: Sisteme de calcul de mare performanta 7
a altor procese biologice de optimizare ar putea furniza dovezi indirecte ale procesarii cuantice
atunci cand nu se ıntrevede nicio explicatie bazata pe legile fizicii clasice. In aceste conditii, desi
calculatoarele cuantice nu au fost construite ın afara laboratoarelor de cercetare2, interesul comu-
nitatii stiintifice pentru formularea de solutii pentru probleme specifice informaticii cuantice este
ın continua crestere. In prezent, validarea acestor solutii poate fi realizata la nivel teoretic sau prin
intermediul simularii.
Pentru o mai buna ıntelegere a influentei pe care sistemele de calcul de mare performanta o
au asupra dezvoltarii aplicatiilor destinate sa rezolve probleme din cele mai complexe este nece-
sara definirea acestor sisteme. Existenta a numeroase modalitati de caracterizare a sistemelor de
calcul de mare performanta (strategiile de programare a aplicatiilor HPC, modul de manipulare a
instructiunilor si a fluxului de date) a determinat formularea unor multiple definitii mai mult sau
mai putin generale. De-a lungul timpului toate formularile destinate sa caracterizeze calculul de
mare performanta provin din natura revolutionara a sistemelor construite la momentul respectiv.
Astfel, termenul de ”Super Computing”, asociat ın mod frecvent cu sistemele de calcul de mare
performanta, a fost prima data folosit ın 1920 ın ziarul New York World cu referire la tabulatoarele
construite de IBM pentru Universitatea Columbia [Baehne 35, Bashe 85]. Unii autori considera ca
gradul mare de performanta provine din paralelism [Bell 02, Kunz 04, van der Steen 09], ın timp
ce alte formulari caracterizeaza sistemele de calcul de mare performanta ca fiind acele sisteme,
cele mai puternice din punctul de vedere al capacitatii de procesare, existente la un moment dat
sau acele sisteme care poseda capacitatea de a stoca si procesa mult mai multe informatii decat un
calculator conventional. In [mic 04] autorii considera ca sistemele de calcul de mare performanta
pot fi definite pe larg de tehnologia utilizata pentru rezolvarea unor probleme de calcul ce nece-
sita o semnificativa putere de procesare precum si accesarea si procesarea rapida a unor cantitati
masive de date. In lucrarea de fata consideram ca o caracterizare a sistemelor de calcul de mare
performanta trebuie sa exprime actualitatea acestor sisteme si necesitatea studierii lor dar si sa
prevada tendintele de viitor de natura sa introduca un grad de performanta ın continua crestere.
Acest ultim considerent este inerent datorita orizonturilor oferite de Legea lui Moore. Conform
acestor considerente, ın cele ce urmeaza vom trece ın revista acele sisteme ce pot fi ıncadrate
ın clasa sistemelor de calcul de mare performanta, cu referire ın special la sistemele dezvoltate
pana ın prezent, dar si la acele tehnologii care se preconizeaza a reprezenta viitorul calculului de
mare performanta. Din aceasta perspectiva vom considera aici calculatoarele cuantice ca facand
parte din clasa sistemelor de calcul de mare performanta. Desi din punct de vedere practic aceste
tehnologii se afla ıntr-o etapa incipienta de dezvoltare, ele prezinta un potential demonstrat de a
creste puterea de calcul ın mod exponential. Deoarece calculul de mare performanta se bazeaza
ın esenta pe calculul paralel si distribuit, consideram ca o clasificare a acestor sisteme se va baza
ın cele din urma pe taxonomia introdusa de Flynn [Flynn 72], extinsa si completata mai tarziu de
[Johnson 88] si [Duncan 90]:
• Masini SISD - single instruction single data. Contin o singura unitate de procesare ce executa
2cu o singura exceptie: compania DWave Systems a demonstrat functionarea unui calculator cuantic pe 28 de qubiti
[Neven 08], dar nu este vorba despre un calculator cuantic universal
Capitolul II: Sisteme de calcul de mare performanta 8
instructiunile ın mod serial.
• Masini SIMD - single instruction, multiple data. Aceste masini au de obicei mai multe pro-
cesoare care executa aceeasi instructiune asupra unor seturi de date diferite. O subclasa a
masinilor SIMD o reprezinta clasa procesoarelor vectoriale care opereaza simultan asupra
unui vector de date. In acest caz se utilizeaza un paralelism cu granularitate mare, iar nece-
sitatea de comunicare ıntre procesoare este mica.
• Masini MISD - multiple instructions, single data. Pana ın prezent nu a fost dezvoltata nicio
masina de acest tip.
• Masini MIMD - multiple instructions, multiple data. Aceste masini opereaza ın paralel
asupra unor seturi diferite de date folosind instructiuni diferite. Exista o mare varietate
de sisteme MIMD, pentru aceasta clasa ın special taxonomia lui Flynn dovedindu-se a fi
neadecvata.
In continuare vom face o distinctie importanta ıntre sisteme cu memorie partajata si cele cu
memorie distribuita.
• Sisteme cu memorie partajata - ın aceste sisteme procesoarele trebuie sa se sincronizeze ın
ceea ce priveste accesul la date. Aceste procesoare nu necesita cunostinte despre localizarea
datelor deoarece memoria comuna este disponibila ın aceeasi masura tuturor procesoarelor.
Sistemele cu memorie partajata pot fi ın acelasi timp SIMD sau MIMD. Procesoarele vecto-
riale cu un singur CPU pot fi considerate exemple de sisteme SIMD cu memorie partajata,
iar din a doua categorie amintim procesoarele vectoriale cu mai multe unitati de procesare.
• Sisteme cu memorie distribuita - ın aceasta situatie, fiecare procesor detine propria memorie.
Procesoarele sunt conectate prin intermediul unei retele (care trebuie sa fie proiectata astfel
ıncat sa minimizeze costurile de comunicatie) si utilizeaza tehnici de transmitere a mesajelor
pentru a pune ın comun datele. Din nou, atat arhitectura SIMD cat si cea MIMD pot utiliza
memoria distribuita.
• Sisteme hibride - clustere de noduri cu spatii de adresare separate. Fiecare nod poate avea
mai multe procesoare care folosesc memoria partajata. Bell distinge ıntre doua categorii ma-
jore de arhitecturi [Bell 02]: clustere de supercalculatoare vectoriale de tip Cray si clustere
de uniprocesoare sau multiprocesoare scalare. El considera ca sistemele cluster actuale se
afla ın tranzitia de la (a) calculatoare masiv paralele si clustere ruland software proprietar la
(b) clustere proprietare ruland software standard si la (c) clustere Beowulf construite folosind
componente hardware si software disponibile utilizatorilor comuni.
• Sisteme Grid - realizate prin interconectarea prin intermediul Internet-ului a mai multor
noduri de calcul. Aceste noduri de calcul pot fi oricare din clasele descrise mai sus. Termenul
de ”Grid” a fost inspirat de reteaua electrica (”electrical grid”), avand la baza viziunea de
conectare la un grid de calcul care ar putea fi la fel de simpla precum conectarea la o retea
Capitolul II: Sisteme de calcul de mare performanta 9
electrica. Ideea este ca, la fel ca ıntr-o retea electrica, utilizatorii ar putea pur si simplu accesa
puterea de calcul de care au nevoie fara sa cunoasca provenienta acesteia sau cum este ea
produsa. In prezent acest lucru nu este ınca posibil, dar aceasta idee a condus la termenul
de ”utility computing” ın care puterea de calcul este vazuta ca o utilitate, disponibila ın
baza platii pe baza de consum, ın aceeati maniera ca ın utilizarea retelelor electrice sau de
gaz. ”Cloud computing” reprezinta o forma de utility computing ce a castigat popularitate
ın ultima perioada.
In viitorul foarte apropiat toate calculatoarele vor avea probabil arhitecturi paralele iar pana
acum s-au depus eforturi considerabile pentru a dezvolta noi limbaje de programare si compilatoare
care sa sustina o astfel de evolutie. Calculatoarele cuantice sunt sisteme paralele ın esenta lor si
pot fi ıncadrate ın clasa arhitecturilor SIMD ın care datele sunt reprezentate de diferite stari cuantice
iar instructiunile sunt reprezentate de legile fizicii. Cercetarea ın domeniul programarii sistemelor
SIMD atinge probleme cu care ne vom confrunta ıncercand sa programam calculatoarele cuantice,
o calitate unica a algoritmilor cuantici fiind aceea ca vor presupune doar interactiuni locale ıntre
starile cuantice.
In continuarea acestui capitol sunt prezentate, pe rand, conceptele ce stau la baza dezvoltarii
si utilizarii calculului Grid si respectiv a calculului cuantic, evidentiind principiile care sugereaza
imensul potential de calcul al acestor sisteme.
Sisteme Grid
In sectiunea dedicata sistemelor Grid sunt prezentate definitia si arhitectura stratificata a aces-
tor sisteme si sunt analizate cerintele ce se impun pentru implementarea si utilizarea lor (cerinte
legate de securitate si autentificare, planificarea si alocarea resurselor, transferul datelor si re-
alizarea comunicatiilor, monitorizarea si descoperirea resurselor, heterogenitate). De asemenea,
sunt prezentate principalele standarde Grid care trateaza aspecte esentiale legate de administrarea si
descoperirea resurselor, transferul datelor si realizarea comunicatiilor, suportul pentru executia pro-
gramelor ıntr-un mediu de calcul heterogen. Desi proiectul Globus Toolkit3 nu reprezinta o solutie
Grid completa, acesta furnizeaza instrumentele necesare pentru adresarea multora din cerintele
impuse ın dezvoltarea de sisteme si aplicatii Grid, el devenind standardul de facto ın Grid. In dez-
voltarea aplicatiilor si serviciilor Grid propuse ın aceasta teza a fost utilizata versiunea 4 (cea mai
recenta) a middleware-ului Globus Toolkit (GT4) astfel ıncat se impune prezentarea ın acest capi-
tol a arhitecturii GT4 precum si a modului ın care, pe baza componentelor GT4, pot fi dezvoltate
servicii Grid.
Dezvoltarea de servicii si aplicatii Grid, fie ele complet noi sau bazate pe functionalitatile unor
aplicatii existente, presupune tratarea unei game largi de aspecte legate de analiza problemei, arhi-
tectura aplicatiei si implementare. Dificultatea acestor sarcini cauzeaza o lipsa evidenta de utiliza-
tori ın aceste sisteme Grid. Pentru a furniza accesul la un sistem Grid la un nivel mai ınalt, ın acest
capitol este propusa o platforma generica noua pentru integrarea serviciilor Grid [Arustei 08b].
3http://www.globus.org/toolkit/
Capitolul II: Sisteme de calcul de mare performanta 10
Figura II.1: Architectura platformei generice pentru integrarea serviciilor Grid [Arustei 08b]
Sunt descrise arhitectura platformei, tipurile de aplicatii Grid ce pot fi dezvoltate prin simpla con-
figurare a componentelor acesteia precum si principalele avantaje ale solutiei propuse fata de alte
proiecte de natura asemanatoare descrise ın literatura de specialitate.
Arhitectura platformei propuse este bazata pe trei componente: componenta client, compo-
nenta serviciu si componenta nod de lucru (Figura II.1). Fiecare componenta este configura-
bila astfel ıncat utilizatorul are posibilitatea de a personaliza functionalitatea platformei. Intregul
proces de executie Grid este condus prin intermediul componentei client. Acest modul permite
interactiunea utilizatorului cu sistemul generic ın doua moduri: pe de o parte, prin specificarea
sau furnizarea componentelor aplicatiei specifice si datelor de intrare, iar pe de alta parte, prin
interactiunea cu modulul de vizualizare a rezultatelor care permite manipularea unui set de parame-
tri dinamici pentru aplicatie. Componenta serviciu generic controleaza executia pe nodurile de lu-
cru a componentelor aplicatiei furnizate. De asemenea, aceasta componenta poate avea si responsa-
bilitatea de a realiza etapele de pre- si post-procesare a datelor.
Colaborarea dintre cele trei componente se realizeaza prin notificari, permitand astfel co-
municarea datelor de intrare si iesire ıntr-o maniera orientata pe servicii. Transferul datelor de
intrare/iesire poate fi realizat si prin intermediul fisierelor, ın functie de natura aplicatiei.
Aplicatia ce va fi transformata ın serviciu Grid (Figura II.2) este specificata modular de catre
utilizator si poate fi compusa din pana la trei module: modulul de partitionare a datelor, modulul
de executie a procesarii si modulul de compunere a rezultatelor. Pentru dezvoltarea fiecarui modul
Capitolul II: Sisteme de calcul de mare performanta 11
Figura II.2: Etapele din rezolvarea unei probleme ce poate fi implementata utilizand serviciul Grid
generic
este furnizata o interfata Java usor de folosit, fiecare modul avand posibilitatea de a fi extins din
clase built-in ce ascund detaliile middleware-ului Grid.
Intrarea modulului de partitionare a datelor este reprezentata de numarul de unitati ce vor exe-
cuta procesarea precum si datele de intrare pentru aceste componente.
Modulul de executie a procesarii este responsabil pentru lansarea ın executie a sarcinilor de
procesare pe fiecare nod de lucru. Nodurile de lucru pot executa toate aceeasi procesare, sau pot
avea functionalitati diferite. In sistem pot exista unul sau mai multe astfel de noduri de lucru, iar
masinile gazda pe care vor rula pot fi specificate prin intermediul componentei client sau pot fi
determinate de componenta serviciu.
Daca rezultatele partiale produse de nodurile de lucru necesita o etapa finala de rafinare sau
compunere, aceasta poate fi executata prin intermediul modulului de compunere a rezultatelor.
Prin simpla configurare a serviciului generic descris pot fi dezvoltate aplicatii Grid de orice
natura, care pot fi exprimate sub forma descrisa ın Figura II.2. In rezolvarea unei astfel de prob-
leme pot aparea una sau mai multe din etapele de partitionare a datelor, executie a sarcinilor de
lucru si de compunere a rezultatului final pe baza rezultatelor partiale produse de fiecare nod de
lucru. Mai mult, sarcinile efective de lucru pot fi executate pe unul sau mai multe noduri de lucru,
ın primul caz etapele de partitionare a datelor si de compunere a rezultatului nefiind necesare. Uti-
lizatorului ıi sunt prezentate rezultatele obtinute ın urma procesarii si poate interactiona cu acestea
(spre ex., daca este vorba despre o aplicatie de randare, interactiunea utilizatorului cu scena se
poate traduce ın aplicarea de noi transformari de modelare, observare sau iluminare). Procesul
care implementeaza etapele de lucru poate fi reluat cu noi parametri specifici aplicatiei, serviciul
generic putand fi configurat sa permita bucle de executie ın care se asteapta evenimente de la uti-
lizator. O aplicatie care prezinta etapele generice din Figura II.2 este vizualizarea folosind randarea
Capitolul II: Sisteme de calcul de mare performanta 12
paralela ın spatiul obiect, pentru care, ın capitolul al III-lea, este formulata o implementare Grid
bazata pe configurarea serviciului generic propus.
Unul din principalele avantaje ale acestei abordari ıl reprezinta posibilitatea de exploatare a
resurselor slab cuplate disponibile ın mediile Grid. Acest lucru poate fi util pentru aplicatii care
necesita exploatarea unor instrumente dedicate de procesare (sisteme de calcul vizual multi-GPU,
supercalculatoare dedicate, pereti de afisare, etc.), deoarece aceste resurse sunt de cele mai multe
ori disparate. Spre exemplu, una dintre principalele probleme asociate sistemelor de vizualizare
dezvoltate pana ın prezent o reprezinta stransa cuplare a hardware-ului grafic si a dispozitivelor de
afisare. Multe aplicatii necesita puterea de randare a mai multor supercalculatoare sau clustere, dar
care nu sunt usor accesibile din afara centrelor specializate de vizualizare. Mai mult, majoritatea
proiectelor care exploateaza randarea paralela si pentru care s-a ıncercat integrarea ın sisteme Grid
[Fewings 07, Cedilnik 06, Song 06, Wood 04, Moad 05], nu sunt adaptate sa lucreze cu resurse de
vizualizare distribuite geografic.
Indiferent ca este vorba de configurarea serviciului Grid sub forma unei aplicati grafice sau a
uneia de alta natura, detaliile middleware-ului Grid sunt abstractizate fata de utilizator/program-
ator, acestuia revenindu-i o sarcina mult mai simpla, aceea de a dezvolta cele trei module ale
aplicatiei (partitionarea datelor, executia sarcinii de lucru si compunerea rezultatelor) prin imple-
mentarea interfetelor corespunzatoare si transferarea acestor module sub forma unor arhive Java.
Astfel, pasii necesari proiectarii si dezvoltarii unui serviciu Grid sunt ınlocuiti de aceste sarcini
mult mai simple.
Cerintele implicate ın implementarea conceptului de sisteme Grid ridica provocari pentru care
sunt furnizate diferite solutii. Construirea unei infrastructuri Grid presupune combinarea ıntr-
o maniera complexa a experientelor cu diferite sisteme de operare, middleware si instrumente
de instalare si configurare. Dezvoltarea unei infrastructuri Grid implica testarea diferitelor in-
strumente si aplicatii disponibile (alegerea dispozitivelor hardware adecvate, a infrastructurii de
retea, proiectarea clusterelor si instalarea sistemului de operare si a instrumentelor de administrare,
ınglobarea tehnologiilor de securitate) pentru a obtine o reducere a timpului necesar mentenantei
si dezvoltarii ulterioare a acesteia [Amarandei 08], dar si pentru a permite o exploatare eficienta
a resurselor existente [Amarandei 06]. Dezvoltarea de servicii si aplicatii Grid, fie ele com-
plet noi sau bazate pe solutii existente, presupun tratarea unei game largi de aspecte legate de
analiza problemei, arhitectura aplicatiei si implementare [Arustei 08b, Arustei 08a, Archip 08a,
Archip 08b].
Calculatoare cuantice
In ceea ce priveste calculul cuantic, sunt prezentate conceptele ce stau la baza acestuia, de-
taliind principiile precum interferenta cuantica, reversibilitatea procesului de calcul, initializarea si
masurarea starilor cuantice, copierea informatiei cuantice, prin care acest tip de calcul se diferentia-
za de cel clasic. De asemenea, sunt prezentate cele mai utilizate modele de calcul cuantic descrise
ın literatura de specialitate: modelul circuitului cuantic, masina Turing cuantica, calculul cuantic
adiabatic, calculul cuantic bazat pe stari cluster si calculul cuantic topologic. Pentru prezentarea
notiunilor teoretice de baza si a rezultatelor obtinute, ın cadrul acestei teze este folosit modelul
Capitolul II: Sisteme de calcul de mare performanta 13
circuitului cuantic.
Un calculator cuantic este construit, ca si cel clasic, din trei componente principale: proce-
sor, memorie si sisteme de intrare/iesire. Un calculator cuantic poate fi descris formal de M =
(H ,O,T, δ, β), undeH - reprezinta spatiul starilor (spatiul Hilbert C2n
) sistemului cuantic, O - se-
tul de transformari unitare, T - setul comenzilor de masurare, δ - este un operator de initializare iar
β - descrie masurarea finala.
Analogul cuantic al bitului clasic este qubit-ul (prescurtarea de la quantum bit). Un qubit este
un sistem cuantic ale carui stari pot fi descrise complet de o superpozitie a doua stari ortonormale
ale bazei de calcul, notate |0〉 si |1〉 (ıntr-un spatiu HilbertH = C2, |0〉 = (10)T , |1〉 = (01)T ). Orice
stare |ψ poate fi descrisa prin:
|ψ〉 = α|0〉 + β|1〉, |α|2 + |β|2 = 1, (II.1)
unde α si β sunt numere complexe. Deci, spre deosebire de bitul clasic, qubitul se poate afla si
ıntr-o alta stare decat |0〉 sau |1〉: se pot forma combinatii liniare de stari, numite superpozitii (ec.
II.1). O observatie importanta este aceea ca un qubit nu poate fi examinat pentru a-i determina
starea, adica valorile α si β. In schimb, pot fi obtinute informatii mult mai restrictive despre starea
cuantica. La masurarea unui qubit se obtine fie rezultatul 0, cu probabilitatea |α|2, fie rezultatul 1,
cu probabilitatea |β|2. Suma probabilitatilor trebuie sa fie 1, deci starea unui qubit reprezinta un
vector unitate ıntr-un spatiu vectorial complex bi-dimensional.
Pentru ca procesul de calcul sa fie coerent, registrii cuantici trebuie sa fie izolati astfel ıncat sa
nu existe interferenta cu mediul ınconjurator. Entropia unui astfel de sistem trebuie sa ramana con-
stanta deoarece nu este posibila disiparea de caldura. Astfel, schimbarea starii sistemului trebuie
sa fie adiabatica, ceea ce presupune ca toate procesele de calcul sa fie reversibile.
Orice operatie reversibila poate fi descrisa prin intermediul unui operator unitar U care ındepli-
neste conditia U−1 = U∗. Compunerea operatorilor unitari este tot un operator unitar deoarece
(UV)−1 = V∗U∗.
O transformare unitara generala ın spatiul Hilbert bidimensional C2 poate fi definita astfel:
U =
(
u11 u12
u21 u22
)
. (II.2)
Daca acest operator poate fi aplicat subspatiilor bidimensionale arbitrare aleH , atunci orice trans-
formare unitara poate fi construita prin compunere.
Analogul cuantic al portii clasice NOT este notat X si poate fi definit astfel ıncat X|0〉 = |1〉si X|1〉 = |0〉. Poarta cuantica NOT actioneaza similar portii clasice, desi, spre deosebire de cazul
clasic, actiunea sa este liniara: starea α|0〉 + β|1〉 este transformata ıntr-o stare corespunzatoare
β|0〉 + α|1〉. O modalitate convenabila de reprezentare a actiunii portii cuantice NOT este ın forma
sa matriceala:
X =
(
0 1
1 0
)
. (II.3)
Poarta Hadamard, data ın forma matriceala de
H =1√
2
(
1 1
1 −1
)
, (II.4)
Capitolul II: Sisteme de calcul de mare performanta 14
este uneori descrisa ca fiind ”radical din NOT”, deoarece aplicarea ei asupra oricarei stari a bazei
|0〉 sau |1〉, produce o superpozitie uniforma a acestora:
H|0〉 = 1√
2(|0〉 + |1〉) si H|1〉 = 1
√2
(|0〉 − |1〉). (II.5)
Poarta de shiftare a fazei, data prin
P =
(
1 0
0 eiθ
)
, (II.6)
modifica fazele relative, α si β, ale amplitudinilor starilor unui qubit.
Portile controlate sunt porti logice cuantice care actioneaza asupra mai multor qubiti. Notiunea
de poarta controlata permite implementarea constructiilor de tip i f − else. Portile cuantice contro-
late pe doi qubiti utilizeaza un qubit de control pentru a determina daca o actiune unitara specificata
va fi aplicata unui qubit tinta.
Operatorul NOT controlat (CNOT) este prototipul de poarta quantica pe mai multi qubiti.
Primul parametru al portii CNOT este qubitul de control. Daca acest qubit se afla ın starea |0〉,atunci qubitul tinta este lasat nemodificat, iar daca qubitul de control se afla ın starea |1〉, qubitul
tinta este inversat:
|00〉 → |00〉; |01〉 → |01〉; |10〉 → |11〉; |11〉 → |10〉.
Operatorul CNOT este o generalizare a portii clasice XOR, deoarece actiunea sa poate fi rezu-
mata astfel: |x, y〉 → |x, x⊕ y〉, unde ⊕ este adunarea modulo doi. Reprezentarea matriceala a portii
CNOT este:
CNOT =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
. (II.7)
Exista mai multe alte porti cuantice pe mai multi qubiti. Cu toate acestea, poarta CNOT si
portile pe un qubit reprezinta prototipurile pentru orice alta poarta cuantica datorita urmatorului
rezultat de universalitate: orice poarta cuantica pe mai multi qubiti poate fi construita folosind
porti CNOT si porti pe un singur qubit. Demonstratia acestei afirmatii reprezinta analogul cuantic
al universalitatii portii clasice NAND.
In aceasta sectiune introductiva sunt prezentati si principalii algoritmi cuantici cunoscuti, in-
cluzand cateva aplicatii notabile ale acestora. In acest context, este analizata o trasatura importanta
a algoritmilor cuantici, paralelismul cuantic, care reprezinta principala sursa a impresionantei put-
eri de calcul a acestor sisteme. Astfel, exista doua mari clase de algoritmi cuantici a caror com-
plexitate timp este mai mica decat ın cazul clasic. Prima dintre acestea este bazata pe transfor-
mata Fourier cuantica [Nielsen 00] si include algoritmi remarcabili pentru rezolvarea problemelor
de factorizare si de calculul logaritmului discret, furnizand o accelerare exponentiala fata de cei
mai buni algoritmi clasici cunoscuti. Cea de a doua clasa de algoritmi este bazata pe algoritmul
Capitolul II: Sisteme de calcul de mare performanta 15
Figura II.3: Principalii algoritmi cuantici si relatiile dintre acestia, incluzand cateva aplicatii nota-
bile [Nielsen 00].
cuantic de cautare al lui Grover [Grover 96]. Aceasta clasa de algoritmi furnizeaza o accelerare
patratica fata de cei mai buni algoritmi clasici. Importanta algoritmului cuantic de cautare consta ın
raspandirea utilizarii tehnicilor bazate pe cautare ın algoritmii clasici, care, ın multe cazuri, permit
o adaptare naturala a algoritmului clasic pentru enuntarea unui algoritm cuantic mai rapid.
Figura II.3 schiteaza stadiul cunoasterii algoritmilor cuantici, incluzand cateva exemple de
aplicatii ale acestora. Un interes deosebit ıl prezinta algoritmul cuantic de numarare care reprezinta
o combinare inspirata a cautarii cuantice cu transformata Fourier si care permite estimarea numarului
de solutii ale unei probleme de cautare mai rapid decat este posibil pe un calculator clasic.
Capitolul III
Procesare grafica ın sisteme cluster si Grid
Acest capitol analizeaza problematica procesarii grafice ın sisteme Grid. Este discutata nece-
sitatea integrarii procesarii grafice a informatiilor ın sisteme Grid, dar si necesitatea abordarii cal-
culului Grid pentru rezolvarea unor probleme de procesare grafica. In multitudinea de domenii ın
care procesarea grafica joaca un rol decisiv, au fost identificati acei factori care impun provocari ın
dezvoltarea unor solutii eficiente: cantitatile imense de date ce pot fi generate utilizand instrumente
moderne de achizitie sau chiar prin exploatarea acestor sisteme de calcul, necesitatea vizualizarii
ın timp real a acestor date, precum si dificultatile ıntampinate ın integrarea si expunerea ın sisteme
Grid a functionalitatilor sistemelor de procesare grafica. In acest capitol sunt descrise noi solutii
propuse pentru fiecare din aceste provocari.
Consideram necesara acordarea unei atentii deosebite prelucrarii seturilor de date de intrare de
dimenisuni mari de tip nori de puncte care au devenit din ce in ce mai frecvente datorita raspandirii
sistemelor de achizitie prin scanare laser 3D. Acestea vor constitui baza aplicatiilor analizate ın
continuare, astfel ıncat una din sectiunile acestui capitol trateaza problematica achizitiei acestor
seturi de date precum si a metodelor propuse ın literatura de specialitate pentru vizualizarea lor.
Simplificarea seturilor de date de mari dimensiuni
Pentru a ıntampina necesitatea de vizualizare interactiva a seturilor de date de mari dimen-
siuni sunt propuse solutii care exploateaza calculul paralel pentru simplificarea, reprezentarea si
vizualizarea eficienta a acestora. Astfel, ın sectiunea III.3, este propus si analizat un algoritm par-
alel (PRANSAC) pentru identificarea structurilor planare ın nori de puncte proveniti de la scanere
laser 3D, ın vederea obtinerii unei reprezentari hibride a acestor seturi de date care sa asigure
randari de calitate superioara realizate la rate de afisare mari si cu un consum redus de memo-
rie [Arustei 07]. Algoritmul este o extensie paralela a algoritmului RANdom SAmple Consen-
sus (RANSAC) [Bolles 81]. Reconstructia unui model hibrid dintr-un nor de puncte necesita un
pas de preprocesare costisitor, mai ales ın cazul seturilor de date foarte de mari. O metoda de a
crea aceasta reprezentare hibrida presupune identificarea structurilor planare ın norul de puncte si
ınlocuirea punctelor corespunzatoare cu poligoane texturate [Arustei 06]. In zonele ın care mo-
delul este foarte detaliat, acesta este reprezentat prin intermediul punctelor originale, ın timp ce ın
16
Capitolul III: Procesare grafica ın sisteme cluster si Grid 17
rest se folosesc structuri planare texturate. Algoritmul RANSAC (RANdom SAmple Consensus)
[Bolles 81] s-a dovedit a fi o solutie foarte buna pentru problema detectiei planelor deoarece poate
fi adaptat pentru extragerea instantelor multiple dintr-un set de date si poate ignora valorile aber-
ante (care nu apartin niciunei structuri planare) fara nevoia tratarii explicite a acestora [Wahl 05]. In
ciuda caracterului robust, general si a simplitatii algoritmului RANSAC, acesta prezinta de aseme-
nea un consum mare de timp si memorie. Coroborat cu necesitatea procesarii unor seturi de date
de mari dimensiuni, este evidenta importanta introducerii unei abordari paralele pentru executia
algoritmului RANSAC ın vederea identificarii planelor ıntr-un nor de puncte. O astfel de abor-
dare este prezentata ın [Arustei 07], rezultatele obtinute ın urma procesarii unor nori de puncte de
diferite dimensiuni demonstrand ca algoritmul paralel prezinta o scalare buna ın raport cu numarul
de noduri de calcul si ca poate manipula eficient seturi de date de mari dimensiuni. Algoritmul
RANSAC paralel (PRANSAC), ca si cel secvential, identifica structuri planare ın norul de puncte
ın vederea reducerii numarului de puncte ce trebuie randate. Pentru aceasta datele sunt partitionate
astfel ıncat ın fiecare pas al schemei RANSAC suportul unui plan candidat este calculat ın paralel
de catre toate nodurile de procesare (Algoritmul 1).
Intrare: m - nr. de iteratii ale algoritmului, np - nr. de noduri de procesare
Iesire : Planes - lista planelor detectate ın norul de puncte
// Pbest - cel mai bun plan dupa un nr de m iteratii
stopRansac := f alse;1
repeat2
Pbest := 0;3
C(Pbest) := 0;4
foreach iteration i do5
genereaza candidatul Pi;6
foreach procesor j par do7
calculeaza C j(Pi);8
calculeaza C(Pi) =∑np
j=1C j(Pi);9
if C(Pi) 〉 C(Pbest) then10
Pbest := Pi;11
if compact(Pbest) and C(Pbest) 〉 thresh then12
adauga Pbest la Planes;13
elimina punctele planului Pbest din setul de date;14
else15
stopRansac := true;16
until stopRansac = f alse ;17
Algoritm 1: Algoritmul PRANSAC pentru detectia planelor ın nori de puncte [Arustei 07]
Este prezentata o analiza detaliata a complexitatii algoritmului paralel propus care releva faptul
ca, ın cazul cel mai defavorabil, timpul total pentru detectarea a k structuri planare este de ordinul
Capitolul III: Procesare grafica ın sisteme cluster si Grid 18
O(nk3
p), unde n reprezinta dimensiunea setului de date de intrare, iar p denota numarul de noduri de
procesare utilizate. Cum ın cazul utilizarii algoritmului RANSAC secvential sunt necesari O(nk3)
pasi, se observa ca accelerarea (raportul dintre timpul de executie secventiala si timpul de executie
ın paralel) algoritmului paralel creste liniar cu numarul de noduri de procesare folosite. Analiza
teoretica a performantelor algoritmului paralel propus ın raport cu cel secvential este confirmata de
rezultatele obtinute ın urma testelor efectuate pe nori de puncte reprezentand scanari ale castelului
Welfenschloss din Germania4 (fig. III.1 - stanga), si ale Catedralei Sf. Stefan din Viena5 (fig. III.1
- dreapta).
Figura III.1: Nori de puncte achizitionati folosind instrumente de scanare la distanta: (stanga)
scanare panoramica a castelului Welfenschloss - Universitatea Hannover (aprox. 400 000 puncte);
(dreapta) scanare interioara a Catedralei Sf. Stefan din Viena (aprox. 3 milioane de puncte).
Figura III.2: Planele detectate folosind algoritmul paralel propus. Punctele ce apartin unui plan
sunt afisate cu aceeasi culoare: (stanga) 217 structuri planare detectate ın norul Welfenschloss;
(dreapta) 135 structuri planare descoperite ın setul de date corespunzator Catedralei Sf. Stefan.
4http://www.ikg.uni-hannover.de/en/research/nachwuchsgruppe/scanmap/
5set de date furnizat de Computer Graphisc Institute, TU Vienna
Capitolul III: Procesare grafica ın sisteme cluster si Grid 19
Structurile planare detectate sunt prezentate ın figura III.2 unde punctele corespunzatoare unui
plan sunt afisate cu aceeasi culoare.
Din evolutia timpilor de procesare pentru ambii nori de puncte ın cazul cresterii numarului
de noduri de lucru si pastrand constanta dimensiunea norului de puncte s-a observat ca timpul de
procesare se reduce odata cu cresterea numarului de noduri de lucru rezultand ıntr-o accelerare
semnificativa fata de algoritmul secvential (de aproximativ 6.2 la utilizarea a 8 noduri de procesare
ın cazul norului Sf. Stefan) [Arustei 07]. De asemenea, ın ambele cazuri de test, s-a observat o
crestere a accelerarii odata cu numarul de noduri de procesare.
Eficienta algoritmului paralel este calculata ca raport ıntre timpul de executie a algoritmului
secvential si produsul dintre timpul de executie a algoritmului paralel si numarul de noduri de
procesare folosite. Si pentru acest indicator s-a constatat, pentru ambii nori de puncte, ca eficienta
creste odata cu adaugarea de puncte ın setul de date la mentinerea constanta a numarului de noduri
de procesare utilizate, ajungand pana la 0.8 pentru procesarea unui nor de aproximativ 4 milioane
de puncte utilizand 8 noduri de lucru.
Vizualizarea seturilor de date de mari dimensiuni ın sisteme Grid
Tehnologia Grid poate fi foarte folositoare pentru a accelera multe tipuri de procese grafice
de vizualizare, avand ın vedere ca majoritatea acestor procese sunt foarte costisitoare din punct
de vedere al volumului de calcul. Imbunatatirea performantelor tehnicilor de vizualizare prin in-
termediul tehnologiei Grid poate pune bazele pentru implementarea de aplicatii precum cele de
vizualizare a datelor stiintifice, medii colaborative, generarea de imagini fotorealiste etc. Inte-
grarea ın sisteme Grid a procesului de vizualizare trebuie sa tina cont de faptul ca ın multe situatii
seturile de date ce trebuie vizualizate fie nu permit aplicarea unui proces de simplificare, fie chiar si
ın urma simplificarii au dimensiuni ce nu permit o vizualizare interactiva. In astfel de conditii este
necesara exploatarea unor solutii noi, precum introducerea paralelismului ın procesul de randare.
Dar exploatarea puterii de calcul a sistemelor Grid presupune o sarcina dificila, aceea de a trans-
forma aceste solutii ın servicii Grid. In aceste conditii, utilitatea platformei generice prezentata ın
capitolul anterior este demonstrata prin configurarea ei sub forma unui serviciu Grid de vizualizare
care utilizeaza tehnici de randare paralela ın spatiul obiect. Sunt descrise arhitectura serviciului
Grid obtinut, modul ın care utilizatorul poate interactiona cu procesul de randare si executia aces-
tuia, precum si rezultatele ınregistrate la vizualizarea unor seturi de date obtinute prin scanare la
distanta [Arustei 08a].
In contrast cu alte proiecte Grid de vizualizare descrise ın literatura de specialitate, ın [Arustei 08a]
este prezentata o alta abordare, care poate permite componentelor ce executa procesul de vizualizare,
surselor de date si aplicatiilor client sa fie atat slab cuplate cat si strans cuplate. Framework-ul Grid
descris ın [Arustei 08a] este bazat pe o arhitectura orientata pe servicii ın care fiecare componenta
ce intervine ın procesul de vizualizare furnizeaza propria functionalitate sub forma unei resurse
de tip Web Service (resursa-WS) ıntr-un serviciu Grid. Configuratia procesului de vizualizare este
stabilita de catre utilizator prin intermediul componentei client, interconectarea diferitelor compo-
nente fiind realizata prin intermediul notificarilor. Spre exemplu, pentru configurarea unui proces
de vizualizare OpenGL bazat pe randarea paralela ın spatiul obiect, pot fi definite trei tipuri de
Capitolul III: Procesare grafica ın sisteme cluster si Grid 20
Figura III.3: Arhitectura serviciului de vizualizare obtinut prin configurarea platformei generice
[Arustei 08a].
componente: modulul de partitionare a datelor, modulul de executie a procesarii si modulul de
compunere a imagii finale. Utilizatorul poate configura executia fiecarui astfel de modul si poate
interactiona cu sistemul de vizualizare. Arhitectura platformei de vizualizare este prezentata ın
Figura III.3. Procesul de randare este controlat si rezultatele produse sunt vizualizate prin in-
termediul componentei client. Acest modul permite utilizatorului sa interactioneze cu sistemul de
vizualizare ın doua moduri: (1) prin specificarea sau furnizarea datelor de intrare, si (2) prin contro-
larea parametrilor de vizualizare prin interactiunea cu fereastra OpenGL de vizualizare. Parametrii
de executie Grid si parametrii de vizualizare sunt furnizati serviciului de randare care controleaza
executia unitatilor de procesare ce produc imaginile asociate sub-seturilor datelor de intrare. Ser-
viciul de randare este de asemenea responsabil cu compunerea imaginii finale ce va fi trimisa
clientului, pe baza rezultatelor partiale obtinute de la unitatile de procesare.
Cele trei module utilizate pentru configurarea serviciului generic ıntr-un serviciu de vizualizare
exprima pasii ce trebuie executati pentru implementarea schemei de randare paralela ın spatiul
obiect (Figura III.3).
Pentru testarea serviciului de randare au fost efectuate masuratori la vizualizarea unor nori
de puncte de diferite marimi reprezentand scanari ale Catedralei Sf. Stefan din Viena. Pentru
fiecare nor de puncte s-a masurat timpul de rulare pentru fiecare modul al serviciului (modulul de
Capitolul III: Procesare grafica ın sisteme cluster si Grid 21
Figura III.4: Randarea paralela ın spatiul obiect.
partitionare, modulul de executie si modulul de compunere a rezultatelor). In fiecare caz, serviciul
a fost configurat prin intermediul aplicatiei client sa ruleze job-urile de randare pe un numar diferit
de noduri de lucru. Eficienta sistemului a fost evaluata folosind doua abordari: pe de o parte,
prin pastrarea constanta a dimensiunii norului de puncte si cresterea numarului de noduri de lucru,
iar pe de alta parte, prin pastrarea constanta a raportului dintre dimensiunea setului de intrare si
numarul de noduri de lucru.
Pentru analiza timpilor de executie ınregistrati la procesarea unor nori de puncte de diferite
marimi, timpul de procesare este defalcat pe activitatile ce compun ıntreaga procesare necesara
vizualizarii unui cadru. In toate cele trei cazuri timpul de lansare a job-urilor Grid este aproximativ
acelasi, fiind constant si ın raport cu numarul de job-uri lansate ın executie. S-a observat ca odata
cu cresterea numarului de noduri care executa randarea imaginilor partiale se obtine o reducere a
timpului total de procesare care determina o accelerare semnificativa fata de algoritmul secvential
de randare.
Eficienta sistemului paralel de vizualizare este calculata ca raportul dintre timpul de executie
secvential si produsul dintre numarul de noduri de procesare utilizat si timpul de executie a al-
goritmului paralel. Din analiza evolutiei eficientei sistemului de vizualizare propus pentru 2, 6,
9 si respectiv 12 noduri de lucru, ın conditiile cresterii dimensiunii setului de date de intrare, s-a
observat ca aceasta creste odata cu dimensiunea norului de puncte.
Concluzii
In acest capitol a fost analizat modul ın care procesul de vizualizare grafica poate fi imple-
mentat ın sisteme paralele si distribuite analizand posibilitatile de introducere a paralelismului,
problemele uzuale ale algoritmilor paraleli de randare precum si metodele de proiectare pen-
tru vizualizarea paralela. Au fost descrise solutii atat pentru problema simplificarii seturilor de
date de mari dimensiuni [Arustei 07], cat si pentru dezvoltarea de servicii Grid de vizualizare
Capitolul III: Procesare grafica ın sisteme cluster si Grid 22
[Arustei 08a, Arustei 08b], concentrandu-ne atentia asupra unei modalitati recente de generare a
seturilor de date de mari dimensiuni, ın speta scanarea laser la distanta.
S-a aratat ca o reprezentare hibrida a norului de puncte, compusa din structuri planare texturate
si puncte, duce la reducerea spatiului ocupat de modelul obtinut si la obtinerea unor rate de afisare
interactive ale modelului simplificat ın conditiile pastrarii calitatii modelului. Deficientele acestei
abordari, timpul de preprocesare foarte mare, si consumul mare de memorie ın faza de preproce-
sare, au fost eliminate prin formularea unei abordari paralele a schemei de votare RANSAC. Abor-
darea propusa ın [Arustei 07] a fost construita pe baza algoritmului RANSAC datorita robustetei,
generalitatii si simplitatii acestuia, precum si a faptului ca s-a dovedit a furniza rezultate bune la de-
tectarea structurilor planare ın nori de puncte afectati de zgomot [Arustei 06]. In ciuda aspectelor
pozitive legate de RANSAC, aceasta schema de votare este totusi mare consumatoare de timp si
memorie, ın special cand norul de puncte procesat contine un numar foarte mare de esantioane si
structuri planare. Pentru depasirea acestei probleme, s-a ımpartit efortul de calcul al suportului
pentru fiecare plan ıntre mai multe noduri de procesare, obtinandu-se astfel o accelerare semnifica-
tiva fata de metoda secventiala. Dezvoltarea de tehnici de simplificare bazate pe acest algoritm vor
putea considera integrarea acestuia ıntr-un sistem ce construieste o subdivizare spatiala a norului
de puncte care sa permita selectarea nivelelor de detaliu ın timpul randarii ca ın [Arustei 06].
In [Arustei 08b] a fost descrisa proiectarea si implementarea unui framework generic pentru
transformarea aplicatiilor ın servicii Grid. Abordarea propusa simplifica procesul de dezvoltare
a unui serviciu Grid pe baza unei aplicatii noi sau deja existente si furnizeaza un model de pro-
gramare de nivel ınalt, ınlaturand complexitatea implicata de manipularea serviciilor Web si a
tehnologiilor Grid. Framework-ul dezvoltat permite astfel integrarea dinamica de servicii Grid si
adaugarea de noi functionalitati celor existente. Sistemul dezvoltat a fost testat prin configurarea
serviciului generic ın vederea obtinerii unei functionalitati de vizualizare a seturilor de date de mari
dimensiuni, ın speta a norilor de puncte proveniti de la scanere 3D [Arustei 08a]. Vizualizarea
norului de puncte s-a realizat prin configurarea unei instante a framework-ului generic pentru
generarea unui serviciu de vizualizare ce foloseste o schema de randare paralela ın spatiul obiect.
Din experimentele efectuate rezulta eficienta crescuta a sistemului propus precum si validitatea
acestuia ın vederea construirii unei extensii dedicate vizualizarii ın sisteme Grid.
Capitolul IV
Procesare grafica ın sisteme cuantice
In capitolul al IV-lea sunt analizate modalitatile ın care proprietatile specifice calculului cuantic
pot fi exploatate ın vederea formularii de noi solutii pentru probleme de procesare grafica. Abor-
darea calculului cuantic ın rezolvarea acestor probleme necesita redefinirea lor ın termeni speci-
fici care sa permita exploatarea paralelismului superpozitiilor cuantice. S-a constatat ca pentru
definirea unor solutii cuantice care sa aduca imbunatatiri considerabile fata de cazul clasic pentru
probleme fundamentale de randare si de geometrie computationala, o metoda convenabila este de
a exprima aceste probleme astfel ıncat sa fie posibila exploatarea algoritmilor cuantici cu cele mai
crescute performante fata de cazul clasic - algoritmul de cautare al lui Grover si algoritmul de
factorizare al lui Shor. Astfel, algoritmi precum Z-Buffering, Ray Tracing, calculul radiantei, con-
struirea hartilor de fotoni, managementul nivelurilor de detaliu, sunt exprimati prin subprobleme
care presupun cautare. Pentru acesti algoritmi, precum si pentru schema de votare RANSAC, sunt
formulati algoritmi cuantici echivalenti si sunt analizate performantele ın raport cu cazul clasic.
Capitolul include o sectiune destinata prezentarii abordarii cuantice pentru problema cautarii ın
care sunt analizati atat algoritmul original al lui Grover, dar si solutiile pentru aspectele neluate ın
considerare de acesta, si anume cazul cand dimensiunea setului de date nu este o putere a lui 2, ex-
tragerea solutiilor multiple pentru o problema de cautare precum si solutii pentru formele diferite
ın care problema cautarii poate aparea (determinarea valorii maxime, minime, medii dintr-un set
de valori).
Paralelismul implicit al sistemelor cuantice a determinat investigarea aplicatiilor ce pot fi dez-
voltate cu ajutorul acestor sisteme de calcul de mare performanta dar si modalitatile de ımbunatatire
a performantelor fata de cazul clasic. Exploatarea acestui paralelism a condus de curand la aparitia
unor idei inovatoare si ın ceea ce priveste procesarea grafica, trasandu-se astfel tendintele de dez-
voltare a unor algoritmi cuantici de randare si a geometriei computationale cuantice. Urmarind
aceste directii se pot ınchipui si alti algoritmi de procesare grafica care sa aduca ımbunatatiri
considerabile fata de cazul clasic. Astfel, ın [Caraiman 09c] este formulat echivalentul cuan-
tic al algoritmului RANSAC (RANdom SAmple Consensus) - QRANSAC - ce prezinta multiple
aplicatii ın domeniul procesarii grafice. Analiza complexitatii algoritmului propus demonstreaza
performantele crescute ale acestuia fata de algoritmul clasic. Aplicarea lui pentru rezolvarea efec-
tiva a unei probleme de procesare grafica presupune o adaptare corespunzatoare a acestuia la
23
Capitolul IV: Procesare grafica ın sisteme cuantice 24
conditiile problemei, natura informatiei procesate, tipul rezultatului procesarii, dar mai ales for-
mularea problemei de rezolvat ın termenii specifici formalismului cuantic. O astfel de adaptare a
algoritmului QRANSAC este descrisa ın [Caraiman 09d] unde acest algoritm este utilizat pen-
tru identificarea structurilor planare ıntr-un nor de puncte. Probleme fundamentale de procesare
grafica, precum probleme de randare (Z-Buffering, metode de iluminare globala - Ray-Tracing,
calculul radiantei, metoda hartilor de fotoni - sau managementul nivelurilor de detaliu), probleme
de geometrie computationala (cautarea ın regiuni multidimensionale, determinarea ınfasuratoarei
convexe a unui set de puncte, determinarea intersectiilor dintre obiecte) pot fi exprimate prin sub-
probleme care presupun cautare si factorizare. In acesti termeni pot fi formulati algoritmi cuantici
corespunzatori care sa exploateze performantele introduse de paralelismul superpozitiilor cuantice.
Alte directii de dezvoltare a aplicatiilor algoritmilor cuantici ın procesarea grafica includ potrivirea
sabloanelor folosind transformata Fourier [Curtis 04], stocarea unei imagini folosind un sistem
cuantic [Venegas-Andraca 03] precum si dezvoltarea de tehnici de procesare a imaginii [Beach 03].
Abordarea cuantica a problemei cautarii
Multe probleme din calculul clasic pot reformulate pentru a exprima cautarea unui element
unic care satisface o conditie de cautare predefinita [Caraiman 09c]. Daca nu este furnizata nicio
informatie aditionala despre conditia de cautare, cel mai bun algoritm clasic este o cautare brute-
force ın care elementele sunt testate secvential asupra conditiei de cautare. Pentru o lista de N
elemente, acest algoritm executa ın medie N/2 comparatii. Prin exploatarea paralelismului cuantic
si interferenta starilor cuantice, Grover a formulat un algoritm cuantic care poate gasi elementul
cautat ıntr-o baza de date nestructurata ın doar O(√
N) pasi [Grover 96].
Algoritmul lui Grover se bazeaza pe conceptul de amplificare a amplitudinii iar principiul sau
este de a codifica elementele din setul de date folosind starile unui registru cuantic si de a aplica
un operator, G, al carui efect este de a creste probabilitatea ca sistemul sa se afle ın starea marcata
(starea ce codifica solutia problemei de cautare):
G = HZHO, (IV.1)
unde H reprezinta transformarea Walsh-hadamard:
H =1√
2
(
1 1
1 −1
)
, (IV.2)
Z este operatorul de inversare a semnului amplitudinii daca si numai daca sistemul se afla ın starea
|0〉:
Z =
−1 0 . . . 0
0 1 . . . 0...
... . . ....
0 0 . . . 1
, (IV.3)
Capitolul IV: Procesare grafica ın sisteme cuantice 25
iar O este operatorul oracol ce actioneaza asupra bazei de calcul astfel:
O|x〉 = (−1) f (x)|x〉 =
|x〉, x , a
−|a〉, x = a, (IV.4)
realizand de fapt o rotatie cu π radiani a fazei tuturor vectorilor proprii care ındeplinesc conditia
x = a. Algoritmul lui Grover necesita o subrutina cuantica ce indica daca un numar ıntreg dat, x,
(pe n biti) este cel cautat, a, returnand aceasta informatie drept valoarea unei functii f : 0, 1, ...,N−1 → 0, 1 ce satisface
f (x) = 0, x , a; f (x) = 1, x = a. (IV.5)
Deoarece asupra sistemului se actioneaza doar cu transformari unitare, are loc conservarea
probabilitaatii. Acest fapt permite ca pe masura ce probabilitatea ca sistemul sa se afle ın starea
dorita creste, probabilitatea tuturor celorlalte stari (nemarcate) scade corespunzator. Aplicand op-
eratorul Grover G de un numar corespunzator de ori (⌊π4
√N⌋) va determina ca probabilitatea starii
marcate sa devina foarte apropiata de 1 (mai exact, mai mare decat N−1N
ori). Pentru a obtine acest
comportament al sistemului cuantic, o iteratie Grover realizeaza inversarea fazei amplitudinii starii
marcate, urmata de o inversare a fazei amplitudinii tuturor starilor ın jurul mediei. Inversarea starii
solutiei poate fi obtinuta folosind o asa numita functie ”cutie-neagra” (cunoscuta si sub denumirea
de oracol cuantic) care trebuie doar sa fie capabila sa identifice daca un anumit element este sau
nu membru al setului de solutii, astfel mecanismul fiind foarte general.
Dupa o aplicare a operatorului Grover, amplitudinea starii marcate creste cu O( 1√N
), ın timp ce
amplitudinile starilor nemarcate scad corespunzator (ın mod egal). Pentru a obtine probabilitatea
O(1) pentru starea solutiei, iteratia Grover trebuie aplicata de O(√
N) ori. Exista o probabilitate
finita ca operatia de cautare sa nu se ıncheie cu succes, caz ın care algoritmul lui Grover trebuie
repetat.
In cazul ın care N nu este o putere a lui 2, transformarea H nu este bine definita, dar poate fi
ınlocuita cu transformata Fourier cuantica [Shor 94]
F|x〉n =1
2n/2
2n−1∑
y=0
e2πixy
2n |y〉n, (IV.6)
care poate fi implementata eficient ca ın [Shor 97].
Algoritmul lui Grover ia ın considerare doar cazul ın care numarul de elemente ce satisfac
conditia de cautare este t = 1. Totusi, ın cele mai multe aplicatii practice, numarul t este necunoscut
si intereseaza extragerea ıntregului set de t solutii. Exista variatii ale algoritmului lui Grover ce pot
extrage aleator una din solutii cand t este necunoscut aplicand un numar de iteratii egal cu ⌊π4
√
Nt⌋
pentru t<N2
[Boyer 96].
Extragerea ıntregului set de solutii presupune determinarea numarului t ınainte de a efectua
cele O(
√
Nt) iteratii ale algoritmului lui Grover. Algoritmul cuantic optimal pentru determinarea
numarului t de solutii [Brassard 00] are complexitatea O(√
(t + 1)(N − t + 1)) ce domina astfel
Capitolul IV: Procesare grafica ın sisteme cuantice 26
complexitatea algoritmului lui Grover pentru cazul cand t este necunoscut. Totusi, cunoasterea
valorii t nu permite extragerea secventiala a celor t solutii deoarece de fiecare data cand se masoara
o stare pentru extragerea unei solutii, superpozitia de solutii data de aplicarea iteratiilor Grover
este distrusa. Astfel, ar fi necesara aplicarea repetata a algoritmului lui Grover pentru extragerea
aleatoare a solutiilor, iar numarul de cautari ce trebuie aplicate pentru determinarea tuturor celor
t solutii este de ordinul O(t log t) ceea ce ar implica o complexitate totala de O(√
tN log t). In
[Lanzagorta 05a] autorii propun un algoritm, denumit protocol de semiclonare, pentru extragerea
celor t solutii cu o complexitate optimala, O(t), eliminand necesitatea de a extrage ın mod aleator
solutiile.
Un alt rezultat important, bazat pe aceeasi tehnica a amplificarii amplitudinii, este algoritmul
cuantic pentru determinarea valorii minime ıntr-o baza de date nestructurata. Fie T [0...N − 1] o
tabela nesortata cu N ınregistrari, fiecare ınregistrare mentinand o valoare dintr-un set ordonat de
valori. Se poate presupune, pentru simplitate, ca toate valorile sunt distincte. Problema cautarii
minimului se reprezinta prin gasirea indexului y al unei ınregistrari astfel ıncat T [y] reprezinta
valoarea minima din set. Pe o masina Turing probabilistica clasica, rezolvarea acestei probleme
necesita, ın mod clar, efectuarea unui numar liniar de ıncercari.
In [Durr 99] autorii prezinta o extensie a algoritmului de cautare al lui Grover care permite de-
terminarea valorii minime dupa doar O(√
N) ıncercari. Algoritmul propus apeleaza o subrutina de
cautare (o generalizare a algoritmului lui Grover) pentru a determina indexul unei ınregistrari mai
mici ca valoare decat o valoare determinata de un index de prag. Rezultatul este apoi ales drept noul
index de prag. Acest proces este repetat pana cand probabilitatea ca indexul de prag sa corespunda
valorii minime este suficient de apropiata de 1. Se demonstreaza ın [Durr 99] ca daca se considera
o constanta oarecare c ≥ 1, prin masurarea registrului de intrare dupa un numar de O(c√
N) iteratii,
algoritmul propus pentru cautarea minimului gaseste valoarea minima (indexul acesteia ın tabela)
cu o probabilitate de cel putin 1−1/2c. Analog rezultatului prezentat ın [Durr 99], se poate formula
algoritmul pentru determinarea indexului valorii maxime ca ın [Caraiman 09d].
Aplicatii ale algoritmilor cuantici ın procesarea grafica
Utilizand rezultatele prezentate anterior, o serie de probleme din grafica ce implica algoritmi de
cautare pot fi rezolvate mult mai rapid si eficient. Cateva din aceste probleme sunt algoritmul Ray
Tracing, calculul radiozitatii, metoda hartilor de fotoni, algoritmul Z-Buffering si managementul
nivelurilor de detaliu, pentru care vom arata ca pot fi construiti algoritmi care prezinta complexitati
mult mai bune fata de cazul clasic.
In aceasta sectiune este descrisa modalitatea de definire a unor probleme de randare pentru a
permite abordarea calculului cuantic ın rezolvarea acestora si exploatarea potentialului acestuia.
Pornind de la aceasta maniera de exploatare a proprietatilor remarcabile ale calculului cuantic
este propusa si varianta cuantica pentru schema de votare RANSAC [Caraiman 09c] ale carei
performante sunt analizate comparativ cu cazul clasic. De asemenea, este descrisa varianta cuan-
tica a algoritmului pentru o aplicatie importanta a acestei scheme de votare ın procesarea norilor
de puncte proveniti de la scanere 3D [Caraiman 09d].
Capitolul IV: Procesare grafica ın sisteme cuantice 27
Determinarea vizibilitatii primitivelor geometrice
In procesul de randare, ın care sunt sintetizate imagini ale unor scene cu obiecte tridimen-
sionale, este necesara aplicarea unei etape de determinare a vizibilitatii primitivelor geometrice
continute ın scena. Una dintre cele mai simple metode de determinare a poligoanelor vizibile
dintr-o scena ce urmeaza a fi vizualizata este algoritmul Z-Buffering [Catmull 75].
Algoritmul Z-Buffering nu este neaparat o problema de cautare, dar poate fi modificat ın asa
fel ıncat sa poata fi formulat utilizand varianta algoritmului lui Grover pentru gasirea elementului
cu valoare minima ıntr-un set de date.
Sa presupunem ca pentru fiecare pixel cream o superpozitie a starilor cuantice, unde fiecare
element al superpozitiei reprezinta unul din cele N poligoane din baza de date. Acestei superpozitii
i se poate aplica algoritmul cuantic de cautare cu solutii multiple pentru determinarea poligoanelor
ce intersecteaza pixelul curent. Aceasta etapa se executa ın O(√
dN) timp, unde d reprezinta
numarul de poligoane ce satisfac conditia de cautare. Aceasta complexitate corespunde timpilor
necesari pentru executia celor doi pasi implicati: numararea aproximativa a solutiilor si extragerea
acestora prin protocolul de semiclonare.
Pentru toate poligoanele pi din scena care intersecteaza pixelul curent, se pot calcula valo-
rile zpi, distanta dintre pixelul curent si poligonul i. Acest pas este executat ın O(1) timp prin
exploatarea paralelismului natural al calculului cuantic. Apoi, pentru acest pixel, trebuie sa de-
terminam poligonul aflat la cea mai mica distanta. De aici se poate aplica foarte usor varianta
algoritmului lui Grover pentru a gasi poligonul cu distanta minima pana la ecran, determinand ast-
fel poligonul ce trebuie utilizat pentru colorarea pixelului ın O(√
d). Acest proces trebuie repetat
pentru fiecare pixel (Algoritmul 2).
Astfel, complexitatea algoritmului Z-Buffering este de O(√
d) per pixel si cu un total de com-
plexitate de O(P√
d), unde P este numarul total de pixeli, iar d reprezinta numarul mediu de
poligoane ce intersecteaza un acelasi pixel din scena. In cazul cuantic, complexitatea etapei de
determinare a poligoanelor ce intersecteaza un anumit pixel este O(P√
dN). Daca tinem cont de
faptul ca d = N p/P, putem rescrie aceasta complexitate ın termenii numarului mediu de pixeli ce
intersecteaza un poligon ca O(N√
pP). Astfel, complexitatea totala ın cazul cuantic va fi data de
O(P√
dN), fata de cazul clasic ın care aceasta are expresia O(P(d + N)).
Desi factorul P din complexitatea algoritmului Z-Buffering cuantic este foarte mare, algoritmul
cuantic prezinta o scalabilitate mult mai buna ın raport cu numarul N de poligoane decat corespon-
dentul sau din calculul clasic. Astfel, cand N tinde spre miliarde de poligoane, algoritmul cuantic
obtine o mai buna complexitate timp de interogare decat algoritmii clasici. Aceasta dimensiune a
problemei este relevanta pentru multe aplicatii de realitate virtuala, de ex. reprezentarea completa
a unui mediu urban. Desi se poate argumenta ca utilizarea unei structuri de date clasice poate fi
folosita pentru a accelera algoritmul clasic, dupa cum s-a aratat ın [Lanzagorta 05b], cele mai bune
solutii ale algoritmilor clasici sunt posibile cu pretul unei complexitati spatiu mai mari. La fel de
important, un alt avantaj introdus de solutia cuantica este acela ca este valabila pentru obiecte cu
forme arbitrare si nu se limiteaza la poligoane simple.
Capitolul IV: Procesare grafica ın sisteme cuantice 28
Intrare: baza de date cu N poligoane
Iesire : FB - buferul de culoare asociat imaginii rezultate
foreach pixel (x, y) din imagine do1
creeaza o superpozitie uniforma de stari, |Ψ0〉, ın care fiecare element reprezinta unul din2
cele N poligoane din baza de date, P1, P2, ..., PN, |Ψ0〉 = 1√N
(|P1〉 + |P2〉 + ... + |PN〉) ;
aplica algoritmul de numarare aproximativa, ın care o stare este considerata solutie daca3
poligonul corespunzator intersecteaza pixelul (x, y);
aplica protocolul de semiclonare pentru extragerea celor d solutii ale problemei de la4
pasul 3;
creeaza o superpozitie uniforma de stari, |Ψ1〉, ın care fiecare element reprezinta unul din5
cele d poligoane din baza de date care intersecteaza pixelul curent, P1, P2, ..., Pd,|Ψ1〉 = 1√
d(|P1〉 + |P2〉 + ... + |Pd〉) ;
|Ψ2〉 = determinaZ(|Ψ1〉);6
Pm = detMin(|Ψ2〉) // determinarea valorii minime [Durr 99]7
FB(x, y) = IPm(x, y);8
Algoritm 2: Algoritmul cuantic propus pentru determinarea vizibilitatii primitivelor geome-
trice ıntr-o scena 3D
Metode de iluminare globala
In grafica pe calculator, ecuatia randarii descrie fluxul energiei luminoase ıntr-o scena. Aceasta
ecuatie se bazeaza pe fizica transportului luminii si furnizeaza rezultate perfecte din punct de
vedere teoretic, ın contrast cu diferitele tehnici practice de randare care aproximeaza acest ideal.
Baza fizica a ecuatiei randarii consta ın legea conservarii energiei. Pentru o anumita directie
si pozitie de pe o suprafata, lumina ce paraseste suprafata (Lo) este suma dintre lumina emisa (Le)
si cea reflectata (Lr). La randul ei, lumina refectata este data de lumina incidenta (Li) din toate
directiile ınmultita cu coeficientul de reflexie al suprafetei si unghiul de incidenta [Dutre 06]:
L0(x,w) = Le(x,w) +
∫
Ω
fr(x,w′,w)Li(x,w′)(w′· n)dw′, (IV.7)
unde:
L0(x,w) reprezinta lumina care paraseste suprafata din punctul x ın directia w,
Le(x,w) reprezinta lumina emisa din acelasi punct ın aceeasi directie,∫
Ω· · ·dw′ reprezinta suma infinitezimala peste o emisfera de directii incidente,
fr(x,w′,w) este proportia din lumina reflectata ın pozitia x,
Li(x,w′) reprezinta lumina incidenta ın punctul x din directia w′,
(w′· n) reprezinta atenuarea luminii incidente datorata unghiului de incidenta.
Rezolvarea ecuatiei randarii pentru orice scena data reprezinta principala provocare ın randarea
fotorealista. O abordare pentru rezolvarea acestei ecuatii se bazeaza pe metoda elementelor finite,
conducand la algoritmul de calcul al radiantei. O alta abordare ce foloseste metode de tip Monte
Capitolul IV: Procesare grafica ın sisteme cuantice 29
Figura IV.1: Algoritmul Ray-Tracing - se calculeaza intersectia cu obiectele din scena a unor raze
imaginare ce pornesc din punctul de observare
Carlo a condus la diferiti algoritmi, incluzand Ray Tracing sau construirea hartilor de fotoni (Pho-
ton Mapping).
Algoritmul Ray Tracing este una din cele mai folosite tehnici de randare [Glassner 89]. Un
astfel de algoritm determina vizibilitatea suprafetelor prin urmarirea unei raze pornind de la obser-
vator pana la obiectele din scena. Intersectia dintre o raza si un obiect determina culoarea pixelului,
dupa cum se poate observa si ın Figura IV.1. Acest proces are loc pentru fiecare pixel de pe ecran.
Astfel, pentru fiecare pixel de pe ecran, algoritmul determina daca exista o intersectie ıntre raza
si oricare obiect din scena. Daca raza intersecteaza multe obiecte, doar acel obiect care este cel
mai aproape de ecran este afisat. Astfel, sunt necesare O(N) operatii per raza, deoarece trebuie
determinate intersectiile pentru fiecare din cele N obiecte din scena.
Deoarece Ray Tracing este prin natura sa un algoritm de cautare, necesitand o cautare a
intersectiilor dintre o raza si o colectie de N obiecte, acesta este un bun candidat pentru optimizarea
folosind algoritmul cuantic de cautare al lui Grover. Astfel, algoritmul de urmarire a razei poate fi
implementat prin executarea unei cautari cuantice a intersectiilor dintre raze si poligoane, urmata
de o cautare cuantica a poligonului cel mai apropiat de ecran. Odata determinat acest poligon, se
poate executa o rafinare pentru colorarea adecvata a pixelului corespunzator. Intersectia dintre o
raza si un poligon este o procedura foarte simpla si implica doar calcule de geometrie analitica de
baza.
Pentru implementarea algoritmului Ray Tracing cuantic, se creeaza o stare |Ψ〉 ce codifica toate
poligoanele din scena ıntr-o superpozitie uniforma de stari cuantice:
|Ψ〉 = α(|00...01〉 + |00...10〉 + ...), (IV.8)
ın care fiecare element din superpozitie reprezinta unul din diferitele poligoane din scena. Aceasta
superpozitie de stari este utilizata pentru fiecare raza urmarita. Mai este necesara definirea unei
functii f care va actiona asupra fiecarei stari din superpozitie astfel:
f (x) =
1, x intersecteaza raza
0, alt f el.(IV.9)
Paralelismul cuantic poate fi utilizat pentru evaluarea f (x) pentru fiecare element al superpozitiei
(fiecare obiect din scena) ıntr-un singur pas de calcul. In continuare, protocolul de semiclonare
Capitolul IV: Procesare grafica ın sisteme cuantice 30
poate fi utilizat pentru determinarea tuturor celor k poligoane ce intersecteaza raza ın O(√
Nk)
pasi. Extensia algoritmului lui Grover pentru determinarea minimului poate fi utilizata pentru
determinarea poligonului cel mai apropiat de ecran ın O(√
k) timp. Complexitatea totala a algo-
ritmului cuantic de urmarire a razei devine O(√
Nk +√
k) per raza urmarita, iar ın cele mai multe
aplicatii practice, k ≈ O(1) si k ≪ N.
In mod clar, unul din avantajele solutiei cuantice este acela ca nu este necesara utilizarea
poligoanelor pentru reprezentarea scenei. In procesul clasic de randare, poligoanele sunt uti-
lizate deoarece calcularea intersectiei cu acestea este mai usoara decat cu obiecte generice. Daca
intersectia dintre un obiect si o raza se poate stabili ın timp constant, ın solutia cuantica se poate
utiliza orice tip de obiect. Astfel, solutia cuantica este mult mai robusta pentru obiecte cu o ge-
ometrie arbitrara. In concluzie, principalul avantaj al solutiei cuantice consta ın complexitatea timp
optima a interogarii pentru obiecte generale, cu o complexitate spatiu liniara.
Algoritmul Ray Tracing este o excelenta metoda de simulare a luminii reflectate si refractate.
Totusi, acest algoritm nu poate aproxima decat ıntr-un mod rudimentar si costisitor lumina difuza
(lumina emisa de materialele opace). Calculul radiantei este o metoda care modeleaza foarte
bine lumina difuza, dar ofera o slaba reprezentare a luminii reflectate [Cohen 93]. Cu alte cuvinte,
metoda Ray Tracing este o metoda buna pentru a reda imagini cu obiecte din materiale lucioase sau
semitransparente, ın timp ce calculul radiantei este o metoda optima pentru redarea suprafetelor
opace.
Metoda de calcul al radiantei se bazeaza pe principiul conservarii energiei [Foley 96]. Astfel,
totalul de energie radiata de catre un material opac este egal cu energia natural emisa de material
plus energia reflectata:
Radianta = energie emisa + energie re f lectata, (IV.10)
unde, Energia reflectata= coeficientul de reflexie * totalul de energie incidenta obiectului provenind
de la toate celelalte obiecte din scena.
Aceasta se poate scrie sub forma asa-numitei ecuatii a radiantei [Cohen 93]:
BidAi = EidAi + ζi
∫
B jF jidA j. (IV.11)
Daca presupunem ca scena contine un numar discret de obiecte, atunci aceasta ecuatie ia forma:
BidAi = EidAi + ζi
∑
j
B jF jidA j (IV.12)
In aceste ecuatii, Bi reprezinta radianta fiecarui element, dAi este elementul de arie, Ei reprezinta
energia emisa, ζi reprezinta coeficientul de reflexie al materialului, iar F este matricea factorilor de
forma ce determina energia incidenta emisa de celelalte obiecte din scena. Ecuatia radiantei poate
fi rescrisa ın forma matriceala:
M· B = E, (IV.13)
Capitolul IV: Procesare grafica ın sisteme cuantice 31
unde M este o matrice a interactiunilor:
M =
1 − ζ1F11 −ζ1F12 ... −ζ1F1N
−ζ2F21 1 − ζ2F22 ... −ζ2F2N
......
. . ....
−ζN FN1 −ζN FN2 ... 1 − ζN FNN
. (IV.14)
Daca E si M sunt cunoscute, se poate aplica metoda lui Gauss pentru rezolvarea sistemului
si calcularea vectorului de radianta B ın O(N) pasi. E este o proprietate intrinseca a materialului
si deci este o cantitate cunoscuta. Factorii de forma din matricea M nu sunt cunoscuti dar pot fi
calculati prin aplicarea algoritmului Ray Tracing ın scena considerata, necesitand O(N2) pasi ın
cazul clasic. Odata determinat B, mai trebuie calculata culoarea fiecarui pixel de pe ecran, operatie
ce se poate realiza prin utilizarea unei tehnici foarte similare cu algoritmul Ray Tracing.
Astfel, folosind un raytracer cuantic putem executa etapele implicate ın calculul radiantei ın
O(N3/2) pasi pentru calcularea factorilor de forma si respectiv O(√
N) pasi pentru determinarea
culorii unui pixel prin tehnica urmaririi razelor. Totusi, nu putem folosi calculatoarele cuantice
pentru a optimiza etapa de rezolvare a ecuatiei matriceale a radiantei pentru care sunt necesari
O(N) pasi. In consecinta, calculul cuantic al radiantei cuantica poate fi executat ın O(N3/2) timp,
ın contrast cu timpul O(N2) necesar ın cazul clasic.
Accelerarea obtinuta prin folosirea algoritmului cuantic de calcul al radiantei poate fi folosita
pentru a creste realismul imaginilor randate. Dupa cum a mai fost mentionat anterior, radianta nu
modeleaza cu acuratete lumina reflectata. Totusi, exista o extensie a metodei de calcul al radiantei,
cunoscuta sub numele de calculul radiantei prin urmarirea razelor, care simuleaza corect atat re-
flexia cat si refractia. Dupa cum indica si numele, radianta prin urmarirea razelor implementeaza
ambele tehnici ıntr-una singura, mult mai complexa. Aceasta metoda presupune doi pasi. In primul
pas se executa calculul radiantei, ca de obicei, iar ın al doilea pas, se iau ın considerare reflexiile.
In acest pas secund, pentru fiecare pixel, se traseaza cateva raze si se obtine radianta razelor reflec-
tate. Daca sunt folosite M raze pentru fiecare pixel, al doilea pas necesita O(M ∗ N ∗ S ) operatii
daca sunt luate ın considerare S − 1 reflexii. Evident, acesta este un algoritm cu un mare consum
de timp, dar este usor de implementat. Al doilea pas este apoi executat ın O(M ∗ S ∗√
N) timp ın
cazul cuantic.
Metoda hartilor de fotoni (Photon Mapping) este un algoritm de iluminare globala ın doi
pasi dezvoltat de Henrik Jensen [Jensen 01] ca o alternativa eficienta la tehnicile Monte Carlo
pure de urmarire a razelor. Photon Mapping decupleaza solutia de calcul a iluminarii de geome-
tria scenei, aceasta solutie fiind reprezentata ıntr-o structura de date spatiala denumita harta de
fotoni. Aceasta decuplare se dovedeste a fi foarte importanta deoarece permite ca termenii din
ecuatia randarii sa fie calculati separat si stocati ın harti de fotoni separate. De asemenea confera
flexibilitate metodei deoarece unele parti din ecuatia randarii pot fi rezolvate utilizand alte tehnici.
In primul pas al metodei se construieste harta de fotoni prin trasarea si urmarirea fotonilor ce
pleaca de la o sursa de lumina, iar ın al doilea pas scena este randata utilizand informatia stocata
ın harta de fotoni.
In prima etapa, pachete de lumina (fotoni) sunt emise ın scena de catre sursele de lumina. La
intersectia unui foton cu o suprafata, se stocheaza ın harta de fotoni punctul de intersectie, directia
Capitolul IV: Procesare grafica ın sisteme cuantice 32
de incidenta si puterea fotonului. In mod tipic, pentru o scena sunt create doua harti de fotoni: una
specifica fenomenelor caustice si una pentru alte tipuri de iluminare. Dupa intersectarea suprafetei,
proprietatile de material furnizeaza o probabilitate ca fotonul sa fie reflectat, absorbit sau refrac-
tat/transmis. O metoda de tip Monte Carlo, denumita Ruleta Ruseasca este utilizata pentru a alege
una din aceste actiuni [Jensen 01]. Daca fotonul este absorbit, acestuia nu ıi este asignata o directie
noua, urmarirea parcursului acestui foton fiind ıncheiata. Daca fotonul este reflectat sau refractat,
proprietatile suprafetei si unghiul de incidenta sunt utilizate pentru determinarea noii directii.
In cea de a doua etapa, harta de fotoni este utilizata pentru estimarea radiantei fiecarui pixel din
imaginea finala. Pentru fiecare pixel, se traseaza cate o raza ın scena si se determina intersectia cu
cea mai apropiata suprafata. In acest punct este utilizata ecuatia randarii pentru a calcula radianta
suprafetei ce paraseste punctul de intersectie ın directia razei. Pentru eficienta, ecuatia este des-
compusa ın patru factori: iluminarea directa, reflexia speculara, refractia caustica si iluminarea
indirecta.
O implementare cuantica a metodei hartilor de fotoni poate beneficia de proprietatile calculului
cuantic sub doua aspecte. Pe de o parte, la fel ca si ın cazul algoritmului Ray Tracing, cautarea
intersectiilor dintre un foton transmis de la o sursa de lumina si o colectie de N obiecte poate fi
realizata prin intermediul algoritmului cuantic de cautare cu solutii multiple. Determinarea primu-
lui obiect intersectat se poate realiza prin cautarea cuantica a obiectului cu distanta minima fata de
sursa de lumina dintre cele considerate solutii pentru problema anterioara de cautare. Astfel, etapa
de urmarire a traseului unui foton prin scena prezinta ın cazul cuantic complexitatea O(√
N), fata
de O(N) ın cazul clasic, unde N reprezinta numarul de obiecte (poligoane) din scena.
Pe de alta parte, spre deosebire de calculatoarele clasice, sistemele de calcul cuantic pot imple-
menta metode de tip Monte Carlo cu valori aleatoare autentice. In calculul clasic, ın locul valorilor
aleatoare se utilizeaza valori pseudo-aleatoare (de fapt, numere complet deterministe). In metoda
hartilor de fotoni tehnicile Monte Carlo sunt utilizate atat pentru emisia de fotoni de catre o sursa
de lumina, cat si pentru a decide daca, la intersectia cu o suprafata, un foton este absorbit, reflectat
sau refractat, ın functie de proprietatile materialului.
Utilizarea unui calculator cuantic drept generator de numere aleatoare este foarte simpla si
presupune aplicarea transformatei Hadamard unei stari cuantice ce codeaza distributia de proba-
bilitate. Efectul transformatei Hadamard este de a creea o superpozitie uniforma de stari, astfel
ıncat fiecare stare are aceeasi probabilitate de a fi masurata:
H(|0〉|0〉 . . . |0〉) = 1
2m/2
2m−1∑
i=0
|i〉 masurare−−−−−−→ |i〉 cu probabilitatea 2−m
Managementul nivelurilor de detaliu
Generarea nivelurilor de detaliu pentru obiectele dintr-o scena se bazeaza pe ideea ca ın multe
aplicatii, fidelitatea sau realismul pot fi diminuate ın favoarea vitezei de randare. Spre exemplu,
unele detalii ale unui obiect pot sa nu fie vizibile din punctul de observare, sau aceste detalii sunt
atat de mici ıncat sunt imperceptibile. In alte cazuri, o imagine de rezolutie mica a unui obiect
poate fi necesara pentru realizarea unei introspectii vizuale rapide (Figura IV.2). In aceste cazuri
Capitolul IV: Procesare grafica ın sisteme cuantice 33
(a) (b)
Figura IV.2: ”Stanford Bunny” - model de test obtinut de Greg Turk si Marc Levoy ın 1994 la
Universitatea Stanford prin scanarea 3D a unei figurine ceramice reprezentand un iepure. (a) De
la stanga la dreapta sunt prezentate modele cu nivel maxim de detaliu pana la nivelul minim. (b)
Utilizarea mai multor niveluri de detaliu ıntr-o scena 3D.
se poate utiliza un algoritm de generare si parcurgere a nivelurilor de detaliu care determina unde
si cat de mult poate fi simplificat un obiect din scena.
Daca pentru descrierea modelelor sunt utilizate suprafate reprezentate prin retele de poligoane,
metoda nivelurilor de detaliu determina care varfuri ale retelei sunt necesare pentru reprezentarea
modelului ın circumstantele date. Daca anumite varfuri nu sunt necesare, acestea sunt eliminate din
retea. Pentru a determina daca un varf este necesar sau nu, metoda nivelurilor de detaliu evalueaza
o functie de eroare ǫ(ν) pentru fiecare varf ν. Daca eroarea asociata unui varf este mai mica
decat o valoare de prag impusa, δ, atunci varful poate fi eliminat. Aceasta procedura este repetata
pentru toate varfurile retelei de poligoane, ın fiecare cadru redat. Pentru a creste performanta,
toate poligoanele sunt codate ıntr-o structura ierarhica arborescenta ce determina varfurile active
la un moment dat. In acest caz, daca eroarea este mai mica decat valoarea de prag, varful poate fi
expandat pentru a include portiuni inferioare din arbore. Totusi, procesul trebuie executat pentru
ıntregul set de varfuri active si necesita O(N) pasi, unde N este numarul de varfuri active.
In versiunea cuantica a metodei nivelurilor de detaliu, se genereaza o stare cuantica |Ψ〉 ce
codeaza ıntreaga retea formata din N varfuri. Portile Hadamard pot fi utilizate pentru obtinerea
unei superpozitii uniforme de stari. Fiecare element din aceasta superpozitie reprezinta un varf al
retelei. Se defineste o functie f astfel ıncat:
f (ν) =
1, daca ǫ(ν) < δ
0, alt f el(IV.15)
Paralelismul cuantic poate fi exploatat pentru a evalua functia f (ν) pentru fiecare element al
superpozitiei ıntr-un singur pas. Algoritmul lui Grover poate fi aplicat apoi pentru a gasi un numar
necunoscut de varfuri cu o eroare suficient de mica pentru a fi eliminate. Aceasta operatie poate fi
realizata ın O(√
N) pasi, ın contrast cu cei O(N) pasi necesari ın cazul clasic. Aceasta procedura
este utilizata pentru fiecare cadru afisat iar N este numarul de varfuri din structura ierarhica.
Capitolul IV: Procesare grafica ın sisteme cuantice 34
Algoritmul RANSAC cuantic - QRANSAC
RANSAC (RANdom SAmple Consensus) este un algoritm pentru potrivirea robusta a mod-
elelor parametrice si s-a dovedit a fi un rezultat foarte important atat ın domeniul graficii pe cal-
culator cat si al vederii artificiale. Algoritmul RANSAC a fost propus ın [Bolles 81] si a fost
aplicat de atunci pentru rezolvarea unei game variate de probleme: estimarea matricii fundamen-
tale [Torr 97a], estimarea tensorului trifocal [Torr 97b], estimarea pozitiei si orientarii camerei
[Nister 05], detectia formelor [Schnabel 07], reconstructia modelelor din imagini [Hartley 04],
[Nister 05]. In aceasta sectiune vom arata cum exploatarea proprietatilor unice ale calculului cuan-
tic - generarea de superpozitii uniforme de stari ın spatiul problemei si aplicarea operatorilor cuan-
tici tuturor starilor simlutan - permite descrierea unui algoritm cuantic pentru schema de votare
RANSAC (QRANSAC) cu performante net superioare celui clasic.
Pentru a realiza potrivirea unui model ıntr-un set de date, algoritmul RANSAC genereaza ın
mod repetat posibile solutii ale modelului, estimate plecand de la subseturi minimale generate
aleator din setul de date original si se masoara consensul pentru aceste solutii candidate. Consid-
erarea unui subset minimal necesar pentru descrierea modelului parametric minimizeaza probabil-
itatea ca acesta sa contina valori extreme. Dupa masurarea consensului asupra unui numar fix de
candidati, se alege modelul cu cel mai bun suport (cu cel mai mare numar de voturi) iar daca su-
portul acestuia este suficient de mare (mai mare decat o valoare de prag), modelul este considerat
valid iar obiectele ce ıi corespund sunt eliminate din setul de date initial. Pentru a detecta structuri
multiple ıntr-un set de date, procesul este repetat pana cand cel mai bun candidat nu ındeplineste
conditia de validare (ex. numarul de obiecte din setul de date ce voteaza pentru acesta este mai mic
decat o valoare de prag). In acest moment se poate considera ca setul de date ramas nu mai poate
contine structuri valide. Criteriul de stop al algoritmului poate fi combinat cu conditia ca numarul
de articole ramase ın setul de date sa fie mai mic decat o valoare de prag euristica.
Se poate observa ca ın schema de votare RANSAC, gasirea celui mai bun model parametric
dupa un numar fix de iteratii poate fi vazuta ca o problema de cautare. Calcularea consensului
pentru fiecare candidat este de asemenea o problema de cautare cu solutii multiple. Este evident
faptul ca daca fiecare pas al algoritmului poate fi exprimat ın termeni de cautare, atunci exploatarea
proprietatilor calculului cuantic ar putea ımbunatati semnificativ performantele schemei de votare
RANSAC.
Pentru potrivirea primei structuri planare ın setul de date folosind varianta clasica a algoritmu-
lui, sunt necesari O(mN) pasi de calcul deoarece N obiecte voteaza pentru m modele candidate.
Cand este necesara manipularea unor seturi de date de mari dimensiuni aceasta abordare prezinta o
complexitate nesatisfacatoare. Daca problema determinarii celui mai bun model parametric potrivit
ın setul de date este redusa la o problema de cautare atunci termenul m al expresiei poate fi redus
la√
m. Mai mult, complexitatea algoritmului poate fi redusa folosind o abordare similara pentru
determinarea consensului pentru un candidat. O observatie importanta este aceea ca, de fapt, deter-
minarea efectiva a obiectelor ce apartin fiecarui model nu este necesara decat ın cazul modelului cu
suport maxim. Pentru restul candidatilor este suficienta doar cunoasterea numarului de obiecte ce
formeaza acest suport. Astfel, pentru calcularea consensului pentru fiecare candidat se poate uti-
liza numararea exacta sau aproximativa folosind estimarea amplitudinii starilor cuantice. Aceasta
Capitolul IV: Procesare grafica ın sisteme cuantice 35
abordare reduce termenul N al complexitatii la O(√
(k + 1)(N − k + 1)), unde k reprezinta numarul
de itemi ce apartin unui model candidat. Deoarece pentru cel mai bun candidat este necesara si
determinarea efectiva a subsetului de date ce formeaza suportul acestuia, ın expresia complexitatii
trebuie adaugat un termen corespunzator. In cazul clasic acesta ar fi O(N), dar, exploatand proto-
colul de semiclonare pentru extragerea solutiilor multiple ale unei probleme de cautare, termenul
este redus la O(k), unde k reprezinta numarul de solutii cunoscut apriori.
Schema de votare descrisa mai sus poate fi sintetizata sub forma algoritmului RANSAC cuantic
(Algoritmul 3).
Intrare: m - nr. de modele candidate
Iesire : Modelul parametric identificat si itemii din setul de date de intrare asociati
creeaza o superpozitie uniforma de stari, |Ψ〉, in care fiecare element reprezinta unul din cele1
m modele candidate M1, M2, ..., Mm, |Ψ〉 = 1√m
(|M1〉 + |M2〉 + ... + |Mm〉) ;
|C〉 = Calculeaza Consensul(|Ψ〉) ;2
Mmax = Cauta Val Max(|C〉) // det. M j, cu C j = Cmax, j = 1,m3
creeaza o superpozitie uniforma de stari, |Φ〉, ın care fiecare element reprezinta unul din cei4
N itemi ai setului de date initial, |Φ〉 = 1√N
(|V1〉 + |V2〉 + ... + |VN〉) ;
Cautare Solutii Multiple(Φ, Mmax, Cmax) // determina cei Cmax itemi ai5
modelului Mmax
Algoritm 3: Algoritmul RANSAC cuantic (QRANSAC) [Caraiman 09c]
Primul pas al algoritmului pregateste o superpozitie uniforma de m stari corespunzatoare celor
m modele candidate generate prin selectarea aleatoare a unui subset minimal al setului original.
Pentru fiecare candidat, ın pasul al 2-lea se calculeaza valorile Ci ce reprezinta consensul pentru
fiecare model candidat (numarul de itemi apartinand modelului). Consensul este calculat ın paralel
pentru toti candidatii, exploatand paralelismul inerent al calculului cuantic. In pasul al 3-lea se
determina candidatul cu suport maxim. Dupa cum s-a aratat ıntr-o sectiune anterioara, aceasta
problema este rezolvata prin aplicarea unei variante a algoritmului lui Grover. Pentru modelul
cu suport maxim se pregateste o superpozitie uniforma de stari, corespunzatoare celor N itemi
din setul initial de date, ın vederea determinarii obiectelor ce apartin acestuia. Aceasta problema
corespunde extragerii solutiilor multiple folosind protocolul de semiclonare, numarul de solutii,
Cmax, fiind cunoscut din pasul 3.
Calcularea consensului pentru fiecare candidat poate fi realizata prin aplicarea algoritmului
cuantic de numarare aproximativa. Astfel, pentru fiecare model candidat, acest algoritm este apli-
cat unei superpozitii uniforme de stari ca ın pasul 4, iar operatorul oracol din iteratia Grover este
construit folosind functiile fi : X → 0, 1 cu
fi(x) =
1, x ∈ Pi
0, x < Pi
, i = 1,m, (IV.16)
unde X reprezinta setul initial de date. Pentru fiecare candidat, algoritmul va returna numarul de
obiecte apartinand modelului (consensul Ci).
Capitolul IV: Procesare grafica ın sisteme cuantice 36
Candidatul Pmax cu valoarea maxima a consensului poate fi determinat apoi prin aplicarea al-
goritmului cuantic de cautare a valorii maxime.
Urmarind analiza complexitatii pentru algoritmul de numarare aproximativa, din [Brassard 00]
rezulta ca sunt necesari O(√
(t + 1)(N − t + 1)) pasi de calcul pentru calcularea consensului pen-
tru m modele candidate, unde t reprezinta de fapt consensul Cmax asociat celui mai bun candidat
deoarece acest candidat va impune cel mai mare numar de iteratii Grover necesare. Pentru cautarea
valorii maxime a consensului pentru cei m candidati, sunt necesari O(√
m) pasi, iar pentru deter-
minarea celor Cmax itemi apartinand candidatului Pmax sunt aplicati O(√
t) pasi de calcul. Astfel,
complexitatea generala a a algoritmului QRANSAC pentru potrivirea unui model parametric ıntr-
un set de date este O(√
(t + 1)(N − t + 1) +√
m +√
t).
In [Caraiman 09d] este descrisa aplicarea variantei cuantice a algoritmului RANSAC ın proce-
sarea norilor de puncte proveniti de la scanere 3D pentru simplificarea acestora prin metoda de-
scrisa ın capitolul al III-lea.
Concluzii
Cercetarile teoretice si experimentale realizate pana ın prezent ın domeniul calculului cuantic
se afla ınca ıntr-o etapa incipienta si ınca este necesara depunerea unor eforturi semnificative pentru
clarificarea aspectelor teoretice si practice legate de codificarea si procesarea informatiei pe baza
fenomenelor cuantice. Cu toate acestea, a devenit un domeniu de cercetare important pentru stiinta
calculatoarelor iar interesul crescut este justificat de existenta unor algoritmi cuantici eficienti care
pot executa unele calcule semnificativ mai rapid decat ın calculul clasic. Construirea unui calcu-
lator cuantic functional reprezinta o sarcina cu multe provocari ce necesita utilizarea unei cantitati
imense de resurse. Dezvoltarea de algoritmi cuantici eficienti pentru probleme practice ar justifica
aceste eforturi imense. Astfel de algoritmi au fost dezvoltati pentru domeniul procesarii grafice,
astfel ıncat, ın [Caraiman 09c, Caraiman 09d] este prezentat modul ın care algoritmi cuantici
existenti (precum algoritmul lui Grover si variante ale sale) pot fi utilizati pentru furnizarea unui
algoritm cuantic pentru schema de votare RANSAC, o paradigma cu multiple aplicatii importante
ın grafica pe calculator. Definirea variantei cuantice a RANSAC a fost posibila prin reformularea
algoritmului pentru a putea exploata proprietatile speciale ale superpozitiei starilor cuantice. Ast-
fel, au fost identificati pasii algoritmului care pot fi exprimati ın termeni de probleme de cautare,
conducand la performante net superioare ale algoritmului cuantic fata de cel clasic. In acest con-
text, ımpreuna cu algoritmii formulati pentru problema randarii (determinarea vizibilitatii primi-
tivelor geometrice, metode de iluminare globala, managementul nivelurilor de detaliu), algoritmul
QRANSAC reprezinta un rezultat promitator pentru investigarea mai multor astfel de aplicatii ale
calculului cuantic ın procesarea grafica.
Capitolul V
Simularea calculelor cuantice
Deoarece hardware-ul cuantic nu este disponibil ın afara laboratoarelor de cercetare, simula-
toarele cuantice au devenit instrumente pretioase ın dezvoltarea si testarea algoritmilor cuantici
precum si ın simularea modelelor fizice pentru implementarea hardware a unui procesor cuan-
tic. Capitolul al V-lea abordeaza aceasta tematica a simularii calculelor cuantice folosind sisteme
de calcul clasice. Este prezentata importanta simularii precum si o trecere ın revista a simula-
toarelor si a limbajelor de programare cuantica dezvoltate pana ın prezent. Pentru simularea al-
goritmilor cuantici studiati, acestia sunt analizati folosind formalismul portilor cuantice si sunt
furnizate implementari ale acestora ıntr-un limbaj de programare cuantica (problema Bernstein-
Vazirani [Arustei 08c], problema cautarii [Caraiman 10a]). S-a demonstrat ca resursele clasice
(memorie, putere de procesare) necesare simularii cuantice sunt exponentiale ın raport cu dimen-
siunea problemei simulate, impunand limitari drastice asupra problemelor ce pot fi simulate. Sis-
temele Grid pot furniza resursele de calcul necesare simularii unui calculator cuantic, ın acest
capitol fiind propus un serviciu Grid, GQCL, care expune aceasta functionalitate. Este descrisa
arhitectura acestui serviciu Grid care permite utilizarea unui limbaj de programare cuantica, QCL
- Quantum Computation Language [Omer 03], prin executia programelor cuantice folosind o noua
varianta a simulatorului QC-lib [Omer 96] care utilizeaza procesarea paralela pe clustere de calcu-
latoare. Sunt analizate rezultatele experimentale obtinute ın urma rularii mai multor cazuri de test
incluzand algoritmi de cautare ce intervin ın probleme de procesare grafica.
Necesitatea simularii calculelor cuantice folosind calcul paralel
O colectie de n qubiti se numeste registru cuantic de dimensiune n. Starea generala a unui
registru pe n qubiti este
|ψ〉 =2n−1∑
i=0
ai|i〉, (V.1)
unde ai ∈ C,∑2n−1
i=0 |ai|2 = 1.
Aceasta ınseamna ca starea unui registru pe n qubiti este reprezentata de un vector complex
de lungime unitate ın spatiul Hilbert H2n . Pe un calculator clasic, stocarea unui numar complex
37
Capitolul V: Simularea calculelor cuantice 38
a = x + iy necesita stocarea unei perechi de numere reale (x, y). In perspectiva unui numar foarte
mare de operatii aritmetice, este preferata utilizarea reprezentarii pe 8 octeti a numerelor reale.
Astfel, pentru a stoca un registru cuantic pe n qubiti folosind un calculator conventional (clasic),
sunt necesari cel putin 2n+4 octeti. Memoria necesara pentru simularea unui calculator cuantic pe
n qubiti creste exponential ın raport cu n. Spre exemplu, pentru n = 24 (n = 36) este necesar un
spatiu de memorie de cel putin 256 MB (1 TB) pentru stocarea unei singure stari arbitrare |ψ〉.Evolutia ın timp a unui registru cuantic pe n qubiti este determinata de un operator unitar definit
ın spatiul H2n . Dimensiunea matricei este de 2n x 2n. In general sunt necesare 2n x 2n spatiu si
2n(2n+1−1) operatii aritmetice pentru executarea clasica a unui astfel de pas de evolutie [Niwa 02].
Astfel, simularea unui calculator cuantic folosind un calculator clasic reprezinta o problema
grea, memoria si procesorul generand limitari drastice asupra dimensiunilor calculatoarelor cuan-
tice ce pot fi simulate. Datorita comportamentului exponential al sistemelor cuantice, simularea
acestora folosind calculatoare clasice impune utilizarea unui spatiu de memorie exponential si exe-
cutarea unui numar exponential de operatii. Utilizarea calculului paralel poate reprezenta o solutie
a acestei probleme [Raedt 07, Niwa 02, Obenland 98].
Totusi, dezvoltarea unui simulator cuantic impune luarea ın considerare si a unui alt aspect:
faptul ca acesta trebuie sa fie usor accesibil. Dar aceasta vine ın contradictie cu prima cerinta
care restrictioneaza grupul potentialilor utilizatori. O solutie bazata pe conceptul de Grid poate fi
utilizata pentru a rezolva aceasta contradictie si a pune la dispozitia comunitatii de cercetatori ın
domeniul calculului cuantic un instrument util si usor accesibil. Conceptul de Grid adreseaza prob-
lema partajarii coordonate a resurselor si rezolvarea de probleme ın organizatii virtuale dinamice,
multi-institutionale [Foster 01].
Un simulator cuantic ce ruleaza ın sisteme Grid este cel propus ın acest capitol si descris ın
[Caraiman 09a]. Acest simulator permite utilizarea limbajului de programare cuantica QCL prin
executia programelor cuantice folosind o varianta a bibliotecii QC-lib care utilizeaza procesarea
paralela pe clustere de calculatoare. Schema de partitionare a datelor ıntre procesoare si stocarea
eficienta a starii cuantice au permis obtinerea unor performante foarte bune ın ceea ce priveste
accelerarea si eficienta implementarii paralele propuse.
GQCL - Serviciu Grid pentru simularea calculelor cuantice
Acest simulator cuantic este bazat pe biblioteca QC-lib care furnizeaza un framework pentru
executarea programelor scrise ın limbajul de programare cuantica QCL, ın absenta hardware-ului
cuantic. Motivele care au condus la alegerea acestui limbaj de programare cuantica sunt detaliate
ın acest capitol al tezei si se refera, ın principal, la reprezentarea starii cuantice folosind numere
complexe, posibilitatea de a construi operatori cuantici complecsi, existenta unei extensii clasice a
limbajului QCL precum si caracterul universal al acestuia. Acest limbaj este un limbaj procedural
de nivel ınalt cu o sintaxa asemanatoare limbajului C. QC-lib este o biblioteca C++ pentru simu-
larea calculatoarelor cuantice la un nivel functional abstract si este utilizata ca interpretor pentru
QCL.
Capitolul V: Simularea calculelor cuantice 39
Figura V.1: Modelul Serviciu Fabrica/Serviciu Instanta adoptat ın GQCL. O aplicatie client se
poate conecta fie la serviciul Fabrica pentru a creea o noua resursa Grid, fie direct la o resursa
existenta, prin intermediul serviciului Instanta.
Arhitectura serviciului Grid de simulare
In [Caraiman 09a] s-a optat pentru expunerea ın sisteme Grid a implementarii paralele a QCL
prin intermediul unui serviciu GT4. Pentru paralelizare s-a folosit implementarea LAM 7.1.2/7.1.4
a standardului MPI-2. Executia paralela a QCL este lansata ca job Grid prin intermediul unui
serviciu bazat pe arhitectura Fabrica/Instanta prezentand urmatoarele avantaje [Archip 08a]:
• orice utilizator Grid autorizat poate accesa implementarea QCL fara interventia directa a
unui administrator de sistem (nu este necesar ca un administrator de sistem sa instaleze
implementarea QCL pentru fiecare utilizator Grid autorizat);
• orice utilizator Grid autorizat poate rula instante de simulare multiple, task-urile de adminis-
trare a aplicatiei fiind tratate de serviciu ıntr-o maniera automatizata;
• utilizatorii autorizati pot construi cu usurinta aplicatii Grid mai complexe prin utilizarea
tehnicilor de compunere a serviciilor (e.g. rezultatele produse ın urma unei simulari cuantice
pot fi utilizate ca intrare pentru alte task-uri).
Arhitectura serviciului GQCL respecta sablonul de proiectare Fabrica/Instanta [Sotomayor 05]
(Figura V.1). Un astfel de model permite o buna administrare a resurselor Grid si ofera suport pen-
tru accesarea aceluiasi serviciu de catre utilizatori multipli. Pentru a expune functionalitatea simu-
latorului de calcul cuantic, serviciul GQCL foloseste metoda de integrare a aplicatiilor paralele ca
servicii Grid propusa ın [Archip 08b].
Urmarind acest model, serviciul GQCL prezinta doua componente majore. Prima dintre aces-
tea este componenta Fabrica, QCLFactoryService. Aceasta implementeaza o functionalitate de
Capitolul V: Simularea calculelor cuantice 40
baza, aceea de a crea noi resurse-WS ce pot fi utilizate de cea de a doua componenta, QCLIns-
tanceService. Odata creata o resursa-WS, QCLFactoryService returneaza un obiect EndpointRefe-
renceType ce identifica ın mod unic noua resursa.
Cea de-a doua componenta, QCLInstanceService este responsabila cu administrarea efectiva
a simularii cuantice ca job ın sistemul Grid. Prin utilizarea unei resurse-WS, serviciul instanta
lanseaza job-ul Grid si monitorizeaza starea acestuia notificand aplicatiile client asupra modificarilor
relevante. De asemenea este automatizat transferul de fisiere astfel ıncat, la ıncheierea executiei
job-ului Grid, aplicatia client poate accesa fisierele ce contin rezultatele simularii.
Dupa cum s-a mentionat, resursa-WS este responsabila cu administrarea job-ului de simulare
cuantica. Implementarea descrisa ın [Caraiman 09a] prezinta urmatoarele caracteristici:
• odata ce un utilizator lanseaza ın executie job-ul Grid, resursa-WS actioneaza ın numele
acestuia ın calitate de client pentru suita WS-GRAM furnizata de implementarea GT4;
• utilizarea firelor de executie pentru administrarea job-urilor utilizator;
• administrarea firului de executie pentru controlul LAM/MPI asociat utilizatorului curent -
ınainte de pornirea executiei aplicatiei paralele, este verificata existenta unei instante a firului
de executie de control al daemon-ului LAM pentru utilizatorul curent; daca lamd nu ruleaza,
atunci daemon-ul este pornit folosind o configuratie predefinita pentru situl Grid respectiv.
• mentinerea informatiilor despre starea curenta a job-ului Grid lansat - resursa-WS este ınre-
gistrata ca ”listener” pentru PropertyChangeEvent; odata ce starea job-ului se modifica,
resursa-WS este notificata si va produce la randul ei o notificare pentru aplicatiile client
ınregistrate.
Aceasta abordare prezinta un avantaj suplimentar: daca simularea se ıncheie cu eroare, uti-
lizatorul poate semnala resursei-WS sa distruga firul de executie sau poate distruge chiar resursa
afectata, asigurand astfel un mediu ”curat” pentru simulari ulterioare.
Implementarea paralela a bibliotecii QC-lib
In QCL, un registru cuantic contine un numar de vectori ai bazei, fiecare avand o amplitudine
corespunzatoare. Cand qubitii care formeaza registrul cuantic se afla ıntr-o superpozitie de stari,
numarul de vectori creste exponential. In QC-lib, starea de superpozitie a unui registru pe un
qubit este reprezentata prin intermediul a doi vectori ai bazei (termeni) pentru care trebuie stocate
valorile complexe ale amplitudinilor: 2 x complex < double >= 32 octeti. La aplicarea unui
operator cuantic sunt create doua liste de termeni: una pentru stocarea termenilor din starea curenta
si una pentru acumularea rezultatului operatiei asupra starii. Rezulta un total de 64 octeti/termen
care, pentru un registru pe n qubiti, necesita utilizarea a 2n+6 octeti. Astfel, pentru n = 25 (n = 29)
qubiti sunt necesari 2 GB (32 GB) memorie.
Orice operatie aplicata unei stari cuantice poate fi reprezentata sub forma unei matrice. Operatia
efectuata este ın esenta multiplicarea acestei matrice cu vectorul de amplitudini ale starii cuantice.
Cand dimensiunea registrului cuantic creste, resursele necesare efectuarii operatiei de ınmultire
Capitolul V: Simularea calculelor cuantice 41
Figura V.2: Distributia celor 16 stari de baza ale unui registru cuantic pe 4 qubiti folosind 23 = 8
procesoare. Procesoarele reprezinta varfurile unui hipercub 3-dimensional.
matrice-vector cresc exponential facand imposibila executia pe un PC. O abordare naturala pentru
rezolvarea acestei probleme ar putea fi paralelizarea acestei operatii de ınmultire. Aceasta abor-
dare nu este ınsa potrivita pentru medii de simulare cu memorie distribuita datorita costurilor mari
de comunicatie ıntre noduri [Patz 03, Caraiman 09b]. Totusi, se pot utiliza doar operatori care
prezinta o structura mai simpla, astfel ıncat un pas de evolutie poate fi executat prin aplicarea
unui operator unitar de dimensiune 2 x 2 unui singur qubit (poarta cuantica pe un qubit) sau prin
aplicarea operatorului unitar controlat cum este poarta CNOT.
Pentru a furniza o executie paralela eficienta a simulatorului QC-lib se exploateaza forma spe-
cifica a procesului de calcul cuantic si se distribuie cele 2n stari de baza ale unui registru cuantic la
2p procesoare ın baza celor mai putin semnificativi p biti. De fapt, ın aceasta reprezentare, nodurile
de procesare si vectorii bazei sunt considerati coordonatele unui hipercub n-dimensional (Figura
V.2). Spre exemplu, ın cazul unui registru pe 3 qubiti, folosind 4 procesoare, P0...P3, distributia
starilor va arata astfel:P0 : |000〉, |100〉P1 : |001〉, |101〉P2 : |010〉, |110〉P3 : |011〉, |111〉
Fiecare nod de procesare aplica operatorii cuantici doar asupra termenilor locali si, daca este
necesar, comunica termenii generati nodurilor carora le apartin. O caracteristica importanta a
implementarii propuse o reprezinta faptul ca, pentru o stare cuantica, sunt stocati doar termenii cu
amplitudine diferita de zero, ceea ce diminueaza atat costurile de comunicatie ın etapele primare
ale executiei unor operatori (ex. transformata Hadamard) precum si spatiul necesar stocarii unei
stari cuantice.
In cazul operatorului general pe un qubit, comunicatia ıntre procesoare este necesara doar la
aplicarea operatorului unui qubit ce determina distributia datelor. Aplicand un operator general pe
un qubit U =
(
u11 u12
u21 u22
)
asupra unei stari cuantice |ψ〉 = α|0〉 + β|1〉 se obtine
U |ψ〉 = (αu11 + βu12)|0〉 + (αu21 + βu22)|1〉 (V.2)
Capitolul V: Simularea calculelor cuantice 42
Daca sunt utilizate 2 procesoare, atunci fiecare procesor detine amplitudinea unei stari a bazei.
Aplicand operatorul U local pe fiecare procesor, sunt creati termeni care nu apartin procesorului
respectiv, fiind astfel necesara comunicarea acestora:
P0 : α|0〉 U−→ u11α|0〉 + u21α|1〉P1 : β|1〉 U−→ u12β|0〉 + u22β|1〉
Comm−→ u11α|0〉 + u12β|0〉u21α|1〉 + u22β|1〉
Pentru fiecare termen din starea cuantica initiala sunt creati cel mult doi termeni dintre care
cel mult unul trebuie sa fie comunicat. Daca se lucreaza, spre exemplu, cu un registru cuantic pe
n-qubiti si 2p procesoare, comunicatia este necesara doar la aplicarea operatorului U asupra unui
qubit ce formeaza cheia de distributie. In cazul celorlalti qubiti toti termenii ce intervin ın calculul
amplitudinii starii rezultate sunt detinuti local de fiecare procesor. Mai mult, ın primul caz, toti
termenii detinuti remote apartin aceluiasi alt procesor deoarece un singur bit este inversat ın cheia
de distributie.
Implementarea paralela ın QC-lib a operatorului general pe un qubit, U, permite aplicarea
portilor NOT, Hadamard, shiftarea fazei amplitudinii, exponentiere.
Operatorul CNOT (controlled-NOT). In implementarea paralela a bibliotecii QC-lib, cand
qubitul de control este ın starea |0〉, starea qubitului tinta nu se modifica, deci nu se genereaza
termeni noi si nici nu se modifica amplitudinea termenilor existenti. Cand qubitul de control este
ın starea |1〉, starea qubitului tinta este inversata. In aceasta situatie se genereaza noi termeni
care trebuie comunicati altui procesor doar daca qubitul tinta face parte din cheia de distributie
[Caraiman 10b]. Spre exemplu, lucrand cu 4 procesoare si aplicand operatorul CNOT celui mai
putin semnificativ qubit dintr-un registru pe 3 qubiti aflat initial ın starea α|100〉+β|011〉, iar qubitul
de control este qubitul 2, se obtine:
P0 : α|100〉 CNOT−−−−→ α|101〉P1 : −P2 : −P3 : β|011〉 CNOT−−−−→ β|011〉
Comm−→
−α|101〉−
β|011〉
Cu operatorul CNOT, ın QC-lib poate fi construita poarta CNOT care actioneaza asupra a doua
registre: registrul de control si registrul tinta. Cei doi registri pot reprezenta substari ale starii
cuantice de baza (subregistre). In acest caz, poarta CNOT inverseaza starea (sub-)registrului tinta
daca (sub-)registrul de control se afla ın starea |1〉c, unde c este numarul de qubiti ai acestuia. Daca
se definesc un registru cuantic a pe 1 qubit aflat ın starea |0〉, un registru cuantic b pe doi qubiti aflat
ın starea α0|01〉 + β0|10〉 si un registru cuantic c pe 2 qubiti aflat ın starea α1|10〉 + β1|11〉, aplicand
poarta CNOT registrului b cu registrul de control c, starea ıntregii memorii cuantice distribuita pe
8 procesoare va fi:
P2 : |10010〉, |11010〉 CNOT−−−−→ |10010〉, |11100〉P4 : |10100〉, |11100〉 CNOT−−−−→ |10100〉, |11010〉
Comm−→ |10010〉, |11010〉|10100〉, |11100〉
Capitolul V: Simularea calculelor cuantice 43
Ca si ın cazul operatorului general pe un qubit, la aplicarea portii CNOT, fiecare procesor
comunica cu cel mult un alt procesor. Indexul procesorului cu care se face comunicatia este de-
terminat de acei qubiti ai (sub-)registrului tinta care fac parte si din qubitii ce determina cheia de
distributie a ıntregii memorii cuantice.
Operatorul de shiftare controlata a fazei, CPhase, este un alt exemplu de poarta cuantica
pe doi qubiti implementata ın QC-lib. Acesta primeste ca parametri un unghi de rotatie, θ, si
un qubit de control, actionand ın aceeasi maniera ca poarta CNOT. Amplitudinile starilor bazei
unde qubitul de control este |0〉 raman neschimbate, iar daca starea qubitului de control este |1〉,atunci amplitudinile starilor bazei sunt multiplicate cu eiθ. Reprezentarea matriceala a operatorului
CPhase este:
CPhase =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 eiθ
(V.3)
Si operatorul CPhase poate actiona asupra unor (sub-)registre ale memoriei cuantice, imple-
mentarea paralela a acestuia fiind asemanatoare cu cea a operatorului CNOT. Diferenta dintre cele
doua implementari provine din faptul ca la aplicarea operatorului CPhase nu apare necesitatea
comunicarii ıntre procesoare, prin actiunea acestui operator nefiind generati termeni noi, ci doar
modificate amplitudinile termenilor locali [Caraiman 10b].
Masurarea starilor cuantice. In QC-lib, pasul de masurare a starii unui registru pe n qubiti
este simulat ın O(2n) timp. Fie |ψ〉 = ∑2n−1j=0 α j| j〉 starea unui registru pe n qubiti. Operatia de
masurare este simulata astfel:
• Se genereaza ın mod aleator un numar p, 0 ≤ p < 1,
• Se genereaza ın mod aleator un numar ıntreg pozitiv x, mai mic decat numarul de termeni cu
amplitudine diferita de zero,
• Se determina un ıntreg i, 0 ≤ i < 2n − 1, a.ı.∑i−1
j=x |α j|2 ≤ p <∑i
j=x |α j|2.
Intregul i este reprezentarea starii masurate. Dupa masurare, starea registrului devine |i〉.Deaorece termenii starii registrului cuantic sunt distribuiti ıntre procesoare, operatia de masurare
presupune comunicatie ıntre acestea atat pentru selectarea termenului i, cat si pentru colapsarea
registrului cuantic ın starea |i〉 [Caraiman 10b]. Astfel, un proces master este responsabil cu
generarea aleatoare a numerelor p si i si realizarea sumei. Sincronizarea ıntre procesoare se re-
alizeaza folosind operatii de tip MPI Bcast astfel ıncat procesorul master sa poata primi norma
amplitudinii unui termen j de la procesorul ce ıl detine. In finalul operatiei de selectare a termenu-
lui i, toate procesoarele cunosc acest numar si se poate trece starea registrului cuantic ın |i〉.
Rezultate experimentale
O aplicatie client poate invoca operatiile serviciului GQCL si poate specifica parametrii din
linia de comanda pentru QCL, numarul de procesoare necesare simularii si fisierele de redirectare a
Capitolul V: Simularea calculelor cuantice 44
intrarii standard, iesirii standard si de eroare. Testarea serviciului GQCL a fost realizata folosind un
nod al Grid-ului GRAI [Amarandei 08] compus dintr-un server frontend IBM3800 cu 4x XEON
HT 3.66GHz, 64 bit, 2MB Cache L2, 8 GB RAM, 2x 1Gbit Ethernet Controller si un cluster de 12
statii Dell Optiplex 755 fiecare fiind dotate cu procesor Intel Core 2 Duo E6550 2.33GHz / 4MB
L2, 2 GB RAM, Gigabit ethernet.
Aplicatia paralela este SPMD (Single Program Multiple Data), fiecare proces ruland o copie a
aceluiasi cod, cu exceptia procesului master care este responsabil si cu administrarea interactiunii
cu utilizatorul.
Un studiu de caz pentru analiza performantelor serviciului GQCL foloseste transformata
Hadamard. Executia acestui operator permite analiza situatiei ın care pentru un registru cuan-
tic se genereaza toate starile bazei ın acelasi timp. In masuratorile efectuate s-au ınregistrat
pentru accelerare valori de pana la 17.7 pentru 29 de qubiti pe 16 procesoare si s-a observat o
crestere liniara a accelerarii cu numarul de procesoare chiar si pentru probleme de dimensiuni mici
[Caraiman 09a]. Efectul este notabil ın special ın etapele primare ale procesului de calcul unde
are loc ıntreaga comunicatie. De asemenea, s-a observat ca scalarea implementarii paralele este
asemanatoare cu cea a versiunii secventiale, pentru care timpul de rulare creste cu un factor de
aproximativ 2 la fiecare extra qubit (fiecare extra qubit reprezinta o dublare a dimensiunii proble-
mei).
Pentru analiza accelerarii si eficientei implementarii paralele a bibliotecii QC-lib, ın imple-
mentarea QCL a problemei Bernstein-Vazirani s-a fortat generarea aceluiasi numar a pentru
toate instantele analizate. Aceasta abordare este necesara deoarece actiunea operatorului U f este
simulata prin porti CNOT iar numarul de aplicari ale acestei porti depinde de numarul de biti de 1
din reprezentarea binara a numarului a. S-a dorit analiza timpilor de executie variind dimensiunea
problemei (numarul de qubiti din registrul de intrare) si numarul de procesoare, pastrand constant
numarul de aplicari ale operatorului CNOT. Spre deosebire de transformata Hadamard, factorul
de crestere al accelerarii scade odata cu cresterea numarului de procesoare, acest fapt fiind datorat
gradului mai mic de paralelism, introdus ın problema Bernstein-Vazirani de secventa de simulare
a actiunii operatorului U f prin intermediul portilor CNOT [Arustei 08c].
Algoritmul de cautare al lui Grover a fost de asemenea simulat folosind QC-lib, timpul de ru-
lare fiind masurat pentru o portiune din algoritm pana ın punctul ın care se realizeaza prima operatie
de masurare. Acest fapt permite compararea elocventa a timpilor de rulare, deoarece, ın versiunea
completa a algoritmului, exista o probabilitate finita ca operatia de cautare sa nu se ıncheie cu
succes, astfel ıncat ea trebuie repetata. In acest caz timpul de rulare este non-deterministic. Com-
portamentul algoritmului este similar cu cel al transformatei Hadamard, doar ca ın acest caz panta
de crestere a timpului de rulare ın cazul secvential corespunde unui factor mediu de 2.8 pentru
fiecare qubit aditional. Aceasta se datoreaza faptului ca numarul de iteratii din bucla principala a
algoritmului creste cu un factor de√
2 pentru fiecare extra qubit, si, ımpreuna cu dublarea dimen-
siunii problemei, implica o crestere a timpului de rulare cu factorul 2.82. Pentru doar 18 qubiti s-a
obtinut o accelerare de 7.4, iar masuratorile indica un trend crescator al accelerarii atat odata cu
cresterea dimensiunii problemei dar si cu numarul de procesoare utilizate [Caraiman 10b].
Capitolul V: Simularea calculelor cuantice 45
Concluzii
Calculatoarele secventiale clasice impun limitari drastice asupra procesului de simulare a cal-
culelor cuantice. Simulatoarele cuantice reprezinta o alternativa atractiva pentru experimentarea
algoritmilor cuantici, dar scopul lor nu poate fi atins fara utilizarea unor resurse semnificative de
calcul. O abordare promitatoare o reprezinta executarea acestor simulari ın sisteme Grid care pot
furniza accesul la resurse de calcul de mare performanta. In acest context s-a constatat necesitatea
dezvoltarii de servicii si aplicatii Grid care sa furnizeze aceasta functionalitate aplicatiilor client.
Un astfel de serviciu este prezentat ın [Caraiman 09a]. Serviciul Grid pentru simularea calculelor
cuantice este bazat pe simulatorul QCL pentru care s-au realizat implementari paralele ale oper-
atorului general pe un qubit, ale portilor controlate si a operatiei de masurare a starilor cuantice.
Rezultatele experimentale obtinute la simularea unor algoritmi cuantici pentru care s-au furnizat
implementari ın limbaj de programare cuantica (problema Bernstein-Vazirani [Arustei 08c] si al-
goritmi pentru probleme de procesare grafica [Caraiman 10a]) indica performante foarte bune
ale implementarii paralele din punctul de vedere al timpului de rulare, al accelerarii si eficientei
acesteia [Caraiman 09a, Caraiman 10b].
Capitolul VI
Concluzii finale, contributii si directii
viitoare de cercetare
VI.1 Concluzii
Procesarea grafica a informatiilor reprezinta o necesitate importanta pentru ıntelegerea aces-
tora, iar multitudinea de domenii de aplicabilitate recomanda subiectul de cercetare ca fiind unul
de actualitate. Mai mult, abordarea calculului de mare performanta pentru dezvoltarea si imple-
mentarea de tehnici de procesare grafica reprezinta o directie de cercetare noua, care prezinta un
potential imens ın formularea de solutii pentru probleme actuale de procesare grafica. O astfel de
problema o reprezinta necesitatea procesarii si vizualizarii seturilor de date de mari dimensiuni, iar
rezolvarea ei presupune dezvoltarea de noi tehnici de procesare care sa utilizeze calculul de mare
performanta. De-a lungul timpului, toate formularile destinate sa caracterizeze ”calculul de mare
performanta” au provenit din natura revolutionara a sistemelor construite la momentul respectiv.
Indiferent de modalitatea de caracterizare a sistemelor de calcul de mare performanta, orizonturile
oferite de tehnologiile de integrare a semiconductorilor au determinat investigarea de noi solutii
pentru cresterea puterii de calcul. Astfel, la nivel mondial, o atentie deosebita, atat din punctul de
vedere al eforturilor de cercetare cat si financiare, este concentrata ın prezent asupra dezvoltarii
sistemelor Grid si a calculatoarelor cuantice. In acest context, se impune cercetarea modalitatilor
ın care domeniul procesarii grafice poate beneficia de solutii care sa exploateze imensul potential
de calcul al acestor doua tipuri de sisteme. Astfel, ın aceasta lucrare, problema procesarii grafice
a seturilor de date de mari dimensiuni a fost analizata, atat ın contextul calculului Grid cat si al
calculului cuantic, utilizand doua directii principale de abordare: simplificarea modelelor expri-
mate de aceste seturi de date pentru reducerea dimensiunilor acestora si obtinerea de vizualizari
interactive, iar pe de alta parte, introducerea paralelismului ın procesul de randare.
Calculul heterogen, ce poate fi implementat prin intermediul sistemelor Grid, prezinta un
potential imens pentru accelerarea aplicatiilor, odata cu depasirea multor bariere ce limiteaza arhi-
tecturile conventionale. Cercetarile ın domeniul calculului Grid au luat amploare atat la nivel
mondial, european dar si national, dezvoltarea proiectelor Grid antrenand atat centrele de cercetare
46
Capitolul VI: Concluzii finale, contributii si directii viitoare de cercetare 47
si universitati de prestigiu, dar si reprezentanti de marca ai industriei. Cu toate acestea, sistemele
Grid nu si-au atins ınca potentialul promis, iar principalul motiv ıl reprezinta complexitatea con-
ceptelor implicate. Nu numai ca solutiile pentru dezvoltarea de sisteme de vizualizare integrate
ın sisteme Grid trebuie sa exploateze tehnici de calculul paralel si distribuit, dar proiectarea si
implementarea acestora trebuie sa tina cont de toate cerintele formulate pentru aceste sisteme,
cerinte legate de securitate si autentificare, de monitorizarea, descoperirea, planificarea si alocarea
resurselor, transferul datelor, precum si virtualizarea resurselor heterogene. Aceste considerente au
implicatii determinante ın dezvoltarea de aplicatii si servicii Grid, care reprezinta o sarcina dificila,
chiar ın conditiile existentei unor standarde Grid bine definite si a unui sistem software stratificat
a carui functionalitate adreseaza aceste cerinte, cum este Globus Toolkit 4. Cu toate acestea, ın
aceasta lucrare, s-a aratat cum complexitatea dezvoltarii si/sau utilizarii de aplicatii si servicii Grid
poate fi ascunsa, utilizatorului sau programatorului fiindu-le pusa la dispozitie o modalitate simpla
si eficienta de interactiune cu sistemul Grid. O astfel de solutie este propusa ın aceasta lucrare ın
capitolul al II-lea, fiind furnizata sub forma unui serviciu Grid generic, prin configurarea caruia
s-a aratat ca se pot obtine functionalitati noi, precum un serviciu de vizualizare ce foloseste ran-
darea paralela ın spatiul obiect ca cel descris ın capitolul al III-lea. Aceasta solutie are ca avantaje
abstractizarea detaliilor middleware-ului Grid fata de utilizator/programator, permite o configurare
facila prin specificarea unor module de executie personalizate, este conforma cu viziunea impusa
de ultimele standarde specifice sistemelor Grid, si, poate cel mai important, permite exploatarea
resurselor Grid slab cuplate. In cazul aplicatiilor ce trebuie sa exploateze resurse strans cuplate,
cum sunt spre exemplu aplicatiile MPI, acestea pot fi integrate ca servicii Grid prin utilizarea unei
componente de nivel ınalt cum este cea propusa ın capitolul al V-lea.
In ceea ce priveste tehnicile de simplificare a seturilor de date de mari dimensiuni, desi lite-
ratura de specialitate descrie diverse metode ce pot fi utilizate, acestea nu ofera o solutie completa
care sa adreseze concomitent toate cele trei aspecte problematice asociate: reducerea consumului
de memorie, reducerea timpului de procesare si pastrarea calitatii modelelor obtinute. O solutie
eficienta la aceasta problema este propusa ın capitolul al III-lea, ea adresand cazul norilor de
puncte achizitionati folosind scanarea laser 3D, seturi de date de mari dimensiuni care prezinta
o raspandire din ce ın ce mai larga ıntr-o multitudine de domenii de la medicina, arta si cultura, si
pana la procesarea materialelor, productie si inginerie inversa. Solutia propusa presupune obtinerea
unei reprezentari hibride a norului de puncte, formata din structuri planare texturate si puncte din
setul initial. Aceasta metoda permite o reducere a spatiului ocupat de modelul obtinut cu un factor
de aproximativ 100 si o crestere de aproximativ 35 de ori a performantelor de randare. Problemele
legate de consumul mare de memorie si de timpul mare de procesare caracteristice fazei de iden-
tificare a structurilor planare ın norul de puncte ce utilizeaza algoritmul RANSAC sunt rezolvate
prin formularea unui algoritm paralel pentru aceasta schema de votare.
O alta directie de cercetare abordata ın aceasta lucrare o reprezinta definirea conceptului de
procesare grafica ın sisteme cuantice. Desi aceste sisteme se afla ıntr-un stadiu incipient de dez-
voltare, potentialul lor a fost demonstrat atat la nivel teoretic cat si practic, prin multitudinea
de solutii ce s-au dovedit utile ın implementarea fizica a acestor sisteme de calcul. Interferenta
starilor cuantice si paralelismul inerent al calculului cuantic sunt proprietati remarcabile care au
permis formularea de solutii optime pentru doua probleme fundamentale: problema factorizarii
Capitolul VI: Concluzii finale, contributii si directii viitoare de cercetare 48
unui numar ıntreg (algoritmul Shor) si problema cautarii ıntr-o baza de date nestructurata (algo-
ritmul Grover). Aceste rezultate au determinat investigarea aplicatiilor inovatoare ın care pot fi
utilizate, a problemelor pentru care, ıntr-o maniera asemanatoare, pot fi formulate solutii net su-
perioare cazului clasic, dar si a problemelor pentru care ın cazul clasic nici nu au fost ınchipuite
ınca solutii. In acest context, domeniul procesarii grafice se afla ıntr-un stadiu incipient de dez-
voltare, pentru care se impune, ın primul rand, formularea solutiilor problemelor fundamentale,
precum problema randarii sau probleme de geometrie computationala. Pentru ca aceste solutii sa
fie eficiente ın raport cu abordarile ce folosesc calculul clasic, si sa prezinte o accelerare semni-
ficativa care sa justifice eforturile de implementare a lor utilizand hardware-ul cuantic, s-a dovedit
utila exprimarea problemelor corespunzatoare sub forma de subprobleme de cautare si factorizare,
pentru care algoritmii cuantici sunt optimali. Astfel, ın capitolul al IV-lea, aspecte fundamentale
ale randarii precum algoritmul Z-Buffering, calculul iluminarii sau managementul nivelurilor de
detaliu sunt reformulate ın termeni de cautare, obtinandu-se solutii cuantice eficiente. Mai mult, se
arata cum formalismul cuantic poate fi utilizat pentru analizarea schemei de votare RANSAC, un
algoritm care, pe langa simplificarea norilor de puncte ca ın capitolul al III-lea, prezinta multe alte
aplicatii importante ın domeniul vederii artificiale, al modelarii pe baza de imagini si al detectiei
formelor. Algoritmul cuantic propus, QRANSAC, prezinta performante net superioare variantei
clasice, iar pentru utilizarea lui ın identificarea structurilor planare ın nori de puncte este descris
circuitul cuantic care implementeaza etapa specifica de calculare ın paralel a consensului asupra
tuturor structurilor candidate.
Ca si ın cazul clasic, formularea si validarea unei solutii algoritmice ce foloseste calcul cuantic
presupune mai multe etape: analiza si descrierea problemei utilizand un formalism specific (ex.
formalismul portilor cuantice), implementarea ıntr-un limbaj de programare (ex. QCL - Quan-
tum Computation Language) si testarea algoritmului. Aceste etape au fost urmarite ın dezvoltarea
solutiilor pentru problemele de procesare grafica mentionate. In contextul indisponibilitatii la scara
larga a hardware-ului cuantic, ultima etapa, cea de testare, nu poate fi realizata decat prin simularea
calculelor cuantice folosind sisteme conventionale de calcul. Desi exista o varietate de astfel de
medii de simulare, resursele clasice (memorie, putere de procesare) necesare impun limitari dras-
tice asupra problemelor ce pot fi simulate. Pentru a depasi acest inconvenient, ın capitolul al V-lea
este propusa o metoda de exploatare a calculului paralel si distribuit pentru simularea cuantica si
expunerea acestei functionalitati ın sisteme Grid sub forma unui serviciu de simulare, GQCL.
Se poate concluziona ca sistemele Grid pot oferi solutii complexe, cuprinzatoare, pentru prob-
lema procesarii grafice a seturilor de date de mari dimensiuni, iar aceste solutii trebuie sa ex-
ploateze nu numai tehnicile existente de procesare bazate pe calcul paralel si distribuit, cat si noi
tehnici precum cele descrise ın aceasta lucrare. Nu se poate spune ınsa ca domeniul procesarii
grafice ın sisteme Grid a ajuns la maturitate, fiind necesara cercetarea continua si sustinuta ın ceea
ce priveste atat dezvoltarea de noi tehnici care sa adreseze problemele de actualitate cat si de solutii
pentru integrarea acestora sub forma unei noi paradigme care a aparut foarte recent sub numele de
”supercalcul vizual”.
Mai mult, sistemele Grid s-au dovedit a fi si cea mai buna solutie ce poate fi exploatata pentru
facilitarea simularii cuantice, atat din prisma resurselor performante de calcul oferite cat si a fa-
cilitarii accesului comunitatii stiintifice la astfel de functionalitati prin implementarea conceptului
Capitolul VI: Concluzii finale, contributii si directii viitoare de cercetare 49
de colaborare prin intermediul Organizatiilor Virtuale. Cu astfel de facilitati este posibila investi-
garea de noi solutii cuantice pentru probleme precum cele de procesare grafica. Din perspectiva
celor prezentate ın capitolele IV si V se poate concluziona ca sistemele cuantice pot accelera sem-
nificativ procesele grafice, iar rezultatele obtinute pentru algoritmi fundamentali ıncurajeaza cer-
cetarea si a altor probleme ce pot beneficia de caracteristicile acestor sisteme, conturandu-se astfel
un nou domeniu, cel al procesarii grafice ın sisteme cuantice.
VI.2 Contributii
Sintetizand, contributiile aduse ın cadrul acestei lucrari s-au conturat de-a lungul urmatoarelor
directii de cercetare:
1. Furnizarea de solutii bazate pe calcul paralel si distribuit pentru probleme de procesare
grafica
• reprezentarea hibrida a norilor de puncte sub forma de structuri planare texturate si
puncte corespunzatoare detaliilor fine pentru obtinerea unui model simplificat [Arustei 06];
• algoritmul RANSAC paralel pentru identificarea structurilor planare ın nori de puncte
(PRANSAC) [Arustei 07].
2. Dezvoltarea de servicii Grid pentru probleme de procesare grafica
• platforma generica pentru integrarea dinamica de servicii Grid [Arustei 08b];
• vizualizarea seturilor de date de mari dimensiuni ın sisteme Grid - serviciu Grid de
vizualizare folosind randarea paralelaa ın spatiul obiect [Arustei 08a].
3. Dezvoltarea de solutii algoritmice pentru probleme de procesare grafica ın sisteme
cuantice
• formularea de algoritmi cuantici pentru probleme fundamentale de randare: algorit-
mul Z-Buffering, metode de iluminare globala (Ray Tracing, calculul radiantei, metoda
hartilor de fotoni), managementul nivelurilor de detaliu;
• definirea algoritmului cuantic QRANSAC, corespondentul schemei de votare RANSAC
clasice [Caraiman 09c];
• definirea variantei cuantice a algoritmului QRANSAC pentru procesarea norilor de
puncte proveniti de la scanere 3D [Caraiman 09d].
4. Implementarea algoritmilor cuantici ın limbaje de programare cuantica si simularea
calculului cuantic ın sisteme Grid
• analiza unor probleme cuantice (problema Bernstein-Vazirani, algoritmul Grover, algo-
ritmul de numarare aproximativa a solutiilor unei probleme de cautare, algoritmul de
Capitolul VI: Concluzii finale, contributii si directii viitoare de cercetare 50
determinare a valorii maxime ıntr-un set de date) utilizand formalismul portilor cuan-
tice si implementarea acestora ıntr-un limbaj de programare cuantica, QCL [Arustei 08c,
Caraiman 10a];
• dezvoltarea unei implementari paralele a simulatorului cuantic QC-lib, furnizand versi-
uni paralelizate ale operatorului general pe un qubit, ale portilor controlate si a operatiei
de masurare a starii cuantice [Caraiman 09a, Caraiman 09b, Caraiman 10b];
• dezvoltarea unui serviciu Grid, GQCL, pentru expunerea ın sisteme Grid a functionali-
tatii simulatorului paralel [Caraiman 09a, Caraiman 09b, Archip 08b].
De asemenea, trebuie mentionat faptul ca cercetarile ce au condus la scrierea acestei teze au
fost efectuate, ın mare parte, ın contextul a trei contracte de cercetare:
• Grid academic pentru aplicatii complexe (GRAI), contract 74 CEEX-II03/31.07.2006,
Parteneri: UT Iasi (coordonator), UAIC Iasi, USAMV Iasi, IIT Iasi, Director proiect: prof.
dr. Mitica Craus, Perioada: 2006 - 2008
• Modele de calcul cuantic. Implementari ale unor algoritmi cuantici ın QCL, Grant tip
A CNCSIS, cod 253/2006, Director proiect: prof. dr. ing. Vasile Ion Manta, Perioada: 2006
- 2007
• Modele clasice si cuantice, Contract tip ID CNCSIS, cod 620/2007, Director proiect: prof.
dr. Gheorghe Zet, Perioada: 2007 - 2010
VI.3 Directii viitoare de cercetare
Furnizarea unei solutii complete pentru supercalculul vizual impune ın mod clar necesitatea re-
zolvarii unei colectii de probleme infrastructurale legate de administrarea sarcinilor de vizualizare
ın interiorul unei platforme comune. Cerintele aplicatiilor precum cele de data mining vizual, con-
ducerea proceselor de calcul, vizualizarea proceselor de tip misiune critica sau vizualizarea mo-
bila, indica o prioritate mare a cercetarii ın domeniul infrastructurii supercalculului vizual. Chiar
daca o astfel de infrastructura poate beneficia de cele mai avansate tehnologii pentru vizualizare,
apar multe alte noi provocari legate de realizarea unei infrastructuri bine proiectata, ce poate fi
ıntretinuta si care sa fie eficienta din punctul de vedere al costurilor.
Construirea unei infrastructuri pentru supercalculul vizual poate fi considerata o provocare im-
portanta ın domeniul vizualizarii, aceasta ridicand o serie de probleme legate de proiectarea arhi-
tecturii, de tehnologia utilizata sau de calitatea serviciilor. Astfel, se pune problema daca utilizarea
infrastructurii sistemelor Grid este dezirabila sau fezabila pentru construirea unei infrastructuri
pentru supercalculul vizual, modalitatea ın care aceasta infrastructura poate fi adaptata la diferitele
cerinte de servicii centralizate, distribuite sau independente ce provin de la diferite aplicatii si
cum ar putea o astfel de infrastructura sa ofere suport generic pentru diferite aplicatii precum
vizualizarea de seturi de date de foarte mari dimensiuni sau a proceselor de tip misiune critica.
Este, de asemenea, important de stabilit daca nucleul central al unui mediu pentru supercalcul
Capitolul VI: Concluzii finale, contributii si directii viitoare de cercetare 51
vizual ar trebui sau nu sa ıl formeze dispozitivele hardware grafice si care ar fi relatia dintre astfel
de dispozitive centrale si cele disponibile calculatoarelor personale. In acest context trebuie evaluat
si impactul diferitelor caracteristici ale acestor dispozitive asupra algoritmilor de vizualizare. In
ceea ce priveste calitatea serviciilor de vizualizare, trebuie stabilit rolul infrastructurii ın admini-
strarea interactiunii, a datelor si a cunostintelor despre experientele utilizatorilor, precum si modul
ın care utilizatorii ar putea beneficia, eventual, de o infrastructura bazata pe cunostinte.
O strategie inovatoare pentru dezvoltarea de infrastructuri complexe de calcul ar putea fi repre-
zentata de calculul autonom, ce se inspira din sistemele biologice auto-adaptabile precum si din
sistemele sociale si economice auto-guvernate. Adaptand un astfel de model de dezvoltare, se
poate ınchipui un model similar de dezvoltare, stratificat, pentru rezolvarea evolutiei graduale a
mediilor complexe pentru supercalculul vizual. Un astfel de model ar trebui sa fie bazat pe o plat-
forma integrata care sa furnizeze aplicatiilor de vizualizare resursele de calcul si de comunicatie
necesare, iar utilizatorii sa fie complet deconectati de identificarea instrumentelor potrivite, lo-
calizarea resurselor de calcul si de administrarea distributiei datelor. De altfel, dupa cum s-a aratat
si ın aceasta lucrare, de multe ori ın prezent, este necesar ca utilizatorii ınsisi sa strabata prin ob-
stacole tehnice complicate, precum retelisticaa, securitate, paralelizare, replicarea datelor s.a.m.d.
Tot realista este si provocarea de a dezvolta sisteme de calcul cuantic, iar acest lucru reiese ın
mod evident din rezultatele produse recent de cercetarile ın domeniu. Dupa cum s-a demonstrat ın
aceasta lucrare, proprietatile sistemelor cuantice pot fi exploatate ın mod eficient pentru definirea
unui calcul de mare performanta care sa utilizeze aceste sisteme. Si, indiferent de tipul de sis-
teme sau de modelul de calcul utilizat, vizualizarea si ın general procesarea grafica a informatiilor
reprezinta o componenta indispensabila. Dupa cum s-a aratat, chiar la o analiza preliminara, dome-
niul procesarii grafice poate beneficia semnificativ de puterea de calcul a sistemelor cuantice. Dar
pentru definirea complexa a acestui domeniu se impune cercetarea modului ın care pot fi exprimate
solutii cuantice eficiente pentru o multitudine de alti algoritmi si metode specifice. S-au obtinut
deja rezultate promitatoare si pentru potrivirea sabloanelor utilizand transformata Fourier cuantica,
stocarea unei imagini utilizand un sistem cuantic sau dezvoltarea de sarcini de procesare a imaginii.
Bibliografie selectiva
[Amarandei 06] C.M. Amarandei, A. Archip & S. (Caraiman) Arustei. Performance Study
for MySQL Database Access within Parallel Applications. Buletinul Insti-
tutului Politehnic din Iasi, Automatic Control and Computer Science Sec-
tion, vol. LII(LVI), no. 1-4, pages 127–134, 2006.
[Amarandei 08] C.M. Amarandei, A. Rusan, A. Archip & S. (Caraiman) Arustei. On the
Development of a GRID Infrastructure. In H.N. Teodorescu & M. Craus,
editeurs, Scientific and Educational Grid Applications, pages 13–23, Iasi,
Romania, 2008. Politehnium.
[Archip 08a] A. Archip, S. (Caraiman) Arustei, C.M. Amarandei & A. Rusan. On the
design of Higher Order Components to integrate MPI applications in Grid
Services. In H.N. Teodorescu & M. Craus, editeurs, Scientific and Educa-
tional Grid Applications, pages 25–35, Iasi, Romania, 2008. Politehnium.
[Archip 08b] A. Archip, M. Craus & S. (Caraiman) Arustei. Efficient grid service de-
sign to integrate parallel applications. In Marten van Sinderen, editeur,
Proceedings of 2nd International Workshop on Architectures, Concepts
and Technologies for Service Oriented Computing held in conjunction with
3rd International Conference on Software and Data Technologies, 5-8 JUL,
2008 Porto PORTUGAL, pages 7–16, Setubal, Portugal, 2008. INSTICC
Press.
[Arustei 06] S. (Caraiman) Arustei. Procesarea norilor de puncte proveniti de la
scanere 3d. Master’s thesis, Technical University of Vienna, Institute for
Computer Graphics and Algorithms - Universitatea Tehnica Iasi, Facultatea
de Automatica si Calculatoare, Septembrie 2006.
[Arustei 07] S. (Caraiman) Arustei, A. Archip & C.M. Amarandei. Parallel RANSAC
for Plane Detection in Point Clouds. Buletinul Institutului Politehnic din
Iasi, Automatic Control and Computer Science Section, vol. LIII(LVII),
no. 1-4, pages 139–150, 2007.
[Arustei 08a] S. (Caraiman) Arustei, A. Archip & C.M. Amarandei. Grid Based Vi-
sualization Using Sort-Last Parallel Rendering. In H.N. Teodorescu &
52
Bibliografie selectiva 53
M. Craus, editeurs, Scientific and Educational Grid Applications, pages
101–109, Iasi, Romania, 2008. Politehnium.
[Arustei 08b] S. (Caraiman) Arustei, M. Craus & A. Archip. Towards a generic frame-
work for deploying applications as grid services. In Marten van Sinderen,
editeur, Proceedings of 2nd International Workshop on Architectures, Con-
cepts and Technologies for Service Oriented Computing held in conjunc-
tion with 3rd International Conference on Software and Data Technologies,
5-8 JUL, 2008 Porto PORTUGAL, pages 17–26, Setubal, Portugal, 2008.
INSTICC Press.
[Arustei 08c] S. (Caraiman) Arustei & V. Manta. QCL Implementation of the
Bernstein-Vazirani Algorithm. Buletinul Institutului Politehnic din Iasi,
Automatic Control and Computer Science Section, vol. LIV(LVIII), no. 1,
pages 35–44, 2008.
[Baehne 35] G.W. Baehne. Practical applications of the punched card method in col-
leges and universities. Columbia University Press, New York, 1935.
[Bashe 85] C.J. Bashe, L.R. Johnson, E.W. Pugh & J.H. Palmer. Ibm’s early comput-
ers. MIT Press, Cambridge, MA, USA, 1985.
[Beach 03] G. Beach, C. Lomont & C. Cohen. Quantum image processing (QuIP).
In Proceedings of 32nd Applied Imagery Pattern Recognition Workshop,
2003, pages 39 – 44, Los Alamitos, CA, USA, 2003. IEEE Computer So-
ciety.
[Bell 02] G. Bell & J. Gray. What’s next in high-performance computing? Commun.
ACM, vol. 45, no. 2, pages 91–95, 2002.
[Bolles 81] M.A. Fischler.and R.C. Bolles. Random sample consensus: a paradigm
for model fitting with applications to image analysis and automated car-
tography. Commun. ACM, vol. 24, no. 6, pages 381–395, 1981.
[Boyer 96] M. Boyer, G. Brassard, P. Hoyer & A. Tapp. Tight bounds on quantum
searching. In Proceedings of Fourth Workshop on Physics and Computa-
tion, 1996.
[Brassard 00] G. Brassard, P. Hoyer, M. Mosca & A. Tapp. Quantum amplitude amplifi-
cation and estimation, 2000. quant-ph/0005055.
[Caraiman 09a] S. (Arustei) Caraiman, A. Archip & V. Manta. A Grid Enabled Quantum
Computer Simulator. In Proceedings of the 11th International Symposium
on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC
2009). IEEE Computer Society, 2009.
Bibliografie selectiva 54
[Caraiman 09b] S. (Arustei) Caraiman & V. Manta. Grid Enabling QC-lib Quantum Com-
puter Simulator Library. In Proceedings of the 17th International Confer-
ence on Control Systems and Computer Science, pages 531–538, 2009.
[Caraiman 09c] S. (Arustei) Caraiman & V. Manta. New applications of quantum algo-
rithms to computer graphics: the quantum random sample consensus algo-
rithm. In CF ’09: Proceedings of the 6th ACM conference on Computing
frontiers, pages 81–88, New York, NY, USA, 2009. ACM.
[Caraiman 09d] S. (Arustei) Caraiman & V. Manta. A Quantum Random Sample Con-
sensus Algorithm for Point Cloud Simplification. In B.H.V. Topping &
P. Ivanyi, editeurs, Proceedings of the First International Conference on
Parallel, Distributed and Grid Computing for Engineering, Stirlingshire,
UK, 2009. Civil-Comp Press.
[Caraiman 10a] S. (Arustei) Caraiman. QCL Implementation of Quantum Search Algo-
rithms. accepted in Buletinul Institutului Politehnic din Iasi, Automatic
Control and Computer Science Section, vol. LVI(LX), no. 1, 2010.
[Caraiman 10b] S. (Arustei) Caraiman & V. Manta. Paralel Simulation of Quantum
Search. In Submitted at International Conference on Computers, Com-
munications and Control (ICCCC), Oradea, Romania, May 12-16, 2010.
[Catmull 75] E. Catmull. Computer Display of Curved Surfaces. In Proceedings of the
IEEE Conference on Computer Graphics, Pattern Recognition and Data
Structures, pages 11–17, 1975.
[Cedilnik 06] A. Cedilnik, B. Geveci, K. Moreland, J. Ahrens & J. Favre. Remote Large
Data Visualization in the ParaView Framework. In A. Heirich & B. Raffi-
nand L.P. Santos, editeurs, Eurographics Symposium on Parallel Graphics
and Visualization, pages 162–170, 2006.
[Cohen 93] M.F. Cohen & J.R. Wallace. Radiosity and realistic image synthesis. Aca-
demic Press Professional, San Diego, CA, USA, 1993.
[Curtis 04] D. Curtis & D.A. Meyer. Towards quantum template matching. In R.E.
Meyers & Y. Shih, editeurs, Proceedings of the SPIE, pages 134–141. SPIE
Press, 2004.
[Duncan 90] R. Duncan. A Survey of Parallel Computer Architectures. Computer,
vol. 23, no. 2, pages 5–16, 1990.
[Durr 99] C. Durr & P. Hoyer. A quantum algorithm for finding the minimum, 1999.
quant-ph/9607014.
Bibliografie selectiva 55
[Dutre 06] P. Dutre, K. Bala, P. Bekaert & P. Shirley. Advanced global illumination.
AK Peters Ltd, 2006.
[Fewings 07] A.J. Fewings & N. W. John. Distributed Graphics Pipelines on the Grid.
IEEE Distributed Systems Online, vol. 8, no. 1, 2007. art. no. 0701-o1001.
[Flynn 72] M. J. Flynn. Some Computer Organizations and Their Effectiveness. IEEE
Transactions on Computers, vol. 21, no. 9, pages 948–960, 1972.
[Foley 96] J. D. Foley, A. Van Dam, S.K. Feiner & J.F. Hughes. Computer graphics:
Principles and practice. Addison Wesley, 1996.
[Foster 01] I. Foster, C. Kesselman & S. Tuecke. The Anatomy of the Grid: Enabling
Scalable Virtual Organizations. Int. J. High Perform. Comput. Appl.,
vol. 15, no. 3, pages 200–222, 2001.
[Glassner 89] A.S. Glassner, editeur. An introduction to ray tracing. Academic Press
Ltd., London, UK, 1989.
[Grover 96] L.K. Grover. A fast quantum mechanical algorithm for database search.
In Proceedings of 28th ACM Annual STOC, pages 212–219, 1996.
[Hartley 04] R. I. Hartley & A. Zisserman. Multiple view geometry in computer vision.
Cambridge University Press, ISBN: 0521540518, second edition, 2004.
[Jensen 01] H. Jensen. Realistic image synthesis using photon mapping. A. K. Peters,
Ltd., Natick, MA, USA, 2001.
[Johnson 88] E.E. Johnson. Completing an MIMD multiprocessor taxonomy. SIGARCH
Comput. Archit. News, vol. 16, no. 3, pages 44–47, 1988.
[Kunz 04] R. Kunz. Modern High Performance Computing Platforms.
www.ics.psu.edu/fallnotes/Kunz Lecture 1.pdf, 2004.
[Lanzagorta 05a] M. Lanzagorta & J.Uhlmann. Hybrid quantum computing: semicloning
for general database retrieval. In Proceedings of the Quantum Informa-
tion and Quantum Computation Conference, SPIE Defense and Security
Symposium, volume 5815, pages 78–86, 2005.
[Lanzagorta 05b] M. Lanzagorta & J.K. Uhlmann. Hybrid quantum-classical computing with
applications to computer graphics. In SIGGRAPH ’05: ACM SIGGRAPH
2005 Courses, page 2, New York, NY, USA, 2005. ACM.
[mic 04] Microsoft Solution Guide for Migrating High Performance Computing
(HPC) Applications from UNIX to Windows. Technet, Microsoft, 2004.
Bibliografie selectiva 56
[Moad 05] C. Moad & B. Plale. Portal access to parallel visualization of sci-
entific data on the Grid. Rapport technique TR593, Computer Sci-
ence Department, Indiana University, Bloomington, IN, USA, 2005.
http://www.cs.indiana.edu/pub/techreports/TR593.pdf/.
[Neven 08] H. Neven, G. Rose & W.G. Macreadz. Image recognition with an adi-
abatic quantum computer I. Mapping to quadratic unconstrained binary
optimization. quant-ph/arXiv:0804.4457v1, April 2008.
[Nielsen 00] M. Nielsen & I. Chuang. Quantum computation and quantum information.
Cambridge Series on Information and the Natural Sciences. Cambridge
University Press, Cambridge, UK, 2000.
[Nister 05] D. Nister. Preemptive RANSAC for live structure and motion estimation.
Mach. Vision Appl., vol. 16, no. 5, pages 321–329, 2005.
[Niwa 02] J. Niwa, K. Matsumoto & H. Imai. General-Purpose Parallel Simulator for
Quantum Computing. In UMC ’02: Proceedings of the Third International
Conference on Unconventional Models of Computation, pages 230–251,
London, UK, 2002. Springer-Verlag.
[Obenland 98] K.M. Obenland & A.M. Despain. A Parallel Quantum Computer Simula-
tor. 1998.
[Omer 96] B. Omer. Simulation of Quantum Computers, 1996.
http://tph.tuwien.ac.at/ oemer/doc/qcsim.ps.
[Omer 03] B. Omer. Structured Quantum Programming. PhD thesis, TU Vi-
enna, 2003. Available online at http://tph.tuwien.ac.at/ oemer/doc/struc-
tquprog.pdf.
[Patz 03] G. Patz. A parallel environment for simulating quantum computa-
tion. Master’s thesis, Massachusetts Institute of Technology, 2003.
http://dspace.mit.edu/bitstream/handle/1721.1/16955/53364325.pdf?sequence=1.
[Raedt 07] K. De Raedt, K. Michielsen, H. De Raedt, B. Trieuc, G. Arnoldc,
M. Richterc, Th. Lippertc, H. Watanabed & N. Itoe. Massively paral-
lel quantum computer simulator. Computer Physics Communications,
vol. 176, no. 2, pages 121–136, 2007.
[Schnabel 07] R. Schnabel, R. Wahl & R. Klein. Efficient RANSAC for Point-Cloud Shape
Detection. Computer Graphics Forum, vol. 26, no. 2, pages 214–226, 2007.
[Shor 94] P.W. Shor. Algorithms for quantum computation: discrete logarithms and
factoring. In SFCS ’94: Proceedings of the 35th Annual Symposium on
Bibliografie selectiva 57
Foundations of Computer Science, pages 124–134. IEEE Computer Soci-
ety, 1994.
[Shor 97] P.W. Shor. Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer. SIAM Journal on Computing, vol. 26,
no. 5, page 1484 – 1509, 1997.
[Song 06] G. Song, Y. Zheng & H. Shen. ParaView-Based Collaborative Visualiza-
tion for the Grid. In Advanced Web and Network Technologies, and Appli-
cations, volume 3842, pages 819–826, Berlin/Heidelberg, 2006. Springer.
[Sotomayor 05] B. Sotomayor. The Globus Toolkit 4 Programmer’s Tutorial, 2005.
http://gdp.globus.org/gt4-tutorial/multiplehtml/index.html.
[Torr 97a] P. H. S. Torr & D. W. Murray. The development and comparison of ro-
bust methods for estimating the fundamental matrix. International J. of
Computer Vision, vol. 24, no. 3, pages 271–300, 1997.
[Torr 97b] P. H. S. Torr & A. Zisserman. Robust parameterization and computation of
the trifocal tensor. Image and Vision Computing, vol. 15, pages 591–605,
1997.
[van der Steen 09] A. J. van der Steen. Overview of recent supercomputers. http://top500.org,
2009.
[Venegas-Andraca 03] S. E. Venegas-Andraca & S. Bos. Quantum Computation and Image Pro-
cessing: New Trends in Artificial Intelligence. In G. Gottlob & T. Walsh,
editeurs, Proceedings of IJCAI’2003, page 1563 1563, San Francisco,
USA, 2003. Morgan Kaufmann.
[Wahl 05] R. Wahl, M. Guthe & R. Klein. Identifying Planes in Point-Clouds for
Efficient Hybrid Rendering. In Proceedings of 13th Pacific Conference
on Computer Graphics and Applications (Macao, China, October 12-14,
2005), 2005.
[Wood 04] J. Wood & K. Brodlie. gViz: visualization and computational steering on
the Grid. In S.J. Cox, editeur, Proceedings of the UK e-Science All Hands
Meeting 2004, pages 54–60, 2004.