Etuliitteen määrä

Tietojenkäsittelytieteessä etuliitteen summa , kumulatiivinen summa , inclusive scan tai pelkkä lukujonon x0, x1, x2, ... skannaus on numerosarja y0, y1, y2, ..., joka on etuliitesumma syöttösekvenssistä:

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

Esimerkiksi luonnollisten lukujen etuliitteiden summat ovat kolmiolukuja :

syötä numerot	yksi	2	3	neljä	5	6	…
etuliitteen summa	yksi	3	6	kymmenen	viisitoista	21	…

Etuliitteiden summat ovat triviaaleja laskea peräkkäisissä laskentamalleissa soveltamalla kaavaa y i = y i − 1 + x i laskemaan jokainen lähtöarvo peräkkäisessä järjestyksessä. Vaikka etuliitesummat ovat laskennallisesti yksinkertaisia, ne ovat kuitenkin hyödyllinen primitiivi joissakin algoritmeissa, kuten counting sort , [1] [2] ja ne muodostavat perustan korkeamman asteen skannausfunktiolle toiminnallisissa ohjelmointikielissä . Etuliitteiden summia on myös tutkittu laajasti rinnakkaisissa algoritmeissa sekä ratkaistavana testiongelmana että hyödyllisenä primitiivinä käytettäväksi alirutiinina muissa rinnakkaisissa algoritmeissa. [3] [4] [5]

Teoreettisesti etuliitesumma vaatii vain binaarisen assosiatiivisen operaattorin ⊕ , mikä tekee siitä hyödyllisen monissa algoritmeissa, hyvin erotettujen parikohtaisten pistehajotelmien laskemisesta merkkijonojen käsittelyyn. [6] [7]

Matemaattisesti etuliitesummien ottaminen voidaan yleistää äärellisistä äärettömiin sarjoihin; tässä mielessä etuliitesumma tunnetaan sarjan osasummana . Etuliitesumma tai osittainen summaus muodostaa lineaarisen kuvauksen äärellisten tai äärettömien sekvenssien vektoriavaruuksiin ; niiden käänteiset operaattorit ovat äärellisiä eroja.

Korkeamman asteen toiminnon skannaus

Toiminnallisen ohjelmoinnin termein etuliitesumma voidaan yleistää mille tahansa binäärioperaatiolle (ei vain yhteenlaskuoperaatiolle ); tästä yleistyksestä johtuvaa korkeamman asteen funktiota kutsutaan skannaukseksi ja se liittyy läheisesti konvoluutiooperaatioon . Sekä skannaus- että vertailuoperaatiot soveltavat tiettyä binäärioperaatiota samaan arvosarjaan, mutta eroavat siinä, että skannaus palauttaa binäärioperaation koko tulossarjan, kun taas fold palauttaa vain lopullisen tuloksen. Esimerkiksi tekijälukujen sarja voidaan luoda skannaamalla luonnollisia lukuja käyttämällä kertolaskua summauksen sijaan:

syötä numerot	yksi	2	3	neljä	5	6	…
etuliitearvot	yksi	2	6	24	120	720	…

Kattavat ja eksklusiiviset skannaukset

Skannauksen kieli - ja kirjastototeutukset voivat olla osallisia tai yksinomaisia . Sisällyttävä skannaus sisältää syötteen x i laskettaessa tulostetta y i ( ), kun taas eksklusiivinen skannaus ei sisällä sitä ( ). Jälkimmäisessä tapauksessa toteutukset joko jättävät y 0 : n määrittelemättä tai hyväksyvät erityisen arvon " x -1 ", jolla skannaus aloitetaan. Eksklusiiviset skannaukset ovat yleisempiä siinä mielessä, että kattava skannaus voidaan aina toteuttaa yksinomaisena skannauksena (yhdistämällä sen jälkeen x i :n kanssa y i ), mutta eksklusiivista skannausta ei aina voida toteuttaa kattavana skannauksena, kuten etuliitteen enimmäissumman tapaus . ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j))$ ${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j))$

Seuraavassa taulukossa on esimerkkejä useiden ohjelmointikielten ja kirjastojen tarjoamista sisältävistä ja yksinomaisista skannausominaisuuksista:

Kielet/kirjastot	Inclusive Scan	Ainutlaatuinen skannaus
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Ruoste	scan Arkistoitu 6. kesäkuuta 2021 Wayback Machinessa

Rinnakkaisalgoritmit

