Ku tlhantlha Xiphiqo xa Tindlela to Koma swinene ta All-pairs Hi Algorithm ya Floyd-Warshall eka C# .

Hinkwerhu ka hina hi tlhantlha xiphiqo xa “ ” minkarhi yo tala hi siku. Ku nga ri hi vomu hakunene. Hi swi tlhantlha loko hi ri endleleni ya ntirho kumbe loko hi pfula Internet kumbe loko hi hlela swilo swa hina ehenhla ka desika. ndlela yo koma swinene Swi twala nyana... ngopfu ngopfu? A hi kumeni. Anakanya, u teke xiboho xo hlangana na vanghana, kahle kahle ... a hi nge ekhefini. Xosungula, ufanele ku kuma ndlela (kumbe ndlela) yoya eka khefi, kutani u sungula ku lava swofamba swa mani na mani leswi kumekaka (loko uri hi milenge) kumbe tindlela na switarata (loko u chayela). U lava ndlela kusuka eka ndzhawu ya wena ya sweswi kuya eka khefi kambe kungari ndlela “yihi na yihi” – yo koma kumbe yo hatlisa swinene. Hi lexi xikombiso xin’wana, lexi nga vonakiki ngopfu ku fana ni lexi hundzeke. Hi nkarhi wa ntirho wa wena wa ndlela u teka xiboho xo teka “short cut” hi xitarata xa le tlhelo hikuva kahle kahle... i “short cut” naswona swa “hatlisa” ku famba hi ndlela leyi. Kambe u swi tivise ku yini leswaku “ku tsemiwa loku ko koma” ku hatlisa? Hi ku ya hi ntokoto wa munhu hi xiyexe u tlhantlhe xiphiqo xa “ndlela yo koma swinene” ivi u hlawula ndlela, leyi hundzaka hi xitarata xa le tlhelo. Eka swikombiso leswi haswimbirhi, ndlela “yo koma swinene” yi kumiwa hi mpfhuka kumbe nkarhi lowu lavekaka ku suka endhawini yin’wana ku ya eka yin’wana. Swikombiso swo famba i matirhiselo ya ntumbuluko swinene ya na xiphiqo xa “ndlela yo koma swinene” ngopfungopfu. Hambiswiritano, ku vuriwa yini hi xikombiso xa ku hlela swilo ehenhla ka desika? Eka xiyimo lexi “shortest” yi nga yimela nhlayo kumbe ku rharhangana ka swiendlo leswi u faneleke ku swi endla ku kuma, xikombiso, phepha: pfula desika, pfula folda, teka phepha vs teka phepha kunene kusuka eka desika . thiyori ya girafu Swikombiso hinkwaswo leswi nga laha henhla swi yimela xiphiqo xo kuma ndlela yo koma swinene exikarhi ka tinhloko timbirhi eka girafu (ndlela kumbe ndlela exikarhi ka tindhawu timbirhi, nhlayo ya swiendlo kumbe ku rharhangana ka ku kuma phepha ku suka eka ndhawu yin’wana kumbe yin’wana). Tlilasi leyi ya swiphiqo swa ndlela yo koma yi vuriwa naswona algorithm ya xisekelo yo tlhantlha swiphiqo leswi i , leyi nga na ku rharhangana ka xibalo . SSSP (Single Source Shortest Path) algorithm ya Dijkstra O(n^2) Kambe, minkarhi yin’wana hi fanele ku kuma tindlela hinkwato to koma exikarhi ka ti vertexes hinkwato. Anakanya hi xikombiso lexi landzelaka: u ku endlela mepe ku famba-famba ka nkarhi na nkarhi exikarhi ka , na . Eka xiyimo lexi u ta hetelela u ri na tindlela ta 6: , , , , na (tindlela to tlhelela endzhaku ti nga ha hambana hikwalaho ka magondzo ya ndlela yin’we xikombiso) . kaya entirhweni theatre work ⭢ home home ⭢ work work ⭢ theatre theatre ⭢ work home ⭢ theatre theatre ⭢ home Ku engetela ndzhawu yotala eka mepe swita endla leswaku kuva na kukula lokukulu ka swihlanganisi – kuya hi formula ya swinga hlayeriwa tani hi: permutations ya n combinatorics 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) Leswi swi hi nyikaka 12 wa tindlela ta 4 wa tindhawu na 90 wa tindlela ta 10 wa tindhawu (leswi swi hlamarisaka). Xiya... leswi swi endliwa handle ko tekela enhlokweni ti intermediate points exikarhi ka tindzhawu ie, ku suka ekaya kuya entirhweni ufanele ku tsemakanya 4 wa switarata, u famba hi nambu u tsemakanya buloho. Loko hi ehleketa, tindlela tin’wana ti nga va na tinhla ta le xikarhi leti tolovelekeke... kahle ... tani hi mbuyelo hi ta va na girafu leyikulu swinene, leyi nga na ti vertex to tala, laha vertex yin’wana na yin’wana yi nga ta yimela ndhawu kumbe ndhawu ya le xikarhi ya nkoka. Tlilasi ya swiphiqo, laha hi lavaka ku kuma tindlela hinkwato to koma exikarhi ka mimpatswa hinkwayo ya ti-vertex eka girafu, yi vuriwa naswona algorithm ya xisekelo yo tlhantlha swiphiqo leswi i , leyi nga ku rharhangana ka xibalo. APSP (All Pairs Shortest Paths) Floyd-Warshall algorithm O(n^3) Naswona leyi i algorithm leyi hi nga ta yi tirhisa namuntlha 🙂 Xitirhisiwa xa Floyd-Warshall xa xirhendzevutani Floyd-Warshall algorithm yi kuma tindlela hinkwato to koma exikarhi ka mpatswa wun’wana na wun’wana wa ti vertexes eka girafu. Tialgorithm ti kandziyisiwile hi Robert Floyd eka [1] (vona xiyenge xa “Swikombo” ku kuma vuxokoxoko byo tala). Hi lembe leri fanaka, Peter Ingerman eka [2] u hlamusele ku tirhisiwa ka manguva lawa ka algorithm hi xivumbeko xa ti nested loop tinharhu: 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 Loko u nga si tshama u va na ku cinca ku tirha na girafu leyi yimeriweke hi xivumbeko xa matiriki kutani swi nga tika ku twisisa leswi algorithm leyi nga laha henhla yi swi endlaka. Kutani, ku tiyisisa leswaku hi le ka tluka rin’we, a hi languteni ndlela leyi girafu yi nga yimeriwaka ha yona hi xivumbeko xa matiriki na leswaku hikokwalaho ka yini vuyimeri byo tano byi pfuna ku tlhantlha xiphiqo xa ndlela yo koma swinene. Xifaniso lexi nga laha hansi xi kombisa girafu ya 5 wa tinhlohlorhi. Eka tlhelo ra ximatsi, girafu yi nyikeriwile hi xivumbeko xa xivono, lexi endliweke hi swirhendzevutani na miseve, laha xirhendzevutani xin’wana na xin’wana xi yimelaka nhlohlorhi kasi museve wu yimela tlhelo leri nga na nkongomiso. Nomboro endzeni ka xirhendzevutani yi fambelana na nomboro ya vertex naswona nomboro yale henhla ka ncila yi fambelana na ntiko wa ncila. Eka tlhelo ra xinene, girafu leyi fanaka yi nyikeriwile hi xivumbeko xa matiriki ya ntiko. Matiriki ya ntiko i xivumbeko xa laha sele yin’wana na yin’wana ya matiriki yi nga na “ndzilo” – mpfhuka exikarhi ka vertex (row) na vertex (kholomo). Matrix ya ntiko a yi katsi vuxokoxoko mayelana na “ndlela” exikarhi ka ti vertexes (nxaxamelo wa ti vertexes leti u kumaka eka tona kusuka eka kuya eka ) – ntsena ntiko (mpfhuka) exikarhi ka ti vertexes leti. leyi kongomisiweke, leyi pimiweke matiriki ya le kusuhi i j i j Eka matiriki ya ntiko hi nga vona leswaku mimpimo ya tisele yi ringana na ntiko exikarhi ka ti vertexes . Hi yona mhaka, loko hi kambela tindlela ku suka eka vertex (row ), hi ta vona leswaku ... ku na ndlela yin’we ntsena – ku suka eka ku ya eka . Kambe, eka vuyimeri bya xivono hi nga vona kahle tindlela ku suka eka vertex ku ya eka vertex na (hi ku tirhisa vertex ). Xivangelo xa leswi xa olova – eka xiyimo xosungula, matiriki ya ntiko yina mpfhuka exikarhi ka ti vertexes letinga ekusuhi ntsena. Hambiswiritano, rungula leri ntsena ri ringanerile ku leswi seleke. leti nga ekusuhi 0 0 0 1 0 2 3 1 kuma A hi voneni leswaku swi tirha njhani. Nyikela nyingiso eka sele ya . Nkoka wa yona wu kombisa, ku na ndlela yo suka eka vertex ku ya eka vertex leyi nga na ntiko lowu ringanaka na (hi ku komisa hi nga tsala eka tani hi: ). Hi vutivi lebyi, sweswi hi nga skena tisele hinkwato ta layini (leyi nga na ntiko hinkwawo wa tindlela hinkwato ku suka eka vertex ) ivi hi tlherisela endzhaku rungula leri eka layini , hi engetela ntiko hi (nxavo wa ). W[0, 1] 0 1 1 0 ⭢ 1: 1 1 1 0 1 W[0, 1] Hiku tirhisa magoza lawa ya fanaka hinga kuma tindlela kusuka eka vertex kuya eka ti vertexes tin’wana. Hi nkarhi wa ku lavisisa, swinga endleka leswaku kuna tindlela to tlula yin’we leti yisaka eka vertex yin’we naswona leswinga swa nkoka swinene ntiko wa tindlela leti wunga hambana. Xikombiso xa xiyimo xo tano xi kombisiwile eka xifaniso lexi nga laha hansi, laha ku lavisisa ku suka eka vertex ku ya eka vertex ku paluxeke ndlela yin’wana yo ya eka vertex ya ntiko wutsongo. 0 0 2 3 Hi na tindlela timbirhi: ndlela yo sungula – na ndlela leyintshwa leyi hi ha ku yi kumaka – (hlayisa emiehleketweni, matiriki ya ntiko a yi na tindlela, hikwalaho a hi tivi leswaku hi yihi ti vertexes ti katsiwile eka ndlela yo sungula). Lowu i nkarhi lowu hi endlaka xiboho xo hlayisa xo koma swinene ivi hi tsala eka sele . 0 ⭢ 3: 4 0 ⭢ 2 ⭢ 3: 3 3 W[0, 3] Swi vonaka onge hi lo kuma ndlela ya hina yo sungula yo koma! Magoza lawa hi nga ha ku ma vonaka i xisekelo xa algorithm ya Floyd-Warshall. Languta pseudocode ya algorithm kan’we nakambe: 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 Xirhendzevutani xa le handle swinene on xi vuyeleriwa ehenhla ka ti vertex hinkwato eka girafu naswona eka iteration yin’wana na yin’wana, variable yi yimela vertex leyi . Xirhendzevutani xa le ndzeni on xi tlhela xi vuyeleriwa ehenhla ka ti-vertex hinkwato eka girafu naswona eka ku vuyeleriwa kun’wana na kun’wana, yi yimela vertex . Naswona xo hetelela xirhendzevutani xa le ndzeni swinene on iterates ehenhla ka ti vertexes hinkwato eka girafu na le ka iteration yin’wana na yin’wana, yi yimela vertex leyi Hi ku hlanganisiwa yi hi nyika leswi landzelaka: eka iteration yin’wana na yin’wana hi le ku laveni ka tindlela ku suka eka ti vertexes hinkwato ku ya eka ti vertexes hinkwato ku ya eka vertex . Endzeni ka xirhendzevutani hi pimanisa ndlela (leyi yimeriweke hi ) na ndlela (leyi yimeriweke hi nhlayo ya na ) na ku tsala yo koma swinene yin’we yi tlhelela endzhaku eka . for k k hi lavaka tindlela eka yona for i i leyi hi lavaka tindlela ku suka eka yona for j j hi lavaka ndlela yo ya eka yona. k i j k i ⭢ j W[i, j] i ⭢ k ⭢ j W[I, k] W[k, j] W[i, j] Sweswi, loko hi twisisa makhanikhi i nkarhi wo tirhisa algorithm. Ku tirhisiwa ka xisekelo Khodi ya xihlovo na tigirafu ta swikambelo swi kumeka eka eka GitHub. Tigirafu ta swikambelo ti nga kumeka eka directory. Swipimelo hinkwaswo eka poso leyi swi tirhisiwile eka fayili ya . vuhlayiselo Data/Sparse-Graphs.zip APSP01.cs Loko hi nga si nghena eka ku tirhisiwa hi fanele ku hlamusela minkarhi yi nga ri yingani ya xithekiniki: Ku tirhisiwa hinkwako ku tirha na matiriki ya ntiko leyi yimeriweke hi xivumbeko xa lineal array. Ku tirhisiwa hinkwako ku tirhisa tinhlayo ta nhlayo leyi heleleke. Ku pfumaleka ka ndlela exikarhi ka ti vertexes swi yimeriwe hi ntiko wo hlawuleka lowu nga cinciki: . NO_EDGE = (int.MaxValue / 2) - 1 Sweswi, a hi kumeni leswaku ha yini sweswo swi ri tano. Loko hi vulavula hi matiriki hi hlamusela tisele hi ku ya hi “tirow” na “tikholomu”. Hikwalaho ka leswi swi vonaka swi ri swa ntumbuluko ku ehleketa hi matiriki hi xivumbeko xa “xikwere” kumbe “rectangle” (Xifaniso xa 4a). Malunghana na #1. Kambe leswi a swi bohi leswaku hi fanele ku yimela matiriki hi xivumbeko xa array of arrays (Xifaniso xa 4b) ku namarhela miehleketo ya hina. Ematshan’wini ya leswi, hi nga yimela matiriki hi xivumbeko xa lineal array (Xifaniso 4c) laha index ya sele yin’wana na yin’wana yi hlayiwaka hi ku tirhisa fomula leyi landzelaka: i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row. Lineal array ya weight matrix i xa ku hetisisiwa loku humelelaka ka algorithm ya Floyd-Warshall. Xivangelo xa sweswo a xi olovi naswona nhlamuselo ya vuxokoxoko yi faneriwa hi post yo hambana... kumbe ti post ti nga ri tingani. Kambe, sweswi, i swa nkoka ku boxa leswaku vuyimeri byo tano byi antswisa swinene , leswi entiyisweni swi nga na nkucetelo lowukulu eka matirhelo ya algorithm. xiyimo xa le mahlweni data locality Laha, ndzi kombela leswaku mi ndzi kholwa na ntsena mahungu lawa emiehleketweni tani hi xiyimo xa le mahlweni, hambiswiritano, hi nkarhi lowu fanaka ndzi ku ringanyeta ku heta nkarhi wo karhi u dyondza xivutiso, naswona hi ndlela leyi – u nga pfumeli vanhu eka inthanete . - Xitsundzuxo xa mutsari Loko u languta swinene eka algorithm pseudocode, a wu nge kumi ku kamberiwa kwihi na kwihi loku fambelanaka na vukona bya ndlela exikarhi ka ti vertexes timbirhi. Ematshan’weni ya sweswo, pseudocode yi tirhisa ntsena ntirho wa . Xivangelo xa olova – ekusunguleni, loko kungari na ndlela exikarhi ka ku ya eka ti vertexes, ntikelo wa sele wu vekiwa eka naswona eka tindzimi hinkwato, handle ka loko kungava JavaScript, mimpimo hinkwayo yile hansi ka . Eka tinomboro leti heleleke swi nga ha ringeta ku tirhisa tanihi ntikelo wa “ku hava ndlela”. Hambiswiritano leswi swi ta yisa eka ku tala ka tinomboro leti heleleke eka swiyimo laha mimpimo ya tindlela ta na ti nga ta ringana na . Hi yona mhaka leyi hi tirhisaka ntikelo lowu nga wun’we ehansi ka hafu ya . Malunghana na #2. min() infinity infinity int.MaxValue i ⭢ k k ⭢ j int.MaxValue int.MaxValue Heyi! Kambe hikokwalaho ka yini hi nga swi koti ku kambela ntsena loko ndlela yi ri kona hi nga si endla swibalo swihi na swihi. Xikombiso hi ku pimanisa tindlela hi vumbirhi bya tona eka 0 (loko hi teka zero tanihi “no path” value). - Muhlayi la ehleketaka Hakunene swa koteka kambe khombo ra kona swi ta yisa eka nhlawulo lowukulu wa matirhelo. Hi ku komisa, CPU yi hlayisa tinhlayo ta mimbuyelo ya nkambisiso wa marhavi ex. loko swin'wana swa switatimende swi kambisisa ku va kumbe . Yi tirhisa tinhlayo leti ku tirhisa khodi ya “rhavi leri vhumbhiweke hi tinhlayo” ka ha ri emahlweni loko xitatimende xa xiviri xi nga si kamberiwa (leswi swi vuriwa ) naswona hikwalaho yi tirhisa khodi hi ndlela leyinene. Kambe loko ku vhumbha ka CPU ku nga ri ntiyiso, swi vanga ku lahlekeriwa lokukulu ka matirhelo loko ku pimanisiwa na ku vhumbha lokunene na ku hetisisiwa loku nga riki na swipimelo hikuva CPU yi fanele ku yima no hlayela rhavi leri faneleke. if true false if ku hetisisiwa ka ku ehleketa Hikuva eka iteration yin’wana na yin’wana hi pfuxeta xiphemu xa nkoka xa matiriki ya ntiko, tinhlayo ta marhavi ya CPU ti hundzuka leti nga pfuniki nchumu hikuva a ku na xivumbeko xa khodi, marhavi hinkwawo ya sekeriwe ntsena eka datha. Kutani ku kamberiwa ko tano ku ta endla leswaku ku va ni nhlayo leyikulu ya . k ku vhumbha loku hoxeke ka marhavi Laha ndzi tlhela ndzi kombela leswaku mi ndzi kholwa (sweswi) ivi mi heta nkarhi wo dyondza nhlokomhaka. Uhh, swi vonaka onge hi hetile hi xiphemu xa thiyori – a hi tirhiseni algorithm (hi kombisa ku tirhisiwa loku tanihi ): Baseline public void Baseline(int[] matrix, int sz) { for (var k = 0; k distance) { matrix[i * sz + j] = distance; } } } } } Khodi leyi nga laha henhla yi lava ku va khopi leyi fanaka ya pseudocode leyi boxiweke khale handle ka xihlawuhlawu xin’we – ematshan’wini ya hi tirhisa ku pfuxeta sele ntsena loko swi laveka. Math.Min() if Heyi! Yimela nyana, a hi wena loyi u nga tsala marito yo tala ntsena hi leswaku why if's a yi kahle laha naswona endzhaku ka mitila yi nga ri yingani hina hi hexe hi nghenisa if? - Muhlayi la ehleketaka Xivangelo xa kona xa olova. Hi nkarhi wa ku tsala JIT yi humesa khodi leyi lavaka ku ringana eka havumbirhi bya na implementations. U nga yi kambela hi vuxokoxoko eka kambe hi leswi swiphemu swa mimiri leyikulu ya loop: 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 nga ha vona, ku nga khathariseki leswaku hi tirhisa kumbe ku ha ri na conditional check. Kambe, eka xiyimo xa ku nga ri na tsala leri nga lavekiki. if Math.Min if Sweswi loko hi heta hi ku tirhisa, i nkarhi wo tsutsuma khodi hi vona leswaku yi hatlisa ku fikela kwihi?! U nga tiyisisa ku lulama ka khodi hi wexe hi ku fambisa swikambelo eka . vuhlayiselo Ndzi tirhisa (version 0.12.1) ku pimanisa khodi. Tigirafu hinkwato leti tirhisiwaka eka swipimelo ti ta 300, 600, 1200, 2400 na 4800 wa ti vertexes. Nhlayo ya makumu eka tigirafu yi kwalomu ka 80% wa maximum leyi kotekaka leyi eka tigirafu leti kongomisiweke, ta acyclic tinga hlayeriwa tani hi: Benchmark.NET kongomisiwile, tigirafu ta acyclic var max = v * (v - 1)) / 2; // where v - is a number of vertexes in a graph. A hi rhurhumeleni! Hi lowu mbuyelo wa swipimelo leswi tirhisiwaka eka PC ya mina (Windows 10.0.19042, Intel Core i7-7700 CPU 3.60Ghz (Kaby Lake) / 8 wa tiphurosesa leti twisisekaka / 4 wa ti-core): Ndlela Sayizi Vula Xihoxo StdDev Xisekelo xa le henhla 300 27.525 ms 0.1937 ms 0.1617 ms Xisekelo xa le henhla 600 217.897 ms 1.6415 ms 1.5355 ms Xisekelo xa le henhla 1200 1 763.335 ms 7.4561 ms 6.2262 ms Xisekelo xa le henhla 2400 14,533.335 ms 63.3518 ms 52.9016 ms Xisekelo xa le henhla 4800 119,768.219 wa timis 181.5514 ms 160.9406 ms Kusuka eka mbuyelo lowu hinga wuvonaka, nkarhi wa xibalo wukula swinene loko wu pimanyisiwa na vukulu bya girafu – eka girafu ya 300 wa ti vertexes switeke 27 milliseconds, eka girafu ya 2400 vertexs – 14.5 seconds na girafu ya 4800 – 119 seconds leswinga ! kwalomu ka 2 wa timinete Loko hi languta khodi ya algorithm swi nga tika ku swi ehleketa, ku na leswi hi nga swi endlaka ku hatlisisa swibalo... hikuva kahle kahle... ku na ti loop TINHARHU, ti loop TINHARHU ntsena. Kambe, tani hi leswi swi talaka ku humelela – swilo leswi nga kotekaka swi fihliwile hi vuxokoxoko 🙂 Tiva wena data – tigirafu to tala Floyd-Warshall algorithm i algorithm ya xisekelo yo tlhantlha xiphiqo xa ndlela yo koma ya ti pair hinkwato, ngopfu ngopfu loko swita eka ti graphs kumbe (hikuva algorithm yi lavisisa tindlela exikarhi ka ti pair hinkwato ta vertexes). to enta leti heleleke Kambe eka swikambelo swa hina hi tirhisa tigirafu , leti nga na nhundzu yo hlamarisa – loko ku ri na ndlela yo suka eka vertex ku ya eka vertex , kutani a ku na ndlela yo suka eka vertex ku ya eka vertex . Eka hina, swi vula leswaku, ku na ti vertexes to tala leti nga riki ekusuhi leti hi nga ti tlulaka loko ku nga ri na ndlela yo suka eka ku ya eka (hi kombisa ku tirhisiwa loku tanihi ). leti kongomisiweke, ta acyclic 1 2 2 1 i k SpartialOptimisation public void SpartialOptimisation(int[] matrix, int sz) { for (var k = 0; k distance) { matrix[i * sz + j] = distance; } } } } } Hi lowu mbuyelo wa ku tirhisiwa ka khale ( ) na ka sweswi ( ) eka sete yin’we ya tigirafu (mimbuyelo yo hatlisa swinene yi kombisiwile hi ): Baseline SpartialOptimisation ku olova Ndlela Sayizi Vula Xihoxo StdDev Vuxaka Xisekelo xa le henhla 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 Ku antswisiwa ka xiphemu 300 12.399 ms 0.0943 ms 0,0882 ms 0.45 Xisekelo xa le henhla 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 Ku antswisiwa ka xiphemu 600 99.122 ms 0.8230 ms 0.7698 ms 0.45 Xisekelo xa le henhla 1200 1 763.335 ms 7.4561 ms 6.2262 ms 1.00 Ku antswisiwa ka xiphemu 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 Xisekelo xa le henhla 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 Ku antswisiwa ka xiphemu 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 Xisekelo xa le henhla 4800 119,768.219 wa timis 181.5514 ms 160.9406 ms 1.00 Ku antswisiwa ka xiphemu 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 Swi hlamarisa swinene! Hi hungute nkarhi wo hlayela hi hafu! I ntiyiso leswaku loko girafu yi ri leyi tsindziyeleke, ku ta va ku ri ni rivilo leritsongo. Kambe leyi i yin’wana ya ti optimisations leti ti pfunaka loko u tiva ka ha ri emahlweni leswaku i class yihi ya data leyi u kunguhatiweke ku tirha na yona. Xana hi nga endla leswi engetelekeke? 🙂 Tiva hardware ya wena – parallelism PC ya mina yi hlomisiwile hi processor leyi nga na 8 wa ti logical processor ( ) kumbe 4 wa ti cores leti nga na thekinoloji ya . Ku va na ti core to tlula yin’we swi fana na ku va na “mavoko yo tala” lawa hi nga ma vekaka entirhweni. Kutani, a hi voneni leswaku hi xihi xiphemu xa ntirho lexi nga avanyisiwa hi ndlela leyinene exikarhi ka vatirhi vo tala ivi endzhaku, hi xi ringanisa. Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) HW Hyper-Threading Ti loops ti tshama tiri candidate leyi vonakaka swinene eka parallelisation hikuva eka swiyimo swotala ti iterations ti tiyimele naswona tinga endliwa hi nkarhi wun’we. Eka algorithm, hi na ti loop tinharhu leti hi faneleke ku ti xopaxopa hi vona loko ku ri na ti dependencies leti hi sivelaka ku ti parallelise. A hi sunguleni eka loop. Eka iteration loop yin’wana na yin’wana yi hlayela tindlela kusuka eka vertex yin’wana na yin’wana kuya eka vertex yin’wana na yin’wana hiku tirhisa vertex . Tindlela letintshwa na leti pfuxetiweke ti hlayisiwa eka matiriki ya ntiko. Loko u languta eka ku vuyeleriwa u nga ha swi xiya – swi nga endliwa hi ku landzelelana kwihi na kwihi: 0, 1, 2, 3 kumbe 3, 1, 2, 0 handle ko khumba mbuyelo. Kambe, ta ha fanele ku endliwa hi ku landzelelana, handle ka sweswo tin’wana ta ti-iterations a ti nge swi koti ku tirhisa tindlela letintshwa kumbe leti pfuxetiweke hikuva a ti nge tsariwi eka matiriki ya ntiko, ku fikela sweswi. Ku nga fambisani ko tano hakunene ku ta pfotlosa vuyelo bya kona. Kutani hi fanele hi hambeta hi languta. for of k k Muhlawuriwa loyi a landzelaka i loop. Eka iteration loop yin’wana na yin’wana yi hlaya ndlela kusuka eka vertex kuya eka vertex (cell: ), ndlela kusuka eka vertex kuya eka vertex (cell: ]) kutani yi kambela loko ndlela leyi tivekaka kusuka eka ku ya eka (sele: ) yi komile ku tlula ndlela ya (nhlayo ya: + ). Loko u languta swinene eka xivumbeko xa mfikelelo, u nga ha xiya – eka iteration yin’wana na yin’wana loop yi hlaya data ku suka eka row na updated row leswi hi xisekelo swi vulaka leswaku – iterations yi tiyimele naswona yi nga endliwa ku nga ri hi ku landzelelana kwihi na kwihi ntsena kambe na hi ku fambisana! 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 Leswi swi languteka swi tshembisa, kutani a hi swi tirhiseni (hi kombisa ku tirhisiwa loku tanihi ). SpartialParallelOptimisations loop na yona yi nga fambelanisiwa. Kambe, parallelisation ya innermost cycle eka mhaka leyi a yi tirhi ngopfu. U nga swi tiyisekisa hi wexe hi ku endla ku cinca ko hlayanyana ko olova eka . for of j khodi ya xihlovo - Xitsundzuxo xa mutsari public void SpartialParallelOptimisations(int[] matrix, int sz) { for (var k = 0; k { if (matrix[i * sz + k] == NO_EDGE) { return; } for (var j = 0; j distance) { matrix[i * sz + j] = distance; } } }); } } Hi leyi mimbuyelo ya ku tirhisiwa ka , na eka sete yin’we ya tigirafu (ku ringanisa ku endliwa hi ku tirhisa tlilasi ya ): Baseline SpartialOptimisation SpartialParallelOptimisations Parallel Ndlela Sayizi Vula Xihoxo StdDev Vuxaka Xisekelo xa le henhla 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 Ku antswisiwa ka xiphemu 300 12.399 ms 0.0943 ms 0,0882 ms 0.45 SpartialParallelKu antswisiwa ka swilo 300 6.252 ms 0.0211 ms 0.0187 ms 0.23 Xisekelo xa le henhla 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 Ku antswisiwa ka xiphemu 600 99.122 ms 0.8230 ms 0.7698 ms 0.45 SpartialParallelKu antswisiwa ka swilo 600 35.825 ms 0.1003 ms 0.0837 ms 0.16 Xisekelo xa le henhla 1200 1 763.335 ms 7.4561 ms 6.2262 ms 1.00 Ku antswisiwa ka xiphemu 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelKu antswisiwa ka swilo 1200 248.801 ms 0.6040 ms 0.5043 ms 0.14 Xisekelo xa le henhla 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 Ku antswisiwa ka xiphemu 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelKu antswisiwa ka swilo 2400 2,076.403 wa ms 20.8320 ms 19.4863 ms 0.14 Xisekelo xa le henhla 4800 119,768.219 wa timis 181.5514 ms 160.9406 ms 1.00 Ku antswisiwa ka xiphemu 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelKu antswisiwa ka swilo 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 Ku suka eka mbuyelo hi nga vona leswaku parallelisation ya loop yi hungute nkarhi wa xibalo hi 2-4 wa minkarhi loko ku pimanisiwa na ku tirhisiwa ka khale ( )! Leswi swa hlamarisa swinene, hambiswiritano, i swa nkoka ku tsundzuka, ku fambelanisiwa ka swibalo swo basa swi dya switirhisiwa hinkwaswo swa xibalo leswi nga kona leswi nga tisaka ndlala ya switirhisiwa swa switirhisiwa swin’wana eka sisiteme. for of i SpartialOptimisation Parallelisation yifanele kutirhisiwa hi vukheta. Hilaha u nga ha ehleketaka hakona – lawa a hi makumu 🙂 Tiva pulatifomo ya wena – vectorisation i ku hundzuriwa ka khodi leyi tirhaka eka elemente yin’we ku va khodi leyi tirhaka eka elemente yo tala hi nkarhi wun’we. Vectorisation Leswi swi nga ha twala onge i mhaka leyi rharhanganeke, kutani a hi voneni ndlela leyi swi tirhaka ha yona eka xikombiso xo olova: 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]; Hi ndlela , ku hetisisiwa ka iteration ya loop leyi nga laha henhla eka levele ya CPU ku nga kombisiwa hi ndlela leyi landzelaka: yo olova ngopfu 0 for Hi leswi leswi humelelaka. CPU yi layicha mimpimo ya ti-array na ku suka eka memori eka tirhejisitara ta CPU (rhijisitara rin’we ri nga khoma ). Kutani CPU yi endla ntirho wo engetela wa scalar eka tirhejisitara leti naswona yi tsala mbuyelo wu tlhelela eka memori leyikulu – kunene eka array . Endlelo leri ri phindha-phindhiwa ka mune loko loop yi nga si hela. a b kahle-kahle ntikelo wun’we c Vectorisation swi vula ku tirhisiwa ka tirhejisitara to hlawuleka ta CPU – tirhejisitara ta vector kumbe SIMD (single instruction multiple data), na swiletelo swa CPU leswi fambelanaka ku endla matirhelo eka mimpimo yo tala ya array hi nkarhi wun’we: Hi leswi leswi humelelaka. CPU yi layicha mimpimo ya ti-array na ku suka eka memori eka tirhejisitara ta CPU (hambiswiritano eka nkarhi lowu, rhijisitara rin’we ra vector ri nga khoma mimpimo ya ti-array ). Kutani CPU yi endla ntirho wo engetela vector eka tirhejisitara leti naswona yi tsala mbuyelo wu tlhelela eka memori leyikulu – kunene eka array . Hikwalaho ka leswi hi tirhaka hi mimpimo yimbirhi hi nkarhi wun’we, endlelo leri ri phindha-phindhiwa kambirhi ematshan’weni ya mune. a b timbirhi c Ku tirhisa vectorisation eka .NET hi nga tirhisa – na tinxaka (hi nga tlhela hi tirhisa tinxaka ku suka eka namespace, hambiswiritano ti le mahlweninyana eka ku tirhisiwa ka sweswi, hikwalaho a ndzi nge ti tirhisi, kambe titwa ntshunxekile ku ti ringeta hi wexe): Vector Vector System.Runtime.Intrinsics public void SpartialVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k (matrix[i * sz + k]); var j = 0; for (; j .Count; j += Vector .Count) { var ij_vec = new Vector (matrix, i * sz + j); var ikj_vec = new Vector (matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector (-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j distance) { matrix[i * sz + j] = distance; } } } } } Khodi ya vectorised yi nga languteka yi ri bizarre nyana, kutani a hi hundzeni eka yona hi goza hi goza. Hi tumbuluxa vector ya ndlela: . Hikwalaho ka sweswo, loko vector yi nga khoma mimpimo ya mune ya muxaka na ntiko wa path wu ringana na 5, hi ta tumbuluxa vector ya mune wa 5’s – [5, 5, 5, 5]. Endzhaku ka sweswo, eka ku vuyeleriwa kun’wana na kun’wana, hi nkarhi wun’we hi hlayela tindlela ku suka eka vertex ku ya eka vertexes . i ⭢ k var ik_vec = new Vector (matrix[i * sz + k]) int i ⭢ k i j, j + 1, ..., j + Vector .Count Property yi vuyisa nhlayo ya swiaki swa muxaka leswi nghenaka eka tirhejisitara ta vector. Vukulu bya tirhejisitara ta vector byi titshege hi modele wa CPU, kutani nhundzu leyi yi nga vuyisa mimpimo yo hambana eka ti CPU to hambana. Vector .Count int - Xitsundzuxo xa mutsari Endlelo hinkwaro ra xibalo ri nga avanyisiwa hi magoza manharhu: Layicha vuxokoxoko ku suka eka matiriki ya ntiko eka tivekitara: na . ij_vec ikj_vec Fanisa ti vector ta na kutani u hlawula mimpimo leyintsongo swinene eka vector leyintshwa . ij_vec ikj_vec r_vec Tsala endzhaku eka matiriki ya ntiko. r_vec Loko na ti ri leti kongomeke swinene, yi lava nhlamuselo. Hilaha swi boxiweke hakona eku sunguleni, hi ti vector hi manipulate mimpimo yo tala hi nkarhi wun’we. Hikwalaho, mbuyelo wa matirhelo man’wana a wu nge vi wun’we i.e., ntirho wo pimanisa a wu nge vuyisi kumbe hikuva wu pimanisa mimpimo yo tala. Kutani ematshan’wini ya sweswo yi vuyisa vector leyintshwa leyi nga na mbuyelo wo pimanisa exikarhi ka mimpimo leyi fambelanaka ku suka eka ti vector na ( , loko ntikelo ku suka eka wu ri ehansi ka ntikelo ku suka eka na loko swi nga ri tano). Vector leyi vuyiseriweke (hi yoxe) a yi pfuni ngopfu, hambiswiritano, hi nga tirhisa ntirho wa vector ku humesa mimpimo leyi lavekaka eka ti vector ta na eka vector leyintshwa – . Ntirho lowu wu vuyisa vector leyintshwa laha mimpimo yi ringanaka na yitsongo eka mimpimo yimbirhi leyi fambelanaka ya ti vectors to nghenisa i.e., loko ntikelo wa vector wu ringana na , kutani ntirho wu hlawula ntikelo ku suka eka , handle ka sweswo wu hlawula ntikelo ku suka eka . #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 Handle ka , ku na xiphemu xin’we xin’wana, lexi lavaka nhlamuselo – xa vumbirhi, lexi nga vekiwangiki vector. Swi laveka loko sayizi ya matiriki ya ntiko yi nga ri xiendliwa xa value. Eka xiyimo xexo xirhendzevutani lexikulu a xi nge swi koti ku tirhisa mimpimo hinkwayo (hikuva a wu nge swi koti ku layicha xiphemu xa vector) naswona xa vumbirhi, lexi nga vekiwangiki, xirhendzevutani xi ta hlayela ku vuyeleriwa loku saleke. #2 Vector .Count Hi lowu mbuyelo wa leswi na ku tirhisiwa hinkwako ka khale: Ndlela sz Vula Xihoxo StdDev Vuxaka Xisekelo xa le henhla 300 27.525 ms 0,1937 ms 0.1617 ms 1.00 Ku antswisiwa ka xiphemu 300 12.399 ms 0.0943 ms 0,0882 ms 0.45 SpartialParallelKu antswisiwa ka swilo 300 6.252 ms 0.0211 ms 0.0187 ms 0.23 SpartialVectorKu antswisiwa ka swilo 300 3.056 ms 0.0301 ms 0.0281 ms 0.11 Xisekelo xa le henhla 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 Ku antswisiwa ka xiphemu 600 99.122 ms 0.8230 ms 0.7698 ms 0.45 SpartialParallelKu antswisiwa ka swilo 600 35.825 ms 0.1003 ms 0.0837 ms 0.16 SpartialVectorKu antswisiwa ka swilo 600 24.378 ms 0.4320 ms 0.4041 ms 0.11 Xisekelo xa le henhla 1200 1 763.335 ms 7.4561 ms 6.2262 ms 1.00 Ku antswisiwa ka xiphemu 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelKu antswisiwa ka swilo 1200 248.801 ms 0.6040 ms 0.5043 ms 0.14 SpartialVectorKu antswisiwa ka swilo 1200 185.628 ms 2.1240 ms 1.9868 ms 0.11 Xisekelo xa le henhla 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 Ku antswisiwa ka xiphemu 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelKu antswisiwa ka swilo 2400 2,076.403 wa ms 20.8320 ms 19.4863 ms 0.14 SpartialVectorKu antswisiwa ka swilo 2400 2 568.676 wa ti ms 31.7359 ms 29.6858 ms 0.18 Xisekelo xa le henhla 4800 119,768.219 wa timis 181.5514 ms 160.9406 ms 1.00 Ku antswisiwa ka xiphemu 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelKu antswisiwa ka swilo 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 SpartialVectorKu antswisiwa ka swilo 4800 18,257.991 wa ms 84.5978 ms 79.1329 ms 0.15 Kusuka eka mbuyelo swile rivaleni, vectorisation yihungute swinene nkarhi wa xibalo – kusuka eka 3 kuya eka 4 wa minkarhi loko ku pimanyisiwa na non-parallelised version ( ). Nkarhi wo tsakisa laha, hileswaku vectorised version yitlhela yi tlula parallel version ( ) eka tigirafu letintsongo (ehansi ka 2400 wa ti vertexes). SpartialOptimisation SpartialParallelOptimisations Naswona xo hetelela kambe ku nga ri xo hetelela – a hi hlanganiseni vectorisation na parallelism! Loko u tsakela ku tirhisiwa loku tirhaka ka vectorisation, ndzi ku ringanyeta ku hlaya nxaxamelo wa ti post hi laha a nga vectorised (mimbuyelo leyi endzhaku yi tikume yi ri eka update ya Garbage Collector eka ). Dan Shechter Array.Sort .NET 5 Tiva pulatifomo ya wena na hardware – vectorisation na parallelism! Ku tirhisiwa ko hetelela ku hlanganisa matshalatshala ya parallelisation na vectorisation naswona ... ku vula ntiyiso swi pfumala vumunhu 🙂 Hikuva... kahle kahle, hi ha ku siva miri wa ku suka eka hi vectorised loop ku suka eka : Parallel.For SpartialParallelOptimisations SpartialVectorOptimisations public void SpartialParallelVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k { if (matrix[i * sz + k] == NO_EDGE) { return; } var ik_vec = new Vector (matrix[i * sz + k]); var j = 0; for (; j .Count; j += Vector .Count) { var ij_vec = new Vector (matrix, i * sz + j); var ikj_vec = new Vector (matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector (-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j distance) { matrix[i * sz + j] = distance; } } }); } } Vuyelo hinkwabyo bya post leyi byi nyikeriwile laha hansi. Tani hilaha swi languteriweke hakona, ku tirhisiwa ka parallelism na vectorisation hi nkarhi wun’we swi kombisile mbuyelo wa kahle swinene, leswi hunguteke nkarhi wa xibalo ku fika eka 25 wa minkarhi (eka tigirafu ta 1200 wa ti vertexes) loko ku pimanisiwa na ku tirhisiwa ko sungula. Ndlela sz Vula Xihoxo StdDev Vuxaka Xisekelo xa le henhla 300 27.525 ms 0,1937 ms 0.1617 ms 1.00 Ku antswisiwa ka xiphemu 300 12.399 ms 0.0943 ms 0,0882 ms 0.45 SpartialParallelKu antswisiwa ka swilo 300 6.252 ms 0.0211 ms 0.0187 ms 0.23 SpartialVectorKu antswisiwa ka swilo 300 3.056 ms 0.0301 ms 0.0281 ms 0.11 SpartialParallelVectorKu antswisiwa ka swilo 300 3.008 ms 0.0075 ms 0,0066 ms 0.11 Xisekelo xa le henhla 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 Ku antswisiwa ka xiphemu 600 99.122 ms 0.8230 ms 0.7698 ms 0.45 SpartialParallelKu antswisiwa ka swilo 600 35.825 ms 0.1003 ms 0,0837 ms 0.16 SpartialVectorKu antswisiwa ka swilo 600 24.378 ms 0.4320 ms 0.4041 ms 0.11 SpartialParallelVectorKu antswisiwa ka swilo 600 13.425 ms 0.0319 ms 0,0283 ms 0.06 Xisekelo xa le henhla 1200 1 763.335 ms 7.4561 ms 6.2262 ms 1.00 Ku antswisiwa ka xiphemu 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelKu antswisiwa ka swilo 1200 248.801 ms 0.6040 ms 0.5043 ms 0.14 SpartialVectorKu antswisiwa ka swilo 1200 185.628 ms 2.1240 ms 1.9868 ms 0.11 SpartialParallelVectorKu antswisiwa ka swilo 1200 76.770 ms 0.3021 ms 0.2522 ms 0.04 Xisekelo xa le henhla 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 Ku antswisiwa ka xiphemu 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelKu antswisiwa ka swilo 2400 2,076.403 wa ms 20.8320 ms 19.4863 ms 0.14 SpartialVectorKu antswisiwa ka swilo 2400 2 568.676 wa ti ms 31.7359 ms 29.6858 ms 0.18 SpartialParallelVectorKu antswisiwa ka swilo 2400 1 281.877 ms 25.1127 ms 64.8239 ms 0.09 Xisekelo xa le henhla 4800 119,768.219 wa timis 181.5514 ms 160.9406 ms 1.00 Ku antswisiwa ka xiphemu 4800 55,590.374 wa ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelKu antswisiwa ka swilo 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 SpartialVectorKu antswisiwa ka swilo 4800 18,257.991 wa ms 84.5978 ms 79.1329 ms 0.15 SpartialParallelVectorKu antswisiwa ka swilo 4800 12 785.824 wa ti ms 98.6947 ms 87.4903 ms 0.11 Mahetelelo Eka post leyi hi nghene nyana eka xiphiqo xa ndlela yo koma ya ti-pair hinkwato naswona hi tirhise algorithm ya Floyd-Warshall eka C # ku xi tlhantlha. Hi tlhele hi pfuxeta ku tirhisiwa ka hina ku xixima datha na ku tirhisa swihlawulekisi swa xiyimo xa le hansi swa .NET na hardware. Eka post leyi hi tlangile “all in”. Kambe, eka switirhisiwa swa vutomi bya xiviri i swa nkoka ku tsundzuka – a hi hexe. Hardcore parallelisation yinga onha swinene matirhelo ya sisiteme naswona yivanga khombo rotala kutlula leswinene. Vectorisation hi tlhelo rin’wana yi hlayisekile nyana loko yi endliwa hi ndlela yo tiyimela hi yoxe ya platform. Tsundzuka swin’wana swa swiletelo swa vector swi nga kumeka ntsena eka ti-CPU to karhi. Ndza tshemba leswaku u tiphinile hi ku hlaya naswona u tiphinile hi ku “squeezing” swiphemu swin’wana swa matirhelo ku suka eka algorithm leyi nga na swirhendzevutana SWIMBIRHI ntsena 🙂 Swikombo Floyd, RW Algorithm 97: Ndlela yo koma swinene / RW Floyd // Vuhlanganisi bya ACM. – 1962. – Vhol. 5, No. 6. – Tluka 345-. Ingerman, PZ Algorithm 141: Matiriki ya ndlela / PZ Ingerman // Vuhlanganisi bya ACM. – 1962. – Vhol. 5, No. 11. – Tluka ra 556.