Præfiks beløb

I datalogi er en præfikssum , kumulativ sum , inklusiv scanning eller bare en scanning af en talfølge x0, x1, x2, ... en talfølge y0, y1, y2, ..., som er en præfikssum fra inputsekvensen:

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

For eksempel er præfikset summen af naturlige tal trekantede tal :

indtaste tal	en	2	3	fire	5	6	…
præfiks sum	en	3	6	ti	femten	21	…

Præfikssummer er trivielle at beregne i sekventielle beregningsmodeller ved at anvende formlen y i = y i − 1 + x i til at beregne hver outputværdi i sekventiel rækkefølge. På trods af at de er beregningsmæssigt enkle, er præfikssummer en nyttig primitiv i nogle algoritmer, såsom tællesortering , [1] [2] og de danner grundlaget for den højere ordens scanningsfunktion i funktionelle programmeringssprog . Præfiks-summer er også blevet grundigt undersøgt i parallelle algoritmer , både som et testproblem, der skal løses, og som en nyttig primitiv til brug som en subrutine i andre parallelle algoritmer. [3] [4] [5]

Teoretisk set kræver præfikssummen kun den binære associative operator ⊕ , hvilket gør den nyttig i mange algoritmer, fra beregning af veladskilte parvise punktnedbrydninger til strengbehandling. [6] [7]

Matematisk kan operationen med at tage præfikssummer generaliseres fra endelige til uendelige sekvenser; i denne forstand er præfikset sum kendt som seriens partielle sum . Præfiks summation eller delvis summation danner en lineær afbildning på vektorrum af endelige eller uendelige sekvenser; deres inverse operatorer er endelige forskelle.

Scanning af en højere ordens funktion

I funktionelle programmeringstermer kan præfikset summen generaliseres til enhver binær operation (ikke kun additionsoperationen ); den højere ordens funktion, der er resultatet af denne generalisering, kaldes en scanning , og den er tæt forbundet med foldningsoperationen . Både scannings- og sammenligningsoperationer anvender en given binær operation på den samme sekvens af værdier, men adskiller sig ved, at scanning returnerer hele sekvensen af resultater af den binære operation, mens fold kun returnerer det endelige resultat. For eksempel kan en sekvens af faktortal genereres ved at scanne naturlige tal ved hjælp af multiplikation i stedet for addition:

indtaste tal	en	2	3	fire	5	6	…
præfiksværdier	en	2	6	24	120	720	…

Inklusive og eksklusive scanninger

Sprog- og biblioteksimplementeringer af scanning kan være inkluderende eller eksklusive . En inklusiv scanning inkluderer input x i ved beregning af output y i ( ), mens en eksklusiv scanning ikke inkluderer det ( ). I sidstnævnte tilfælde forlader implementeringer enten y 0 udefineret eller accepterer en speciel værdi " x -1 ", som skal starte scanning med. Eksklusive scanninger er mere generelle i den forstand, at en inklusiv scanning altid kan implementeres i form af en eksklusiv scanning (ved efterfølgende at kombinere x i med y i ), men en eksklusiv scanning kan ikke altid implementeres i form af en inklusiv scanning, som i tilfældet med den maksimale præfikssum . ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j))$ ${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j))$

Følgende tabel viser eksempler på inkluderende og eksklusive scanningsfunktioner leveret af flere programmeringssprog og biblioteker:

Sprog/biblioteker	Inklusiv scanning	Eksklusiv scanning
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Rust	scan Arkiveret 6. juni 2021 på Wayback Machine

Parallelle algoritmer

Der er to nøglealgoritmer til at beregne præfikssummen parallelt. Den første metode indebærer mindre dybde og en større tilbøjelighed til parallelisering , men denne metode er ikke effektiv nok. Den anden mulighed er mere effektiv, men kræver dobbelt dybde og giver færre muligheder for parallelisering. Begge algoritmer er præsenteret nedenfor.

Algoritme 1: mindre dybde, mere tilbøjelig til parallelisering

Hillis og Steele præsenterer følgende parallelle præfiks-sumalgoritme: [8]