Etuliitteen summan laskemiseen rinnakkain on kaksi avainalgoritmia. Ensimmäinen menetelmä merkitsee vähemmän syvyyttä ja suurempaa rinnakkaustaipumusta , mutta tämä menetelmä ei ole tarpeeksi tehokas. Toinen vaihtoehto on tehokkaampi, mutta vaatii kaksinkertaisen syvyyden ja tarjoaa vähemmän vaihtoehtoja rinnakkaisuudelle. Molemmat algoritmit on esitetty alla.

Algoritmi 1: vähemmän syvyyttä, alttiimpi rinnakkaisuudelle

Hillis ja Steele esittävät seuraavan rinnakkaisen etuliitesumma-algoritmin: [8]

tekemiseen _ _

saan 0

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

tehdä rinnakkain _

j\gets 0

n-1

jos sitten

j<2^{i}

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

muu

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

Merkintä tarkoittaa taulukon x j :nnen alkion arvoa vaiheessa i . ${\displaystyle x_{j}^{i))$

Annettu n prosessoria suorittamaan jokainen sisemmän silmukan iteraatio vakioajassa, algoritmi toimii O (log n ) -ajassa.

Algoritmi 2: tehokas

Tehokas rinnakkaisetuliitesummalaskenta-algoritmi voidaan toteuttaa seuraavalla tavalla: [3] [9] [10]

Laske niiden peräkkäisten alkioparien summat, joissa parin ensimmäisellä alkiolla on parillinen indeksi: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 jne.
Laske rekursiivisesti sekvenssin z 0 , z 1 , z 2 , ... etuliitesumma w 0 , w 1 , w 2 , ...
Ilmaise sekvenssin y 0 , y 1 , y 2 , ... kukin jäsen näiden välisekvenssien enintään kahden jäsenen summana: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 jne. Jokainen y i :n arvo ensimmäistä lukuun ottamatta lasketaan joko kopioimalla kohdasta puolet sekvenssin w kohdasta tai lisäämällä x -jonon arvo edelliseen arvoon y-1 i .

Jos syötesekvenssin koko on n , niin rekursio jatkuu syvyyteen O (log n ) , jota rajoittaa myös tämän algoritmin rinnakkainen suoritusaika. Algoritmioperaatioiden määrä on O ( n ) ja ne voidaan toteuttaa abstraktilla rinnakkaisjaetulla muistilla (PRAM) tietokoneella, jossa on O ( n /log n ) -prosessoreita ilman asymptoottista hidastumista antamalla jokaiselle prosessorille useita indeksejä algoritmimuunnelmissa, joissa on enemmän elementtejä kuin prosessoreita. [3]

Algoritmien vertailu

Jokainen aiemmista algoritmeista toimii O :ssa (log n ) . Edellinen vie kuitenkin tasan log 2 n askelta, kun taas jälkimmäinen vaatii 2 log 2 n − 2 askelta. Esitetyissä 16 syötteisissä esimerkeissä algoritmi 1 on 12-rinnakkais (49 työyksikköä jaettuna 4:llä), kun taas algoritmi 2 on vain 4-rinnakkais (26 työyksikköä jaettuna 6:lla). Algoritmi 2 on kuitenkin työtehokas, se suorittaa vain vakiokertoimen (2) peräkkäisen algoritmin vaatimasta työmäärästä ja algoritmi 1 on tehoton, se suorittaa asymptoottisesti enemmän työtä (logaritminen tekijä) kuin peräkkäin vaaditaan. Siksi Algoritmi 1 on parempi, kun suuri määrä rinnakkaisia prosesseja on mahdollista, muuten algoritmi 2 on etusijalla.

Rinnakkaisalgoritmit etuliitteiden summille voidaan usein yleistää muihin assosiatiivisiin binääriskannaustoimintoihin, [3] [4] , ja ne voidaan myös laskea tehokkaasti nykyaikaisilla rinnakkaislaitteistoilla, kuten GPU :lla (Graphics Processing Unit). [11] Uzi Vishkin patentoi ajatuksen toiminnallisen lohkon luomisesta laitteistoon, joka on suunniteltu laskemaan moniparametrisen etuliitteen summa . [12]

Monet samanaikaiset toteutukset käyttävät kaksivaiheista proseduuria, jossa osaetuliitesumma lasketaan ensimmäisessä vaiheessa kullekin käsittely-yksikölle; näiden osittaisten summien etuliitesumma lasketaan sitten ja syötetään takaisin prosessointiyksiköille toista vaihetta varten käyttämällä nyt tunnettua etuliitettä siemenarvona. Asymptoottisesti tämä menetelmä vaatii noin kaksi lukua ja yhden kirjoituksen jokaista elementtiä kohden.

