Famahana ny olan'ny lalana fohy indrindra miaraka amin'ny Algorithm Floyd-Warshall amin'ny C#

Isika rehetra dia mamaha olana " " imbetsaka isan'andro. Tsy nahy mazava ho azy. Mamaha azy io isika eny am-piasana na rehefa mijery Internet na rehefa mandamina ny entanay eo ambony latabatra.

Toa somary… be loatra? Andeha hojerentsika.

Alao sary an-tsaina, nanapa-kevitra ny hihaona amin'ny namana ianao, eny… ndao atao hoe any amin'ny cafe. Voalohany indrindra, mila mitady lalana (na lalana) mankany amin'ny cafe ianao, ka manomboka mitady fitateram-bahoaka misy (raha mandeha an-tongotra ianao) na lalana sy arabe (raha mitondra fiara). Mitady lalana avy any amin'ny toerana misy anao ankehitriny mankany amin'ny kafe ianao fa tsy lalana "izay" - ny fohy na haingana indrindra.

Ity misy ohatra iray hafa, izay tsy dia mazava loatra toy ny teo aloha. Rehefa miasa ianao dia manapa-kevitra ny hanao "fohy" amin'ny sisin-dalana satria eny ... "fohy" izany ary "haingana kokoa" ny mandeha amin'io lalana io. Ahoana anefa no nahafantaranao fa haingana kokoa io "fohy fohy" io? Miorina amin'ny traikefanao manokana dia namaha olana "lalana fohy indrindra" ianao ary nifidy lalana iray, izay mandalo amin'ny sisin-dalana.

Amin'ireo ohatra roa ireo, ny lalana "fohy indrindra" dia voafaritra na amin'ny halavirana na ny fotoana ilaina hifindrana amin'ny toerana iray mankany amin'ny iray hafa. Ny ohatra fitsangatsanganana dia fampiharana ara-boajanahary amin'ny ary indrindra indrindra ny olana "lalana fohy indrindra". Ahoana anefa ny amin’ilay ohatra amin’ny fandaminana zavatra eo ambony latabatra? Amin'ity tranga ity, ny "fohy" dia afaka maneho isa na fahasarotana amin'ny hetsika tsy maintsy ataonao mba hahazoana, ohatra, taratasy iray: misokatra birao, misokatra lahatahiry, maka ravin-taratasy vs maka ravin-taratasy avy hatrany amin'ny birao. .

Ireo ohatra rehetra voalaza etsy ambony ireo dia maneho olana amin'ny fitadiavana lalana fohy indrindra eo anelanelan'ny vertex roa amin'ny grafika (lalana na lalana eo anelanelan'ny toerana roa, hetsika maromaro na fahasarotana amin'ny fahazoana ravin-taratasy avy amin'ny toerana iray na hafa). Ity kilasy olana amin'ny lalana fohy indrindra ity dia antsoina hoe SSSP (Single Source Shortest Path) ary ny algorithm fototra hamahana ireo olana ireo dia ny , izay manana fahasarotana fikajiana O(n^2) .

Saingy, indraindray isika dia mila mahita ny lalana fohy indrindra eo anelanelan'ny vertex rehetra. Diniho ity ohatra manaraka ity: mamorona sarintany ho anao ianao fihetsiketsehana tsy tapaka eo anelanelan'ny trano , ny asa ary ny teatra . Amin'ity tranga ity dia hiafara amin'ny lalana 6 ianao: work ⭢ home , home ⭢ work , work ⭢ theatre , theatre ⭢ work , home ⭢ theatre sy theatre ⭢ home (mety ho hafa ny lalana mivadika noho ny lalana tokana ohatra) .

Ny fampidirana toerana bebe kokoa amin'ny sari-tany dia hiteraka fitomboana lehibe amin'ny fitambarana - araka ny formula of dia azo kajy toy ny:

 A(k, n) = n! / (n - m)! // where n - is a number of elements, // k - is a number of elements in permutation (in our case k = 2)

Izay manome lalana 12 ho an'ny toerana 4 ary lalana 90 ho an'ny toerana 10 (izay mahavariana). Marihina… tsy misy fiheverana ireo teboka manelanelana eo amin'ny toerana izany, izany hoe, raha handeha hiasa any an-trano ianao dia mila miampita arabe 4, mandehandeha manamorona ny renirano ary miampita tetezana. Raha alaina sary an-tsaina, ny lalana sasany dia mety manana teboka mpanelanelana iraisana… eny… vokatr'izany dia hanana grafika tena lehibe isika, miaraka amin'ny vertex be dia be, izay ahitana ny vertex tsirairay na toerana iray na teboka manelanelana manan-danja. Ny kilasin'ny olana, izay ilaintsika hahitana ny lalana fohy indrindra eo anelanelan'ny vertexes rehetra ao amin'ny grafika, dia antsoina hoe APSP (All Pairs Shortest Paths) ary ny algorithm fototra amin'ny famahana ireo olana ireo dia ny , izay manana O(n^3) fahasarotana amin'ny kajy.

Ary ity no algorithm izay hampiharintsika anio 🙂

Floyd-Warshall algorithm

