Előtag összege

A számítástechnikában az előtag összege , kumulatív összege , inkluzív letapogatás , vagy csak egy x0, x1, x2, ... számsorozat letapogatása y0, y1, y2, ... számsorozat, amely egy előtag összege a beviteli sorozatból:

y0 = x0 _ _ y 1 = x 0 + x 1 y 2 \ u003d x 0 + x 1 + x 2 …

Például a természetes számok előtag összegei háromszög alakú számok :

beírni a számokat	egy	2	3	négy	5	6	…
előtag összege	egy	3	6	tíz	tizenöt	21	…

Az előtag összegei triviálisak a szekvenciális számítási modellekben az y i = y i − 1 + x i képlet alkalmazásával az egyes kimeneti értékek szekvenciális sorrendben történő kiszámításához. Annak ellenére azonban, hogy számításilag egyszerűek, az előtag összegei hasznos primitívek egyes algoritmusokban, mint például a counting sort , [1] [2] , és ezek képezik a funkcionális programozási nyelvek magasabb rendű letapogatási függvényének alapját . Az előtag összegeit párhuzamos algoritmusokban is alaposan tanulmányozták , mind megoldandó tesztproblémaként, mind hasznos primitívként más párhuzamos algoritmusok szubrutinjaként. [3] [4] [5]

Elméletileg az előtag összegéhez csak a ⊕ bináris asszociatív operátorra van szükség , ami számos algoritmusban hasznossá teszi, a jól elkülönített páronkénti pontbontások kiszámításától a karakterlánc-feldolgozásig. [6] [7]

Matematikailag az előtag összegek felvételének művelete végestől végtelen sorozatig általánosítható; ebben az értelemben az előtag összege sorozatrészösszegként ismert . Az előtag összegzése vagy részleges összegzése véges vagy végtelen sorozatok vektortereire lineáris leképezést képez ; inverz operátoraik véges különbségek.

Magasabb sorrendű funkció beolvasása

Funkcionális programozási szempontból az előtag összege általánosítható bármely bináris műveletre (nem csak az összeadási műveletre ); az ebből az általánosításból származó magasabb rendű függvényt pásztázásnak nevezzük , és ez szorosan összefügg a konvolúciós művelettel . Mind a vizsgálati, mind az összehasonlítási műveletek egy adott bináris műveletet ugyanarra az értéksorozatra alkalmaznak, de abban különböznek, hogy a vizsgálat a bináris művelet teljes eredménysorát adja vissza, míg a fold csak a végeredményt adja vissza. Például faktorszámok sorozata előállítható természetes számok pásztázásával összeadás helyett szorzással:

beírni a számokat	egy	2	3	négy	5	6	…
előtag értékek	egy	2	6	24	120	720	…

Befogadó és exkluzív szkennelések

A szkennelés nyelvi és könyvtári megvalósítása lehet inkluzív vagy exkluzív . Az inkluzív letapogatás az y i kimenet kiszámításakor tartalmazza az x i bemenetet ( ), míg a kizárólagos vizsgálat nem ( ). Az utóbbi esetben az implementációk vagy meghatározatlanul hagyják az y 0 értéket, vagy elfogadnak egy speciális " x -1 " értéket, amellyel elindítják a keresést. Az exkluzív szkennelés általánosabb abban az értelemben, hogy az inkluzív vizsgálat mindig megvalósítható exkluzív vizsgálatként (az x i és az y i utólagos kombinálásával ), de a kizárólagos vizsgálat nem mindig valósítható meg inkluzív vizsgálatként, mint pl. a maximális előtag összegének esete . ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j))$ ${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j))$

Az alábbi táblázat példákat sorol fel a több programozási nyelv és könyvtár által biztosított átfogó és exkluzív szkennelési funkciókra:

Nyelvek/könyvtárak	Inclusive Scan	Exkluzív szkennelés
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Rozsda	scan Archiválva : 2021. június 6. a Wayback Machine -nél

Párhuzamos algoritmusok

Két kulcsfontosságú algoritmus létezik az előtag összegének párhuzamos kiszámítására. Az első módszer kisebb mélységet és nagyobb párhuzamosítási hajlandóságot jelent , de ez a módszer nem elég hatékony. A második lehetőség hatékonyabb, de kétszeres mélységet igényel, és kevesebb lehetőséget kínál a párhuzamosításra. Az alábbiakban mindkét algoritmust bemutatjuk.