Algoritmien toteutukset etuliitesummien laskemiseen

Etuliitesumman rinnakkaislaskenta-algoritmin toteutuksessa, kuten muidenkin rinnakkaisten algoritmien, tulee ottaa huomioon alustan rinnakkaisarkkitehtuuri . On monia algoritmeja, jotka on mukautettu jaetuille muistialustoille , samoin kuin algoritmeja, jotka sopivat hyvin hajautetuille muistialustoille , samalla kun viestintää käytetään ainoana prosessien välisen viestinnän muotona.

Jaettu muisti: Kaksitasoinen algoritmi

Seuraava algoritmi olettaa jaetun muistikoneen mallin ; kaikilla prosessointielementeillä PE (englanniksi käsittelyelementeistä) on pääsy samaan muistiin. Tämän algoritmin muunnelma on toteutettu Multicore Standard Template Libraryssa (MCSTL) [13] [14] , C++ Standard Template Libraryn rinnakkaistoteutuksessa, joka tarjoaa mukautettuja versioita eri algoritmien rinnakkaislaskentaan.

Tietoelementtien etuliitesumman laskemiseksi samanaikaisesti prosessointielementtien kanssa tiedot jaetaan lohkoihin, joista jokainen sisältää elementtejä (yksinkertaisuuden vuoksi oletetaan, että se on jaollinen : llä ). Huomaa, että vaikka algoritmi jakaa tiedot lohkoihin, vain käsittelyelementit toimivat rinnakkain. $n$ $s$ $p+1$ ${\frac {n}{p+1}}$ $n$ $p+1$ $p+1$ $s$

Ensimmäisessä silmukassa kukin PE laskee paikallisen etuliitesumman lohkolleen. Viimeistä lohkoa ei tarvitse laskea, koska nämä etuliitesummat lasketaan vain myöhempien lohkojen etuliitesummien poikkeuksina, ja viimeinen lohko ei ole määritelmän mukaan sopiva.

Kunkin lohkon viimeiseen paikkaan tallennetut siirtymät kerätään omaan etuliitteensä summaan ja tallennetaan seuraaviin paikkoihin. Jos se on pieni, peräkkäinen algoritmi toimii riittävän nopeasti; suurille tämä vaihe voidaan suorittaa rinnakkain. $s$ $s$ $s$

Siirrytään nyt toiseen kiertoon. Tällä kertaa ensimmäistä lohkoa ei tarvitse käsitellä, koska sen ei tarvitse ottaa huomioon edellisen lohkon siirtymää. Viimeinen lohko on kuitenkin nyt mukana ja kunkin lohkon etuliitesummat lasketaan käyttämällä edellisessä jaksossa laskettujen etuliitesummalohkojen siirtymiä.

