Prefixbelopp

Inom datavetenskap är en prefix summa , kumulativ summa , inkluderande skanning , eller bara en skanning av en sekvens av tal x0, x1, x2, ... en sekvens av siffror y0, y1, y2, ..., vilket är en prefix summa från inmatningssekvensen:

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

Till exempel är prefixsummorna för naturliga tal triangulära tal :

mata in siffror	ett	2	3	fyra	5	6	…
prefix summa	ett	3	6	tio	femton	21	…

Prefixsummor är triviala att beräkna i sekventiella beräkningsmodeller, genom att använda formeln y i = y i − 1 + x i för att beräkna varje utdatavärde i sekventiell ordning. Men trots att de är beräkningsmässigt enkla är prefixsummor en användbar primitiv i vissa algoritmer som counting sort , [1] [2] och de utgör grunden för den högre ordningens skanningsfunktionen i funktionella programmeringsspråk . Prefixsummor har också studerats omfattande i parallella algoritmer , både som ett testproblem som ska lösas och som en användbar primitiv för användning som en subrutin i andra parallella algoritmer. [3] [4] [5]

Teoretiskt sett kräver prefixsumman endast den binära associativa operatorn ⊕ , vilket gör den användbar i många algoritmer, från beräkning av väl separerade parvisa punktuppdelningar till strängbearbetning. [6] [7]

Matematiskt kan operationen att ta prefixsummor generaliseras från finita till oändliga sekvenser; i denna mening är prefixsumman känd som seriens partiella summa . Prefixsummering eller partiell summering bildar en linjär mappning på vektorrum med ändliga eller oändliga sekvenser; deras inversa operatorer är finita skillnader.

Skanna en högre ordningsfunktion

I termer av funktionell programmering kan prefixsumman generaliseras till vilken binär operation som helst (inte bara additionsoperationen ); den högre ordningens funktion som härrör från denna generalisering kallas en scan , och den är nära relaterad till faltningsoperationen . Både scannings- och jämförelseoperationer tillämpar en given binär operation på samma värdesekvens, men skiljer sig genom att genomsökningen returnerar hela sekvensen av resultat från den binära operationen, medan fold endast returnerar det slutliga resultatet. Till exempel kan en sekvens av faktortal genereras genom att skanna naturliga tal med multiplikation istället för addition:

mata in siffror	ett	2	3	fyra	5	6	…
prefixvärden	ett	2	6	24	120	720	…

Inkluderande och exklusiva skanningar

Språk- och biblioteksimplementeringar av skanning kan vara inkluderande eller exklusiva . En inkluderande skanning inkluderar ingången x i vid beräkning av utsignalen y i ( ), medan en exklusiv skanning inte inkluderar den ( ). I det senare fallet lämnar implementeringar antingen y 0 odefinierad eller accepterar ett speciellt värde " x -1 " för att starta skanningen. Exklusiva skanningar är mer generella i den meningen att en inkluderande skanning alltid kan implementeras i termer av en exklusiv skanning (genom att därefter kombinera x i med y i ), men en exklusiv skanning kan inte alltid implementeras i termer av en inkluderande skanning, som i fallet med den maximala prefixsumman . ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j))$ ${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j))$

Följande tabell listar exempel på inkluderande och exklusiva skanningsfunktioner som tillhandahålls av flera programmeringsspråk och bibliotek:

Språk/bibliotek	Inkluderande skanning	Exklusiv skanning
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Rost	scan Arkiverad 6 juni 2021 på Wayback Machine

Parallella algoritmer

Det finns två nyckelalgoritmer för att beräkna prefixsumman parallellt. Den första metoden innebär mindre djup och en större benägenhet för parallellisering , men denna metod är inte tillräckligt effektiv. Det andra alternativet är mer effektivt, men kräver dubbelt djup och erbjuder färre alternativ för parallellisering. Båda algoritmerna presenteras nedan.

Algoritm 1: mindre djup, mer benägen till parallellisering

Hillis och Steele presenterar följande parallellprefixsummaalgoritm: [8]

för att göra

jag får 0

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

för att göra parallellt

