Descrierea problemei si a metodelor de rezolvare utilizate

Aplicaţia GridModRed include algoritmi operând pe modele de sisteme dinamice stabile liniare invariante în timp, descrise în spaţiul stărilor. Sunt incluse metode de balansare şi trunchiere, aproximaţii prin perturbaţii singulare şi aproximaţii în norma Hankel.

Din punct de vedere tehnic, procedurile de reducere a ordinului implică rezolvarea de ecuaţii Lyapunov standard sau generalizate, ecuaţii Riccati, sisteme algebrice liniare, calculul unor factorizări de matrice etc. Problematica de bază este tratată în ^[1] şi în lucrările citate acolo.

Câteva elemente esenţiale sunt prezentate în continuare. Considerăm un model de sistem de ordinul n, descris în spaţiul stărilor, G := (A,B,C,D), cu matricea funcţiilor de transfer (MFT):

G(λ) = C(λI − A) − 1B + D

unde λ este fie variabila complexă s a transformării Laplace, în cazul sistemelor continue, fie variabila complexă z a transformării Z, în cazul sistemelor discrete, şi fie G_r: = (A_r,B_r,C_r,D_r) o aproximaţie de ordinul r a modelului original (r < n), cu MFT:

Gr = Cr(I − Ar) − 1Br + Dr

Algoritmii de calcul pentru metodele de reducere bazate pe balansare, cum ar fi balansare şi trunchiere (BT), balansare şi trunchiere stocastică (BTS), sau balansare şi trunchiere cu ponderare în frecvenţă (BTPF), pot fi interpretaţi ca realizând o transformare de similaritate Z asupra sistemului original stabil, G, furnizând:

Date de intrare şi ieşire

Datele de intrare definesc opţiunile de rezolvare (metoda de utilizat şi parametrii asociaţi, ordinul dorit, configuraţia de procesoare, dimensiunea blocurilor, numărul maxim de iteraţii, toleranţe), opţiunile de listare/memorare a rezultatelor, dimensiunile sistemului original şi numele fişierului conţinând matricele sistemului, în ordinea A, B, C şi D. Matricele sunt stocate în ordinea coloanelor, iar fiecare linie din fişier conţine un singur element al unei matrice.

Datele de ieşire sunt matricele sistemului de ordin redus şi valorile singulare. Matricele rezultate pot fi listate şi/sau memorate într-un fişier specificat.

Implementarea în mediul Grid

Justificare

Uneori, modelele matematice existente provin din discretizarea unor ecuaţii cu derivate parţiale, folosind metode cu diferenţe finite sau elemente finite şi, ca atare, modelele au ordin prea mare ca să fie convenabil şi eficient utilizate. Alteori, modelele se obţin prin compunerea unor modele ale subsistemelor constitutive ale unui sistem. (De pildă, acest lucru se realizează comod folosind Simulink din MATLAB.) Sistemele globale generate astfel pot avea ordin foarte mare. De aceea, este nevoie să se recurgă la tehnici de reducere a ordinului, care însă să păstreze proprietăţile esenţiale ale comportării dinamice şi să menţină precizia descrierii matematice la un nivel acceptabil. Pentru unele modele de ordin nu prea mare, reducerea ordinului poate fi realizată şi pe calculatoare clasice seriale. Dar pentru modele de mari dimensiuni, existente actualmente şi în Internet, acest lucru nu mai este posibil, fiindcă modelul original fie nu mai încape în memorie, fie timpul de calcul devine inacceptabil de mare. Într-adevăr, metodele avansate de reducere a ordinului implică uzual un efort de calcul de ordinul n3 operaţii (notat prescurtat O(n3)) şi memorie O(n2), unde n este ordinul sistemului, adică dimensiunea vectorului de stare. Uneori, astfel de modele sunt folosite în proceduri de optimizare iterative, care implică determinarea unei soluţii a modelului la fiecare iteraţie şi care pot necesita multe iteraţii până la determinarea unei soluţii optimale sau măcar admisibile. Abordarea bazată pe Grid permite rezolvarea unor probleme cu modele de foarte mari dimensiuni.

Soluţia de implementare

Aplicaţia GridModRed are la bază unele implementări din biblioteca SLICOT [2], disponibilă public pentru utilizări academice, în speţă, implementările pe calculatoare paralele distribuite [1], utilizând nucleele paralele din ScaLAPACK [15] şi PBLAS. Aceste implementări au fost transportate şi experimentate în reţeaua GridMOSI. Se foloseşte standardul MPI [17]. La nivelul inferior, s-au folosit rutinele BLAS optimizate produse de pachetul ATLAS [18]. Rutinele au fost generate/selectate folosind şi opţiunea pentru utilizarea execuţiilor paralele (threads), cât şi opţiunea SSE2.

Pentru a rula eficient pe calculatoare cu memorie distribuită, ca în mediul Grid, datele problemei trebuie descompuse şi distribuite proceselor/procesoarelor. Dintre diferitele scheme de distribuire a datelor (pe linii, bloc-linii, coloane, ciclic pe linii etc.) s-a adoptat descompunerea bloc-ciclică (folosită şi în ScaLAPACK), deoarece această schemă dă, în general, cele mai bune rezultate. Prin selectarea unor parametri, această descompunere include schemele pe blocuri, linii sau coloane şi permite realizarea scalabilităţii, prin efectuarea unor calcule balansate (cu încărcarea echilibrată a procesoarelor) şi reducerea costurilor de sincronizare. Dimensiunea optimă a blocurilor (NB) depinde de mulţi parametri, incluzând arhitectura maşinii de calcul, performanţa diferitelor nivele BLAS, latenţa şi lăţimea de bandă a transferului de mesaje, numărul de procesoare, dimensiunea reţelei de procese, dimensiunea problemei etc. O dimensiune prea mică a unui bloc conduce la operaţii de tip BLAS 2, deci performanţe reduse, dar o dimensiune prea mare implică calcule ne-echilibrate şi spaţiu de lucru necesar mai mare, reducând implicit dimensiunea celei mai mari probleme rezolvabile. În practică, se recomandă ca mărimea unui bloc să fie dimensiunea pentru care rutina de înmulţire matriceală PGEMM din PBLAS obţine cea mai bună performanţă. Această dimensiune are, de regulă, valori în gama 20 la 80.