function prefix_sum ( elementit ) { n := koko ( elementit ) p : = prosessointielementtien lukumäärä prefix_sum : = [ 0. . .0 ] kokoa n _ tee rinnakkain i = 0 kohtaan p - 1 { //i := nykyisen PE: n indeksi j = i * n / ( p + 1 ) arvoon ( i + 1 ) * n / ( p + 1 ) - 1 do { // Paikallisten lohkojen etuliitesumma tallennetaan tähän store_prefix_sum_with_offset_in ( elementit , 0 , prefix_sum ) } } x = 0 for i = 1 - p { x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Etuliitteen summan muodostaminen ensimmäisten p lohkojen etuliitesumman päälle [ i * n / ( p + 1 ) ] = x / / Tulosten tallentaminen käytettäväksi siirtymänä toisessa silmukassa } tee rinnakkain i = 1 - p { //i := nykyisen PE: n indeksi j = i * n / ( p + 1 ) - ( i + 1 ) * n / ( p + 1 ) - 1 do { offset : = prefix_sum [ i * n / ( p + 1 )] // Laske etuliitesumma edellisten lohkojen summan offsetina store_prefix_sum_with_offset_in ( elementit , offset , etuliite_summa ) } } palauttaa etuliite_summa } Hajautettu muisti: Hyperkuutio-algoritmi

Hyperkuution etuliitesumma-algoritmi [15] soveltuu hyvin hajautetuille muistialustoille ja käyttää sanomien vaihtoa käsittelyelementtien välillä. Oletetaan, että algoritmi sisältää PE:n, joka on yhtä suuri kuin -ulotteisen hyperkuution kulmien lukumäärä . ${\displaystyle p=2^{d))$ $d$

Algoritmin aikana kutakin PE:tä käsitellään kulmana hypoteettisessa hyperkuutiossa, joka tietää yhteisen etuliitesumman sekä kaikkien elementtien etuliitesumman itseensä asti (PE:iden järjestettävien indeksien mukaan), kukin omaksi. hyperkuutio. $\sigma$ $x$

Algoritmi lähtee olettamuksesta, että jokainen PE on nollaulotteisen hyperkuution ainoa kulma ja on siten yhtä suuri kuin sen omien elementtien paikallisen etuliitteen summa. $\sigma$ $x$
Algoritmi jatkuu yhdistämällä vierekkäiset hyperkuutiot yhdessä ulottuvuudessa. Jokaisen yhdistämisen aikana se vaihdetaan ja summataan kahden hyperkuution välillä, mikä säilyttää invariantin, että kaikki tämän uuden hyperkuution kulmissa olevat PE:t tallentavat yhdistetyn hyperkuution yhteisen etuliitesumman muuttujaansa . Kuitenkin vain hyperkuutio, joka sisältää korkeamman indeksin PE:t, lisää tämän paikallismuuttujaansa säilyttäen samalla invariantin. tallentaa vain etuliitteen summan arvon kaikista PE:n alkioista, joiden indeksit ovat pienempiä tai yhtä suuria kuin heidän oma indeksinsä. $\sigma$ $\sigma$ $\sigma$ $x$ $x$

PE - kulmilla varustetussa -ulotteisessa hyperkuutiossa algoritmi on toistettava kerran, jotta nollaulotteiset hyperkuutiot yhdistetään yksiulotteiseksi hyperkuutioksi. Olettaen duplex-kommunikaatiomallin , jossa kaksi vierekkäistä PE:tä eri hyperkuutioissa voidaan vaihtaa molempiin suuntiin yhdessä viestintävaiheessa, tämä tarkoittaa, että viestintä alkaa. $d$ ${\näyttötyyli 2^{d))$ $d$ ${\näyttötyyli 2^{d))$ $d$ $\sigma$ $d=\log _{2}p$

i : = Oman prosessorielementin ( PE ) indeksi m : = tämän PE : n paikallisten elementtien etuliitesumma d : = hyperkuution mittojen lukumäärä _ _ _ _ x = m ; // Invariantti: PE-etuliitesumma nykyisessä sisäkkäisessä kuutiossa σ = m ; // Invariantti: nykyisen alikuution kaikkien elementtien etuliitesumma for ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Hanki vastakkaisen alikuution kokonaisetuliitesumma ulottuvuudesta k σ = σ + y / / Molempien sisäkkäisten kuutioiden summaetuliite summat if ( i & 2 ^ k ){ x = x + y // Etuliitesumman summaus toisesta sisäkkäisestä kuutiosta vain, jos tämä PE on korkeampi indeksi } } Suuret viestikoot: liukuhihnamuotoinen binaaripuu

Binary Tree Pipeline Algorithm [16] on toinen algoritmi hajautetuille muistialustoille, joka sopii erityisen hyvin suurille viestikokoille.

Kuten hyperkuutio-algoritmi, se olettaa erityisen viestintärakenteen. PE:t sijaitsevat hypoteettisesti binääripuussa (esim. Fibonacci-puussa), jossa on infix-numerointi niiden indeksin mukaisesti PE:ssä. Kommunikaatio tällaisessa puussa tapahtuu aina pää- ja lapsisolmujen välillä.

Infix-numerointi varmistaa, että mille tahansa PE j :lle kaikkien sen vasemman alipuun tavoittamien solmujen indeksit ovat pienempiä kuin , ja oikean alipuun kaikkien solmujen indeksit ovat suurempia kuin . Vanhemman indeksi on suurempi kuin mikään PE j -alipuun indekseistä, jos PE j on vasen lapsi, ja pienempi kuin mikään indeksistä PE j -alipuussa . Tämä mahdollistaa seuraavan päättelyn: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

Vasemman alipuun paikallinen etuliitesumma on yhdistettävä PE j :n paikallisen etuliitesumman laskemiseksi . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
Oikean alipuun paikallinen etuliitesumma on ketjutettava, jotta voidaan laskea vasemman alipuun sisältävän polun (merkitys ) korkeamman tason paikallisen etuliitteen PE h summa . $\mathbb {\oplus [j+1..r]}$ $h>j$
PE j :n etuliitesumma tarvitaan oikean alipuun etuliitteen kokonaismäärän laskemiseen (esim. alipuun korkeimman indeksin solmulle). $\mathbb {\oplus [0..j]}$ $\mathbb {\oplus [0..j..r]}$
PE j :n on sisällettävä ensimmäisen korkeamman asteen solmun yhteinen etuliitesumma, joka saavutetaan nousevalla polulla, johon liittyy oikeiden lapsien liittäminen, jotta sen yhteinen etuliitesumma voidaan laskea. $\mathbb {\oplus [0..l-1]}$

Huomaa ero alipuun paikallisen ja yleisen etuliitesumman välillä. Pisteet kaksi, kolme ja neljä voivat saada ne muodostamaan pyöreän riippuvuuden, mutta eivät. Alemman tason PE:t voivat vaatia ylemmän tason PE:iden kokonaisetuliitesumman laskeakseen yhteisen etuliitesummansa, mutta ylemmän tason PE:t vaativat vain alipuun paikallisen etuliitesumman laskeakseen yhteisen etuliitesummansa. Juurisolmu korkeimman tason solmuna tarvitsee vain vasemman alipuunsa paikallisen etuliitesumman laskeakseen oman etuliitesummansa. Jokainen PE polulla PE 0 :sta PE-juureen tarvitsee vain vasemman alipuunsa paikallisen etuliitesumman laskeakseen oman etuliitesummansa, kun taas jokainen solmu polulla PE p-1 : stä (viimeinen PE) PE - juureen tarvitsee kokonaissumman. emonumeron etuliitesumma laskeakseen oman etuliitesummansa.

Tämä johtaa kaksivaiheiseen algoritmiin:

Nouseva vaihe
Levitä alipuun paikallinen etuliitesumma sen yläpuolelle jokaiselle PE j :lle . $\mathbb {\oplus [l..j..r]}$

Alaspäin oleva vaihe Kaikkien alemman indeksin PE:iden, jotka eivät sisälly PE j:n osoitettuun alipuuhun, eksklusiivisen
(poissulkeva PE j sekä sen vasemmassa alipuussa oleva PE) etuliitteen summan eteneminen vasemmanpuoleisen alempien tasojen PE:ihin. PE j :n lapsialipuu . Laajenna etuliitteen summa ⊕ [0…j] oikeaan alipuuhun PE j . $\mathbb {\oplus [0..l-1]}$

On syytä huomata, että algoritmi suoritetaan jokaisessa PE:ssä ja PE:t odottavat, kunnes kaikki paketit kaikilta lapsilta/vanhemmilta on vastaanotettu.

k := pakettien määrä viestissä m PE: n m @ { vasen , oikea , vanhempi , tämä } : = // Viestit eri PE : ille x = m @ tämä // Ylävirran vaihe - Laske paikallisen alipuun etuliitesumma kohteille j = 0 - k - 1 : // Liukuinti: per viestipurske , jos hasLeftChild : estetään vastaanotto m [ j ] @ vasemmalle // Korvataan paikallinen m[j] vastaanotetulla m[ j ] // Kumulatiivinen, mukaan lukien paikalliset etuliitesummat pienistä indekseistä x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : esto vastaanottaa m [ j ] @ right // Emme yhdistä m[j]:ää paikalliseen etuliitesummaan, koska oikeat lapset ovat korkeampiin indeksoituja PE : itä lähetä x [ j ] ⨁ m [ j ] vanhemmalle else : lähetä x [ j ] vanhemmalle _ // Vaihe alaspäin arvolle j = 0 - k - 1 : m [ j ] @ tämä = 0 if hasParent : esto vastaanottaa m [ j ] @ vanhempi // Vasemmalle lapselle m[j] on vanhemman yksinomaisen etuliitesumma, oikean lapsen etuliitteen summa x [ j ] = m [ j ] ⨁ x [ j ] lähetä m [ j ] vasemmalle // Kaikkien tämän PE:n tai minkä tahansa vasemman alipuun PE:n kokonaissumma lähetä x [ j ] oikealle // Kaikkien PE: iden etuliitteiden kokonaissumma, joka on pienempi tai yhtä suuri kuin tämä PE Välittäminen

Liukutusta voidaan soveltaa, kun pituussanoma voidaan jakaa osiin ja operaattoria ⨁ voidaan soveltaa jokaiseen tällaiseen osaan erikseen . [16] $m$ $n$ $k$

Jos algoritmia käytetään ilman putkistoa, vain kaksi kerrosta (lähettävä PE ja vastaanottava PE) ovat käynnissä puussa kulloinkin, kun taas muut PE:t odottavat. Jos käytetään tasoja sisältävien käsittelyelementtien binaarista tasapainotettua puuta , niin polun pituus on välillä - , mikä vastaa ei-rinnakkaisen ylävirran viestintäoperaatioiden enimmäismäärää. Samoin myös downlink-linkit on rajoitettu samaan arvoon. Kun otetaan huomioon tiedonsiirron alkamisaika ja tavunsiirtoaika, saadaan, että vaiheet ovat aikarajoitettuja ei-liukuhihnasiirrossa. Jaettaessa osiin, joissa jokaisessa on elementtejä ja joka lähettää ne itsenäisesti, ensimmäinen osa on siirrettävä osaksi paikallista etuliitesummaa ja tämä aika on voimassa viimeiselle osalle, jos . $s$ $\log _{2}p$ $PE_{0}$ $PE_{\mathbb {juuri} }$ $\log _{2}p-1$ $T_{\mathbb {aloitus} }$ $T_{\mathbb {tavu} }$ $(2\log _{2}p-2)(T_{\mathbb {aloitus} }+n\cdot T_{\mathbb {tavu} })$ $k$ ${\frac {n}{k))$ $(\log _{2}p-1)(T_{\mathbb {aloitus} }+{\frac {n}{k))\cdot T_{\mathbb {tavu} })$ $PE_{\mathbb {juuri} }$ $k>\log _{2}p$

Muissa osissa kaikki PE:t voivat toimia rinnakkain ja joka kolmas vuorovaikutustoiminto (vastaanota vasemmalla, vastaanota oikealla, lähetä vanhemmalle) lähettää paketin seuraavalle tasolle, joten yksi vaihe voidaan tehdä vuorovaikutusoperaatioille ja molemmille vaiheet yhdessä vaativat , mikä on erittäin hyvä viestin pituuden indikaattori . $2\log _{2}p-1+3(k-1)$ $(4\cdot \log _{2}p-2+6(k-1))(T_{\mathbb {aloitus} }+{\frac {n}{k))\cdot T_{\mathbb {tavu}})$ $n$

Algoritmia voidaan edelleen optimoida käyttämällä full duplex- tai tietoliikennemallia ja päällekkäisiä ylä- ja alavirran vaiheita. [16]

Tietorakenteet

Jos tietojoukko on päivitettävä dynaamisesti, se voidaan tallentaa Fenwick-puuhun . Tällainen tietorakenne mahdollistaa paitsi etuliitesumman minkä tahansa arvon löytämisen logaritmisessa ajassa, myös taulukon elementin arvon muuttamisen. [17] . Koska termiä etuliitesumma ei vielä käytetty laajasti vuonna 1982, ilmestyi teos [18] , jossa otettiin käyttöön tietorakenne nimeltä Partial Sum Tree (5.1), joka korvasi Fenwick-puun nimen.

Mielivaltaisten suorakaiteen muotoisten aliryhmien summien laskemiseksi moniulotteisissa taulukoissa summattujen alueiden taulukkoa edustaa tietorakenne, joka on rakennettu etuliitesummiin. Tällainen taulukko voi olla hyödyllinen kuvan konvoluutioongelmissa . [19]

Sovellukset

Laskentalajittelu on kokonaislukujen lajittelualgoritmi , joka käyttää avaimen taajuuden histogrammin etuliitesummaa laskeakseen kunkin avaimen sijainnin lajitetussa lähtötaulukossa. Se suoritetaan lineaarisessa ajassa kokonaislukuavaimille, jotka ovat pienempiä kuin elementtien lukumäärä, ja sitä käytetään usein osana kantalukulajittelua , nopeaa algoritmia, jolla lajitellaan kooltaan vähemmän rajoitettuja kokonaislukuja. [yksi]

Listan ranking , tehtävä linkitetyn luettelon muuntaminen taulukoksi , joka sisältää saman elementtisarjan, voidaan ajatella etuliitesummina ykkösten sarjoissa ja sitten sovittaa jokainen elementti taulukon sijaintiin, joka on johdettu sen etuliitteen arvosta. summa. Monet tärkeät puuongelmat voidaan ratkaista rinnakkaisilla algoritmeilla yhdistämällä listasijoitus, etuliitesummat ja Euler-läpikulku . [neljä]

Etuliitteiden summien rinnakkaislaskentaa käytetään myös kehitettäessä binäärisummaimia , logiikkapiirejä, jotka voivat lisätä kaksi n - bittistä binaarilukua. Tässä tapauksessa lisäyssiirtobittisekvenssi voidaan esittää skannausoperaationa syöttöbittiparien sekvenssille käyttämällä enemmistöfunktiota yhdistämään annettu siirto näiden kahden bitin kanssa. Jokainen lähtönumeron bitti voidaan löytää kahden tulobitin eksklusiivisena disjunktorina vastaavalla bittikääreellä. Tällä tavalla on mahdollista rakentaa summain, joka käyttää O ( n ) porttia ja O (log n ) aikaaskeleita. [3] [9] [10]

Rinnakkaisessa hajasaantilaskentakonemallissa etuliitteiden summia voidaan käyttää mallintamaan rinnakkaisia algoritmeja, jotka sallivat useiden prosessorien pääsyn samaan muistipaikkaan samanaikaisesti rinnakkaisissa koneissa, jotka estävät samanaikaisen käytön. Lajitteluverkon kautta joukko samanaikaisia muistinkäyttöpyyntöjä voidaan järjestää sekvenssiin, jolloin pääsy samaan soluun on peräkkäin sekvenssin sisällä. Skannaustoimintoja voidaan sitten käyttää määrittämään, mitkä kirjoituspääsyistä pyydettyihin soluihin onnistuivat, ja jakaa muistin lukutoimintojen tulokset useille prosessoreille, jotka pyytävät samaa tulosta. [kaksikymmentä]

Guy Blallockin väitöskirjassa [21] rinnakkaiset etuliiteoperaatiot ovat osa datan rinnakkaisuusmallin formalisointia, jonka tarjoavat koneita, kuten Connection Machine . Yhteyskone CM-1 ja CM-2 tarjosivat hyperkuutioverkon , jossa edellä mainittu algoritmi 1 voitiin toteuttaa, kun taas CM-5 tarjosi verkon algoritmin 2 toteuttamiseksi. [22]

Kun rakennetaan Gray-koodeja , binääriarvosarjoja, joilla on ominaisuus, että peräkkäisten sekvenssien arvot eroavat toisistaan yhdessä bittikohdassa, luku n voidaan muuntaa Gray-koodin arvoksi kohdassa n yksinkertaisesti ottamalla XOR. n ja n /2 (luku, joka muodostuu siirtämällä n : tä oikealle yhden bitin paikan verran). Käänteinen operaatio, joka dekoodaa Gray-koodatun arvon x:n binääriluvuksi, on monimutkaisempi, mutta se voidaan ilmaista x :n bittien etuliitesummana , jossa jokainen summaoperaatio etuliitesumman sisällä suoritetaan modulo kaksi. Tämän tyyppinen etuliitesumma voidaan suorittaa tehokkaasti käyttämällä nykyaikaisissa tietokoneissa saatavilla olevia bittikohtaisia loogisia operaatioita laskemalla eksklusiivinen "tai" tai x , jossa jokainen luku muodostetaan siirtämällä x :ää vasemmalle kahden potenssin verran.

Rinnakkaisetuliitettä (käyttäen kertolaskua pääasiallisena assosiatiivisena operaationa) voidaan käyttää myös nopeiden rinnakkaisten polynomiinterpolointialgoritmien rakentamiseen . Erityisesti sitä voidaan käyttää interpolaatiopolynomin Newtonin muodon eron jakokertoimien laskemiseen . [23] Tätä etuliitteeseen perustuvaa lähestymistapaa voidaan käyttää myös yleisten jaettujen erojen saamiseksi (yhtenäiselle) Hermite-interpoloinnille sekä rinnakkaisalgoritmeille Vandermonde -järjestelmille .

Katso myös

GPGPU

Muistiinpanot

↑ 1 2 Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. painos), MIT Press ja McGraw-Hill , s. 168–170, ISBN 0-262-03293-7 .
↑ Cole, Richard & Vishkin, Uzi (1986), Deterministinen kolikonheitto sovellusten kanssa optimaaliseen rinnakkaisjärjestykseen
↑ 1 2 3 4 5 Ladner, RE & Fischer, MJ (1980), Parallel Prefix Computation , Journal of the ACM , osa 27 (4): 831–838 , DOI 10.1145/322217.322232 .
↑ 1 2 3 Tarjan, Robert E. & Vishkin, Uzi (1985), Tehokas rinnakkaiskytkentäalgoritmi , SIAM Journal on Computing osa 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), Etuliitesummat ja niiden sovellukset (luentomuistiinpanot) , Carnegie Mellon University , < https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts /PrefixSumBlelloch.pdf > Arkistoitu 14. kesäkuuta 2021 Wayback Machinessa .
↑ Callahan, Paul & Kosaraju, S. Rao (1995), A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields , Journal of the ACM vol . 42(1): 67– 90 , DOI 10.1145/200836.200853 .
↑ Hillis, W. Daniel; Steele, Jr., Guy L. Data rinnakkaisalgoritmit // Communications of the ACM . - 1986. - joulukuu ( osa 29 , nro 12 ). - s. 1170-1183 . doi : 10.1145 / 7902.7903 .
↑ 1 2 Ofman, Yu. (1962), Doklady Akademii Nauk SSSR T. 145 (1): 48–51 . Englanninkielinen käännös, "Diskreettien funktioiden algoritmisesta monimutkaisuudesta", 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 . Englanninkielinen käännös Syst. Theory Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Skannaa primitiivit GPU-laskentaa varten . Proc. 22. ACM SIGGRAPH/EUROGRAPHICS -symposium grafiikkalaitteistosta. s. 97-106. Arkistoitu alkuperäisestä 2014-09-03 . Haettu 21.04.2020 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Vishkin, Uzi (2003). Etuliitesummat ja niiden soveltaminen . US-patentti 6,542,918. Arkistoitu alkuperäisestä 22.05.2013 . Haettu 21.04.2020 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Singler , Johannes MCSTL: Multi-Core Standard Template Library . Haettu 29. maaliskuuta 2019. Arkistoitu alkuperäisestä 3. marraskuuta 2016. (määrätön)
↑ Singler, Johannes; Sanders, Peter; Putze, Felix. MCSTL: Multi-core Standard Template Library // Euro-Par 2007 Parallel Processing. - 2007. - T. 4641. - S. 682-694. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-74465-8 . - doi : 10.1007/978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Johdatus rinnakkaislaskentaan . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Peter; Liikenne, Jesper Larsson. Rinnakkaiset etuliite (Scan) -algoritmit MPI:lle // Viimeaikaiset edistysaskeleet rinnakkaisvirtuaalikoneessa ja viestien välitysliittymässä . - 2006. - Voi. 4192. - s. 49-57. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-39110-4 . - doi : 10.1007/11846802_15 .
↑ Fenwick, Peter M. (1994), Uusi tietorakenne kumulatiivisille taajuustaulukoille , Software: Practice and Experience , osa 24 (3): 327–336 , DOI 10.1002/spe.4380240306
↑ Shiloach, Yossi & Vishkin, Uzi (1982b), An O ( n 2 log n ) rinnakkainen maksimivirtausalgoritmi , Journal of Algorithms osa 3 (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, s. 106–107, ISBN 9781848829350 , < https://books.google.com/books?id=bXzAlkODwa8C&pg=PA106 > .
↑ Vishkin, Uzi (1983), Samanaikaisen muistiosoitteen käytön toteutus malleissa, jotka kieltävät sen , Journal of Algorithms vol. 4 (1): 45–50 , DOI 10.1016/0196-6774(83)90033-0 .
↑ Blelloch, Guy E. Vektorimallit tietojen rinnakkaislaskentaan (katalaani) . - 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.; St. Pierre, Margaret A. Yhteyskoneen CM-5 verkkoarkkitehtuuri // Journal of Parallel and Distributed Computing : Journal. - 1996. - 15. maaliskuuta ( nide 33 , nro 2 ). - s. 145-158 . — ISSN 0743-7315 . - doi : 10.1006/jpdc.1996.0033 .
↑ Eğecioğlu, O.; Gallopoulos, E. & Koç, C. (1990), Rinnakkainen menetelmä nopeaan ja käytännölliseen korkean asteen Newtonin interpolaatioon , BIT Computer Science and Numerical Mathematics , osa 30 (2): 268–288 , DOI 10.1007/BF02017348 .

Linkit

Weisstein, Eric W. Kumulatiivinen summa Wolfram MathWorld -verkkosivustolla .