Tiered-parallell grafform

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 juli 2014; kontroller kräver 4 redigeringar .

En tiered-parallel graph form (JPF) är en uppdelning av hörnen av en riktad acyklisk graf i omnumrerade delmängder så att om bågen går från vertex till vertex , då nödvändigtvis . $V_i$ $e$ ${\displaystyle v_{1}\in V_{j))$ $v_{2}\in V_{k}$ $j<k$

Var och en av uppsättningarna kallas JPF-nivån , dess antal , antalet hörn i nivån är dess bredd . Antalet nivåer i JPF kallas dess höjd , och den maximala bredden på dess nivåer är bredden på JPF . $V_i$ $i$ $\left|V_{i}\right|$

För algoritmgrafens LPF är det viktigt att de operationer som hörn av en nivå motsvarar inte är beroende av varandra (de är inte i relation ), och därför finns det säkert en parallell implementering av algoritmen , där de kan utföras parallellt på olika datorenheter . Därför kan LPF för algoritmgrafen användas för att förbereda en sådan parallell implementering av algoritmen .

Den minsta höjden för alla möjliga NPF i en graf är dess kritiska väg . Det är omöjligt att konstruera en NPF med en höjd som är mindre än den kritiska vägen.

Om en nivå kan innehålla hörn som står i olika relationer (till exempel parallellism eller alternativ , vilket är typiskt för grafscheman av parallella algoritmer ), kallas nivån en sektion och CPF kallas en uppsättning sektioner. Närvaron av mer än ett samband mellan sektionens hörn komplicerar betydligt de flesta bearbetningsalgoritmer [1] [2] .

Se även topologisk sortering .

Anteckningar

↑ Organisation och syntes av mikroprogram multimikrokontroller / I.V. Zotov, V.A. Koloskov, V.S. Titov [i dr.]. Kursk: Publishing House "Kursk", 1999. 368 sid. ISBN 5-7277-0253-4
↑ Kombinatoriskt-logiska problem med att syntetisera partitioner av parallella logiska styralgoritmer i designen av logiska multikontroller / E.I. Vatutin, I.V. Zotov, V.S. Titov [i dr.]. Kursk: Kursk State Technical Universitys förlag, 2010. 200 sid. ISBN 978-5-7681-0523-5 .