for at gøre

jeg får 0

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

for at gøre parallelt

j\gets 0

n-1

hvis da

j<2^{i}

{\displaystyle x_{j}^{i+1}\får x_{j}^{i))

andet

x_{j}^{i+1}\får x_{j}^{i}+x_{j-2^{i}}^{i}

Notationen betyder værdien af det j -te element i arrayet x i trin i . ${\displaystyle x_{j}^{i))$

Givet n processorer til at fuldføre hver iteration af den indre sløjfe i konstant tid, kører algoritmen i O (log n ) tid.

Algoritme 2: effektiv

En effektiv parallel præfiks sum beregningsalgoritme kan implementeres på følgende måde: [3] [9] [10]

Beregn summen af på hinanden følgende par af elementer, hvor det første element i parret har et lige indeks: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 osv.
Beregn rekursivt præfikssummen w 0 , w 1 , w 2 , ... , af sekvensen z 0 , z 1 , z 2 , ...
Udtryk hvert medlem af sekvensen y 0 , y 1 , y 2 , ... som summen af op til to medlemmer af disse mellemliggende sekvenser: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 osv. Hver værdi af y i , undtagen den første, beregnes enten ved at kopiere fra en position halvdelen af sekvensen w , eller ved at lægge værdien af x -sekvensen til den foregående værdi af y-1 i .

Hvis inputsekvensen har størrelsen n , så fortsætter rekursionen til en dybde på O (log n ) , som også er begrænset af den parallelle udførelsestid for denne algoritme. Antallet af algoritmeoperationer er O ( n ) , og de kan implementeres på en abstrakt parallel delt hukommelse (PRAM)-computer med O ( n /log n ) -processorer uden nogen asymptotisk afmatning ved at tildele flere indekser til hver processor i algoritmevarianter, som har flere elementer end processorer. [3]

Sammenligning af algoritmer

Hver af de foregående algoritmer kører i O (log n ) . Førstnævnte tager dog præcis log 2 n trin, mens sidstnævnte kræver 2 log 2 n − 2 trin. For de viste 16-input eksempler er algoritme 1 12-parallel (49 arbejdsenheder divideret med 4), mens algoritme 2 kun er 4-parallel (26 enheder arbejde divideret med 6). Algoritme 2 er imidlertid arbejdseffektiv, den udfører kun en konstant faktor (2) af mængden af arbejde, der kræves af den sekventielle algoritme, og algoritme 1 er ineffektiv, den udfører asymptotisk mere arbejde (en logaritmisk faktor), end der kræves sekventielt. Derfor er algoritme 1 at foretrække, når et stort antal parallelle processer er mulige, ellers har algoritme 2 forrang.

Parallelle algoritmer for præfikssummer kan ofte generaliseres til andre associative binære scanningsoperationer, [3] [4] , og de kan også beregnes effektivt på moderne parallel hardware såsom GPU (Graphics Processing Unit). [11] Ideen om at skabe en funktionel blok i hardware designet til at beregne en multi-parameter præfiks sum blev patenteret af Uzi Vishkin . [12]

Mange samtidige implementeringer bruger en to-trins procedure, hvor den partielle præfikssum beregnes i det første trin for hver behandlingsblok; præfikssummen af disse delsummer beregnes derefter og føres tilbage til behandlingsenhederne for det andet trin ved at bruge det nu kendte præfiks som startværdien. Asymptotisk tager denne metode cirka to læsninger og en skrivning for hvert element.

Implementeringer af algoritmer til beregning af præfikssummer

Implementeringen af præfikset sum parallel beregningsalgoritme skal ligesom andre parallelle algoritmer tage højde for platformens paralleliseringsarkitektur . Der er mange algoritmer, der er tilpasset til delte hukommelsesplatforme , såvel som algoritmer, der er velegnede til distribuerede hukommelsesplatforme , mens de bruger meddelelser som den eneste form for kommunikation mellem processer.

Delt hukommelse: To-Level Algorithm