Ny algorithm Floyd-Warshall dia mahita ny lalana fohy indrindra eo anelanelan'ny vertexes tsirairay ao anaty grafika. Ny algorithm dia navoakan'i Robert Floyd tao amin'ny [1] (jereo ny fizarana "References" raha mila fanazavana fanampiny). Tamin'io taona io ihany, Peter Ingerman ao amin'ny [2] dia nanoritsoritra ny fampiharana maoderina ny algorithm amin'ny endrika telo nested for loops:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i, j] = min(W[i, j], W[i, k] + W[k, j]) end for end for end for end algorithm // where W - is a weight matrix of N x N size, // min() - is a function which returns lesser of it's arguments

Raha toa ka tsy nanana fiovana hiasa amin'ny grafika aseho amin'ny endrika matrix ianao dia mety ho sarotra ny hahatakatra ny ataon'ny algorithm etsy ambony. Noho izany, mba hahazoana antoka fa eo amin'ny pejy iray ihany isika, andeha hojerentsika ny fomba azo aseho amin'ny endrika matrix sy ny antony maha-soa ny fanehoana toy izany hamahana ny olan'ny lalana fohy indrindra.

Ity sary etsy ambany ity dia mampiseho grafika misy vertex 5. Eo amin'ny ankavia, aseho amin'ny endrika hita maso ny kisary, izay vita amin'ny faribolana sy zana-tsipìka, ka ny faribolana tsirairay dia maneho vertex ary ny zana-tsipìka maneho sisiny misy lalana. Ny isa ao anaty faribolana dia mifanandrify amin'ny laharan'ny vertex ary ny isa eo ambonin'ny sisiny dia mifanitsy amin'ny lanjan'ny sisiny. Eo amin'ny ankavanana, dia aseho amin'ny endrika matrix lanja ilay grafika mitovy. Weight matrix dia endriky ny izay misy "lanja" ny sela matrix tsirairay - elanelana eo anelanelan'ny vertex i (row) sy vertex j (tsanganana). Weight matrix dia tsy ahitana fampahalalana momba ny "lalana" eo anelanelan'ny vertex (lisitra avy amin'ny vertex izay hidiranao avy amin'ny i ka hatramin'ny j ) - lanja (halavirana) eo anelanelan'ireo vertex ireo fotsiny.

Ao amin'ny matrix lanja dia hitantsika fa mitovy ny lanjan'ny sela amin'ny lanja eo anelanelan'ny vertex . Izany no antony, raha mandinika lalana avy amin'ny vertex 0 (andalana 0 ) isika, dia ho hitantsika fa … misy lalana iray ihany – manomboka amin'ny 0 ka hatramin'ny 1 . Saingy, amin'ny fanehoana an-tsary dia afaka mahita mazava tsara ny lalana manomboka amin'ny vertex 0 mankany vertex 2 sy 3 (hatramin'ny vertex 1 ). Ny anton'izany dia tsotra - amin'ny toe-javatra voalohany, ny matrix lanja dia misy elanelana eo amin'ny vertex mifanakaiky ihany. Na izany aza, ity fampahalalana ity fotsiny dia ampy hahitana ny ambiny.

Andeha hojerentsika ny fomba fiasa. Tandremo ny cellule W[0, 1] . Ny sandany dia manondro, misy lalana avy amin'ny vertex 0 mankany vertex 1 miaraka amin'ny lanja mitovy amin'ny 1 (amin'ny teny fohy dia azontsika soratana amin'ny hoe: 0 ⭢ 1: 1 ). Miaraka amin'izany fahalalana izany, dia afaka mijery ny sela rehetra amin'ny laharana 1 isika (izay misy ny lanja rehetra amin'ny lalana rehetra manomboka amin'ny vertex 1 ) ary miverina amin'ny laharana 0 ity fampahalalana ity, mampitombo ny lanja amin'ny 1 (ny lanjan'ny W[0, 1] ).

Amin'ny fampiasana ireo dingana mitovy ireo dia afaka mahita lalana avy amin'ny vertex 0 mankany amin'ny vertex hafa isika. Mandritra ny fikarohana dia mety hisy lalana mihoatra ny iray mankany amin'ny vertex iray ary ny tena zava-dehibe dia mety tsy hitovy ny lanjan'ireo lalana ireo. Ny ohatra iray amin'ny toe-javatra toy izany dia aseho eo amin'ny sary etsy ambany, izay ahitana ny fikarohana avy amin'ny vertex 0 ka hatramin'ny vertex 2 dia nahitana lalana iray hafa mankany amin'ny vertex 3 amin'ny lanja kely kokoa.