j\gets 0

n-1

om då

j<2^{i}

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

annan

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

Notationen betyder värdet av det j : te elementet i matrisen x i steg i . ${\displaystyle x_{j}^{i))$

Givet n processorer för att slutföra varje iteration av den inre slingan i konstant tid, körs algoritmen i O (log n ) tid.

Algoritm 2: effektiv

En effektiv summaberäkningsalgoritm för parallellprefix kan implementeras på följande sätt: [3] [9] [10]

Beräkna summan av på varandra följande par av element där det första elementet i paret har ett jämnt index: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 , etc.
Beräkna rekursivt prefixsumman w 0 , w 1 , w 2 , ... , för sekvensen z 0 , z 1 , z 2 , ...
Uttryck varje medlem av sekvensen y 0 , y 1 , y 2 , ... som summan av upp till två medlemmar av dessa mellansekvenser: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 , etc. Varje värde på y i , förutom det första, beräknas antingen genom att kopiera från halva positionen i sekvensen w , eller genom att addera värdet på x -sekvensen till det föregående värdet på y-1 i .

Om inmatningssekvensen har storlek n fortsätter rekursionen till ett djup av O (log n ) , vilket också begränsas av den parallella exekveringstiden för denna algoritm. Antalet algoritmoperationer är O ( n ) , och de kan implementeras på en abstrakt parallellt delat minne (PRAM)-dator med O ( n / log n ) -processorer utan någon asymptotisk nedgång genom att tilldela flera index till varje processor i algoritmvarianter, för vilka har fler element än processorer. [3]

Jämförelse av algoritmer

Var och en av de tidigare algoritmerna körs i O (log n ) . Den förra tar dock exakt log 2 n steg, medan den senare kräver 2 log 2 n − 2 steg. För exemplen med 16 ingångar som visas är Algoritm 1 12-parallell (49 arbetsenheter dividerat med 4), medan algoritm 2 endast är 4-parallell (26 arbetsenheter dividerat med 6). Men Algoritm 2 är arbetseffektiv, den utför bara en konstant faktor (2) av mängden arbete som krävs av den sekventiella algoritmen och Algoritm 1 är ineffektiv den utför asymptotiskt mer arbete (en logaritmisk faktor) än vad som krävs sekventiellt. Därför är Algoritm 1 att föredra när ett stort antal parallella processer är möjliga, annars har algoritm 2 företräde.

Parallella algoritmer för prefixsummor kan ofta generaliseras till andra associativa binära skanningsoperationer, [3] [4] , och de kan också beräknas effektivt på modern parallell hårdvara som GPU (Graphics Processing Unit). [11] Idén att skapa ett funktionellt block i hårdvara designat för att beräkna en prefixsumma med flera parametrar patenterades av Uzi Vishkin . [12]

Många samtidiga implementeringar använder en tvåstegsprocedur där den partiella prefixsumman beräknas i det första steget för varje behandlingsenhet; prefixsumman för dessa delsummor beräknas sedan och matas tillbaka till bearbetningsenheterna för det andra steget, med användning av det nu kända prefixet som startvärde. Asymptotiskt tar denna metod ungefär två läsningar och en skrivning för varje element.

Implementeringar av algoritmer för att beräkna prefixsummor

Implementeringen av prefixsummans parallellberäkningsalgoritm, liksom andra parallella algoritmer, måste ta hänsyn till plattformens parallelliseringsarkitektur . Det finns många algoritmer som är anpassade för delade minnesplattformar , såväl som algoritmer som är väl lämpade för distribuerade minnesplattformar , samtidigt som meddelanden används som den enda formen av kommunikation mellan processer.

Delat minne: tvånivåalgoritm

Följande algoritm förutsätter en maskinmodell med delat minne ; alla processelement PE (från engelska processing elements) har tillgång till samma minne. En variant av denna algoritm är implementerad i Multicore Standard Template Library (MCSTL) [13] [14] , en parallell implementering av C++ Standard Template Library som tillhandahåller anpassade versioner för parallell beräkning av olika algoritmer.

