Többszintű párhuzamos gráfforma

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

A lépcsőzetes párhuzamos gráfforma (JPF) egy irányított aciklikus gráf csúcsainak felosztása újraszámozott részhalmazokra úgy, hogy ha az ív csúcsról csúcsra megy , akkor szükségszerűen . $V_i$ $e$ ${\displaystyle v_{1}\in V_{j))$ $v_{2}\in V_{k}$ $j<k$

Mindegyik halmazt JPF rétegnek nevezzük , száma , a réteg csúcsainak száma a szélessége . A JPF rétegeinek számát magasságnak nevezzük , a szintek maximális szélessége pedig a JPF szélessége . $V_i$ $én$ $\left|V_{i}\right|$

Az algoritmus gráf LPF-je szempontjából fontos, hogy azok a műveletek, amelyeknek egy szint csúcsai megfelelnek, ne függjenek egymástól (nem relációban vannak ), ezért biztosan létezik az algoritmus párhuzamos megvalósítása , amelyben párhuzamosan hajthatók végre különböző számítástechnikai eszközökön.rendszerek . Ezért az algoritmusgráf LPF-je felhasználható az algoritmus ilyen párhuzamos megvalósításának elkészítésére .

Egy gráf összes lehetséges NPF-jének minimális magassága a kritikus útja . Lehetetlen olyan NPF-t építeni, amelynek magassága kisebb, mint a kritikus út.

Ha egy réteg tartalmazhat olyan csúcsokat, amelyek különböző kapcsolatban állnak (például párhuzamosság vagy alternatívák , ami a párhuzamos algoritmusok gráfsémáira jellemző ), a szintet szakasznak, a CPF-et pedig szakaszok halmazának nevezik. A szakasz csúcsai között egynél több kapcsolat jelenléte jelentősen megnehezíti a legtöbb feldolgozási algoritmust [1] [2] .

Lásd még topológiai rendezés .

Jegyzetek

↑ Mikroprogramos multimikrokontrollerek szervezése és szintézise / I.V. Zotov, V.A. Koloskov, V.S. Titov [i dr.]. Kurszk: Kiadó "Kursk", 1999. 368 p. ISBN 5-7277-0253-4
↑ 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 / E.I. Vatutin, I.V. Zotov, V.S. Titov [i dr.]. Kurszk: Kurszki Állami Műszaki Egyetem kiadója, 2010. 200 p. ISBN 978-5-7681-0523-5 .