1. algoritmus: kisebb mélység, hajlamosabb a párhuzamosításra

Hillis és Steele a következő párhuzamos előtag-összeg algoritmust mutatja be: [8]

tennivalóért _ _

0-t kapok

\lceil \log _{2}n\rceil -1

párhuzamosan tenni _

j\gets 0

n-1

ha akkor

j<2^{i}

{\displaystyle x_{j}^{i+1}\gets x_{j}^{i))

más

x_{j}^{i+1}\gets x_{j}^{i}+x_{j-2^{i}}^{i}

A jelölés az x tömb j -edik elemének értékét jelenti az i lépésben . ${\displaystyle x_{j}^{i))$

Adott n processzornak, hogy a belső hurok minden iterációját állandó időben teljesítse, az algoritmus O (log n ) idő alatt fut.

2. algoritmus: hatékony

Egy hatékony párhuzamos előtag összegszámítási algoritmus a következő módon valósítható meg: [3] [9] [10]

Számítsa ki azon egymást követő elempárok összegét, amelyekben a pár első elemének páros indexe van: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 stb.
Számítsa ki rekurzívan a z 0 , z 1 , z 2 , ... sorozat w 0 , w 1 , w 2 , ... előtag összegét
Fejezzük ki az y 0 , y 1 , y 2 , ... sorozat minden tagját e közbenső sorozatok legfeljebb két tagjának összegeként: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 stb. Az első kivételével y i minden értékét úgy számítjuk ki, hogy a w sorozatban lévő pozíció feléből másoljuk , vagy hozzáadjuk az x sorozat értékét az előző értékhez. y-1 i .

Ha a bemeneti szekvencia n méretű, akkor a rekurzió O (log n ) mélységig folytatódik , amit ennek az algoritmusnak a párhuzamos végrehajtási ideje is korlátoz. Az algoritmusműveletek száma O ( n ) , és aszimptotikus lassulás nélkül megvalósíthatók egy absztrakt párhuzamos osztott memóriás (PRAM) számítógépen O ( n /log n ) processzorral , ha algoritmusváltozatokban minden processzorhoz több indexet rendelünk, amelyekhez több elem van, mint processzor. [3]

Algoritmusok összehasonlítása

Az előző algoritmusok mindegyike O (log n ) -ban fut . Az előbbi azonban pontosan log 2 n lépést tesz meg, míg az utóbbi 2 log 2 n − 2 lépést. A bemutatott 16 bemenetes példák esetében az 1. algoritmus 12-párhuzamos (49 munkaegység osztva 4-gyel), míg a 2. algoritmus csak 4-párhuzamos (26 munkaegység osztva 6-tal). Azonban a 2. algoritmus munkahatékony, csak egy állandó tényezőt (2) hajt végre a szekvenciális algoritmus által igényelt munkamennyiségből, az 1. algoritmus pedig nem hatékony, aszimptotikusan több munkát végez (logaritmikus tényező), mint amennyi szekvenciálisan szükséges. Ezért az 1. algoritmus előnyösebb, ha nagyszámú párhuzamos folyamat lehetséges, ellenkező esetben a 2. algoritmus élvez elsőbbséget.

Az előtagösszegekre vonatkozó párhuzamos algoritmusok gyakran általánosíthatók más asszociatív bináris letapogatási műveletekre, [3] [4] , és hatékonyan kiszámolhatók modern párhuzamos hardvereken, például a GPU -n (Graphics Processing Unit). [11] Uzi Vishkin szabadalmaztatta a többparaméteres előtag összegének kiszámítására tervezett hardver funkcionális blokk létrehozásának ötletét . [12]

Számos párhuzamos megvalósítás kétlépcsős eljárást használ, amelyben a részleges előtag összegét az első szakaszban számítják ki minden egyes feldolgozóegységhez; ezeknek a részösszegeknek az előtag összegét azután kiszámítják és visszacsatolják a feldolgozó egységekhez a második lépéshez, a ma ismert előtagot használva magértékként. Aszimptotikusan ez a módszer körülbelül két olvasást és egy írást vesz igénybe minden elemhez.

Algoritmusok implementációi előtag összegek kiszámításához