Manana lalana roa isika: lalana tany am-boalohany – 0 ⭢ 3: 4 ary lalana vaovao vao hitanay – 0 ⭢ 2 ⭢ 3: 3 (tadidio fa tsy misy lalana ny matrice lanja, ka tsy fantatsika hoe iza vertexes dia tafiditra ao amin'ny lalana tany am-boalohany). Izao no fotoana handraisana fanapahan-kevitra hitazona ny iray fohy indrindra ary hanoratra 3 ao anaty sela W[0, 3] .

Toa vao nahita ny lalanay fohy indrindra izahay!

Ny dingana izay vao hitanay dia ny fototry ny algorithm Floyd-Warshall. Jereo indray mandeha ny pseudocode an'ny algorithm:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i, j] = min(W[i, j], W[i, k] + W[k, j]) end for end for end for end algorithm

Ny tsingerina ivelany indrindra for k dia miverimberina amin'ny vertex rehetra ao anaty grafika ary isaky ny famerimberenana, ny variable k dia maneho ny vertex izay tadiavintsika lalana . Ny tsingerina anatiny for amin'ny i koa dia miverimberina amin'ny vertex rehetra ao amin'ny grafika ary amin'ny famerimberenana tsirairay, i maneho vertex izay tadiavintsika ny lalana avy amin'ny . Ary farany, ny tsingerina anatiny indrindra for j dia miverimberina amin'ny vertex rehetra ao amin'ny grafika ary isaky ny famerimberenana, j dia maneho ny vertex tadiavintsika. Amin'ny fitambarany dia manome antsika izao manaraka izao: isaky ny famerimberenana k dia mikaroka lalana avy amin'ny vertex i rehetra mankany amin'ny vertex rehetra j amin'ny vertex k isika. Ao anatin'ny tsingerina iray dia mampitaha ny lalana i ⭢ j (soloin'i W[i, j] ) miaraka amin'ny lalana i ⭢ k ⭢ j (aseho amin'ny fitambaran'ny W[I, k] sy W[k, j] ) ary manoratra ny fohy indrindra. ny iray miverina W[i, j] .

Ankehitriny, rehefa azontsika ny mekanika dia izao no fotoana hampiharana ny algorithm.

Fampiharana fototra

Alohan'ny hidirana amin'ny fampiharana dia mila manazava fotoana ara-teknika vitsivitsy isika:

1. Ny fampiharana rehetra dia miasa miaraka amin'ny matrix lanja aseho amin'ny endrika tsipika.
2. Ny fampiharana rehetra dia mampiasa aritmetika integer. Ny tsy fisian'ny lalana eo anelanelan'ny vertex dia asehon'ny lanja tsy tapaka manokana: NO_EDGE = (int.MaxValue / 2) - 1 .

Andeha hojerentsika izao ny antony mahatonga izany.

Momba ny #1. Rehefa miresaka momba ny matrix isika dia mamaritra ny sela amin'ny teny hoe "lahatra" sy "tsanganana". Noho izany dia toa voajanahary ny maka sary an-tsaina ny matrix amin'ny endrika "efamira" na "mahitsizoro" (sary 4a).

Na izany aza, tsy voatery midika izany fa tsy maintsy misolo tena ny matrix amin'ny endrika array (sary 4b) isika mba hifikitra amin'ny eritreritsika. Raha tokony ho izany, dia afaka maneho matrix amin'ny endrika laharan-tsipika (sary 4c) izay kajy ny tondron'ny sela tsirairay amin'ny fampiasana ity formula manaraka ity:

 i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row.

Ny laharan'ny tsipika lanja dia fepetra takiana amin'ny fanatanterahana mahomby ny algorithm Floyd-Warshall. Ny anton'izany dia tsy tsotra sy amin'ny antsipiriany dia mendrika lahatsoratra manokana… na lahatsoratra vitsivitsy. Na izany aza, amin'izao fotoana izao, zava-dehibe ny manonona fa ny fanehoana toy izany dia manatsara , izay raha ny marina dia misy fiantraikany lehibe amin'ny fahombiazan'ny algorithm.

Momba ny #2. Raha mijery akaiky ny pseudocode algorithm ianao dia tsy hahita fanamarinana mifandraika amin'ny fisian'ny lalana eo anelanelan'ny vertex roa. Fa kosa, ny pseudocode dia mampiasa min() function. Tsotra ny antony – tany am-boalohany, raha tsy misy lalana manelanelana ny vertexes, dia apetraka amin'ny infinity ny sandan'ny sela ary amin'ny fiteny rehetra, afa-tsy ny JavaScript, ny soatoavina rehetra dia latsaky ny infinity . Raha misy integer dia mety halaim-panahy ny mampiasa int.MaxValue ho sanda "tsy misy lalana". Na izany aza dia hitarika amin'ny fihoaran'ny integer izany raha toa ka mitovy amin'ny int.MaxValue ny soatoavin'ny lalana i ⭢ k sy k ⭢ j . Izany no antony hampiasantsika sanda iray izay latsaky ny antsasaky ny int.MaxValue .

Azo atao tokoa izany saingy indrisy fa hitarika ho amin'ny fanasaziana goavana izany. Raha fintinina, ny CPU dia mitazona antontan'isa momba ny valin'ny fanombanana sampana ex. rehefa manombana ho true na false ny sasany amin'ireo fanambarana if . Mampiasa an'io antontan'isa io izy mba hanatanterahana ny kaody "sampana vinavinaina ara-statistika" alohan'ny tena izy if tombanana ny fanambarana (antsoina hoe ) ary noho izany dia manatanteraka kaody mahomby kokoa. Na izany aza, rehefa tsy marina ny vinavinan'ny CPU dia miteraka fahavoazana lehibe izany raha oharina amin'ny vinavina marina sy ny famonoana tsy misy fepetra satria ny CPU dia tsy maintsy mijanona sy manao kajy ny sampana marina.

