Programare Paralela Si Concurenta Topici Avansate

QUICK INFO: CU ?h / SE ?h / LAB ?h / ? CREDITE

PROGRAMA ANALITICA

METODA DE EVALUARE

  • 60% proiecte de laborator, probleme rezolvate intr-un limbaj de programare la alegere. Aici nu prea stiu, poate cineva detalieza.
  • 40% examen scris din teorie

Proiectele sunt două la număr.
Cea dintâi temă se poate alege din unul din următoarele subiecte. Această temă este una ușoară și este nevoie doar de cod.

  • Indian grammar -derivare
  • K-grammar -derivare
  • Cyk –paralel (o versiune la alegere)
  • Earley parallel (o versiune la alegere)
  • Sisteme Lindenmayer (un tip la alegere)
  • Gramatici de insertie cu derivare (maximal) paralela
  • Recunoastere (parsare) in gramatici indiene
  • Recunoastere (parsare) in gramatici de insertie cu derivare (maximal) paralela
  • Algoritm parallel de segmentare a stringurilor (in INSpM grammars): descriere, implementare
  • Aplicatii (teoretice sau practice)

A doua temă trebuie predată până în sesiune și poate fi unul dintre următoarele subiecte.

  • inmultirea a doua matrici
  • rezolvarea sistemelor de ecuatii
  • Arbori de acoperire minimi (Algoritmul lui Prim)
  • Drumuri minime cu origine comuna (Algoritmul lui Dijkstra)
  • Drumurile minime corespunzatoare tuturor perechilor de noduri
  • Algoritmul lui Dijkstra
  • Algoritmul lui Floyd
  • CYK paralel
  • Sortari paralele
  • Procesari paralele de stringuri

Tema este mai grea, iar pe lângă cod, trebuie un referat de o pagină care să discute următoarele aspecte:

  1. Gradul maxim de concurenta
  2. Lungimea drumului critic
  3. Accelerarea S maxima care se poate obtine, presupunand ca exista un
  4. numar nelimitat de procesoare
  5. Care este numarul minim de procesoare necesare atingerii valorii accelerarii de la pct 3
  6. Timpul de Executie Ts siTp
  7. Suprasarcina (Total parallel Overhead) To
  8. Accelerare (Speedup) S
  9. Eficienta E
  10. Cost

Inițial, prima temă trebuia prezentată înainte de vacanță și a doua după. Totuși, cine nu a prezentat proiectele le poate prezenta pe amândouă după vacanță.

Examen

  1. Indian grammars, k-grammars
  2. Gramatici contextuale: definitii, clasificari, leme de pompare; abordare paralela a gramaticilor contextuale (Cap 4,5 pana la pag 47, parallel derivation)
  3. Gramatici de insertie (pana la 285, Lema 14.4 doar enuntata de la pag 281) ; abordare paralela a lor (INS_pM grammars)
  4. Sisteme Lindenmayer: definitii, caracterizare, tipuri de L-system; functia de crestere.

BIBLIOGRAFIE

  • Gh. Paun, marcus Contextual grammars (2,3) (informatii despre gramatici contextuale si gramatici de insertie (fara abordarea paralela a gramaticilor de insertie)
  • Roszenberg & Salomaa The mathematical theory of L systems (pag10-40) (sisteme lindenmayer)
  • Liviu P. Dinu, On the insertion grammars with maximum parallel derivation (abordarea paralela a gramaticilor de insertie)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License