Az előtag-összeg párhuzamos számítási algoritmusának megvalósításánál, más párhuzamos algoritmusokhoz hasonlóan, figyelembe kell venni a platform párhuzamosítási architektúráját . Számos olyan algoritmus létezik, amely a megosztott memóriaplatformokhoz igazodik , valamint olyan algoritmusok, amelyek jól illeszkednek az elosztott memóriaplatformokhoz , miközben az üzenetküldést használják a folyamatok közötti kommunikáció egyetlen formájaként.

Megosztott memória: kétszintű algoritmus

A következő algoritmus egy megosztott memóriagép modellt feltételez ; minden PE feldolgozó elem (az angol feldolgozó elemekből) ugyanahhoz a memóriához fér hozzá. Ennek az algoritmusnak egy változata a Multicore Standard Template Library-ben (MCSTL) [13] [14] valósult meg, amely a C++ Standard Template Library párhuzamos megvalósítása , amely adaptált változatokat biztosít különböző algoritmusok párhuzamos számításaihoz.

Az adatelemek és a feldolgozóelemek előtag összegének egyidejű kiszámításához az adatokat blokkokra osztjuk, amelyek mindegyike tartalmaz elemeket (az egyszerűség kedvéért feltételezzük, hogy osztható -vel ). Felhívjuk figyelmét, hogy bár az algoritmus blokkokra osztja az adatokat , csak a feldolgozó elemek működnek párhuzamosan. $n$ $p$ $p+1$ ${\frac {n}{p+1}}$ $n$ $p+1$ $p+1$ $p$

Az első ciklusban minden PE kiszámol egy helyi előtag összegét a blokkjához. Az utolsó blokkot nem kell kiszámítani, mivel ezek az előtag összegek csak a következő blokkok előtagösszegeinek eltolásaként kerülnek kiszámításra, és az utolsó blokk értelemszerűen nem megfelelő.

Az egyes blokkok utolsó pozíciójában tárolt eltolásokat a rendszer a saját előtag összegében gyűjti, és a következő pozíciókban tárolja. Ha kicsi, akkor a szekvenciális algoritmus elég gyorsan fut, nagyoknál ez a lépés párhuzamosan is végrehajtható. $p$ $p$ $p$

Most térjünk át a második ciklusra. Ezúttal az első blokkot nem kell feldolgozni, mivel nem kell figyelembe vennie az előző blokk eltolását. Most azonban az utolsó blokk is bekerült, és az egyes blokkokhoz tartozó előtagösszegeket az előző ciklusban kiszámított előtagösszeg blokkok eltolásai alapján számítják ki.