För att samtidigt beräkna prefixsumman av dataelement med bearbetningselement, delas data in i block, som vart och ett innehåller element (för enkelhetens skull antar vi att det är delbart med ). Observera att även om algoritmen delar upp data i block, fungerar bara bearbetningselement parallellt. $n$ $sid$ $p+1$ ${\frac {n}{p+1}}$ $n$ $p+1$ $p+1$ $sid$

I den första slingan beräknar varje PE en lokal prefixsumma för sitt block. Det sista blocket behöver inte beräknas eftersom dessa prefixsummor endast beräknas som förskjutningar av prefixsummorna för efterföljande block, och det sista blocket är per definition inte lämpligt.

Offseten som lagras i den sista positionen i varje block ackumuleras i sin egen prefixsumma och lagras i efterföljande positioner. Om det är litet körs den sekventiella algoritmen tillräckligt snabbt, för stora kan detta steg utföras parallellt. $sid$ $sid$ $sid$

Låt oss nu gå vidare till den andra cykeln. Den här gången behöver det första blocket inte bearbetas, eftersom det inte behöver ta hänsyn till förskjutningen av det föregående blocket. Emellertid är det sista blocket nu inkluderat och prefixsummorna för varje block beräknas med användning av förskjutningarna av prefixsummablocken beräknade i föregående cykel.