Den følgende algoritme antager en delt hukommelsesmaskinemodel ; alle behandlingselementer PE (fra engelsk processing elements) har adgang til den samme hukommelse. En variant af denne algoritme er implementeret i Multicore Standard Template Library (MCSTL) [13] [14] , en parallel implementering af C++ Standard Template Library , der giver tilpassede versioner til parallel beregning af forskellige algoritmer.

For samtidig at beregne præfikset summen af dataelementer med behandlingselementer, opdeles dataene i blokke, som hver indeholder elementer (for nemheds skyld vil vi antage, at det er deleligt med ). Bemærk venligst, at selvom algoritmen opdeler dataene i blokke, fungerer kun behandlingselementer parallelt. $n$ $s$ $p+1$ ${\frac {n}{p+1}}$ $n$ $p+1$ $p+1$ $s$

I den første sløjfe beregner hver PE en lokal præfikssum for sin blok. Den sidste blok behøver ikke at blive beregnet, da disse præfikssummer kun beregnes som forskydninger af præfikssummerne for efterfølgende blokke, og den sidste blok er per definition ikke egnet.

Forskydningerne , der er lagret i den sidste position af hver blok, akkumuleres i deres egen præfikssum og lagres i efterfølgende positioner. Hvis den er lille, kører den sekventielle algoritme hurtigt nok; for store kan dette trin udføres parallelt. $s$ $s$ $s$

Lad os nu gå videre til den anden cyklus. Denne gang behøver den første blok ikke at blive behandlet, da den ikke behøver at tage højde for forskydningen af den forrige blok. Imidlertid er den sidste blok nu inkluderet, og præfikssummene for hver blok beregnes ved at bruge forskydningerne af præfikssumblokkene beregnet i den foregående cyklus.

