Krasnokutskaya M az adatmegosztás módszereinek tanulmányozásában a particionálási grafikonok problémáiban
DonNTU, FVTI, PMI
a témában: "Az adatok szervezésének módszereinek vizsgálata a nagyméretű partíciós grafikonok problémáiban"
Befejezett Krasnokutskaya Maria
A párhuzamos számítás jelentősen javíthatja az információfeldolgozás hatékonyságát és sebességét a modern problémák megoldásában. Ilyen problémák merülnek fel az elektromechanikában, a komplex rendszerek optimalizálásában, az időjárás előrejelzésében, a különböző technikai és természetes folyamatok modellezésében.
Az egyes párhuzamos számítások egyik fő problémája az adatfeldolgozás disztribúciója a processzorok között. A megoldás lehet egy matematikai modell alkalmazása az adatáramlási grafikon (GPA) alapján. A programot számítási al-feladatok halmaza képviseli, amelyeknek állandó száma van az információbevitelnek és kimenetnek. Minden részfeladatot külön processzoron hajtanak végre. Csomópont-subtasks - az adatfolyamok gráfjának csúcsai, és közöttük információáramlás - a grafikon élei. A processzorok közötti adatfeldolgozás optimális eloszlása minimálisra csökkenti az összes számítás végrehajtási idejét. Az adatfeldolgozás processzorok terjesztésének feladata a gráf felosztásának feladata. Az adatfolyamok grafikáját meg kell szakítani, hogy az al-grafikonok közötti kapcsolatok száma minimális legyen. Gyakorlati tapasztalatok azt mutatják, hogy a processzorok közötti feladatmegoszlás minősége nagymértékben befolyásolja a teljesítményt, ami jelentős érdeklődést váltott ki a partíciós grafikonok algoritmusaihoz [1].
Sajnos a grafikon felosztása NP-komplex probléma, ezért minden ismert partícionáló algoritmus heurisztikus, és közelítő eredményt ad. Ennek ellenére a korlátozás ellenére számos algoritmust fejlesztettek ki a rövid idő alatt kiváló minőségű bomlást eredményező grafikonok felosztására [2].
Az algoritmusok bármelyikének szoftververziójával a feladat feladata az adattípus kiválasztása a grafikonra vonatkozó információk megjelenítéséhez. Vannak különböző módon belső ábrázolása grafikonok a fő számítógép memóriájában, beleértve egy listát (array) csúcsok és az élek, listák (tömbök) szomszédság, szomszédsági mátrixok, valamint ezek kombinációja tároló szerkezetek. A belső ábrázolás megválasztása döntő hatással van a grafikonok különböző műveleteinek végrehajtására [3].
Ennek a tanulmánynak az a célja, hogy megvizsgálja az adatok rendezésének módszerét a nagy dimenziókból álló particionálási grafikonok problémáiban.
A grafikon felosztásának problémája
A problémák partícionálásának kezdeti objektuma a nem irányított grafikon. A megoldási tér a grafikon összes lehetséges partíciójának halmaza a diszjunktális részgrafokra. A D különbségeket meg lehet határozni a D. diagram különválasztására. Különböző problémákhoz természetesen különböző korlátozások is lehetségesek.
A bomlási feladatoknak az alábbi alapvető kritériumok vannak:
• a szubgrafák közötti külső kapcsolatok száma;
• a részgrafák száma.
Az első kritériumot a külkapcsolatok működése határozza meg. A második kritérium jelentése nyilvánvaló: egyszerűen megegyezik a partíció algráfiáinak számával. A feladat beállításai a modellezett objektum által beállított grafikon tulajdonságaitól függően változnak.
Adjuk meg az n sorrendű, nem irányított G (V, E) gráfot, ahol V = 1, ..., vn> a csúcsok halmaza; - sok éllel.
Ez szükséges, hogy meghatározzuk egy partíciót a csúcshalmaza V. G gráf (V, E) k - részhalmazok (V1, ..., Vk) oly módon, hogy a G1-gráf alkatrészek (V1, E1), ..., Gk (Vk, Ek) megfelel az alábbi követelményeknek:
Ha U1. U2 ... normalizált sajátvektorok L-nek megfelelő sajátértékekkel # 955; <=λ2 <= λ3 …. то матрица L имеет следующие свойства:
(I) L szimmetrikus.
(II) Ui párhuzamos ortogonális.
(III) U1 = n-0,51, # 955; 1 = 0
(IV) Ha a grafikon zárva van, akkor csak # 955; 1 értéke nulla.
Ezután X kifejezzük az L: x = # 931; # 945; i Ui sajátvektorok szempontjából. ahol # 945; igazi konstansok, ilyenek # 931; (# 945; i) 2 = n. A (II) tulajdonság biztosítja, hogy ez mindig lehetséges. Az x helyettesítő funkciót kapunk, minimálisra csökkentve, a Laplace mátrix sajátértékétől függően # 955;
f (x) = 0,25 (# 945; 2 2 # 955; 2 + # 945; 3 2 # 955; 3 + ... + # 945; n 2 # 955; n) kezdődően # 955; 1 = 0.
nyilvánvalóan
(# 945; 2 2 + # 945; 3 2 + ... + # 945, n 2) # 955; <= (α2 2 λ2 + α3 2 λ3 +…+ αn 2 λn ) учитывая упорядоченность собственных величин f(x)>= n # 955; 2/4.
Minimálisra csökkenthetjük az f (x) = n értéket # 955; 2/4, kiválasztva.
Az így kapott x vektor a folyamatos probléma megoldása. Továbbra is megoldani kell az x vektor feltérképezésének problémáját a diszkrét elválasztáshoz. Ehhez a xi értékek mediánja megtalálható, majd a csúcsok a középérték fölött jelennek meg egy sorban, alacsonyabbak a másikban. Ha több csúcs közepes értékű, akkor az egyensúlyt megzavarva oszlanak el. Ez a megoldás a legközelebbi diszkrét pont a folyamatos optimumhoz.
AZ ADATSZERVEZET MÓDSZEREINEK KUTATÁSA
Amint már említettük, az algoritmus végrehajtása feladata az adatok típusának kiválasztása a grafikonra vonatkozó információk képviseletére.
A mátrixok grafikonjainak beállítása olyan mátrixszámításokat alkalmazó algoritmusokhoz megfelelő (pl. A spektrális bisection algoritmus). Ugyanakkor nagy dimenziójú grafikon (n = 1000, 10000) feldolgozása során a mátrix túl sok memóriát vesz fel. Figyelembe kell venni, hogy az adatfolyamok grafikonjainak mátrixai meglehetősen ritkák, vagyis a mátrixok sok nullát tartalmaznak.
Vegye figyelembe a mátrix következő ábrázolásait az algoritmus program végrehajtásában:- kétdimenziós tömb;
- dinamikus tömbök csoportja (a dinamikus tömb első eleme a nem nulla elemek száma a mátrixsorban);
- három tömbök: egy nem-nulla mátrix elemek tömbje, az elemekhez tartozó sor- és oszlop-indexek tömbjei;
- mátrix RR (C) O formátumban. Ennek a formátumnak a rövidített neve az "Row-wise Representation Complete and Ordered" angol sorból származik (vonalnézet, teljes és rendezett) [6].