Satria isaky ny famerimberenana k dia manavao ampahany manan-danja amin'ny matrix lanja isika, dia lasa tsy misy ilàna azy ny antontan'isa sampana CPU satria tsy misy lamina kaody, ny sampana rehetra dia mifototra amin'ny data. Noho izany, ny fisavana toy izany dia hiteraka be dia be.

Eto koa aho dia mangataka aminao mba hino ahy (amin'izao fotoana izao) ary avy eo mandany fotoana handinihana ilay lohahevitra.

Eh, toa vitantsika ny ampahany amin'ny teorika - andao hampihatra ny algorithm (ambarantsika ho Baseline ity fampiharana ity):

 public void Baseline(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } }

Ny kaody etsy ambony dia saika dika mitovy amin'ilay pseudocode voalaza teo aloha miaraka amin'ny singa tokana - fa tsy Math.Min() dia ampiasainay if manavao sela raha ilaina ihany.

Tsotra ny antony. Amin'ny fotoana anoratana ny JIT dia mamoaka fehezan-dalàna saika mitovy amin'ny fampiharana if sy Math.Min . Azonao atao ny manamarina izany amin'ny antsipiriany ao amin'ny fa ireto misy sombin-tsarimihetsika lehibe:

 // // == Assembly code of implementation of innermost loop for of j using if. // 53: movsxd r14, r14d // // compare matrix[i * sz + j] and distance (Condition) // 56: cmp [rdx+r14*4+0x10], ebx 5b: jle short 64 // // if matrix[i * sz + j] greater than distance write distance to matrix // 5d: movsxd rbp, ebp 60: mov [rdx+rbp*4+0x10], ebx 64: // end of loop // // == Assembly code of implementation of innermost loop for of j using Math.Min. // 4f: movsxd rbp, ebp 52: mov r14d, [rdx+rbp*4+0x10] // // compare matrix[i * sz + j] and distance (Condition) // 57: cmp r14d, ebx. // // if matrix[i * sz + j] less than distance write value to matrix // 5a: jle short 5e // // otherwise write distance to matrix // 5c: jmp short 61 5e: mov ebx, r14d 61: mov [rdx+rbp*4+0x10], ebx 65: // end of loop

Mety ho hitanao, na inona na inona mampiasa if na Math.Min dia mbola misy ny fanamarinana fepetra. Na izany aza, if tsy misy ny fanoratana tsy ilaina.

Ankehitriny rehefa vita ny fampiharana, tonga ny fotoana hampandehanana ny kaody ary hijerena ny hafainganam-pandehany?! Mampiasa (version 0.12.1) aho amin'ny code benchmark. Ny grafika rehetra ampiasaina amin'ny mari-pamantarana dia misy vertex 300, 600, 1200, 2400 ary 4800. Ny isan'ny sisiny amin'ny grafika dia manodidina ny 80% amin'ny ambony indrindra azo atao izay ho an'ny grafofaonina acyclic dia azo atao toy izao:

 var max = v * (v - 1)) / 2; // where v - is a number of vertexes in a graph.

Andao hirotsaha!

Ireto ny vokatry ny benchmark mandeha amin'ny PC-ko (Windows 10.0.19042, Intel Core i7-7700 CPU 3.60Ghz (Kaby Lake) / 8 lojika processeur / 4 cores):

FOMBA	Size	fanahy	fahadisoana	StdDev
fototra	300	27.525 ms	0.1937 ms	0.1617 ms
fototra	600	217.897 ms	1.6415 ms	1.5355 ms
fototra	1200	1,763.335 ms	7.4561 ms	6.2262 ms
fototra	2400	14,533.335 ms	63.3518 ms	52.9016 ms
fototra	4800	119,768.219 ms	181.5514 ms	160.9406 ms

Avy amin'ny valiny hitantsika, mitombo be ny fotoana kajy raha oharina amin'ny haben'ny grafika - ho an'ny grafika misy vertex 300 dia 27 milliseconds, ho an'ny grafika 2400 vertex - 14.5 segondra ary ho an'ny grafika 4800 - 119 segondra izay efa ho 2 mn !

Raha mijery ny kaody algorithm dia mety ho sarotra ny mieritreritra, misy zavatra azontsika atao mba hanafainganana ny kajy… satria eny… misy tadivavarana TELO, tadivavarana TELO fotsiny.

Na izany aza, tahaka ny mitranga matetika - miafina amin'ny antsipiriany ny fahafaha-manao 🙂

Fantaro ny angon-drakitrao - kisary kely

Algorithm Floyd-Warshall dia algorithm fototra hamahana ny olan'ny lalana fohy indrindra amin'ny tsiroaroa, indrindra raha ny momba ny grafika na (satria ny algorithm dia mikaroka lalana eo anelanelan'ny vertexes rehetra).

Na izany aza, amin'ny andrana ataonay dia mampiasa grafika acyclic mivantana izahay, izay manana fananana mahafinaritra - raha misy lalana avy amin'ny vertex 1 mankany vertex 2 , dia tsy misy lalana avy amin'ny vertex 2 mankany vertex 1 . Aminay, midika izany fa be dia be ny vertexes tsy mifanakaiky izay azontsika tsidihana raha tsy misy lalana avy amin'ny i ka hatramin'ny k (isika dia manondro an'io fampiharana io ho SpartialOptimisation ).

 public void SpartialOptimisation(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == NO_EDGE) { continue; } for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } }

Ireto ny valin'ny fampiharana teo aloha ( Baseline ) sy ankehitriny ( SpartialOptimisation ) amin'ny andiana grafika mitovy (ny valiny haingana indrindra dia asongadina amin'ny bold ):

FOMBA	Size	fanahy	fahadisoana	StdDev	Taham
fototra	300	27.525 ms	0.1937 ms	0.1617 ms	1.00
SpartialOptimization	300	12.399 ms	0,0943 ms	0,0882 ms	0.45
fototra	600	217.897 ms	1.6415 ms	1.5355 ms	1.00
SpartialOptimization	600	99.122 ms	0.8230 ms	0,7698 ms	0.45
fototra	1200	1,763.335 ms	7.4561 ms	6.2262 ms	1.00
SpartialOptimization	1200	766.675 ms	6.1147 ms	5.7197 ms	0.43
fototra	2400	14,533.335 ms	63.3518 ms	52.9016 ms	1.00
SpartialOptimization	2400	6,507.878 ms	28.2317 ms	26.4079 ms	0.45
fototra	4800	119,768.219 ms	181.5514 ms	160.9406 ms	1.00
SpartialOptimization	4800	55,590.374 ms	414.6051 ms	387.8218 ms	0.46

Tena mahavariana!

Nahena antsasany ny fotoana kajy! Mazava ho azy, ny denser ny grafika, dia ho kely kokoa ny hafainganam-pandeha. Na izany aza, ity dia iray amin'ireo optimisations izay azo ampiasaina raha fantatrao mialoha hoe inona no karazana angona kasainao hiarahana miasa.

Afaka manao bebe kokoa ve isika? 🙂

Fantaro ny fitaovanao - parallèle

---

Ny PC-ko dia manana processeur Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) misy processeur logical 8 ( ) na core 4 miaraka amin'ny teknolojia . Ny fananana fototra mihoatra ny iray dia toy ny fananana “tanana mitsitsy” bebe kokoa izay azontsika ampiasaina. Noho izany, andeha hojerentsika izay ampahany amin'ny asa azo zaraina tsara amin'ny mpiasa marobe ary avy eo, ampifanaraho izany.

Loops no kandidà miharihary indrindra amin'ny fampitoviana satria amin'ny ankamaroan'ny tranga dia mahaleo tena ny famerimberenana ary azo tanterahina miaraka. Ao amin'ny algorithm, manana tadivavarana telo isika izay tokony hodinihina sy hijerena raha misy fiankinan-doha manakana antsika tsy hampifanaraka azy ireo.

Andeha isika hanomboka for of k loop. Amin'ny tadivavarana tsirairay dia manisa lalana avy amin'ny vertex tsirairay mankany amin'ny vertex tsirairay amin'ny vertex k . Ny lalana vaovao sy nohavaozina dia voatahiry ao anaty matrix lanja. Raha mijery ny fanamafisam-peo mety ho hitanao - azo tanterahina amin'ny filaharana rehetra: 0, 1, 2, 3 na 3, 1, 2, 0 tsy misy fiantraikany amin'ny vokatra. Na izany aza, mbola tsy maintsy tanterahina amin'ny filaharana izy ireo, raha tsy izany dia tsy afaka mampiasa lalana vaovao na nohavaozina ny sasany amin'ireo fampitaovana satria tsy hosoratana amin'ny matrix lanja. Ny tsy fitovian-kevitra toy izany dia tena hanorotoro ny vokatra. Mila mitady hatrany àry isika.

Ny kandida manaraka dia for of i loop. Ao amin'ny tadivavarana tsirairay dia mamaky lalana iray avy amin'ny vertex i mankany vertex k (cell: W[i, k] ), lalana iray avy amin'ny vertex k mankany vertex j (cell: W[k, j ]) ary avy eo manamarina raha fantatra ny lalana avy amin'ny i mankany amin'ny j (elatra: W[i, j] ) dia fohy kokoa noho i ⭢ k ⭢ j lalana (ny fitambaran'ny: W[i, k] + W[k, j] ). Raha mijery akaiky kokoa ny lamina fidirana ianao dia mety ho tsikaritrareo - isaky ny famerimberenana dia mamaky angon-drakitra avy amin'ny k row i ary nohavaozina i row izay midika hoe - mahaleo tena ny iterations ary azo tanterahina tsy amin'ny filaharana rehetra fa amin'ny parallèle ihany koa!

Toa mampanantena izany, koa andao hampihatra izany (famaritanay ho SpartialParallelOptimisations ity fampiharana ity).

 public void SpartialParallelOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { Parallel.For(0, sz, i => { if (matrix[i * sz + k] == NO_EDGE) { return; } for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } }); } }