funktion præfiks_sum ( elementer ) { n := størrelse ( elementer ) p : = antal behandlingselementer præfiks_sum : = [ 0. . .0 ] af størrelse n gør parallel i = 0 til p - 1 { // i := indeks for den aktuelle PE fra j = i * n / ( p + 1 ) til ( i + 1 ) * n / ( p + 1 ) - 1 do { // Præfikssummen af lokale blokke gemmes her store_prefix_sum_with_offset_in ( elementer , 0 , prefix_sum ) } } x = 0 for i = 1 til p { x += præfiks_sum [ i * n / ( p + 1 ) - 1 ] // Opbygning af en præfiks sum over de første p blokke præfiks_sum [ i * n / ( p + 1 )] = x / / Gem resultater til brug som forskydninger i den anden sløjfe } gør parallelt i = 1 til p { // i := indeks for den aktuelle PE fra j = i * n / ( p + 1 ) til ( i + 1 ) * n / ( p + 1 ) - 1 do { offset : = præfiks_sum [ i * n / ( p + 1 )] // Beregn præfiks sum som offset af summen af tidligere blokke store_præfiks_sum_med_forskydning_i ( elementer , offset , præfiks_sum ) } } returner præfiks_sum } Distribueret hukommelse: Hypercube Algorithm

Hypercube-præfiks-sumalgoritmen [15] er godt tilpasset til distribuerede hukommelsesplatforme og bruger meddelelsesudveksling mellem behandlingselementer. Det antages, at algoritmen involverer PE svarende til antallet af hjørner i den dimensionelle hyperkube . ${\displaystyle p=2^{d))$ $d$

Gennem hele algoritmen behandles hver PE som et hjørne i en hypotetisk hyperkube med viden om den fælles præfikssum samt præfikssummen af alle elementer op til sig selv (ifølge de ordnede indekser blandt PE'erne), hver til sin egen. hyperkube. $\sigma$ $x$

Algoritmen starter med antagelsen om, at hver PE er det eneste hjørne af en nuldimensional hyperkube og derfor er lig med summen af det lokale præfiks af dets egne elementer. $\sigma$ $x$
Algoritmen fortsætter ved at flette hyperkuber tilstødende i én dimension. Under hver fletning udveksles og summeres det mellem de to hyperkuber, hvilket bevarer den invariante, at alle PE'er i hjørnerne af denne nye hyperkube gemmer den fælles præfikssum af den flettede hyperkube i deres variabel . Det er dog kun en hyperkube, der indeholder højere indekserede PE'er, der tilføjer dette til sin lokale variabel , mens den invariante bibeholdes. gemmer kun værdien af præfikset summen af alle elementer i PE med indeks mindre end eller lig med deres eget indeks. $\sigma$ $\sigma$ $\sigma$ $x$ $x$

I en -dimensionel hyperkube med PE-hjørner skal algoritmen gentages én gang, så de nuldimensionelle hyperkuber slås sammen til en- dimensionelle hyperkuber. Forudsat en duplekskommunikationsmodel , hvor to tilstødende PE'er i forskellige hyperkuber kan udveksles i begge retninger i ét kommunikationstrin, betyder det, at kommunikationen starter. $d$ ${\displaystyle 2^{d))$ $d$ ${\displaystyle 2^{d))$ $d$ $\sigma$ $d=\log _{2}p$

i : = Indeks for eget processorelement ( PE ) m : = præfiks sum af lokale elementer i denne PE d : = antal dimensioner af hyperterningen _ x = m ; // Invariant: PE-præfikssum i den aktuelle indlejrede terning σ = m ; // Invariant: præfiks sum af alle elementer i den aktuelle underkube for ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Få den samlede præfikssum af den modsatte underkube over dimension k σ = σ + y / / Summationspræfiks summer af begge indlejrede terninger if ( i & 2 ^ k ){ x = x + y // Summering af præfikssummen fra en anden indlejret terning kun hvis denne PE er et højere indeks } } Store meddelelsesstørrelser: et pipelinet binært træ

Binary Tree Pipeline Algorithm [16] er en anden algoritme til distribuerede hukommelsesplatforme, der er særligt velegnet til store meddelelsesstørrelser.

Ligesom hyperkubealgoritmen antager den en særlig kommunikationsstruktur. PE'erne er hypotetisk placeret i et binært træ (f.eks. et Fibonacci-træ) med infiksnummerering i henhold til deres indeks i PE'en. Kommunikation i et sådant træ sker altid mellem forældre- og børneknuderne.

Infix-nummerering sikrer, at for enhver given PE j , er indekserne for alle noder, der kan nås af dets venstre undertræ , mindre end , og indekserne for alle knudepunkter i det højre undertræ er større end . Indekset for forælderen er større end nogen af indekserne i PE j-undertræet , hvis PE j er det venstre underordnede, og mindre end nogen af indekserne i PE j -undertræet . Dette tillader følgende ræsonnement: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

Den lokale præfikssum af det venstre undertræ skal kombineres for at beregne den lokale præfikssum af PE j . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
Den lokale præfikssum af det højre undertræ skal sammenkædes for at beregne summen af det lokale præfiks PE h for det højere niveau, der nås på stien, der indeholder det venstre underordnede barn (betyder ). $\mathbb {\oplus [j+1..r]}$ $h>j$
Præfikset total for PE j er nødvendig for at beregne præfikset total i det højre undertræ (f.eks. for den højeste indeksnode i undertræet). $\mathbb {\oplus [0..j]}$ $\mathbb {\oplus [0..j..r]}$
PE j skal inkludere den fælles præfikssum af den første højere ordensknude, som nås af en stigende sti, der involverer sammenføjningen af højre børn, for at beregne dens fælles præfikssum. $\mathbb {\oplus [0..l-1]}$

Bemærk forskellen mellem subtree-lokal og generel præfikssum. Punkt to, tre og fire kan få dem til at danne en cirkulær afhængighed, men det gør de ikke. PE'er på lavere niveau kan kræve den samlede præfikssum af PE'er på øverste niveau for at beregne deres fælles præfikssum, men PE'er på øvre niveau kræver kun undertræets lokale præfikssum for at beregne deres fælles præfikssum. Rodknuden, som noden på højeste niveau, kræver kun den lokale præfikssum af dets venstre undertræ for at beregne sin egen præfikssum. Hver PE på stien fra PE 0 til rod-PE behøver kun den lokale præfikssum af sit venstre undertræ for at beregne sin egen præfikssum, mens hver knude på stien fra PE p-1 (sidste PE) til PE - rod har brug for den samlede præfikssum af sin overordnede for at beregne sin egen samlede præfikssum.

Dette fører til en to-faset algoritme:

Stigende fase
Udbreder den lokale præfikssum af et undertræ til dets overordnede for hver PE j . $\mathbb {\oplus [l..j..r]}$

Nedadgående fase
Udbredelse af den eksklusive (eksklusiv PE j , såvel som PE i dets venstre undertræ) sumpræfiks summen af alle PE'er med lavere indeks, som ikke er inkluderet i det adresserede undertræ af PE j , til PE'er på lavere niveauer i venstre side undertræ af PE j . Udvidelse af det inkluderende præfiks sum ⊕ [0…j] til det højre underordnede undertræ PE j . $\mathbb {\oplus [0..l-1]}$

Det er værd at bemærke, at algoritmen udføres på hver PE, og PE'erne vil vente, indtil alle pakker fra alle børn/forældre er modtaget.

k := antal pakker i en besked m af en PE m @ { venstre , højre , forælder , denne } := // Beskeder til forskellige PE'er x = m @ dette // Opstrøms fase - Beregn lokal subtræpræfikssum for j = 0 til k - 1 : // Pipelining: pr. meddelelse burst if hasLeftChild : blokering modtag m [ j ] @ venstre // Erstatning af lokal m[j] med modtaget m[ j ] // Kumulativ inklusiv lokal præfikssum fra PE'er med lavere indeks x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : blokering modtag m [ j ] @ højre // Vi flettes ikke m[j] ind i en lokal præfikssum, da de korrekte børn er højere indekserede PE'er send x [ j ] ⨁ m [ j ] til forælder else : send x [ j ] til forælder // Nedadgående fase for j = 0 til k - 1 : m [ j ] @ dette = 0 if hasParent : blokering modtage m [ j ] @ parent // For det venstre underordnede barn er m[j] den overordnede eksklusive præfikssum, for det højre underordnede den inklusive præfikssum x [ j ] = m [ j ] ⨁ x [ j ] send m [ j ] til venstre // Samlet præfikssum af alle PE'er mindre end dette eller enhver PE i venstre undertræ send x [ j ] til højre // Samlet præfikssum af alle PE'er mindre end eller lig med denne PE Formidling

Pipelining kan anvendes, når længdemeddelelsen kan opdeles i dele, og ⨁-operatøren kan anvendes på hver sådan del separat. [16] $m$ $n$ $k$

Hvis algoritmen bruges uden rørføring, så kører kun to lag (den afsendende PE og den modtagende PE) i træet på et givet tidspunkt, mens resten af PE'erne venter. Hvis der anvendes et binært balanceret træ af behandlingselementer indeholdende niveauer, så er længden af stien fra til , hvilket svarer til det maksimale antal ikke-parallelle opstrømskommunikationsoperationer. På samme måde er downlink-links også begrænset til samme værdi. I betragtning af kommunikationens starttidspunkt og byteoverførselstiden får vi, at faserne er tidsbegrænsede i ikke-pipelinet overførsel. Ved opdeling i dele, som hver især har elementer og sender dem uafhængigt, skal den første del overføres til som en del af den lokale præfikssum, og en sådan tid vil være gyldig for den sidste del, hvis . $s$ $\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 andre dele kan alle PE'er arbejde parallelt, og hver tredje interaktionsoperation (modtag til venstre, modtag til højre, send til forælderen) sender en pakke til næste niveau, så en fase kan udføres for interaktionsoperationer og begge dele faser sammen kræver , hvilket er en meget god indikator for beskedlængde . $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 optimeres yderligere ved at bruge en fuld duplex- eller telekommunikationsmodel og overlappende opstrøms- og nedstrømsfaser. [16]

Datastrukturer

Hvis et datasæt skal opdateres dynamisk, kan det gemmes i et Fenwick-træ . En sådan datastruktur tillader ikke kun at finde en hvilken som helst værdi af præfikssummen i logaritmisk tid, men også at ændre enhver værdi af et element i arrayet. [17] . Da begrebet præfikssum endnu ikke var meget brugt i 1982, dukkede værket [18] op , hvor en datastruktur kaldet Partial Sum Tree (5.1) blev introduceret, som erstattede navnet på Fenwick-træet.

For at beregne summen af vilkårlige rektangulære subarrays på multidimensionelle arrays er tabellen over summerede arealer repræsenteret af en datastruktur bygget på præfikssummer. En sådan tabel kan være nyttig i billedfoldningsproblemer . [19]

Ansøgninger

Tællesortering er en heltalssorteringsalgoritme , der bruger præfikssummen af nøglefrekvenshistogrammet til at beregne positionen af hver nøgle i det sorterede outputarray . Den kører i lineær tid for heltalsnøgler, der er mindre end antallet af elementer, og bruges ofte som en del af radix sort , en hurtig algoritme til sortering af heltal, der er mindre begrænset i størrelse. [en]

Listerangering , opgaven med at transformere en sammenkædet liste til et array , der indeholder den samme sekvens af elementer, kan opfattes som præfikssummer på sekvenser af ener og derefter matche hvert element til en position i arrayet afledt af værdien af dets præfiks sum. Mange vigtige træproblemer kan løses i parallelle algoritmer ved at kombinere listerangering, præfikssummer og Euler-gennemløb . [fire]

Parallel beregning af præfikssummer bruges også i udviklingen af binære addere , logiske kredsløb, der kan tilføje to n -bit binære tal. I dette tilfælde kan additionsbærebitsekvensen repræsenteres som en scanningsoperation på en sekvens af par af inputbits, ved at anvende en majoritetsfunktion til at kombinere den givne carry med disse to bits. Hver bit af outputnummeret kan findes som en eksklusiv disjunktor af de to inputbits med den tilsvarende bitombrydning. På denne måde er det muligt at konstruere en adderer, der bruger O ( n ) porte og O ( log n ) tidstrin. [3] [9] [10]

I den parallelle random access-computermodel kan præfikssummer bruges til at modellere parallelle algoritmer, der tillader flere processorer at få adgang til den samme hukommelsesplacering på samme tid på parallelle maskiner, der forbyder samtidig adgang. Gennem et sorteringsnetværk kan et sæt samtidige hukommelsesadgangsanmodninger ordnes i en sekvens, så adgang til den samme celle er sammenhængende i sekvensen. Scanningsoperationer kan derefter bruges til at bestemme, hvilken af skriveadgangene til de anmodede celler, der lykkedes, og sprede resultaterne af hukommelseslæseoperationerne på tværs af flere processorer, der anmoder om det samme resultat. [tyve]

I Guy Blallocks ph.d.-afhandling [21] er parallelle præfiksoperationer en del af formaliseringen af dataparallelisme -modellen leveret af maskiner såsom Connection Machine . Forbindelsesmaskinen CM-1 og CM-2 leverede et hyperkubenetværk , hvor den førnævnte algoritme 1 kunne implementeres, mens CM-5 leverede et netværk til at implementere algoritme 2. [22]

Når du konstruerer Gray-koder , sekvenser af binære værdier med den egenskab, at værdierne af på hinanden følgende sekvenser adskiller sig fra hinanden ved en bitposition, kan tallet n konverteres til Gray-kodeværdien ved position n ved blot at tage XOR af n og n /2 (tallet dannet ved at flytte n til højre med en bitposition). Den omvendte operation, afkodning af den grå-kodede værdi af x til et binært tal, er mere kompleks, men kan udtrykkes som en præfikssum af bits af x , hvor hver sumoperation inden for præfikssum udføres modulo to. En præfikssum af denne type kan effektivt udføres ved hjælp af de bitvise logiske operationer, der er tilgængelige på moderne computere, ved at beregne et eksklusivt "eller" eller x med hvert af tallene dannet ved at flytte x til venstre med et antal bit, der er en potens af to.

Det parallelle præfiks (ved hjælp af multiplikation som den primære associative operation) kan også bruges til at bygge hurtige parallelle polynomielle interpolationsalgoritmer . Det kan især bruges til at beregne divisionskoefficienterne for en forskel i Newtons form af et interpolationspolynomium. [23] Denne præfiksbaserede tilgang kan også bruges til at opnå generaliserede opdelte forskelle for (sammenflydende) Hermite-interpolation , såvel som parallelle algoritmer til Vandermonde -systemer .

Se også

GPGPU

Noter

↑ 1 2 Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. udgave), MIT Press og McGraw-Hill , s. 168-170, ISBN 0-262-03293-7 .
↑ Cole, Richard & Vishkin, Uzi (1986), Deterministisk møntkastning med applikationer til optimal parallellisterangering , Information and Control bind 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 bind 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 bind 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 > Arkiveret 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 bind 42(1): 67– 90 , DOI 10.1145/200836.200853 .
↑ Hillis, W. Daniel; Steele, Jr., Guy L. Data parallelle algoritmer // Kommunikation af ACM . - 1986. - December ( bind 29 , nr. 12 ). - S. 1170-1183 . doi : 10.1145 / 7902.7903 .
↑ 1 2 Ofman, Yu. (1962), Doklady Akademii Nauk SSSR T. 145 (1): 48–51 . Engelsk oversættelse, "Om den algoritmiske kompleksitet af diskrete funktioner", Soviet Physics Doklady 7 : 589-591 1963.
↑ 1 2 Khrapchenko, VM (1967), Asymptotisk estimering af tilføjelsestid for en parallel adder, Problemy Kibernet. T. 19: 107–122 . Engelsk oversættelse i Syst. Teori Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scan primitiver til GPU-databehandling . Proc. 22. ACM SIGGRAPH/EUROGRAPHICS symposium om grafikhardware. pp. 97-106. Arkiveret fra originalen 2014-09-03 . Hentet 2020-04-21 . Forældet parameter brugt |deadlink=( hjælp )
↑ Vishkin, Uzi (2003). Præfiksbeløb og en anvendelse heraf . US patent 6.542.918. Arkiveret fra originalen 2013-05-22 . Hentet 2020-04-21 . Forældet parameter brugt |deadlink=( hjælp )
↑ Singler, Johannes MCSTL: The Multi-Core Standard Template Library . Hentet 29. marts 2019. Arkiveret fra originalen 3. november 2016. (ubestemt)
↑ Singler, Johannes; Sanders, Peter; Putze, Felix. MCSTL: Multi-core Standard Template Library // Euro-Par 2007 Parallel Processing. - 2007. - T. 4641. - S. 682-694. — (Forelæsningsnotater i datalogi). — ISBN 978-3-540-74465-8 . - doi : 10.1007/978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Introduktion til Parallel Computing . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Peter; Traf, Jesper Larsson. Parallel Præfiks (Scan) Algoritmer for MPI // Seneste fremskridt i Parallel Virtual Machine og Message Passing Interface . - 2006. - Bd. 4192. - S. 49-57. — (Forelæsningsnotater i datalogi). - ISBN 978-3-540-39110-4 . - doi : 10.1007/11846802_15 .
↑ Fenwick, Peter M. (1994), En ny datastruktur for kumulative frekvenstabeller , Software: Practice and Experience bind 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 bind 3 (2): 128–146 , DOI 10.1016/0196-67004(892) -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), Implementering af samtidig hukommelsesadresseadgang i modeller, der forbyder det , Journal of Algorithms bind 4 (1): 45–50 , DOI 10.1016/0196-6774(83)90033-0 .
↑ Blelloch, Guy E. Vektormodeller til dataparallel databehandling (catalansk) . - 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. Forbindelsesmaskinens netværksarkitektur CM-5 // Journal of Parallel and Distributed Computing: tidsskrift. - 1996. - 15. marts ( bind 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 parallel metode til hurtig og praktisk højordens Newton-interpolation , BIT Computer Science and Numerical Mathematics bind 30 (2): 268–288 , DOI 10.1007/BF02017348 .