Grafikon felosztása

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. március 24-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A gráf részgráfokra történő particionálása ( eng. Graph partition ) (néha a gráf kivágása kifejezést is használják a szakirodalomban [1] ) az eredeti gráf reprezentációja, mint csúcsok részhalmazainak halmaza bizonyos szabályok szerint. Általában a feladat feltételének megfelelően szükséges, hogy , azaz az eredeti gráf minden csúcsát el kell osztani a részhalmazok között, és . Általában a partíció ortogonalitás követelményét is bevezetik : , azaz ugyanaz a csúcs nem lehet része különböző részhalmazoknak. Néha a lehetséges partíciók halmazából ki kell választani azt, amelyik megfelel a megszorításoknak és optimális (vagy szuboptimális) a megadott kritérium szerint, vagy bizonyítania kell, hogy a kívánt partíció nem létezik (a megszorítások inkonzisztensek). A gráf particionálásának feladata az NP-complete osztályba tartozik, a partíciók számának felső becslését a Bell szám határozza meg , azonban általában nem minden lehetséges partíció helyes (nem sérti a korlátozásokat), azaz a a becslés túlbecsült. Ha a gráfcsúcsok száma meghaladja a 15-20-at, akkor az optimális partíciók beszerzése általában lehetetlen elfogadható időn belül (esetenként az elágazás és kötés módszert alkalmazzák ), ezért a gyakorlatban a heurisztika segítségével kapott szuboptimális megoldásokra korlátozódnak. algoritmusok . $G=\left\langle A,V\right\rangle$ $\mathrm {szept.} ~A=\left\{A_{1},A_{2},...,A_{n}\right\},A_{i}\subseteq A$ $\bigcup _{i=1}^{n}A_{i}=A$ $A_{i}\neq \varnothing$ $\forall i\neq j~A_{i}\cap A_{j}=\varnothing$ $N=\left|A\right|$

A partíció megszerzésének szükségessége számos probléma megoldása során merül fel:

Grafikonszínezési probléma — minden csúcskészlet azonos színű csúcsokból áll , és az azonos színű csúcsoknak nincsenek közös beeső élei. Általában a minimális színezés megtalálása érdekli az embert, ami általános esetben NP osztályú probléma (az optimalitási kritérium ). $V_i$ $n\rightarrow \min$
Egy gráf összefüggő komponenseinek számának és összetételének meghatározásának problémája .
A helyi hálózat topológiájának kialakításakor a szórási tartományokra való felosztását a teljesítménykövetelmények határozzák meg (az optimalitási kritérium a különböző szerverek és hálózati szolgáltatások ( fájlszerverekhez való hozzáférés , DHCP , WINS , DNS stb .) használatakor továbbított interdomain forgalom mennyisége. .), korlátozások - a kapcsolók , útválasztók és kommunikációs csatornák száma és sávszélessége, valamint költség).
A nyomtatott áramköri kártyák vagy mikroáramkörök összekapcsolásának nyomon követésének problémájában az eredeti áramkört rétegekre kell osztani (mindegyik síkgrafikon ). Optimalitási kritériumok - a rétegek és összeköttetések minimális száma (sőt, a gyártási költség), korlátozások - általános méretek és az elektronikus alkatrészek termikus és elektromágneses kompatibilitására vonatkozó követelmények. [2]
Egy algoritmus gráfdiagramjának blokkokra bontásának feladatában többprocesszoros rendszeren vagy logikai multivezérlőn való megvalósítás céljából . Optimalitási kritériumok a minimális blokkok száma, a mikroműködési jelek és logikai feltételek megkettőzésének minimális mértéke, a modulok közötti vezérlésátvitel minimális száma, a modulok közötti vezérlés és adatátvitel minimális forgalma; a korlátozásokat a használt elembázis határozza meg. [3] [4] [5] [6]
Egy gráf ábrázolása lépcsőzetes-párhuzamos formában vagy egy algoritmus gráfsémájának ábrázolása szakaszok halmaza formájában (a szakaszok csúcskészletei lehetnek nem merőlegesek).
Az algoritmus gráf felosztása nem metsző részgráfokra, majd ezeket a processzorelemekben vagy az FPGA elemeiben helyezi el adatfolyam-feldolgozás (terheléselosztás) megvalósítása során . [7] [8]

Grafikonos particionálási módszerek [9]

Koordináta particionálás
Rekurzív inerciális felezési módszer
Hálózati felosztás Peano-görbék segítségével
Megosztás a csatlakoztathatóság tekintetében (lényegében a szélességi keresés )
Kernigan

Lásd még

Gerasim@Home

Jegyzetek

↑ Evstigneev V. A. A gráfelmélet alkalmazása a programozásban. M.: Nauka, 1985. 352 p.
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatorikus hardvermodellek és algoritmusok CAD-ban. Moszkva: Rádió és kommunikáció, 1990. 216 p.
↑ Baranov S. I., Zhuravina L. N., Peschansky V. A. Egy módszer az algoritmusok párhuzamos gráfsémáinak szekvenciális gráfsémáival történő megjelenítésére // Automatizálás és számítástechnika. 1984. No. 5. S. 74-81.
↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Mikroprogramos multimikrovezérlők szervezése és szintézise. Kurszk: "Kursk" kiadó, 1999. 368 p. ISBN 5-7277-0253-4
↑ Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Párhuzamos logikai vezérlőalgoritmusok partícióinak szintetizálásának kombinatorikai-logikai problémái logikai multivezérlők tervezésében. Kurszk, a Kurszki Állami Műszaki Egyetem kiadója, 2010. 200 p. ISBN 978-5-7681-0523-5
↑ Vatutin E.I. Logikai multivezérlők tervezése. Algoritmusok párhuzamos gráfsémáinak partícióinak szintézise. Saarbrucken : Lambert Academic Publishing , 2011. 292 pp. ISBN 978-3-8433-1728-3
↑ Kalyaev I. A., Levin I. I., Semernikov E. A., Shmoylov V. I. Reconfigurable multi-pipeline számítási struktúrák: 2. kiadás. Rostov n/a: YuNTs RAN, 2009. 344 p. ISBN 978-5-902982-61-6
↑ Kalyaev I. A., Levin I. I. Újrakonfigurálható többcsöves számítási rendszerek az információfeldolgozás és -vezérlés áramlási problémáinak megoldására // Az 5. nemzetközi konferencia „Párhuzamos számítási és vezérlési problémák” (PACO'10) plenáris jelentései. M.: IPU RAN, 2010, 23-37.
↑ INTUIT.ru: Tanfolyam: Elmélet és gyakorlat ..: 10. előadás: Párhuzamos módszerek gráfokon (elérhetetlen link)