Cerinţe privind infrastructura Grid

Aplicaţia GridModRed necesită rutinele MPI (Message Passing Interface), cât şi rutine ScaLAPACK şi cele apelate de acestea, din bibliotecile LAPACK, BLAS, PBLAS şi BLACS (BLAS pentru comunicaţie). Nu există cerinţe hardware la nivel de Grid / nod de lucru (cum ar fi viteză CPU, memorie, conectivitatea reţelei), dar sunt de dorit performanţe superioare (incluzând cele furnizate de bibliotecile optimizate de nivel inferior, BLAS şi BLACS).

Interfaţa utilizator

Informaţiile principale care trebuie furnizate de utilizator prin interfaţă sunt:

• Metoda de reducere a ordinului şi tehnica numerică specifică (factorizare de tip rădăcină pătrată sau balansare fără factorizare de tip rădăcină pătrată);
• Tipul sistemului (continuu sau discret);
• Opţiuni de echilibrare prealabilă a sistemului şi de specificare (sau nu) a ordinului dorit;
• Dimensiunile sistemului (ordinul n, numărul de intrări m şi numărul de ieşiri p);
• Numele fişierului conţinând matricele de date;
• Dimensiunea NB a blocurilor matricelor;
• Numărul de procesoare de utilizat;
• Numărul de iteraţii;
• Toleranţele folosite.

Mai precis, interfaţa de utilizare este determinată de fişierul pdmr.in care este citit de programul aplicaţiei pentru a defini opţiunile şi datele problemei. Acest fişier este prezentat detaliat în documentaţia de utilizare.

Avantaje

Folosirea unei configuraţii Grid este avantajoasă la rezolvarea unor probleme de dimensiuni mari. De exemplu, modelul MNA_3 ^[2], care reprezintă un sistem dinamic de ordinul 4863, cu 22 intrări şi ieşiri, nu poate fi stocat pe nici unul dintre procesoarele din reţeaua GridMOSI din ICI, deci nu se poate efectua reducerea ordinului folosind configuraţia (1,1). Pentru testare, am considerat ordinul sistemului redus ca fiind 20. Rezolvarea problemei cu dimensiunea blocurilor NB = 80 a durat circa 46180 secunde folosind o configuraţie de procesoare (2,2) şi circa 27210 secunde, folosind o configuraţie (3,3), ceea ce indică o bună scalabilitate. Mai sus, notaţia (m,n) indică o configuraţie cu m procese/procesoare într-o linie şi n procese/procesoare într-o coloană a reţelei. Totuşi, ordinul 20 este întrucâtva prea mic. Într-adevăr, raportul dintre prima valoare singulară Hankel (0.97072E+3) şi valoarea singulară Hankel cu indice 20 (0.91242E+3) este 1.0639. Programul a fost executat din nou pe configuraţia de procesoare (3,3) alegând ordinul r = 100. O scădere semnificativă a valorilor singulare Hankel s-a înregistrat la indicele 23 (de la valoarea 0.91016E+3 la valoarea 0.26657E+3), aşa încât o alegere r = 22 este mai bună decât r = 20. Rezolvarea problemei pentru r = 22 a durat 24360 secunde. Desigur, eroarea în norma H-infinit între matricea de transfer a sistemului original şi cea a sistemului de ordin redus este mărginită de dublul sumei valorilor singulare Hankel neglijate.

Potenţialul de utilizare

Descrierea rezultatelor

Aplicaţia GridModRed furnizează ca rezultate esenţiale matricele Ar, Br, Cr şi Dr ale sistemului dinamic de ordin redus şi vectorul valorilor singulare Hankel ale sistemului redus, ordonate descrescător. Primul element al acestui vector este norma Hankel a sistemului. Valorile singulare Hankel permit evaluarea erorii (în norma H-infinit) dintre matricele de transfer ale sistemului original şi sistemului redus. Mai precis:

deci eroarea este mărginită de dublul sumei valorilor singulare neglijate. Marginea superioară a erorii nu poate fi însă evaluată în versiunea paralelă din GridModRed, dacă se specifică ordinul dorit. De fapt, sunt calculate doar valorile singulare Hankel ale sistemului redus.

Evaluarea impactului ştiinţific şi social

Reducerea ordinului este de interes în multe domenii: aeronautică şi astronautică, industria de automobile, industria chimică şi farmaceutică, modelare sistemică avansată în biologie, analiza şi conducerea structurilor flexibile mari, a sistemelor energetice, simularea circuitelor, proiectarea circuitelor integrate pe scară largă etc. Comunitatea de utilizatori cuprinde cercetători, analişti şi proiectanţi din domeniile menţionate sau similare, cât şi învăţământul universitar de profil.

Referințe

1. ↑ Referința bibliografică - (de completat)
2. ↑ Adaugat bibliografie