We lossen allemaal meerdere keren per dag een “ ”-probleem op. Onbedoeld natuurlijk. We lossen het op terwijl we naar ons werk gaan, of wanneer we op internet surfen, of wanneer we onze spullen op een bureau ordenen. kortste pad Klinkt een beetje… te veel? Laten we dat eens uitzoeken. Stel je voor dat je hebt besloten om af te spreken met vrienden, nou ja … laten we zeggen in een café. Allereerst moet je een route (of pad) naar het café vinden, dus je begint te zoeken naar beschikbaar openbaar vervoer (als je te voet bent) of routes en straten (als je met de auto bent). Je zoekt een route van je huidige locatie naar het café, maar niet "elke" route - de kortste of snelste. Hier is nog een voorbeeld, dat niet zo voor de hand liggend is als het vorige. Tijdens je wegwerk besluit je om een "short cut" te nemen door een zijstraat omdat... nou ja... het is een "short cut" en het is "sneller" om deze kant op te gaan. Maar hoe wist je dat deze "short cut" sneller is? Op basis van persoonlijke ervaring heb je een "shortest path"-probleem opgelost en een route geselecteerd die door de zijstraat gaat. In beide voorbeelden wordt de "kortste" route bepaald in afstand of tijd die nodig is om van de ene naar de andere plaats te komen. Reisvoorbeelden zijn heel natuurlijke toepassingen van en met name het "kortste pad"-probleem. Maar hoe zit het met het voorbeeld met het ordenen van dingen op een bureau? In dit geval kan de "kortste" een aantal of complexiteit van acties vertegenwoordigen die u moet uitvoeren om bijvoorbeeld een vel papier te krijgen: bureau openen, map openen, vel papier pakken versus vel papier rechtstreeks van bureau pakken. grafentheorie Alle bovenstaande voorbeelden vertegenwoordigen een probleem van het vinden van een kortste pad tussen twee hoekpunten in een grafiek (een route of pad tussen twee plaatsen, een aantal acties of complexiteit van het verkrijgen van een vel papier van de ene of andere plaats). Deze klasse van kortste padproblemen wordt genoemd en het basisalgoritme voor het oplossen van deze problemen is , dat een computationele complexiteit heeft. SSSP (Single Source Shortest Path) Dijkstra's algoritme O(n^2) Maar soms moeten we alle kortste paden tussen alle hoekpunten vinden. Overweeg het volgende voorbeeld: u maakt een kaart voor uw regelmatige bewegingen tussen , en . In dit scenario eindigt u met 6 routes: , , , , en (de omgekeerde routes kunnen verschillen vanwege bijvoorbeeld eenrichtingswegen). huis werk theater work ⭢ home home ⭢ work work ⭢ theatre theatre ⭢ work home ⭢ theatre theatre ⭢ home Door meer ruimte aan de kaart toe te voegen, zal het aantal combinaties aanzienlijk toenemen. Volgens de formule van voor kan dit als volgt worden berekend: de combinatoriek permutaties van n 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) Wat ons 12 routes geeft voor 4 plaatsen en 90 routes voor 10 plaatsen (wat indrukwekkend is). Let op... dit is zonder rekening te houden met tussenliggende punten tussen plaatsen, d.w.z. om van huis naar werk te komen moet je 4 straten oversteken, langs de rivier lopen en de brug oversteken. Stel je voor dat sommige routes gemeenschappelijke tussenliggende punten kunnen hebben... nou... als resultaat krijgen we een zeer grote grafiek, met veel hoekpunten, waarbij elk hoekpunt een plaats of een significant tussenliggend punt vertegenwoordigt. De klasse van problemen, waarbij we alle kortste paden tussen alle paren hoekpunten in de grafiek moeten vinden, heet en het basisalgoritme voor het oplossen van deze problemen is , dat een rekencomplexiteit van heeft. APSP (All Pairs Shortest Paths) het Floyd-Warshall-algoritme O(n^3) En dit is het algoritme dat we vandaag gaan implementeren 🙂 Floyd-Warshall-algoritme Het Floyd-Warshall-algoritme vindt alle kortste paden tussen elk paar hoekpunten in een grafiek. Het algoritme werd gepubliceerd door Robert Floyd in [1] (zie sectie “Referenties” voor meer details). In hetzelfde jaar beschreef Peter Ingerman in [2] een moderne implementatie van het algoritme in de vorm van drie geneste -lussen: for 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 Als u nooit de kans hebt gehad om met een grafiek te werken die is weergegeven in de vorm van een matrix, dan kan het lastig zijn om te begrijpen wat het bovenstaande algoritme doet. Om er zeker van te zijn dat we op dezelfde pagina zitten, gaan we kijken hoe een grafiek kan worden weergegeven in de vorm van een matrix en waarom een dergelijke weergave nuttig is om het kortste padprobleem op te lossen. De onderstaande afbeelding illustreert een grafiek van 5 hoekpunten. Links wordt de grafiek gepresenteerd in een visuele vorm, die bestaat uit cirkels en pijlen, waarbij elke cirkel een hoekpunt vertegenwoordigt en de pijl een rand met richting. Het getal binnen een cirkel komt overeen met een hoekpuntnummer en het getal boven een rand komt overeen met het gewicht van de rand. Rechts wordt dezelfde grafiek gepresenteerd in de vorm van een gewichtsmatrix. Gewichtsmatrix is een vorm van waarbij elke matrixcel een "gewicht" bevat - een afstand tussen hoekpunt (rij) en hoekpunt (kolom). Gewichtsmatrix bevat geen informatie over een "pad" tussen hoekpunten (een lijst met hoekpunten waardoor je van naar komt) - alleen een gewicht (afstand) tussen deze hoekpunten. gerichte, gewogen aangrenzende matrix i j i j In een gewichtsmatrix kunnen we zien dat celwaarden gelijk zijn aan gewichten tussen hoekpunten. Daarom zullen we, als we paden inspecteren vanaf hoekpunt (rij ), zien dat … er maar één pad is – van naar Maar op een visuele weergave kunnen we duidelijk paden zien van hoekpunt naar hoekpunten en (via hoekpunt ). De reden hiervoor is eenvoudig – in een begintoestand bevat de gewichtsmatrix alleen de afstand tussen aangrenzende hoekpunten. Deze informatie alleen is echter voldoende om de rest . aangrenzende 0 0 0 1 0 2 3 1 te vinden Laten we eens kijken hoe het werkt. Let op cel . De waarde geeft aan dat er een pad is van hoekpunt naar hoekpunt met een gewicht gelijk aan (kortom, we kunnen het schrijven als: ). Met deze kennis kunnen we nu alle cellen van rij scannen (die alle gewichten van alle paden van hoekpunt bevat) en deze informatie terugsturen naar rij , waarbij het gewicht met wordt verhoogd (waarde van ). W[0, 1] 0 1 1 0 ⭢ 1: 1 1 1 0 1 W[0, 1] Met dezelfde stappen kunnen we paden vinden van hoekpunt via andere hoekpunten. Tijdens het zoeken kan het voorkomen dat er meer dan één pad naar hetzelfde hoekpunt leidt en wat nog belangrijker is, de gewichten van deze paden kunnen verschillen. Een voorbeeld van zo'n situatie wordt geïllustreerd op de onderstaande afbeelding, waar het zoeken van hoekpunt via hoekpunt nog een pad naar hoekpunt met een kleiner gewicht onthulde. 0 0 2 3 We hebben twee paden: een origineel pad – en een nieuw pad dat we net hebben ontdekt – (houd er rekening mee dat de gewichtsmatrix geen paden bevat, dus we weten niet welke hoekpunten in het originele pad zijn opgenomen). Dit is een moment waarop we besluiten om de kortste te behouden en in cel te schrijven. 0 ⭢ 3: 4 0 ⭢ 2 ⭢ 3: 3 3 W[0, 3] Het lijkt erop dat we zojuist de eerste kortste route hebben gevonden! De stappen die we zojuist hebben gezien, vormen de essentie van het Floyd-Warshall-algoritme. Bekijk de pseudocode van het algoritme nog een keer: 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 De buitenste cyclus on itereert over alle hoekpunten in een grafiek en bij elke iteratie vertegenwoordigt variabele een hoekpunt . De binnenste cyclus on itereert ook over alle hoekpunten in de grafiek en bij elke iteratie vertegenwoordigt een hoekpunt . En als laatste een binnenste cyclus on itereert over alle hoekpunten in de grafiek en bij elke iteratie vertegenwoordigt een hoekpunt In combinatie geeft het ons het volgende: bij elke iteratie zoeken we paden van alle hoekpunten naar alle hoekpunten door hoekpunt . Binnen een cyclus vergelijken we pad (vertegenwoordigd door ) met een pad (vertegenwoordigd door de som van en ) en schrijven de kortste terug in . for k k waar we paden doorheen zoeken for i i waar we paden doorheen zoeken for j j waar we paden naartoe zoeken. k i j k i ⭢ j W[i, j] i ⭢ k ⭢ j W[I, k] W[k, j] W[i, j] Nu we de mechanica begrijpen, is het tijd om het algoritme te implementeren. Basis implementatie De broncode en experimentele grafieken zijn beschikbaar in de op GitHub. De experimentele grafieken zijn te vinden in de directory . Alle benchmarks in deze post zijn geïmplementeerd in het bestand . repository Data/Sparse-Graphs.zip APSP01.cs Voordat we met de implementatie beginnen, moeten we een paar technische punten verduidelijken: Alle implementaties werken met een gewichtsmatrix die wordt weergegeven in de vorm van een lineaire matrix. Alle implementaties gebruiken integer-rekenkunde. Afwezigheid van pad tussen hoekpunten wordt weergegeven door een speciaal constant gewicht: . NO_EDGE = (int.MaxValue / 2) - 1 Laten we eens uitzoeken hoe dat komt. Wanneer we het over matrices hebben, definiëren we cellen in termen van “rijen” en “kolommen”. Hierdoor lijkt het logisch om een matrix voor te stellen in de vorm van “vierkant” of “rechthoek” (afbeelding 4a). Betreffende #1. Dit betekent echter niet noodzakelijkerwijs dat we de matrix moeten weergeven in de vorm van een array van arrays (afbeelding 4b) om bij onze verbeelding te blijven. In plaats daarvan kunnen we een matrix weergeven in de vorm van een lineaire array (afbeelding 4c) waarbij de index van elke cel wordt berekend met behulp van de volgende formule: i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row. Lineaire array van gewichtsmatrix is een voor effectieve uitvoering van het Floyd-Warshall-algoritme. De reden daarvoor is niet eenvoudig en een gedetailleerde uitleg verdient een apart bericht... of een paar berichten. Momenteel is het echter belangrijk om te vermelden dat een dergelijke representatie aanzienlijk verbetert, wat in feite een grote impact heeft op de prestaties van het algoritme. voorwaarde de datalokaliteit Ik vraag u om mij te geloven en alleen deze informatie in gedachten te houden als voorwaarde. Tegelijkertijd raad ik u aan om wat tijd te besteden aan het bestuderen van de vraag. En trouwens: geloof de mensen op internet niet. - Opmerking van de auteur Als u de pseudocode van het algoritme nader bekijkt, zult u geen enkele controle vinden met betrekking tot het bestaan van een pad tussen twee hoekpunten. In plaats daarvan gebruikt pseudocode gewoon -functie. De reden is eenvoudig: oorspronkelijk, als er geen pad is tussen twee hoekpunten, wordt een celwaarde ingesteld op en in alle talen, behalve JavaScript, zijn alle waarden kleiner dan . In het geval van gehele getallen kan het verleidelijk zijn om te gebruiken als een "geen pad" -waarde. Dit zal echter leiden tot een gehele overloop in gevallen waarin waarden van zowel als paden gelijk zijn aan . Daarom gebruiken we een waarde die één minder is dan de helft van . Betreffende #2. min() infinity infinity int.MaxValue i ⭢ k k ⭢ j int.MaxValue int.MaxValue Hey! Maar waarom kunnen we niet gewoon controleren of het pad bestaat voordat we berekeningen uitvoeren? Bijvoorbeeld door paden te vergelijken met 0 (als we een nul nemen als "geen pad"-waarde). - Bedachtzame lezer Het is inderdaad mogelijk, maar helaas zal het leiden tot een aanzienlijke prestatievermindering. Kortom, CPU houdt statistieken bij van resultaten van branch-evaluatie, bijvoorbeeld wanneer sommige statements worden geëvalueerd als of . Het gebruikt deze statistieken om code van "statistisch voorspelde branch" vooraf uit te voeren voordat de werkelijke -statement wordt geëvalueerd (dit wordt genoemd) en voert code daarom efficiënter uit. Wanneer de CPU-voorspelling echter onnauwkeurig is, veroorzaakt dit een aanzienlijk prestatieverlies in vergelijking met correcte voorspelling en onvoorwaardelijke uitvoering, omdat de CPU moet stoppen en de juiste branch moet berekenen. if true false if speculatieve uitvoering Omdat we bij elke iteratie een significant deel van de gewichtsmatrix updaten, worden CPU-branchstatistieken nutteloos omdat er geen codepatroon is, alle branches zijn uitsluitend gebaseerd op data. Dus een dergelijke controle zal resulteren in een significante hoeveelheid . k branch-misvoorspellingen Ik vraag u ook om mij (voorlopig) te geloven en daarna wat tijd te besteden aan het bestuderen van het onderwerp. Uhh, het lijkt erop dat we klaar zijn met het theoretische gedeelte – laten we het algoritme implementeren (we duiden deze implementatie aan als ): Baseline 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; } } } } } De bovenstaande code is bijna een identieke kopie van de eerder genoemde pseudocode, met één uitzondering: in plaats van gebruiken we om een cel alleen bij te werken als dat nodig is. Math.Min() if Hé! Wacht even, was jij het niet die net een heleboel woorden schreef over waarom if's hier niet goed zijn en een paar regels later introduceren wij zelf een if? - Bedachtzame lezer De reden is simpel. Op het moment van schrijven zendt JIT bijna equivalente code uit voor zowel als -implementaties. U kunt het in detail bekijken op , maar hier zijn fragmenten van de belangrijkste loop bodies: if Math.Min sharplab.io // // == 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 U ziet dat, ongeacht of we of gebruiken, er nog steeds een voorwaardelijke controle is. Echter, in het geval van is er geen onnodige schrijfbewerking. if Math.Min if Nu we klaar zijn met de implementatie, is het tijd om de code uit te voeren en te kijken hoe snel deze is! U kunt zelf de juistheid van de code verifiëren door tests uit te voeren in een . repository Ik gebruik (versie 0.12.1) om code te benchmarken. Alle grafieken die in benchmarks worden gebruikt, zijn grafieken van 300, 600, 1200, 2400 en 4800 vertexes. Het aantal edges in grafieken is ongeveer 80% van het mogelijke maximum, wat voor gerichte, acyclische grafieken als volgt kan worden berekend: Benchmark.NET gerichte, acyclische var max = v * (v - 1)) / 2; // where v - is a number of vertexes in a graph. Laten we rocken! Hier zijn de resultaten van benchmarks die ik op mijn pc heb uitgevoerd (Windows 10.0.19042, Intel Core i7-7700 CPU 3,60 GHz (Kaby Lake) / 8 logische processoren / 4 cores): Methode Maat Gemeen Fout StandaardDev Basislijn 300 27.525 ms 0,1937 ms 0,1617 ms Basislijn 600 217.897 ms 1,6415 ms 1,5355 ms Basislijn 1200 1.763,335 ms 7,4561 ms 6,2262 ms Basislijn 2400 14.533,335 ms 63.3518 ms 52.9016 ms Basislijn 4800 119.768,219 ms 181.5514 ms 160.9406 ms Uit de resultaten kunnen we zien dat de rekentijd dramatisch groeit vergeleken met de grootte van een grafiek – voor een grafiek met 300 hoekpunten duurde het 27 milliseconden, voor een grafiek met 2400 hoekpunten – 14,5 seconden en voor een grafiek met 4800 – 119 seconden, wat is! bijna 2 minuten Als je naar de code van het algoritme kijkt, kun je je misschien moeilijk voorstellen dat er iets is dat we kunnen doen om berekeningen te versnellen... want er zijn DRIE lussen, gewoon DRIE lussen. Maar zoals het meestal gaat – mogelijkheden zitten verborgen in details 🙂 Ken uw gegevens – spaarzame grafieken Het Floyd-Warshall-algoritme is een basisalgoritme voor het oplossen van het kortste-padprobleem voor alle paren, vooral als het gaat om of grafieken (omdat het algoritme paden zoekt tussen alle paren hoekpunten). dichte volledige In onze experimenten gebruiken we echter grafieken, die een prachtige eigenschap hebben: als er een pad is van hoekpunt naar hoekpunt , dan is er geen pad van hoekpunt naar hoekpunt Voor ons betekent dit dat er veel niet-aangrenzende hoekpunten zijn die we kunnen overslaan als er geen pad is van naar (we duiden deze implementatie aan als ). gerichte, acyclische 1 2 2 1 i k 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; } } } } } Hier zijn de resultaten van eerdere ( ) en huidige ( ) implementaties op dezelfde set grafieken (de snelste resultaten zijn ): Baseline SpartialOptimisation vetgedrukt Methode Maat Gemeen Fout StandaardDev Verhouding Basislijn 300 27.525 ms 0,1937 ms 0,1617 ms 1.00 GedeeltelijkeOptimalisatie 300 12.399 ms 0,0943 ms 0,0882 ms 0,45 Basislijn 600 217.897 ms 1,6415 ms 1,5355 ms 1.00 GedeeltelijkeOptimalisatie 600 99,122 ms 0,8230 ms 0,7698 ms 0,45 Basislijn 1200 1.763,335 ms 7,4561 ms 6,2262 ms 1,00 GedeeltelijkeOptimalisatie 1200 766.675 ms 6,1147 ms 5,7197 ms 0,43 Basislijn 2400 14.533,335 ms 63.3518 ms 52.9016 ms 1.00 GedeeltelijkeOptimalisatie 2400 6.507,878 ms 28.2317 ms 26.4079 ms 0,45 Basislijn 4800 119.768,219 ms 181.5514 ms 160.9406 ms 1,00 GedeeltelijkeOptimalisatie 4800 55.590,374 ms 414.6051 ms 387,8218 ms 0,46 Heel indrukwekkend! We hebben de rekentijd gehalveerd! Natuurlijk, hoe dichter de grafiek, hoe minder snelheidswinst. Dit is echter een van de optimalisaties die handig is als u van tevoren weet met welke klasse gegevens u wilt werken. Kunnen we meer doen? 🙂 Ken uw hardware – parallelisme Mijn pc is uitgerust met processor met 8 logische processoren ( ) of 4 cores met technologie. Meer dan één core hebben is alsof je meer "reservehanden" hebt die je aan het werk kunt zetten. Laten we dus eens kijken welk deel van het werk efficiënt verdeeld kan worden over meerdere werknemers en het dan paralleliseren. Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) HW Hyper-Threading Loops zijn altijd de meest voor de hand liggende kandidaat voor parallelisatie, omdat iteraties in de meeste gevallen onafhankelijk zijn en gelijktijdig kunnen worden uitgevoerd. In het algoritme hebben we drie loops die we moeten analyseren en bekijken of er afhankelijkheden zijn die ons verhinderen ze te paralleliseren. Laten we beginnen met lus. Bij elke iteratie berekent de lus paden van elk hoekpunt naar elk hoekpunt via hoekpunt . Nieuwe en bijgewerkte paden worden opgeslagen in de gewichtsmatrix. Als u naar iteraties kijkt, ziet u misschien dat ze in elke volgorde kunnen worden uitgevoerd: 0, 1, 2, 3 of 3, 1, 2, 0 zonder dat dit invloed heeft op het resultaat. Ze moeten echter nog steeds in volgorde worden uitgevoerd, anders kunnen sommige iteraties geen nieuwe of bijgewerkte paden gebruiken omdat ze nog niet in de gewichtsmatrix zijn geschreven. Dergelijke inconsistentie zal de resultaten zeker verpletteren. Dus we moeten blijven zoeken. for of k k De volgende kandidaat is loop. Bij elke iteratie leest de loop een pad van hoekpunt naar hoekpunt (cel: ), een pad van hoekpunt naar hoekpunt (cel: ]) en controleert vervolgens of het bekende pad van naar (cel: ) korter is dan pad (som van: + ). Als u beter kijkt naar het toegangspatroon, ziet u misschien dat bij elke iteratie lus gegevens leest van rij en bijgewerkte rij, wat in feite betekent dat iteraties onafhankelijk zijn en niet alleen in elke volgorde maar ook parallel kunnen worden uitgevoerd! for of i i k W[i, k] k j W[k, j i j W[i, j] i ⭢ k ⭢ j W[i, k] W[k, j] i k i Dit ziet er veelbelovend uit, dus laten we het implementeren (we noemen deze implementatie ). SpartialParallelOptimisations loop kan ook worden geparallelliseerd. Echter, parallelisatie van de binnenste cyclus is in dit geval erg inefficiënt. U kunt het zelf verifiëren door een paar eenvoudige wijzigingen in de aan te brengen. for of j broncode - Opmerking van de auteur 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; } } }); } } Hier zijn de resultaten van de implementaties van , en op dezelfde set grafieken (parallelisatie wordt gedaan met behulp van klasse): Baseline SpartialOptimisation SpartialParallelOptimisations de Parallel- Methode Maat Gemeen Fout StandaardDev Verhouding Basislijn 300 27.525 ms 0,1937 ms 0,1617 ms 1.00 GedeeltelijkeOptimalisatie 300 12.399 ms 0,0943 ms 0,0882 ms 0,45 SpartialParallelOptimalisaties 300 6,252 ms 0,0211 ms 0,0187 ms 0,23 Basislijn 600 217.897 ms 1,6415 ms 1,5355 ms 1,00 GedeeltelijkeOptimalisatie 600 99,122 ms 0,8230 ms 0,7698 ms 0,45 SpartialParallelOptimalisaties 600 35,825 ms 0,1003 ms 0,0837 ms 0,16 Basislijn 1200 1.763,335 ms 7,4561 ms 6,2262 ms 1.00 GedeeltelijkeOptimalisatie 1200 766.675 ms 6,1147 ms 5,7197 ms 0,43 SpartialParallelOptimalisaties 1200 248.801 ms 0,6040 ms 0,5043 ms 0,14 Basislijn 2400 14.533,335 ms 63.3518 ms 52.9016 ms 1.00 GedeeltelijkeOptimalisatie 2400 6.507,878 ms 28.2317 ms 26.4079 ms 0,45 SpartialParallelOptimalisaties 2400 2.076,403 ms 20.8320 ms 19.4863 ms 0,14 Basislijn 4800 119.768,219 ms 181.5514 ms 160.9406 ms 1.00 GedeeltelijkeOptimalisatie 4800 55.590,374 ms 414.6051 ms 387,8218 ms 0,46 SpartialParallelOptimalisaties 4800 15.614,506 ms 115.6996 ms 102.5647 ms 0,13 Uit de resultaten kunnen we zien dat parallelisatie van loop de rekentijd met 2-4 keer heeft verminderd in vergelijking met eerdere implementaties ( )! Dit is erg indrukwekkend, maar het is belangrijk om te onthouden dat parallelisatie van pure berekeningen alle beschikbare rekenbronnen verbruikt, wat kan leiden tot resource-uithongering van andere applicaties in het systeem. for of i SpartialOptimisation Parallelisatie moet met zorg worden gebruikt. Zoals je wel kunt raden, is dit nog niet het einde 🙂 Ken uw platform – vectorisatie is de transformatie van een code die op één element werkt, naar een code die op meerdere elementen tegelijk werkt. Vectorisatie Dit klinkt misschien ingewikkeld, maar laten we eens kijken hoe het werkt aan de hand van een eenvoudig voorbeeld: 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]; Op een manier kan de uitvoering van iteratie van de bovenstaande -lus op CPU-niveau als volgt worden geïllustreerd: zeer vereenvoudigde 0 for Dit is wat er gebeurt. CPU laadt waarden van arrays en uit het geheugen in CPU-registers (één register kan waarde bevatten). Vervolgens voert CPU een scalaire optellingsbewerking uit op deze registers en schrijft het resultaat terug naar het hoofdgeheugen – rechtstreeks in een array . Dit proces wordt vier keer herhaald voordat de lus eindigt. a b precies één c Vectorisatie betekent het gebruik van speciale CPU-registers – vector- of SIMD-registers (single instruction multiple data) en bijbehorende CPU-instructies om bewerkingen op meerdere arraywaarden tegelijk uit te voeren: Dit is wat er gebeurt. CPU laadt waarden van arrays en uit het geheugen in CPU-registers (maar deze keer kan één vectorregister arraywaarden bevatten). Vervolgens voert CPU een vectoroptelbewerking uit op deze registers en schrijft het resultaat terug naar het hoofdgeheugen – rechtstreeks in een array . Omdat we op twee waarden tegelijk werken, wordt dit proces twee keer herhaald in plaats van vier. a b twee c Om vectorisatie in .NET te implementeren kunnen we de typen en gebruiken (we kunnen ook typen uit -naamruimte gebruiken, maar deze zijn wat geavanceerd voor de huidige implementatie, dus ik zal ze niet gebruiken, maar probeer ze gerust zelf): Vector Vector<T> de System.Runtime.Intrinsics 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; } } } } } Gevectoriseerde code kan er wat vreemd uitzien, dus laten we het stap voor stap doornemen. We maken een vector van pad: . Als resultaat, als vector vier waarden van type kan bevatten en het gewicht van pad gelijk is aan 5, maken we een vector van vier 5's – [5, 5, 5, 5]. Vervolgens berekenen we bij elke iteratie gelijktijdig paden van hoekpunt naar hoekpunten . i ⭢ k var ik_vec = new Vector<int>(matrix[i * sz + k]) int i ⭢ k i j, j + 1, ..., j + Vector<int>.Count Eigenschap retourneert het aantal elementen van het type dat in vectorregisters past. De grootte van vectorregisters is afhankelijk van het CPU-model, dus deze eigenschap kan verschillende waarden op verschillende CPU's retourneren. Vector<int>.Count int - Opmerking van de auteur Het hele berekeningsproces kan worden onderverdeeld in drie stappen: Laad informatie uit de gewichtsmatrix in vectoren: en . ij_vec ikj_vec Vergelijk en vectoren en selecteer de kleinste waarden in een nieuwe vector . ij_vec ikj_vec r_vec Schrijf terug naar de gewichtsmatrix. r_vec Terwijl en vrij eenvoudig zijn, vereist uitleg. Zoals eerder vermeld, manipuleren we met vectoren meerdere waarden tegelijkertijd. Daarom kan het resultaat van sommige bewerkingen niet enkelvoudig zijn, d.w.z. de vergelijkingsbewerking kan niet of retourneren omdat het meerdere waarden vergelijkt. Dus in plaats daarvan retourneert het een nieuwe vector die vergelijkingsresultaten bevat tussen overeenkomstige waarden van vectoren en ( , als de waarde van kleiner is dan de waarde van en als dit niet het geval is). De geretourneerde vector (op zichzelf) is niet echt nuttig, maar we kunnen de vectorbewerking gebruiken om vereiste waarden uit de vectoren en te extraheren in een nieuwe vector – . Deze bewerking retourneert een nieuwe vector waarbij de waarden gelijk zijn aan de kleinste van de twee overeenkomstige waarden van de invoervectoren. Als de waarde van de vector gelijk is aan , selecteert de bewerking een waarde uit . Anders selecteert de bewerking een waarde uit . #1 #3 #2 Vector.LessThan(ij_vec, ikj_vec) true false ij_vec ikj_vec -1 ij_vec ikj_vec 0 Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec) ij_vec ikj_vec r_vec lt_vec -1 ij_vec ikj_vec Naast is er nog een onderdeel dat uitleg vereist: de tweede, niet-gevectoriseerde lus. Deze is vereist wanneer de grootte van de gewichtsmatrix geen product is van de waarde . In dat geval kan de hoofdlus niet alle waarden verwerken (omdat u een deel van de vector niet kunt laden) en berekent de tweede, niet-gevectoriseerde lus de resterende iteraties. #2 Vector<int>.Count Hier zijn de resultaten van deze en alle voorgaande implementaties: Methode zo Gemeen Fout StandaardDev Verhouding Basislijn 300 27.525 ms 0,1937 ms 0,1617 ms 1.00 GedeeltelijkeOptimalisatie 300 12.399 ms 0,0943 ms 0,0882 ms 0,45 SpartialParallelOptimalisaties 300 6,252 ms 0,0211 ms 0,0187 ms 0,23 SpartialVectorOptimalisaties 300 3.056 ms 0,0301 ms 0,0281 ms 0,11 Basislijn 600 217.897 ms 1,6415 ms 1,5355 ms 1.00 GedeeltelijkeOptimalisatie 600 99,122 ms 0,8230 ms 0,7698 ms 0,45 SpartialParallelOptimalisaties 600 35,825 ms 0,1003 ms 0,0837 ms 0,16 SpartialVectorOptimalisaties 600 24.378 ms 0,4320 ms 0,4041 ms 0,11 Basislijn 1200 1.763,335 ms 7,4561 ms 6,2262 ms 1.00 GedeeltelijkeOptimalisatie 1200 766.675 ms 6,1147 ms 5,7197 ms 0,43 SpartialParallelOptimalisaties 1200 248.801 ms 0,6040 ms 0,5043 ms 0,14 SpartialVectorOptimalisaties 1200 185,628 ms 2,1240 ms 1,9868 ms 0,11 Basislijn 2400 14.533,335 ms 63.3518 ms 52.9016 ms 1.00 GedeeltelijkeOptimalisatie 2400 6.507,878 ms 28.2317 ms 26.4079 ms 0,45 SpartialParallelOptimalisaties 2400 2.076,403 ms 20.8320 ms 19.4863 ms 0,14 SpartialVectorOptimalisaties 2400 2.568,676 ms 31.7359 ms 29.6858 ms 0,18 Basislijn 4800 119.768,219 ms 181.5514 ms 160.9406 ms 1.00 GedeeltelijkeOptimalisatie 4800 55.590,374 ms 414.6051 ms 387,8218 ms 0,46 SpartialParallelOptimalisaties 4800 15.614,506 ms 115.6996 ms 102.5647 ms 0,13 SpartialVectorOptimalisaties 4800 18.257,991 ms 84.5978 ms 79.1329 ms 0,15 Uit het resultaat blijkt duidelijk dat vectorisatie de rekentijd aanzienlijk heeft verkort – van 3 tot 4 keer vergeleken met de niet-geparalleliseerde versie ( ). Het interessante moment hier is dat de gevectoriseerde versie ook beter presteert dan de parallelle versie ( ) op kleinere grafieken (minder dan 2400 vertexes). SpartialOptimisation SpartialParallelOptimisations En last but not least: laten we vectorisatie en parallellisme combineren! Als u geïnteresseerd bent in de praktische toepassing van vectorisatie, raad ik u aan om een aantal berichten te lezen van , waarin hij vectoriseerde (deze resultaten zijn later terug te vinden in een update voor Garbage Collector in ). Dan Shechter Array.Sort .NET 5 Ken uw platform en hardware – vectorisatie en parallellisme! De laatste implementatie combineert inspanningen van parallelisatie en vectorisatie en … eerlijk gezegd mist het individualiteit 🙂 Omdat … nou ja, we hebben zojuist een body van van vervangen door een gevectoriseerde lus van : Parallel.For SpartialParallelOptimisations SpartialVectorOptimisations 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; } } }); } } Alle resultaten van dit bericht worden hieronder gepresenteerd. Zoals verwacht, leverde gelijktijdig gebruik van parallelisme en vectorisatie de beste resultaten op, waardoor de rekentijd tot 25 keer werd verkort (voor grafieken van 1200 hoekpunten) in vergelijking met de initiële implementatie. Methode zo Gemeen Fout StandaardDev Verhouding Basislijn 300 27.525 ms 0,1937 ms 0,1617 ms 1.00 GedeeltelijkeOptimalisatie 300 12.399 ms 0,0943 ms 0,0882 ms 0,45 SpartialParallelOptimalisaties 300 6,252 ms 0,0211 ms 0,0187 ms 0,23 SpartialVectorOptimalisaties 300 3.056 ms 0,0301 ms 0,0281 ms 0,11 SpartialParallelVectorOptimalisaties 300 3,008 ms 0,0075 ms 0,0066 ms 0,11 Basislijn 600 217.897 ms 1,6415 ms 1,5355 ms 1,00 GedeeltelijkeOptimalisatie 600 99,122 ms 0,8230 ms 0,7698 ms 0,45 SpartialParallelOptimalisaties 600 35,825 ms 0,1003 ms 0,0837 ms 0,16 SpartialVectorOptimalisaties 600 24.378 ms 0,4320 ms 0,4041 ms 0,11 SpartialParallelVectorOptimalisaties 600 13.425 ms 0,0319 ms 0,0283 ms 0,06 Basislijn 1200 1.763,335 ms 7,4561 ms 6,2262 ms 1.00 GedeeltelijkeOptimalisatie 1200 766.675 ms 6,1147 ms 5,7197 ms 0,43 SpartialParallelOptimalisaties 1200 248.801 ms 0,6040 ms 0,5043 ms 0,14 SpartialVectorOptimalisaties 1200 185,628 ms 2,1240 ms 1,9868 ms 0,11 SpartialParallelVectorOptimalisaties 1200 76.770 ms 0,3021 ms 0,2522 ms 0,04 Basislijn 2400 14.533,335 ms 63.3518 ms 52.9016 ms 1.00 GedeeltelijkeOptimalisatie 2400 6.507,878 ms 28.2317 ms 26.4079 ms 0,45 SpartialParallelOptimalisaties 2400 2.076,403 ms 20.8320 ms 19.4863 ms 0,14 SpartialVectorOptimalisaties 2400 2.568,676 ms 31.7359 ms 29.6858 ms 0,18 SpartialParallelVectorOptimalisaties 2400 1.281,877 ms 25.1127 ms 64,8239 ms 0,09 Basislijn 4800 119.768,219 ms 181.5514 ms 160.9406 ms 1.00 GedeeltelijkeOptimalisatie 4800 55.590,374 ms 414.6051 ms 387,8218 ms 0,46 SpartialParallelOptimalisaties 4800 15.614,506 ms 115.6996 ms 102.5647 ms 0,13 SpartialVectorOptimalisaties 4800 18.257,991 ms 84.5978 ms 79.1329 ms 0,15 SpartialParallelVectorOptimalisaties 4800 12.785,824 ms 98,6947 ms 87.4903 ms 0,11 Conclusie In dit bericht zijn we een beetje in een all-pairs shortest path-probleem gedoken en hebben we een Floyd-Warshall-algoritme in C# geïmplementeerd om het op te lossen. We hebben ook onze implementatie bijgewerkt om data te honoreren en low-level features van .NET en hardware te gebruiken. In dit bericht speelden we "all in". In real life-toepassingen is het echter belangrijk om te onthouden dat we niet de enigen zijn. Hardcore-parallellisatie kan de systeemprestaties aanzienlijk verslechteren en meer kwaad dan goed doen. Vectorisatie is daarentegen een stuk veiliger als het op een platformonafhankelijke manier wordt gedaan. Vergeet niet dat sommige vectorinstructies alleen op bepaalde CPU's beschikbaar kunnen zijn. Ik hoop dat je het leuk vond om te lezen en dat je plezier hebt gehad met het 'persen' van wat stukjes prestatie uit een algoritme met slechts DRIE cycli 🙂 Referenties Floyd, RW Algoritme 97: Kortste pad / RW Floyd // Communicatie van de ACM. – 1962. – Vol. 5, №. 6. – P. 345-. Ingerman, PZ Algoritme 141: Padmatrix / PZ Ingerman // Mededelingen van de ACM. – 1962. – Vol. 5, №. 11. – P. 556.
