procesare grafică în sisteme de calcul de mare performanŃă · pdf filev.3 limbaje de...

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


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]


ı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.


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


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


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/


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


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


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


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)


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


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


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


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


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


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


[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)


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


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].


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.


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


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


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)


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


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


(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.


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


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).


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.


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


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


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)


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〉


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


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].


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


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


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


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


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.


[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.


[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.


[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


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.

procesare grafică în sisteme de calcul de mare performanŃă · pdf filev.3 limbaje de...

Documents