function prefix_sum ( element ) { n := storlek ( element ) p : = antal bearbetningselement prefix_sum : = [ 0. . .0 ] av storlek n gör parallellt i = 0 till p - 1 { // i := index för nuvarande PE från j = i * n / ( p + 1 ) till ( i + 1 ) * n / ( p + 1 ) - 1 do { // Prefixsumman av lokala block lagras här store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 för i = 1 till p { x += prefix_summa [ i * n / ( p + 1 ) - 1 ] // Bygger en prefixsumma över de första p-blocken prefix_summa [ i * n / ( p + 1 )] = x / / Spara resultat för att använda som offset i den andra slingan } gör parallellt i = 1 till p { // i := index för den aktuella PE från j = i * n / ( p + 1 ) till ( i + 1 ) * n / ( p + 1 ) - 1 do { offset : = prefix_summa [ i * n / ( p + 1 )] // Beräkna prefixsumman som offset av summan av tidigare block store_prefix_sum_with_offset_in ( element , offset , prefix_sum ) } } returnera prefix_summa } Distribuerat minne: Hypercube Algorithm

Hyperkubprefixsummaalgoritmen [15] är väl anpassad för distribuerade minnesplattformar och använder meddelandeutbyte mellan bearbetningselement. Det antas att algoritmen involverar PE lika med antalet hörn i den dimensionella hyperkuben . ${\displaystyle p=2^{d))$ $d$

Genom hela algoritmen behandlas varje PE som ett hörn i en hypotetisk hyperkub med kunskap om den gemensamma prefixsumman , såväl som prefixsumman för alla element upp till sig själv (enligt de ordnade indexen bland PEs), var och en till sin egen hyperkub. $\sigma$ $x$

Algoritmen börjar med antagandet att varje PE är det enda hörnet av en nolldimensionell hyperkub och därför är lika med summan av det lokala prefixet för dess egna element. $\sigma$ $x$
Algoritmen fortsätter genom att slå samman hyperkuber intill i en dimension. Under varje sammanslagning byts det ut och summeras mellan de två hyperkuberna, vilket bevarar invarianten att alla PE i hörnen av denna nya hyperkub lagrar den gemensamma prefixsumman för den sammanslagna hyperkuben i sin variabel . Det är dock bara en hyperkub som innehåller högre indexerade PEs som lägger till detta till sin lokala variabel samtidigt som den invarianta bibehålls. lagrar endast värdet av prefixsumman av alla element i PE med index mindre än eller lika med deras eget index. $\sigma$ $\sigma$ $\sigma$ $x$ $x$

I en -dimensionell hyperkub med PE-hörn måste algoritmen upprepas en gång så att de nolldimensionella hyperkuberna slås samman till en endimensionell hyperkub. Om man antar en duplexkommunikationsmodell , där två intilliggande PE:er i olika hyperkuber kan bytas ut i båda riktningarna i ett kommunikationssteg, innebär detta att kommunikationen startar. $d$ ${\displaystyle 2^{d))$ $d$ ${\displaystyle 2^{d))$ $d$ $\sigma$ $d=\log _{2}p$

i : = Index för eget processorelement ( PE ) m : = prefix summan av lokala element i denna PE d : = antalet dimensioner av hyperkuben _ x = m ; // Invariant: PE-prefixsumma i den nuvarande kapslade kuben σ = m ; // Invariant: prefixsumman av alla element i den aktuella underkuben for ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Få den totala prefixsumman av den motsatta underkuben över dimensionen k σ = σ + y / / Summeringsprefixsummor av båda kapslade kuber if ( i & 2 ^ k ){ x = x + y // Summera prefixsumman från en annan kapslad kub endast om denna PE är ett högre index } } Stora meddelandestorlekar: ett binärt träd i pipeline

Binary Tree Pipeline Algorithm [16] är en annan algoritm för distribuerade minnesplattformar som är särskilt väl lämpad för stora meddelandestorlekar.

Liksom hyperkubalgoritmen antar den en speciell kommunikationsstruktur. PE:erna är hypotetiskt placerade i ett binärt träd (t.ex. ett Fibonacci-träd) med infixnummer enligt deras index i PE. Kommunikation i ett sådant träd sker alltid mellan föräldra- och barnnoderna.

Infix-numrering säkerställer att indexen för alla noder som kan nås av dess vänstra underträd för varje givet PE j är mindre än , och indexen för alla noder i det högra underträdet är större än . Förälderns index är större än något av indexen i PE j-underträdet om PE j är det vänstra barnet, och mindre än något av indexen i PE j -underträdet . Detta tillåter följande resonemang: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

Den lokala prefixsumman för det vänstra underträdet måste kombineras för att beräkna den lokala prefixsumman för PE j . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
Den lokala prefixsumman för det högra underträdet måste sammanfogas för att beräkna summan av det lokala prefixet PE h för den högre nivån som nås på vägen som innehåller det vänstra barnet (vilket betyder ). $\mathbb {\oplus [j+1..r]}$ $h>j$
Prefixtotal för PE j behövs för att beräkna prefixtotal i det högra underträdet (t.ex. för den högsta indexnoden i underträdet). $\mathbb {\oplus [0..j]}$ $\mathbb {\oplus [0..j..r]}$
PE j måste inkludera den gemensamma prefixsumman för den första högre ordningens nod som nås av en stigande bana som involverar sammanfogningen av högra barn för att beräkna dess gemensamma prefixsumma. $\mathbb {\oplus [0..l-1]}$

Notera skillnaden mellan subträdlokal och generell prefixsumma. Punkt två, tre och fyra kan få dem att bilda ett cirkulärt beroende, men det gör de inte. PE:er på lägre nivå kan kräva den totala prefixsumman av PE:er på övre nivå för att beräkna deras gemensamma prefixsumma, men PE:er på övre nivå kräver endast subträdets lokala prefixsumma för att beräkna deras gemensamma prefixsumma. Rotnoden, som noden på högsta nivån, kräver bara den lokala prefixsumman för sitt vänstra underträd för att beräkna sin egen prefixsumma. Varje PE på vägen från PE 0 till rot-PE behöver bara den lokala prefixsumman för sitt vänstra delträd för att beräkna sin egen prefixsumma, medan varje nod på vägen från PE p-1 (sista PE) till PE- roten behöver totalsumman prefixsumman av dess överordnade för att beräkna sin egen totala prefixsumma.

Detta leder till en tvåfasalgoritm:

Stigande fas
Propagera den lokala prefixsumman för ett underträd till dess förälder för varje PE j . $\mathbb {\oplus [l..j..r]}$

Nedåtgående fas
Utbredning av den exklusiva (exklusiva PE j , såväl som PE i dess vänstra underträd) summaprefix summan av alla PE med lägre index som inte ingår i det adresserade underträdet av PE j , till PE på lägre nivåer i vänster underträd av PE j . Utöka det inkluderande prefixet summan ⊕ [0…j] till det högra underordnade underträdet PE j . $\mathbb {\oplus [0..l-1]}$

Det är värt att notera att algoritmen exekveras på varje PE och PE:erna kommer att vänta tills alla paket från alla barn/föräldrar har tagits emot.

k := antal paket i ett meddelande m av en PE m @ { left , right , parent , this } := // Meddelanden till olika PEs x = m @ detta // Uppströmsfas - Beräkna lokal subträdprefixsumma för j = 0 till k - 1 : // Pipelining: per meddelandeskur om hasLeftChild : blockerar motta m [ j ] @ vänster // Ersätter lokal m[j] med mottagen m[ j ] // Kumulativ inkluderande lokal prefix summa från PE med lägre index x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : blockering ta emot m [ j ] @ right // Vi slår inte samman m[j] till en lokal prefixsumma eftersom de korrekta barnen är högre indexerade PE skicka x [ j ] ⨁ m [ j ] till förälder else : send x [ j ] till förälder // Nedåtgående fas för j = 0 till k - 1 : m [ j ] @ detta = 0 if hasParent : blockering ta emot m [ j ] @ förälder // För det vänstra barnet, m[j] är förälderns exklusiva prefixsumma, för det högra barnet, det inkluderande prefixet summan x [ j ] = m [ j ] ⨁ x [ j ] skicka m [ j ] till vänster // Total prefixsumma av alla PEs mindre än detta eller någon PE i det vänstra underträdet skicka x [ j ] till höger // Total prefixsumma av alla PEs mindre än eller lika med denna PE Förmedla

Pipelining kan tillämpas när längdmeddelandet kan delas upp i delar och ⨁-operatören kan appliceras på varje sådan del separat. [16] $m$ $n$ $k$

Om algoritmen används utan rör, så körs endast två lager (den sändande PE och den mottagande PE) i trädet vid varje given tidpunkt, medan resten av PE:erna väntar. Om ett binärt balanserat träd av bearbetningselement som innehåller nivåer används, är längden på vägen från till , vilket motsvarar det maximala antalet icke-parallella uppströmskommunikationsoperationer. På samma sätt är nedlänkslänkar också begränsade till samma värde. Med tanke på kommunikationens starttid och byteöverföringstiden får vi att faserna är tidsbegränsade i icke-pipelined överföring. Vid uppdelning i delar, som var och en har element och skickar dem oberoende, kommer den första delen att behöva passera till som en del av den lokala prefixsumman och en sådan tid kommer att vara giltig för den sista delen om . $sid$ $\log _{2}p$ ${\displaystyle PE_{0))$ $PE_{\mathbb {root} }$ $\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 {root} }$ $k>\log _{2}p$

I andra delar kan alla PE:er arbeta parallellt och var tredje interaktionsoperation (ta emot till vänster, ta emot till höger, skicka till föräldern) skickar ett paket till nästa nivå, så en fas kan göras för interaktionsoperationer och båda faser tillsammans kräver , vilket är en mycket bra indikator för meddelandelängd . $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$

Algoritmen kan optimeras ytterligare genom att använda en full duplex- eller telekommunikationsmodell och överlappande uppströms- och nedströmsfaser. [16]

Datastrukturer

Om en datauppsättning behöver uppdateras dynamiskt kan den lagras i ett Fenwick-träd . En sådan datastruktur tillåter inte bara att hitta valfritt värde på prefixsumman i logaritmisk tid, utan också att ändra vilket värde som helst på ett element i matrisen. [17] . Eftersom termen prefix summa ännu inte användes i stor utsträckning 1982, dök verket [18] upp , där en datastruktur som kallas Partial Sum Tree (5.1) introducerades, som ersatte namnet på Fenwick-trädet.

För att beräkna summorna av godtyckliga rektangulära subarrayer på flerdimensionella arrayer, representeras tabellen över summerade areor av en datastruktur byggd på prefixsummor. En sådan tabell kan vara användbar vid problem med bildfalsning . [19]

Applikationer

Räknesortering är en heltalssorteringsalgoritm som använder prefixsumman för nyckelfrekvenshistogrammet för att beräkna positionen för varje nyckel i den sorterade utmatrisen. Den körs i linjär tid för heltalsnycklar som är mindre än antalet element, och används ofta som en del av radix sort , en snabb algoritm för att sortera heltal som är mindre begränsade i storlek. [ett]

Listrankning , uppgiften att omvandla en länkad lista till en array som innehåller samma sekvens av element, kan ses som prefixsummor på sekvenser av ettor, och sedan matcha varje element till en position i arrayen härledd från värdet på dess prefix belopp. Många viktiga trädproblem kan lösas i parallella algoritmer genom att kombinera listrankning, prefixsummor och Euler-övergångar . [fyra]

Parallell beräkning av prefixsummor används också i utvecklingen av binära adderare , logiska kretsar som kan addera två n -bitars binära tal. I detta fall kan additionsbärbitsekvensen representeras som en avsökningsoperation på en sekvens av par av inmatade bitar, med användning av en majoritetsfunktion för att kombinera den givna bärningen med dessa två bitar. Varje bit av utgångsnumret kan hittas som en exklusiv disjunktor för de två inmatade bitarna, med motsvarande bitomslutning. På detta sätt är det möjligt att konstruera en adderare som använder O ( n ) grindar och O ( log n ) tidssteg. [3] [9] [10]

I den parallella datormodellen för direktåtkomst kan prefixsummor användas för att modellera parallella algoritmer som tillåter flera processorer att komma åt samma minnesplats samtidigt på parallella maskiner som förbjuder samtidig åtkomst. Genom ett sorteringsnätverk kan en uppsättning samtidiga minnesåtkomstförfrågningar ordnas i en sekvens, så att åtkomst till samma cell är angränsande inom sekvensen. Avsökningsoperationer kan sedan användas för att bestämma vilken av skrivåtkomsterna till de begärda cellerna som lyckades och sprida resultaten av minnesläsoperationerna över flera processorer som begär samma resultat. [tjugo]

I Guy Blallocks doktorsavhandling [21] är parallella prefixoperationer en del av formaliseringen av dataparallellismmodellen som tillhandahålls av maskiner som Connection Machine . Anslutningsmaskinen CM-1 och CM-2 tillhandahöll ett hyperkubnätverk där ovannämnda Algoritm 1 kunde implementeras, medan CM-5 tillhandahöll ett nätverk för att implementera Algoritm 2. [22]

När du konstruerar Gray-koder , sekvenser av binära värden med egenskapen att värdena för på varandra följande sekvenser skiljer sig från varandra vid en bitposition, kan talet n konverteras till Gray-kodvärdet vid position n genom att helt enkelt ta XOR av n och n /2 (talet som bildas genom att flytta n åt höger med en bitposition). Den omvända operationen, avkodning av det gråkodade värdet av x till ett binärt tal, är mer komplex, men kan uttryckas som en prefixsumma av bitarna av x , där varje summaoperation inom prefixsumman utförs modulo två. En prefixsumma av denna typ kan effektivt utföras med hjälp av de bitvisa logiska operationerna som finns tillgängliga på moderna datorer genom att beräkna ett exklusivt "eller" eller x med vart och ett av talen som bildas genom att flytta x vänster med ett antal bitar som är en potens av två.

Parallellprefixet (med multiplikation som den huvudsakliga associativa operationen) kan också användas för att bygga snabba parallella polynominterpolationsalgoritmer . I synnerhet kan den användas för att beräkna divisionskoefficienterna för en skillnad i Newtons form av ett interpolationspolynom. [23] Detta prefix-baserade tillvägagångssätt kan också användas för att erhålla generaliserade uppdelade skillnader för (konfluent) Hermite-interpolation , såväl som parallella algoritmer för Vandermonde- system .

Se även

GPGPU

Anteckningar

↑ 1 2 Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2nd ed.), MIT Press och McGraw-Hill , sid. 168–170, ISBN 0-262-03293-7 .
↑ Cole, Richard & Vishkin, Uzi (1986), Deterministisk myntkastning med tillämpningar för optimal parallelllistrankning , Information and Control vol. 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 vol. 27 (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), Prefix Sums and Their Applications (Lecture Notes) , Carnegie Mellon University , < https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts /PrefixSumBlelloch.pdf > Arkiverad 14 juni 2021 på Wayback Machine .
↑ 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 parallella algoritmer // Kommunikation av ACM . - 1986. - December ( vol. 29 , nr 12 ). - P. 1170-1183 . doi : 10.1145 / 7902.7903 .
↑ 1 2 Ofman, Yu. (1962), Doklady Akademii Nauk SSSR T. 145 (1): 48–51 . Engelsk översättning, "On the algorithmic complexity of discrete functions", Soviet Physics Doklady 7 : 589–591 1963.
↑ 1 2 Khrapchenko, VM (1967), Asymptotisk uppskattning av tilläggstid för en parallelladderare, problematisk Kibernet. T. 19: 107–122 . Engelsk översättning i Syst. Teori Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Skanna primitiver för GPU-beräkningar . Proc. 22:a ACM SIGGRAPH/EUROGRAPHICS-symposiet om grafikhårdvara. pp. 97-106. Arkiverad från originalet 2014-09-03 . Hämtad 2020-04-21 . Utfasad parameter används |deadlink=( hjälp )
↑ Vishkin, Uzi (2003). Prefixsummor och en tillämpning av dessa . US-patent 6,542,918. Arkiverad från originalet 2013-05-22 . Hämtad 2020-04-21 . Utfasad parameter används |deadlink=( hjälp )
↑ Singler, Johannes MCSTL: The Multi-Core Standard Template Library . Hämtad 29 mars 2019. Arkiverad från originalet 3 november 2016. (obestämd)
↑ Singler, Johannes; Sanders, Peter; Putze, Felix. MCSTL: Multi-core Standard Template Library // Euro-Par 2007 Parallell Processing. - 2007. - T. 4641. - S. 682-694. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-540-74465-8 . - doi : 10.1007/978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Introduktion till Parallell Computing . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Peter; Traff, Jesper Larsson. Parallella Prefix (Scan) Algoritmer för MPI // Senaste framsteg i Parallell Virtual Machine och Message Passing Interface . - 2006. - Vol. 4192. - S. 49-57. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-540-39110-4 . - doi : 10.1007/11846802_15 .
↑ Fenwick, Peter M. (1994), En ny datastruktur för kumulativa frekvenstabeller , Software: Practice and Experience vol 24 (3): 327–336 , DOI 10.1002/spe.4380240306
↑ Shiloach, Yossi & Vishkin, Uzi (1982b), An O ( n 2 log n ) parallel max-flow algorithm , Journal of Algorithms vol. 3 (2): 128–146 , DOI 10.1016/0196-67004(89) -X
↑ Szeliski, Richard (2010), Summed area table (integral image) , Computer Vision: Algorithms and Applications , Texts in Computer Science, Springer, sid. 106–107, ISBN 9781848829350 , < https://books.google.com/books?id=bXzAlkODwa8C&pg=PA106 > .
↑ Vishkin, Uzi (1983), Implementation of simultaneous memory address access in models that forbid it , Journal of Algorithms vol. 4 (1): 45–50 , DOI 10.1016/0196-6774(83)90033-0 .
↑ Blelloch, Guy E. Vektormodeller för dataparallell beräkning (katalanska) . - 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. Anslutningsmaskinens nätverksarkitektur CM-5 // Journal of Parallel and Distributed Computing: tidskrift. - 1996. - 15 mars ( vol. 33 , nr 2 ). - S. 145-158 . — ISSN 0743-7315 . - doi : 10.1006/jpdc.1996.0033 .
↑ Eğecioğlu, O.; Gallopoulos, E. & Koç, C. (1990), En parallell metod för snabb och praktisk Newtoninterpolation av hög ordning , BIT Computer Science and Numerical Mathematics vol. 30 (2): 268–288 , DOI 10.1007/BF02017348 .

Länkar

Weisstein, Eric W. Kumulativ summa på Wolfram MathWorlds webbplats .