Formă grafică paralelă în etaje

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 17 iulie 2014; verificările necesită 4 modificări .

O formă de graf paralel- nivelat (JPF) este o împărțire a vârfurilor unui graf aciclic direcționat în submulțimi renumerotate astfel încât, dacă arcul trece de la vârf la vârf , atunci în mod necesar . $V_i$ $e$ $v_{1}\in V_{j)$ $v_{2}\in V_{k}$ $j<k$

Fiecare dintre seturi se numește nivelul JPF , numărul său , numărul de vârfuri din nivel este lățimea acestuia . Numărul de niveluri din JPF se numește înălțimea acestuia , iar lățimea maximă a nivelurilor sale este lățimea JPF . $V_i$ $i$ $\left|V_{i}\right|$

Pentru LPF -ul grafului algoritm, este important ca operațiile cărora le corespund vârfurile unui nivel să nu depindă unele de altele (nu sunt în relație ) și, prin urmare, există cu siguranță o implementare paralelă a algoritmului , în care pot fi realizate în paralel pe diferite dispozitive de calcul.sisteme . Prin urmare, LPF -ul graficului algoritm poate fi utilizat pentru a pregăti o astfel de implementare paralelă a algoritmului .

Înălțimea minimă a tuturor NPF-urilor posibile ale unui grafic este calea sa critică . Este imposibil să construiți un NPF cu o înălțime mai mică decât calea critică.

Dacă un nivel poate conține vârfuri care se află în relații diferite (de exemplu, paralelism sau alternative , ceea ce este tipic pentru schemele grafice ale algoritmilor paraleli ), nivelul se numește secțiune, iar CPF este numit un set de secțiuni. Prezența a mai mult de o relație între vârfurile secțiunii complică semnificativ majoritatea algoritmilor de procesare [1] [2] .

Vezi și sortare topologică .

Note

↑ Organizarea și sinteza microprogramelor multimicrocontrolere / I.V. Zotov, V.A. Koloskov, V.S. Titov [i dr.]. Kursk: Editura „Kursk”, 1999. 368 p. ISBN 5-7277-0253-4
↑ Probleme combinatorii-logice de sintetizare a partițiilor de algoritmi de control logic paralel în proiectarea multicontrolerelor logice / E.I. Vatutin, I.V. Zotov, V.S. Titov [i dr.]. Kursk: editura Universității Tehnice de Stat din Kursk, 2010. 200 p. ISBN 978-5-7681-0523-5 .