Ireto ny valin'ny fampiharana Baseline , SpartialOptimisation ary SpartialParallelOptimisations amin'ny andiana grafika iray ihany (ny parallelisation dia atao amin'ny fampiasana kilasy ):

FOMBA	Size	fanahy	fahadisoana	StdDev	Taham
fototra	300	27.525 ms	0.1937 ms	0.1617 ms	1.00
SpartialOptimization	300	12.399 ms	0,0943 ms	0,0882 ms	0.45
SpartialParallelOptimisations	300	6.252 ms	0,0211 ms	0,0187 ms	0.23
fototra	600	217.897 ms	1.6415 ms	1.5355 ms	1.00
SpartialOptimization	600	99.122 ms	0.8230 ms	0,7698 ms	0.45
SpartialParallelOptimisations	600	35.825 ms	0.1003 ms	0,0837 ms	0.16
fototra	1200	1,763.335 ms	7.4561 ms	6.2262 ms	1.00
SpartialOptimization	1200	766.675 ms	6.1147 ms	5.7197 ms	0.43
SpartialParallelOptimisations	1200	248.801 ms	0,6040 ms	0,5043 ms	0.14
fototra	2400	14,533.335 ms	63.3518 ms	52.9016 ms	1.00
SpartialOptimization	2400	6,507.878 ms	28.2317 ms	26.4079 ms	0.45
SpartialParallelOptimisations	2400	2,076.403 ms	20.8320 ms	19.4863 ms	0.14
fototra	4800	119,768.219 ms	181.5514 ms	160.9406 ms	1.00
SpartialOptimization	4800	55,590.374 ms	414.6051 ms	387.8218 ms	0.46
SpartialParallelOptimisations	4800	15,614.506 ms	115.6996 ms	102.5647 ms	0.13

Hitantsika avy amin'ny valiny fa ny fampitoviana ny for of i loop dia nampihena in-2-4 ny fotoana kajy raha oharina amin'ny fampiharana teo aloha ( SpartialOptimisation )! Tena mahavariana izany, na izany aza, zava-dehibe ny mitadidy, ny fampitoviana amin'ny kajy madio dia mandany ny loharanon-karena rehetra misy izay mety hitarika amin'ny hanoanana loharanon'ny fampiharana hafa ao amin'ny rafitra. Tokony hampiasaina amim-pitandremana ny parallelisation.

Araka ny mety ho eritreretinao – tsy izao no farany 🙂

Fantaro ny sehatrao - vectorisation

dia fanovàna fehezan-dalàna miasa amin'ny singa tokana ho fehezan-dalàna miasa amin'ny singa maromaro miaraka. Mety ho toy ny raharaha sarotra izany, ka andeha hojerentsika ny fomba fiasa amin'ny ohatra tsotra:

 var a = new [] { 5, 7, 8, 1 }; var b = new [] { 4, 2, 2, 6 }; var c = new [] { 0, 0, 0, 0 }; for (var i = 0; i < 4; ++i) c[i] = a[i] + b[i];

Amin'ny fomba tafahoatra , ny famonoana ny 0 amin'ny etsy ambony for loop amin'ny haavon'ny CPU dia azo aseho toy izao manaraka izao:

Toy izao ny zava-mitranga. Ny CPU dia mampiditra ny sandan'ny array a sy b avy amin'ny fitadidiana mankany amin'ny rejisitra CPU (ny rejistra iray dia afaka mitazona sanda iray marina ). Avy eo ny CPU dia manatanteraka asa fanampiny scalar amin'ireo rejisitra ireo ary manoratra ny valiny ao anaty fitadidiana lehibe - avy hatrany ao anaty array c . Averina inefatra io dingana io alohan'ny hifaranan'ny tadivavarana.

Ny vectorisation dia midika fampiasana rejisitra CPU manokana - rejisitra vector na SIMD (toro-hevitra maromaro maromaro), ary torolàlana CPU mifanaraka amin'izany mba hanatanterahana ny asa amin'ny soatoavina maromaro indray mandeha:

Toy izao ny zava-mitranga. Ny CPU dia mameno ny sandan'ny array a sy b avy amin'ny fitadidiana mankany amin'ny rejisitra CPU (na izany aza, amin'ity indray mitoraka ity, ny rejistra vector iray dia afaka mitazona sanda array roa ). Avy eo ny CPU dia manatanteraka hetsika fanampiny vector amin'ireo rejisitra ireo ary manoratra ny valiny ho ao amin'ny fitadidiana fototra - avy hatrany ao anaty array c . Satria miasa amin'ny soatoavina roa miaraka isika, dia miverimberina indroa io dingana io fa tsy in-efatra.

Mba hampiharana ny vectorisation amin'ny .NET dia azontsika ampiasaina - karazana sy (azontsika atao koa ny mampiasa karazana avy amin'ny anaran'ny , na izany aza dia mandroso kely izy ireo amin'ny fampiharana ankehitriny, ka tsy hampiasa azy ireo aho, fa mahatsapa. maimaim-poana ny manandrana azy ireo):

 public void SpartialVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } }

Ny kaody véctorised dia mety ho somary hafahafa, koa andao hojerentsika tsikelikely.

