DonNTU, FVTI, PMI
pe tema: "Investigarea metodelor de organizare a datelor în probleme de distribuire a grafurilor de dimensiuni mari"
Finalizat Krasnokutskaya Maria
Calculul paralel poate îmbunătăți semnificativ eficiența și viteza procesării informațiilor în rezolvarea problemelor moderne. Astfel de probleme apar în electromecanică, în optimizarea sistemelor complexe, în prognoza meteo, în modelarea diferitelor procese tehnice și naturale.
Una dintre principalele probleme care apar în fiecare calcul paralel este distribuția procesării datelor între procesoare. Soluția poate fi folosirea unui model matematic bazat pe graficul fluxului de date (GPA). Programul este reprezentat de un set de sub-sarcini computaționale, care au un număr fix de intrări și ieșiri de informații. Fiecare subtasc este executat pe un procesor separat. Noduri-subtascuri - noduri ale graficului fluxurilor de date și fluxurile de informații între ele - marginile graficului. Distribuția optimă a procesării datelor între procesoare reduce la minimum timpul de execuție al tuturor calculelor. Sarcina distribuirii procesării datelor către procesoare este redusă la sarcina de a împărți graficul. Este necesar să se rupă graficul fluxurilor de date astfel încât numărul de conexiuni între subgrafice să fie minim. Experiența practică a arătat că calitatea distribuirii sarcinilor între procesoare afectează în mare măsură performanța, ceea ce a dus la un interes considerabil în algoritmii de distribuire a grafurilor [1].
Din nefericire, partiționarea unui grafic este o problemă complexă NP și, prin urmare, toți algoritmii de partiționare cunoscuți sunt euristici și dau un rezultat aproximativ. Cu toate acestea, în ciuda acestei limitări, au fost dezvoltate numeroase algoritmi pentru graficele de partiționare care produc descompunere de înaltă calitate într-un timp scurt [2].
Cu implementarea software a oricăror dintre aceste algoritmi, sarcina este de a selecta tipul de date care să reprezinte informațiile despre grafic. Există diferite moduri de reprezentări interne ale graficelor în memoria principală a unui calculator, inclusiv o listă (array) de noduri și muchii, liste (tablouri) contiguitate, matrice adiacenta, precum și combinații ale acestor structuri de stocare. Alegerea reprezentării interne are o influență decisivă asupra eficienței efectuării diferitelor operații pe grafice [3].
Scopul acestei lucrări este de a investiga metodele de organizare a datelor în probleme de împărțire a grafurilor de dimensiuni mari.
Afirmația problemei divizării unui grafic
Obiectul inițial pentru problemele de partiționare este graficul nedirecționat. Spațiul soluției este setul tuturor partițiilor posibile ale graficului în subgrafe disjuncte. Diferențele de D pot fi impuse pentru împărțirea unui grafic D. Pentru diverse probleme, desigur, sunt posibile diferite restricții.
Sarcinile de descompunere au următorul set de criterii de bază:
• numărul de conexiuni externe între subgrafe;
• numărul de subgrafe.
Primul criteriu este determinat de funcționalitatea relațiilor externe. Înțelesul celui de-al doilea criteriu este evident: este pur și simplu egal cu numărul subgrafurilor partiției. Setările pentru activități pot varia în funcție de proprietățile graficului care sunt setate de obiectul modelat.
Fie un graf ponderat nedefectat G (V, E) de ordin n, unde V = 1, ..., vn> este setul de noduri; - multe margini.
Este necesar să se determine o partiție a setului de vârfuri V grafului G (V, E) pentru k - subseturi (V1, ..., Vk) în așa fel încât pentru părțile graficul G1 (V1, E1), ..., Gk (Vk, Ek) să îndeplinească următoarele cerințe:
Dacă U1. U2 ... sunt vectori proprii normalizați ai lui L cu valori proprii corespunzătoare # 955; 1 <=λ2 <= λ3 …. то матрица L имеет следующие свойства:
(I) L este simetric.
(II) Ui sunt perechi ortogonale.
(III) U1 = n-0,51, # 955; 1 = 0
(IV) Dacă graficul este închis, atunci numai # 955; 1 ia valoarea zero.
Apoi exprimăm X în termenii vectorilor proprii L: x = # 931; # 945; i Ui. unde Eu sunt constante reale astfel încât # 931; (# 945; i) 2 = n. Proprietatea (II) asigură că acest lucru este întotdeauna posibil. Un înlocuitor pentru x primim o funcție, pentru minimizare, în funcție de valoarea proprie a matricei Laplace # 955; 2.
f (x) = 0,25 (# 945; # 955; 2 + # 945; 3 2 # 955; 3 + ... + # 945; n2 N) începând cu # 955; 1 = 0.
evident
(# 945; 2 2+ # 945; 3 2 + ... + # 945; n 2) # 955; 2 <= (α2 2 λ2 + α3 2 λ3 +…+ αn 2 λn ) учитывая упорядоченность собственных величин f(x)>= n # 955; 2/4.
Putem minimiza f (x) = n # 955; 2/4, alegând.
Vectorul x rezultat este soluția problemei continue. Rămâne să rezolvăm problema cartografierii vectorului x la separarea discretă. Pentru aceasta, se găsește valoarea mediană a valorilor xi și apoi vârfurile sunt afișate deasupra valorii mediane într-un set, mai mică în cealaltă. Dacă mai multe noduri au valoarea unei medii, atunci acestea sunt distribuite fără a deranja echilibrul. Această soluție este cel mai apropiat punct discret la un optim continuu.
CERCETAREA METODELOR DE ORGANIZARE A DATELOR
Așa cum am menționat deja, implementarea algoritmului ridică sarcina de a selecta tipul de date care să reprezinte informații despre grafic.
Stabilirea graficelor cu matrice este convenabilă pentru algoritmii care utilizează calcule matriceale (de exemplu, algoritmul de bisecție spectral). Cu toate acestea, atunci când se procesează un grafic cu dimensiuni mari (n = 1000, 10000), matricea ocupă prea multă memorie. Ar trebui să se țină seama de faptul că matricele graficelor fluxurilor de date sunt destul de rare, adică matricele conțin multe zerouri.
Luați în considerare următoarele reprezentări ale matricei în implementarea programului al algoritmului:- sferă bidimensională;
- matrice de matrice dinamice (primul element al unei matrice dinamice este numărul de elemente non-zero din rândul matricei);
- trei tablouri: o matrice de elemente de matrice non-zero, matrice de indicatori de rând și coloană corespunzătoare acestor elemente;
- matrice în format RR (C) O. Numele abreviat al acestui format este derivat din expresia engleza "Reprezentare în ordine completă și ordonată" (vizualizare de linie, completă și ordonată) [6].
Articole similare
Trimiteți-le prietenilor: