Parallel programming analysis on OCR

22
Schnell OCR OCR simplu şi rapid 5 ian 2011, laboratorul de APP

description

In Romanian Language. OpenMP, PThread and MPI implementation and comparison of an OCR program.

Transcript of Parallel programming analysis on OCR

Page 1: Parallel programming analysis on OCR

Schnell OCR

OCR simplu şi rapid

5 ian 2011, laboratorul de APP

Page 2: Parallel programming analysis on OCR

Functia programului

• Intrare:– Fisier sau lista fisiere imagine. Suporta jpg, tiff, png in

functie de disponibilitatea bibliotecilor de sistem

• Iesire:– Textul recunoscut in imagine

• Precizari calitate OCR– Fara detectia spatiilor– Poate pune la dispozitie si un calificativ de similaritate

(claritate) al caracterului recunoscut– Nu ignora caracterele cu calificativ scazut de

similaritate

Page 3: Parallel programming analysis on OCR

Descriere algoritm

• einfach_trennen - ia ca parametru o imagine si intoarce o lista dublu inlantuita cu posibilele litere

• vektor_generieren - calculeaza "semnatura" literei - un vector de caracteristici.– alcatuit din 8 metode - ambele sensuri pe 4 directii (orizontala,

verticala, doua diagonale)– fiecare metoda salveaza coeficienti (de fapt coordonate) in

vector

• vektor_vergleichen - calculeaza diferenta intre doi vectori, adica eroarea patratica: cu cat mai mica, cu atat simbolurile sunt mai probabile sa coincida

Page 4: Parallel programming analysis on OCR

Descriere algoritm

• zeichenliste – lista inlantuita de litere probabil– Utilizata implementarea list.h din kernelul de Linux

#define list_entry(ptr, type, member) \

(type *)((char *)(ptr) - (char *)(&((type *)0)->member))

• Comparare iterativa cu toate mostrele hardcodate in kennen_muster.cpp, selectarea celei cu eroare minima

Page 5: Parallel programming analysis on OCR

Fişiere de testare

• Fişiere de rezoluţie diferită – 1, 4, 16, 100 megapixeli, jpg, tiff, png– Obţinute prin umplerea cu text– Obţinute prin scalarea primeia

Page 6: Parallel programming analysis on OCR

Fişiere de testare• Iată un studiu comparativ al rulării programului cu fişierele obţinute

prin umplere cu text şi cu cele obţinute prin scalare:

Page 7: Parallel programming analysis on OCR

Profiling

• Valorile timpilor de procesor folositi de proceduri, sortate dupa timpul exclusiv (fara subprocedurile apelate)

Page 8: Parallel programming analysis on OCR

OMP

• Avantaje– Usor de implementat– Fara probleme de sincronizare / deadlock

• Dezavantaje– Flexibilitate redusa de paralelizare– Mult overhead– Aproape imposibil de paralelizat prelucrari pe

liste

Page 9: Parallel programming analysis on OCR

OMP

Dimensiune test Timp var. seriala Timp var. OMP (12 thr.)

1 Mpx 6,4 4

4 Mpx 17,9 17

16 Mpx 57,1 35

100 Mpx 341,7 220

Page 10: Parallel programming analysis on OCR

Pthreads

• Prima incercare – calcul paralel al similaritatii cu elementele din fisierul de mostre

Page 11: Parallel programming analysis on OCR

Pthreads

• A doua incercare – decodare paralela a literelor din imagine (un nivel mai sus)

Page 12: Parallel programming analysis on OCR

Pthreads

• Varianta 1 – overheadOH_1 = (overhead_creare_thread-uri +

overhead_eliberare_thread-uri) * Nr_thread-uri * Nr_caractere

• Varianta 2 – overheadOH_2 = (overhead_creare_thread-uri +

overhead_eliberare_thread-uri) * Nr_thread-uri

• OH1 / OH2 = Nr_caractere (poate fi foarte mare!!!)

Page 13: Parallel programming analysis on OCR

Pthreads

Dimensiune test Timp var. seriala Timp var. Pthreads (12 thr.)

1 Mpx 6,4 1

4 Mpx 17,9 6

16 Mpx 57,1 11,9

100 Mpx 341,7 78

Page 14: Parallel programming analysis on OCR

MPI

• Broadcast bitmap la workeri• Numarare simboluri, repartizarea punctelor de

start si finish pentru fiecare worker– Isend-ul neblocant asigura transmisia fara overhead

• Asteptarea blocanta a rezultatelor– Asigura valabilitatea datelor in context. Rezultatele

sunt concatenate in ordinea in care au fost plasate sarcinile

– Situatie de timp de stall nedorit: nodurile care primesc primele sarcinile sunt mai lente decat cele care le primesc spre final

Page 15: Parallel programming analysis on OCR

MPI

Dimensiune test Timp var. seriala Timp var. MPI (12 proc)

1 Mpx 6,4 4

4 Mpx 17,9 8

16 Mpx 57,1 17

100 Mpx 341,7 82

Page 16: Parallel programming analysis on OCR

Comparatii

Page 17: Parallel programming analysis on OCR

Verificare corectitudine

Simplu! Diff, sau..

Page 18: Parallel programming analysis on OCR

Comparatii

Page 19: Parallel programming analysis on OCR

Lucrul în echipă

Page 20: Parallel programming analysis on OCR

Concluzii

• Flexibilitatea Pthreads a permis obtinerea unei optimizari mai eficiente decat OpenMP

• MPI a obtinut rezultate bune, scalabile pe hardware; eficient cand calculele au o pondere mai mare decat dimensiunea datelor transmise intre noduri

• Un proiect interesant pentru

• utilizarea bibliotecii de manipulare fisiere media OpenCV

• folosirea listei inlanutite din kernelul Linux

• modul de utilizare al clasificatorilor pentru elemente grafice

• calcul paralel si distribuit

Page 21: Parallel programming analysis on OCR

Dan Greceanu, [email protected]

si

Mihnea Simian, [email protected]

va multumesc pentru atentie!

Nu sunati pana in 10 sau dupa 23. Serios.

Page 22: Parallel programming analysis on OCR

Întrebări?