Mamorona vector amin'ny lalana i ⭢ k izahay: var ik_vec = new Vector<int>(matrix[i * sz + k]) . Vokatr'izany, raha afaka mitazona soatoavina efatra amin'ny karazana int ny vector ary ny lanjan'ny lalana i ⭢ k dia mitovy amin'ny 5, dia hamorona vector misy 5's efatra isika - [5, 5, 5, 5]. Manaraka izany, isaky ny miverimberina, dia ataontsika kajy ny lalana avy amin'ny vertex i mankany amin'ny vertexes j, j + 1, ..., j + Vector<int>.Count .

Ny fizotry ny kajy manontolo dia azo zaraina ho dingana telo:

1. Ampidiro ao anaty vector ny fampahalalana avy amin'ny matrix lanja: ij_vec sy ikj_vec .
2. Ampitahao ny vectors ij_vec sy ikj_vec ary mifidiana sanda kely indrindra ho lasa vector r_vec vaovao.
3. Manorata r_vec miverina amin'ny matrix lanja.

Na dia tsotra aza ny #1 sy #3 , ny #2 dia mila fanazavana. Araka ny voalaza teo aloha, miaraka amin'ny vectors dia manodinkodina soatoavina maromaro miaraka amin'ny fotoana iray. Noho izany, ny vokatry ny asa sasany dia tsy mety ho tokana, izany hoe, fampitahana Vector.LessThan(ij_vec, ikj_vec) dia tsy afaka mamerina true na false satria mampitaha sanda maromaro. Noho izany dia mamerina vector vaovao izay ikj_vec valiny fampitahana eo amin'ny soatoavina mifanandrify avy amin'ny vectors ij_vec sy ikj_vec ( -1 , raha kely noho ny sanda avy amin'ny ij_vec ary 0 raha tsy izany). Tsy dia ilaina loatra ny véctor naverina (ho azy), fa afaka mampiasa Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec) isika mba hanesorana ny soatoavina ilaina avy amin'ny vectors ij_vec sy ikj_vec ho lasa vector vaovao – r_vec . Ity hetsika ity dia mamerina véctor vaovao izay misy soatoavina mitovy amin'ny soatoavina roa mifanandrify amin'ny vektora fampidirana, izany hoe, raha mitovy amin'ny -1 ny sandan'ny vector lt_vec , dia mifidy sanda avy amin'ny ij_vec ny fandidiana, raha tsy izany dia mifidy sanda avy amin'ny ikj_vec .

Ankoatra ny #2 , misy ampahany iray hafa, mitaky fanazavana - ny loop faharoa tsy misy vectorised. Ilaina izany rehefa tsy vokatra avy amin'ny Vector<int>.Count ny haben'ny matriky lanja. Amin'izany toe-javatra izany, ny loop lehibe dia tsy afaka manodina ny soatoavina rehetra (satria tsy afaka mampiditra ampahany amin'ny vector ianao) ary faharoa, tsy misy vectored, loop dia hanao kajy ny fiverenana sisa.

Ireto ny vokatr'izany sy ny fampiharana rehetra teo aloha:

FOMBA	sz	fanahy	fahadisoana	StdDev	Taham
fototra	300	27.525 ms	0.1937 ms	0.1617 ms	1.00
SpartialOptimization	300	12.399 ms	0,0943 ms	0,0882 ms	0.45
SpartialParallelOptimisations	300	6.252 ms	0,0211 ms	0,0187 ms	0.23
SpartialVectorOptimisations	300	3,056 ms	0,0301 ms	0,0281 ms	0.11
fototra	600	217.897 ms	1.6415 ms	1.5355 ms	1.00
SpartialOptimization	600	99.122 ms	0,8230 ms	0,7698 ms	0.45
SpartialParallelOptimisations	600	35.825 ms	0.1003 ms	0,0837 ms	0.16
SpartialVectorOptimisations	600	24.378 ms	0,4320 ms	0,4041 ms	0.11
fototra	1200	1,763.335 ms	7.4561 ms	6.2262 ms	1.00
SpartialOptimization	1200	766.675 ms	6.1147 ms	5.7197 ms	0.43
SpartialParallelOptimisations	1200	248.801 ms	0,6040 ms	0,5043 ms	0.14
SpartialVectorOptimisations	1200	185.628 ms	2.1240 ms	1,9868 ms	0.11
fototra	2400	14,533.335 ms	63.3518 ms	52.9016 ms	1.00
SpartialOptimization	2400	6,507.878 ms	28.2317 ms	26.4079 ms	0.45
SpartialParallelOptimisations	2400	2,076.403 ms	20.8320 ms	19.4863 ms	0.14
SpartialVectorOptimisations	2400	2,568.676 ms	31.7359 ms	29.6858 ms	0.18
fototra	4800	119,768.219 ms	181.5514 ms	160.9406 ms	1.00
SpartialOptimization	4800	55,590.374 ms	414.6051 ms	387.8218 ms	0.46
SpartialParallelOptimisations	4800	15,614.506 ms	115.6996 ms	102.5647 ms	0.13
SpartialVectorOptimisations	4800	18,257.991 ms	84.5978 ms	79.1329 ms	0.15

Avy amin'ny vokatra dia miharihary, ny vectorisation dia nampihena be ny fotoana kajy - in-3 ka hatramin'ny in-4 raha oharina amin'ny dikan-teny tsy mitovy ( SpartialOptimisation ). Ny fotoana mahaliana eto dia ny dikan-vectorised koa dia mihoatra ny dikan-teny parallel ( SpartialParallelOptimisations ) amin'ny grafika kely kokoa (latsaky ny vertex 2400).

Ary farany fa tsy ny kely indrindra – andao hanambatra ny vectorisation sy ny parallèle!

Fantaro ny sehatra sy ny fitaovanao - vectorisation sy parallelism!

Ny fampiharana farany dia manambatra ny ezaka amin'ny fampitoviana sy ny vectorisation SpartialVectorOptimisations … raha ny marina dia tsy misy maha-tokana azy 🙂 Satria SpartialParallelOptimisations eny, vao avy nosoloina vatana Parallel.For

 public void SpartialParallelVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { Parallel.For(0, sz, i => { if (matrix[i * sz + k] == NO_EDGE) { return; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } }); } }

Ny vokatra rehetra amin'ity lahatsoratra ity dia aseho eto ambany. Araka ny efa nampoizina, ny fampiasana mifanandrify sy ny vectorisation dia nampiseho vokatra tsara indrindra, nampihena ny fotoana kajy hatramin'ny in-25 (ho an'ny kisary misy vertex 1200) raha oharina amin'ny fampiharana voalohany.

FOMBA	sz	fanahy	fahadisoana	StdDev	Taham
fototra	300	27.525 ms	0.1937 ms	0.1617 ms	1.00
SpartialOptimization	300	12.399 ms	0,0943 ms	0,0882 ms	0.45
SpartialParallelOptimisations	300	6.252 ms	0,0211 ms	0,0187 ms	0.23
SpartialVectorOptimisations	300	3.056 ms	0,0301 ms	0,0281 ms	0.11
SpartialParallelVectorOptimisations	300	3.008 ms	0,0075 ms	0,0066 ms	0.11
fototra	600	217.897 ms	1.6415 ms	1.5355 ms	1.00
SpartialOptimization	600	99.122 ms	0,8230 ms	0,7698 ms	0.45
SpartialParallelOptimisations	600	35.825 ms	0.1003 ms	0,0837 ms	0.16
SpartialVectorOptimisations	600	24.378 ms	0,4320 ms	0,4041 ms	0.11
SpartialParallelVectorOptimisations	600	13.425 ms	0,0319 ms	0,0283 ms	0.06
fototra	1200	1,763.335 ms	7.4561 ms	6.2262 ms	1.00
SpartialOptimization	1200	766.675 ms	6.1147 ms	5.7197 ms	0.43
SpartialParallelOptimisations	1200	248.801 ms	0,6040 ms	0,5043 ms	0.14
SpartialVectorOptimisations	1200	185.628 ms	2.1240 ms	1,9868 ms	0.11
SpartialParallelVectorOptimisations	1200	76.770 ms	0,3021 ms	0,2522 ms	0.04
fototra	2400	14,533.335 ms	63.3518 ms	52.9016 ms	1.00
SpartialOptimization	2400	6,507.878 ms	28.2317 ms	26.4079 ms	0.45
SpartialParallelOptimisations	2400	2,076.403 ms	20.8320 ms	19.4863 ms	0.14
SpartialVectorOptimisations	2400	2,568.676 ms	31.7359 ms	29.6858 ms	0.18
SpartialParallelVectorOptimisations	2400	1,281.877 ms	25.1127 ms	64.8239 ms	0.09
fototra	4800	119,768.219 ms	181.5514 ms	160.9406 ms	1.00
SpartialOptimization	4800	55,590.374 ms	414.6051 ms	387.8218 ms	0.46
SpartialParallelOptimisations	4800	15,614.506 ms	115.6996 ms	102.5647 ms	0.13
SpartialVectorOptimisations	4800	18,257.991 ms	84.5978 ms	79.1329 ms	0.15
SpartialParallelVectorOptimisations	4800	12,785.824 ms	98.6947 ms	87.4903 ms	0.11

Famaranana

Ato amin'ity lahatsoratra ity dia nitsofoka kely tamin'ny olan'ny lalana fohy indrindra izahay ary nampihatra algorithm Floyd-Warshall ao amin'ny C# hamahana azy. Nohavaozina ihany koa ny fampiharana ataonay mba hanomezam-boninahitra ny angon-drakitra sy hampiasa ny endri-javatra ambany indrindra amin'ny .NET sy ny fitaovana.

Amin'ity lahatsoratra ity dia nilalao ny "all in". Na izany aza, amin'ny fampiharana tena izy dia zava-dehibe ny mitadidy – tsy irery isika. Ny parallelisation hardcore dia mety hanimba ny fahombiazan'ny rafitra ary hiteraka fahavoazana bebe kokoa noho ny tsara. Vectorisation amin'ny lafiny iray hafa dia azo antoka kokoa raha atao amin'ny sehatra tsy miankina. Tsarovy fa ny sasany amin'ireo torolalana vector dia mety tsy misy afa-tsy amin'ny CPU sasany.

Manantena aho fa nankafizinao ny famakiana ary nahafinaritra anao tamin'ny "fanindronana" ny zava-bita sasany avy amin'ny algorithm miaraka amin'ny tsingerina TELO fotsiny 🙂

References

---