function prefix_sum ( elemek ) { n := méret ( elemek ) p := feldolgozó elemek száma prefix_sum : = [ 0 .. .0 ] n méretű _ párhuzamos i = 0 - p - 1 { // i := az aktuális PE indexe j = i * n / ( p + 1 ) - ( i + 1 ) * n / ( p + 1 ) - 1 do { // A helyi blokkok előtag összege itt tárolódik store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 for i = 1 to p { x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Előtag összegének felépítése az első p blokkra prefix_sum [ i * n / ( p + 1 )] = x / / Eredmények mentése eltolásként való használatra a második ciklusban } párhuzamos i = 1 - p { // i := az aktuális PE indexe j = i * n / ( p + 1 ) - ( i + 1 ) * n / ( p + 1 ) - 1 do { eltolás : = prefix_sum [ i * n / ( p + 1 )] // Az előtag összegének kiszámítása az előző blokkok összegének eltolásaként store_prefix_sum_with_offset_in ( elemek , eltolás , előtag_összeg ) } } return prefix_sum } Elosztott memória: A hiperkocka algoritmus

A hypercube prefix sum algoritmus [15] jól adaptálható elosztott memória platformokhoz , és üzenetcserét használ a feldolgozó elemek között. Feltételezzük, hogy az algoritmus a -dimenziós hiperkocka sarkainak számával egyenlő PE-t tartalmaz . ${\displaystyle p=2^{d))$ $d$

Az algoritmus során minden PE-t egy hipotetikus hiperkocka sarokként kezelünk, a közös előtag összegének ismeretében , valamint az összes elem előtag összegét egészen önmagáig (a PE-k közötti rendezett indexek szerint), mindegyik a sajátjában. hiperkocka. $\sigma$ $x$

Az algoritmus abból a feltételezésből indul ki, hogy minden PE egy nulla dimenziós hiperkocka egyetlen sarka, és ezért egyenlő a saját elemei lokális előtagjának összegével. $\sigma$ $x$
Az algoritmus az egyik dimenzióban szomszédos hiperkockák összevonásával folytatódik. Minden egyesítés során a két hiperkocka között kicserélődik és összeadódik, ami megőrzi azt az invariánst, hogy az új hiperkocka sarkaiban lévő összes PE az összevont hiperkocka közös előtag összegét a változójában tárolja . Ezt azonban csak a magasabb indexű PE-ket tartalmazó hiperkocka adja hozzá a lokális változójához , miközben megtartja az invariánst. csak az összes olyan elem előtag összegének értékét tárolja a PE-ben, ahol az indexek kisebbek vagy egyenlőek, mint a saját indexük. $\sigma$ $\sigma$ $\sigma$ $x$ $x$

A PE sarkokkal rendelkező -dimenziós hiperkockában az algoritmust egyszer meg kell ismételni , hogy a nulla dimenziós hiperkockák egydimenziós hiperkockává egyesüljenek. Feltételezve egy duplex kommunikációs modellt , amelyben a különböző hiperkockákban lévő két szomszédos PE mindkét irányban felcserélhető egy kommunikációs lépésben, ez azt jelenti, hogy a kommunikáció elindul. $d$ ${\2. megjelenítési stílus^{d))$ $d$ ${\2. megjelenítési stílus^{d))$ $d$ $\sigma$ $d=\log _{2}p$

i : = Saját processzorelem indexe ( PE ) m : = e PE helyi elemeinek előtag összege d : = a hiperkocka méreteinek száma _ _ _ _ x = m ; // Invariáns: PE előtag összege az aktuális beágyazott kockában σ = m ; // Invariáns: az aktuális alkocka összes elemének előtag összege for ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Az ellentétes részkocka teljes előtag összegének lekérése a k dimenzióhoz képest σ = σ + y / / Összegzési előtag mindkét beágyazott kocka összege if ( i & 2 ^ k ){ x = x + y // Egy másik beágyazott kockából származó előtag összegének összegzése csak akkor, ha ez a PE magasabb index } } Nagy üzenetméretek: csővezetékes bináris fa

A Binary Tree Pipeline Algorithm [16] egy másik algoritmus elosztott memóriaplatformokhoz, amely különösen alkalmas nagy üzenetméretekhez.

A hiperkocka algoritmushoz hasonlóan ez is egy speciális kommunikációs struktúrát feltételez. A PE-k hipotetikusan egy bináris fában (pl. Fibonacci-fában) helyezkednek el, a PE-ben lévő indexüknek megfelelő infix számozással . Egy ilyen fában a kommunikáció mindig a szülő és a gyermek csomópontok között történik.

Az infix számozás biztosítja, hogy bármely adott PE j esetén a bal oldali részfa által elérhető összes csomópont indexe kisebb legyen, mint , és a jobb oldali részfa összes csomópontjának indexe nagyobb legyen, mint . A szülő indexe nagyobb, mint a PE j részfa bármelyik indexe, ha PE j a bal gyermek, és kisebb, mint a PE j részfa bármelyik indexe . Ez lehetővé teszi a következő érvelést: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

A bal oldali részfa helyi előtag összegét kombinálni kell a PE j helyi előtag összegének kiszámításához . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
A jobb oldali részfa helyi előtag összegét össze kell kapcsolni, hogy kiszámítsuk a bal oldali gyermeket (jelentése ) tartalmazó útvonalon elért magasabb szint PE h helyi előtagjának összegét. $\mathbb {\oplus [j+1..r]}$ $h>j$
A PE j összes előtagja szükséges a jobb oldali részfában (pl . a részfa legmagasabb indexű csomópontjához) lévő előtag összegének kiszámításához . $\mathbb {\oplus [0..j]}$ $\mathbb {\oplus [0..j..r]}$
A PE j -nek tartalmaznia kell annak az első magasabb rendű csomópontnak a közös előtag összegét, amelyet egy növekvő útvonalon ér el, amely magában foglalja a jobb gyermekek összekapcsolását, hogy kiszámítsa a közös előtag összegét. $\mathbb {\oplus [0..l-1]}$

Jegyezze meg a különbséget a részfa-helyi és az általános előtag összege között. A kettes, három és négyes pont körkörös függőséget hozhat létre, de nem. Az alsó szintű PE-k megkövetelhetik a felső szintű PE-k teljes előtag összegét a közös előtag összegének kiszámításához, de a felső szintű PE-k csak a részfa helyi előtagjának összegét igénylik a közös előtag összegének kiszámításához. A gyökércsomópontnak, mint a legmagasabb szintű csomópontnak csak a bal oldali részfájának helyi előtagjának összegére van szüksége a saját előtag összegének kiszámításához. A PE 0 -tól a gyökér PE-ig tartó úton minden PE-nek csak a bal oldali részfájának helyi előtagjának összegére van szüksége a saját előtag összegének kiszámításához, míg a PE p-1- től (utolsó PE) a PE gyökérig tartó úton minden csomópontnak szüksége van a teljes összegre. szülőjének előtag összege, hogy kiszámítsa saját teljes előtag összegét.

Ez egy kétfázisú algoritmushoz vezet:

Növekvő fázis
Egy részfa helyi előtag összegét terjeszti a szülőjére minden PE j esetén . $\mathbb {\oplus [l..j..r]}$

Lefelé irányuló fázis A PE j címzett részfájában nem szereplő összes alacsonyabb indexű PE
kizárólagos (kizárólagos PE j , valamint a bal oldali részfájában lévő PE) előtag összegének terjesztése a bal oldal alsóbb szintjén lévő PE-kre. a PE j gyermek részfája . A ⊕ [0…j] előtag összegének kiterjesztése a megfelelő gyermek részfára, PE j . $\mathbb {\oplus [0..l-1]}$

Érdemes megjegyezni, hogy az algoritmus minden PE-n végrehajtódik, és a PE-k megvárják, amíg az összes gyermek/szülő összes csomagja megérkezik.

k := csomagok száma egy üzenetben egy PE m @ { left , right , parent , this } : = // Üzenetek különböző PE - knek x = m @ ezt // Felfelé irányuló fázis - Helyi részfa előtag összegének kiszámítása j = 0 -tól k - 1 -ig : // Csővezeték: üzenetsorozatonként , ha hasLeftChild : blokkolja a fogadást m [ j ] @ left // Helyi m[j] lecserélése vett m[ j-re ] // Kumulatív, inkluzív helyi előtag összege alacsonyabb indexű PE- kből x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : blokkolja a fogadást m [ j ] @ right // Nem egyesítjük az m[j]-et egy helyi előtag összegébe, mivel a megfelelő gyermekek magasabb indexű PE - k küldik x [ j ] ⨁ m [ j ] szülőnek else : küldés x [ j ] a szülőnek // Lefelé irányuló fázis j = 0 - tól k - 1 -ig : m [ j ] @ ez = 0 if hasParent : blokkolja a fogadást m [ j ] @ szülő // A bal oldali gyermeknél m[j] a szülő kizárólagos előtag összege, a jobb oldali gyermek esetében a bezáró előtag összege x [ j ] = m [ j ] ⨁ x [ j ] m [ j ] küldése balra // Az összes PE teljes előtag összege, amely kisebb, mint ez vagy a bal oldali részfában lévő bármely PE, x [ j ] küldése jobbra // Az összes PE teljes előtag összege kisebb vagy egyenlő, mint ez a PE Szállítás

A csővezetékezés akkor alkalmazható, ha a hosszüzenet részekre osztható, és a ⨁ operátor mindegyik ilyen részre külön alkalmazható. [16] $m$ $n$ $k$

Ha az algoritmust csővezeték nélkül használjuk, akkor csak két réteg (a küldő PE és a fogadó PE) fut a fában egy adott időpontban, míg a többi PE várakozik. Ha szinteket tartalmazó feldolgozóelemekből álló bináris kiegyensúlyozott fát használunk, akkor az útvonal hossza tól -ig , ami megfelel a nem párhuzamos felfelé irányuló kommunikációs műveletek maximális számának. Hasonlóképpen, a lefelé irányuló linkek is ugyanarra az értékre korlátozódnak. Figyelembe véve a kommunikáció kezdési idejét és a bájt átviteli idejét, azt kapjuk, hogy a fázisok időkorlátosak a nem pipeline átvitelben. Ha részekre osztjuk , amelyek mindegyike tartalmaz elemeket, és külön küldi el őket, az első részt a helyi előtag összegének részeként kell átadni, és ez az idő az utolsó részre érvényes, ha . $p$ $\log _{2}p$ ${\displaystyle PE_{0))$ $PE_{\mathbb {gyökér} }$ $\log _{2}p-1$ $T_{\mathbb {start} }$ $T_{\mathbb {byte} }$ $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ $k$ ${\frac {n}{k))$ $(\log _{2}p-1)(T_{\mathbb {start} }+{\frac {n}{k))\cdot T_{\mathbb {byte} })$ $PE_{\mathbb {gyökér} }$ $k>\log _{2}p$

Más részeken az összes PE párhuzamosan működhet, és minden harmadik interakciós művelet (fogadás a bal oldalon, fogadás jobb oldalon, küldés a szülőnek) csomagot küld a következő szintre, így az egyik fázis elvégezhető az interakciós műveleteknél és mindkettő fázisok együttesen megkövetelik , ami nagyon jó mutatója az üzenet hosszának . $2\log _{2}p-1+3(k-1)$ $(4\cdot \log _{2}p-2+6(k-1))(T_{\mathbb {start} }+{\frac {n}{k))\cdot T_{\mathbb {byte}})$ $n$

Az algoritmus tovább optimalizálható full duplex vagy távközlési kommunikációs modell használatával , valamint az upstream és downstream fázisok átfedésével. [16]

Adatstruktúrák

Ha egy adatkészletet dinamikusan kell frissíteni, akkor az egy Fenwick-fában tárolható . Egy ilyen adatstruktúra nemcsak az előtag összegének logaritmikus időben történő bármely értékének megtalálását teszi lehetővé, hanem a tömb bármely elemének értékének megváltoztatását is. [17] . Mivel az előtag összege kifejezést 1982-ben még nem használták széles körben, megjelent a munka [18] , ahol bevezették a Partial Sum Tree (5.1) nevű adatstruktúrát, amely a Fenwick-fa nevét váltotta fel.

A többdimenziós tömbökön lévő tetszőleges téglalap alakú altömbök összegének kiszámításához az összegzett területek táblázatát egy előtagösszegekre épített adatstruktúra képviseli. Egy ilyen táblázat hasznos lehet képkonvolúciós problémák esetén . [19]

Alkalmazások

A számláló rendezés egy egész számok rendezési algoritmusa , amely a kulcsfrekvencia hisztogram előtag összegét használja a rendezett kimeneti tömbben lévő egyes kulcsok pozíciójának kiszámításához. Lineáris időben fut az elemek számánál kisebb egész kulcsok esetén, és gyakran használják a radix sort részeként , amely egy gyors algoritmus a kevésbé korlátozott nagyságrendű egész számok rendezésére. [egy]

A lista rangsorolása , az a feladat, hogy egy linkelt listát ugyanazt az elemsorozatot tartalmazó tömbbé alakítsunk , felfogható az egyesek sorozatainak előtagösszegeként, majd az egyes elemeket az előtag értékéből származó tömbbeli pozícióhoz illesztjük. összeg. Számos fontos fa probléma megoldható párhuzamos algoritmusokban a lista rangsorolása, az előtag összegei és az Euler-bejárások kombinálásával . [négy]

Az előtagösszegek párhuzamos számítását bináris összeadók , logikai áramkörök fejlesztésében is használják, amelyek két n bites bináris számot tudnak összeadni. Ebben az esetben az összeadás hordozó bitsorozatot pásztázási műveletként lehet ábrázolni bemeneti bitpárok sorozatán, többségi függvény használatával az adott átvitel és a két bit kombinálására. A kimeneti szám minden bitje megtalálható a két bemeneti bit exkluzív diszjunkciójaként , a megfelelő bittördeléssel. Ily módon lehetséges egy olyan összeadó összeállítása, amely O ( n ) kaput és O (log n ) időlépést használ . [3] [9] [10]

A párhuzamos véletlen hozzáférésű számítástechnikai gép modelljében az előtag összegek használhatók olyan párhuzamos algoritmusok modellezésére, amelyek lehetővé teszik több processzor számára, hogy egyidejűleg ugyanazt a memóriahelyet érjék el párhuzamos gépeken, amelyek tiltják az egyidejű hozzáférést. A rendezési hálózaton keresztül egyidejű memória-hozzáférési kérelmek sorba rendezhetők egy sorozatba, így az ugyanahhoz a cellához való hozzáférés a sorozaton belül szomszédos. A letapogatási műveletek ezután felhasználhatók annak meghatározására, hogy a kért cellákhoz való írási hozzáférések közül melyik sikerült, és a memóriaolvasási műveletek eredményeit több processzor között is szétoszthatjuk, amelyek ugyanazt az eredményt kérik. [húsz]

Guy Blallock doktori értekezésében [21] a párhuzamos előtag-műveletek az olyan gépek által biztosított adatpárhuzamossági modell formalizálásának részét képezik , mint a Connection Machine . A Connection Machine CM-1 és CM-2 egy hiperkocka hálózatot biztosított, amelyben a fent említett 1. algoritmus valósítható meg, míg a CM-5 egy hálózatot biztosított a 2. algoritmus megvalósításához. [22]

Gray-kódok , bináris értéksorozatok készítésekor azzal a tulajdonsággal, hogy az egymást követő sorozatok értékei egy bitpozícióban különböznek egymástól, az n szám az n pozícióban lévő Gray-kód értékévé konvertálható egyszerűen az XOR felvételével. n és n /2 (az a szám , amely az n -nek egy bitpozícióval jobbra való eltolásával keletkezik ). A fordított művelet, amely az x Grey-kódolt értékét bináris számmá dekódolja, bonyolultabb, de kifejezhető az x biteinek előtag összegeként , ahol az előtag összegén belüli minden összegműveletet modulo 2 hajtjuk végre. Az ilyen típusú előtagösszeg hatékonyan végrehajtható a modern számítógépeken elérhető bitenkénti logikai műveletek segítségével, ha egy kizárólagos "vagy"-t vagy x -et számítanak ki az x -et két hatványnyi bittel balra eltoló számok mindegyikével .

A párhuzamos előtag (a szorzást fő asszociációs műveletként használva) gyors párhuzamos polinom interpolációs algoritmusok készítésére is használható . Különösen az interpolációs polinom Newton - formájának különbségének osztási együtthatóinak kiszámítására használható. [23] Ez az előtag-alapú megközelítés általánosított osztott különbségek előállítására is használható (konfluens) Hermite-interpolációhoz , valamint párhuzamos algoritmusokhoz Vandermonde -rendszerekhez .

Lásd még

GPGPU

Jegyzetek

↑ 1 2 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. és Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. kiadás), MIT Press és McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Cole, Richard és Vishkin, Uzi (1986), Determinisztikus érmefeldobás az optimális párhuzamos listás rangsoroláshoz , Information and Control 70(1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
↑ 1 2 3 4 5 Ladner, RE & Fischer, MJ (1980), Parallel Prefix Computation , Journal of the ACM 27. kötet (4): 831–838 , DOI 10.1145/322217.322232 .
↑ 1 2 3 Tarjan, Robert E. & Vishkin, Uzi (1985), An efficient parallel biconnectivity algorithm , SIAM Journal on Computing vol. 14 (4): 862–874 , DOI 10.1137/0214061 .
↑ Lakshmivarahan, S. & Dhall, SK (1994), Parallelism in the Prefix Problem , Oxford University Press , ISBN 0-19508849-2 , < https://archive.org/details/parallelcomputin0000laks > .
↑ Blelloch, Guy (2011), Előtagösszegek és alkalmazásaik (előadásjegyzetek) , Carnegie Mellon Egyetem , < https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts /PrefixSumBlelloch.pdf > Archiválva : 2021. június 14. a Wayback Machine -nél .
↑ Callahan, Paul & Kosaraju, S. Rao (1995), A többdimenziós ponthalmazok dekompozíciója k-legközelebbi szomszédokra és n-test potenciálmezőkre történő alkalmazásokkal , Journal of the ACM 42(1): 67– 90 , DOI 10.1145/200836.200853 .
↑ Hillis, W. Daniel; Steele, Jr., Guy L. Párhuzamos adatalgoritmusok // Az ACM kommunikációja . - 1986. - December ( 29. évf. , 12. sz.). - P. 1170-1183 . doi : 10.1145 / 7902.7903 .
↑ 1 2 Ofman, Yu. (1962), Doklady Akademii Nauk SSSR T. 145 (1): 48–51 . Angol fordítás, "On the Algorithmic complexity of discrete functions", Soviet Physics Doklady 7 : 589–591 1963.
↑ 1 2 Khrapchenko, VM (1967), Asymptotic Estimation of Addition Time of a Parallel Adder, Problemy Kibernet. T. 19: 107–122 . Angol fordítás a Syst. Theory Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Primitívek vizsgálata GPU-számításhoz . Proc. 22. ACM SIGGRAPH/EUROGRAPHICS szimpózium a grafikus hardverekről. pp. 97-106. Archiválva az eredetiből , ekkor: 2014-09-03 . Letöltve: 2020-04-21 . Elavult használt paraméter |deadlink=( súgó )
↑ Viskin, Uzi (2003). Előtagösszegek és azok alkalmazása . US 6,542,918 számú szabadalom. Archiválva az eredetiből , ekkor: 2013-05-22 . Letöltve: 2020-04-21 . Elavult használt paraméter |deadlink=( súgó )
↑ Singler, Johannes MCSTL: The Multi-Core Standard Template Library . Letöltve: 2019. március 29. Az eredetiből archiválva : 2016. november 3. (határozatlan)
↑ Singler, Johannes; Sanders, Péter; Putze, Félix. MCSTL: The Multi-core Standard Template Library // Euro-Par 2007 Parallel Processing. - 2007. - T. 4641. - S. 682-694. — (Számítástechnikai előadásjegyzetek). — ISBN 978-3-540-74465-8 . - doi : 10.1007/978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Bevezetés a párhuzamos számítástechnikába . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Péter; Traff, Jesper Larsson. Párhuzamos előtag (Scan) algoritmusok MPI-hez // Legutóbbi fejlesztések a párhuzamos virtuális gépben és az üzenettovábbítási interfészben . - 2006. - Vol. 4192. - P. 49-57. — (Számítástechnikai előadásjegyzetek). - ISBN 978-3-540-39110-4 . - doi : 10.1007/11846802_15 .
↑ Fenwick, Peter M. (1994), Egy új adatstruktúra kumulatív gyakorisági táblákhoz , Software: Practice and Experience , 24. kötet (3): 327–336 , DOI 10.1002/spe.4380240306
↑ Shiloach, Yossi & Vishkin, Uzi (1982b), An O ( n 2 log n ) párhuzamos max-flow algoritmus , Journal of Algorithms 3. kötet (2): 128–146 , DOI 10.1016/0196-6774(82)900 -X
↑ Szeliski, Richard (2010), Summed area table (integral image) , Computer Vision: Algorithms and Applications , Texts in Computer Science, Springer, p. 106–107., ISBN 9781848829350 , < https://books.google.com/books?id=bXzAlkODwa8C&pg=PA106 > .
↑ Vishkin, Uzi (1983), Egyidejű memóriacím-hozzáférés megvalósítása olyan modellekben, amelyek tiltják , Journal of Algorithms 4. kötet (1): 45–50 , DOI 10.1016/0196-6774(83)90033-0 .
↑ Blelloch, Guy E. Vektormodellek adat-párhuzamos számítástechnikához (katalán) . - Cambridge, MA: MIT Press , 1990. - ISBN 026202313X .
↑ Leiserson, Charles E .; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel; Kuszmaul, Bradley C.; Utca. Pierre, Margaret A. A CM-5 kapcsolati gép hálózati architektúrája // Journal of Parallel and Distributed Computing : Journal. - 1996. - március 15. ( 33. köt. , 2. sz.). - P. 145-158 . — ISSN 0743-7315 . - doi : 10.1006/jpdc.1996.0033 .
↑ Eğecioğlu, O.; Gallopoulos, E. & Koç, C. (1990), A párhuzamos módszer a gyors és praktikus nagyrendű Newton-interpolációhoz , BIT Computer Science and Numerical Mathematics 30. kötet (2): 268–288 , DOI 10.1007/BF02017348 .

Linkek

Weisstein, Eric W. Kumulatív összeg a Wolfram MathWorld webhelyen .