Prefix suma

În informatică , o sumă de prefix, o sumă cumulativă, o scanare inclusivă sau doar o scanare a unei secvențe de numere x0, x1, x2, ... este o secvență de numere y0, y1, y2, ..., care este o suma prefixului din secvența de intrare:

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

De exemplu, sumele prefixelor numerelor naturale sunt numere triunghiulare :

numere de intrare	unu	2	3	patru	5	6	…
suma prefixului	unu	3	6	zece	cincisprezece	21	…

Sumele prefixelor sunt banale de calculat în modelele de calcul secvențial, prin aplicarea formulei y i = y i − 1 + x i pentru a calcula fiecare valoare de ieșire în ordine secvențială. Cu toate acestea, în ciuda faptului că sunt simple din punct de vedere computațional, sumele prefixelor sunt o primitivă utilă în unii algoritmi, cum ar fi sortarea de numărare , [1] [2] și formează baza funcției de scanare de ordin superior în limbaje de programare funcționale . Sumele prefixelor au fost, de asemenea, studiate pe larg în algoritmii paraleli , atât ca problemă de testare de rezolvat, cât și ca primitivă utilă pentru utilizare ca subrutină în alți algoritmi paraleli. [3] [4] [5]

Teoretic, suma prefixelor necesită doar operatorul asociativ binar ⊕ , ceea ce îl face util în mulți algoritmi, de la calcularea descompozițiilor de puncte bine separate în perechi până la procesarea șirurilor. [6] [7]

Din punct de vedere matematic, operația de luare a sumelor prefixelor poate fi generalizată de la șiruri finite la infinite; în acest sens, suma prefixului este cunoscută ca suma parțială a seriei . Însumarea prefixului sau însumarea parțială formează o mapare liniară pe spații vectoriale de secvențe finite sau infinite; operatorii lor inversi sunt diferențe finite.

Scanarea unei funcții de ordin superior

În termeni de programare funcțională , suma prefixului poate fi generalizată la orice operație binară (nu doar operația de adunare ); funcția de ordin superior rezultată din această generalizare se numește scanare și este strâns legată de operația de convoluție . Atât operațiile de scanare, cât și cele de comparare aplică o anumită operație binară aceleiași secvențe de valori, dar diferă prin faptul că scanarea returnează întreaga secvență de rezultate a operației binare, în timp ce fold returnează doar rezultatul final. De exemplu, o secvență de numere factoriale poate fi generată prin scanarea numerelor naturale folosind înmulțirea în loc de adunare:

numere de intrare	unu	2	3	patru	5	6	…
valori de prefix	unu	2	6	24	120	720	…

Scanări inclusive și exclusive

Implementările de limbă și bibliotecă ale scanării pot fi inclusive sau exclusive . O scanare inclusivă include intrarea x i atunci când se calculează ieșirea y i ( ), în timp ce o scanare exclusivă nu o include ( ). În acest din urmă caz, implementările fie lasă y 0 nedefinit, fie acceptă o valoare specială „ x -1 ” cu care să înceapă scanarea. Scanările exclusive sunt mai generale în sensul că o scanare inclusivă poate fi întotdeauna implementată în termeni de scanare exclusivă (prin combinarea ulterioară a x i cu y i ), dar o scanare exclusivă nu poate fi întotdeauna implementată în termenii unei scanări inclusive, ca în cazul sumei maxime de prefix . $y_{i}=\bigoplus _{j=0}^{i}x_{j)$ $y_{i}=\bigoplus _{j=0}^{i-1}x_{j)$

Următorul tabel listează exemple de caracteristici de scanare inclusive și exclusive oferite de mai multe limbaje de programare și biblioteci:

Limbi/biblioteci	Scanare inclusivă	Scanare exclusivă
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Rugini	scan Arhivat pe 6 iunie 2021 la Wayback Machine

Algoritmi paraleli

Există doi algoritmi cheie pentru calcularea sumei prefixelor în paralel. Prima metodă implică mai puțină adâncime și o tendință mai mare de paralelizare , dar această metodă nu este suficient de eficientă. A doua opțiune este mai eficientă, dar necesită o adâncime dublă și oferă mai puține opțiuni de paralelizare. Ambii algoritmi sunt prezentați mai jos.

Algoritmul 1: adâncime mai mică, mai predispus la paralelizare

Hillis și Steele prezintă următorul algoritm de sumă a prefixelor paralele: [8]

pentru a face

primesc 0

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

pentru a face în paralel

j\obține 0

n-1

dacă atunci

j<2^{i)

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

altfel

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

Notația înseamnă valoarea j --lea element al tabloului x la pasul i . $x_{j}^{i)$

Având n procesoare pentru a finaliza fiecare iterație a buclei interioare în timp constant, algoritmul rulează în timp O (log n ) .

Algoritmul 2: eficient

Un algoritm eficient de calcul al sumei prefixelor paralele poate fi implementat în felul următor: [3] [9] [10]

Calculați sumele perechilor consecutive de elemente în care primul element al perechii are un indice par: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 etc.
Calculați recursiv suma prefixului w 0 , w 1 , w 2 , ... , a secvenței z 0 , z 1 , z 2 , ...
Exprimați fiecare membru al șirului y 0 , y 1 , y 2 , ... ca sumă a până la doi membri ai acestor secvențe intermediare: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 , etc. Fiecare valoare a lui y i , cu excepția primei, se calculează fie prin copierea dintr-o poziție jumătate din cea din secvența w , fie prin adăugarea valorii șirului x la valoarea anterioară a lui y-1 i .

Dacă secvența de intrare are dimensiunea n , atunci recursiunea continuă până la o adâncime de O (log n ) , care este, de asemenea, limitată de timpul de execuție paralelă a acestui algoritm. Numărul de operații cu algoritm este O ( n ) și pot fi implementate pe un computer abstract paralel partajat cu memorie (PRAM) cu procesoare O ( n /log n ) fără nicio încetinire asimptotică prin alocarea de mai mulți indici fiecărui procesor în variante de algoritm, pentru care au mai multe elemente decât procesoare. [3]

Compararea algoritmilor

Fiecare dintre algoritmii anteriori rulează în O (log n ) . Cu toate acestea, primul necesită exact log 2 n pași, în timp ce cel de-al doilea necesită 2 log 2 n - 2 pași. Pentru exemplele cu 16 intrări prezentate, algoritmul 1 este paralel cu 12 (49 de unități de lucru împărțite la 4), în timp ce algoritmul 2 este doar cu 4 paralel (26 de unități de lucru împărțite la 6). Cu toate acestea, algoritmul 2 este eficient în muncă, efectuează doar un factor constant (2) din cantitatea de lucru cerută de algoritmul secvenţial, iar algoritmul 1 este ineficient, efectuează asimptotic mai multă muncă (un factor logaritmic) decât este necesar secvenţial. Prin urmare, algoritmul 1 este de preferat atunci când este posibil un număr mare de procese paralele, altfel algoritmul 2 are prioritate.

Algoritmii paraleli pentru sumele prefixelor pot fi adesea generalizați la alte operații de scanare binară asociativă, [3] [4] , și pot fi, de asemenea, calculați eficient pe hardware paralel modern, cum ar fi GPU (Graphics Processing Unit). [11] Ideea creării unui bloc funcțional în hardware conceput pentru a calcula o sumă de prefix cu mai mulți parametri a fost brevetată de Uzi Vishkin . [12]

Multe implementări concurente utilizează o procedură în două etape în care suma parțială a prefixului este calculată în prima etapă pentru fiecare unitate de procesare; suma prefixului acestor sume parțiale este apoi calculată și transmisă înapoi la unitățile de procesare pentru a doua etapă, folosind prefixul acum cunoscut ca valoare de bază. Asimptotic, această metodă necesită aproximativ două citiri și o scriere pentru fiecare element.

Implementări de algoritmi pentru calcularea sumelor prefixelor

Implementarea algoritmului de calcul paralel sum prefix, ca și alți algoritmi paraleli, trebuie să țină cont de arhitectura de paralelizare a platformei . Există mulți algoritmi care sunt adaptați platformelor de memorie partajată , precum și algoritmi care se potrivesc bine platformelor de memorie distribuită , folosind în același timp mesageria ca singura formă de comunicare între procese.

Memorie partajată: algoritm cu două niveluri

Următorul algoritm presupune un model de mașină cu memorie partajată ; toate elementele de procesare PE (din engleză elemente de procesare) au acces la aceeași memorie. O variantă a acestui algoritm este implementată în Multicore Standard Template Library (MCSTL) [13] [14] , o implementare paralelă a C++ Standard Template Library care furnizează versiuni adaptate pentru calcularea paralelă a diferiților algoritmi.

Pentru a calcula simultan suma prefixului elementelor de date cu elementele de procesare, datele sunt împărțite în blocuri, fiecare dintre acestea conținând elemente (pentru simplitate, vom presupune că este divizibil cu ). Vă rugăm să rețineți că, deși algoritmul împarte datele în blocuri, numai elementele de procesare funcționează în paralel. $n$ $p$ $p+1$ ${\frac {n}{p+1}}$ $n$ $p+1$ $p+1$ $p$

În prima buclă, fiecare PE calculează o sumă locală de prefix pentru blocul său. Ultimul bloc nu trebuie să fie calculat deoarece aceste sume de prefix sunt calculate doar ca decalaje ale sumelor de prefix ale blocurilor ulterioare, iar ultimul bloc nu este, prin definiție, adecvat.

Offset -urile care sunt stocate în ultima poziție a fiecărui bloc sunt acumulate în propria lor sumă de prefix și stocate în pozițiile ulterioare. Dacă este mic, atunci algoritmul secvenţial rulează suficient de rapid; pentru cei mari, acest pas poate fi efectuat în paralel. $p$ $p$ $p$

Acum să trecem la al doilea ciclu. De data aceasta, primul bloc nu trebuie procesat, deoarece nu trebuie să ia în considerare decalajul blocului anterior. Cu toate acestea, ultimul bloc este acum inclus și sumele de prefix pentru fiecare bloc sunt calculate folosind decalajele blocurilor de sumă de prefix calculate în ciclul anterior.

function prefix_sum ( elemente ) { n := dimensiune ( elemente ) p := numarul de elemente de procesare prefix_sum := [ 0. . .0 ] de mărimea n face paralel i = 0 la p - 1 { // i := indicele curentului PE de la j = i * n / ( p + 1 ) la ( i + 1 ) * n / ( p + 1 ) - 1 do { // Suma prefixului blocurilor locale este stocată aici store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 pentru i = 1 la p { x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Construirea unei sume de prefix peste primele p blocuri prefix_sum [ i * n / ( p + 1 )] = x / / Salvarea rezultatelor pentru a le utiliza ca decalaje în a doua buclă } face paralel i = 1 la p { // i := indicele curentului PE de la j = i * n / ( p + 1 ) la ( i + 1 ) * n / ( p + 1 ) - 1 do { offset : = prefix_sum [ i * n / ( p + 1 )] // Calculați suma prefixului ca compensare a sumei blocurilor anterioare store_prefix_sum_with_offset_in ( elemente , offset , prefix_sum ) } } return prefix_sum } Memoria distribuită: algoritmul Hypercube

Algoritmul de sumă de prefix hipercub [15] este bine adaptat pentru platformele de memorie distribuită și utilizează schimbul de mesaje între elementele de procesare. Se presupune că algoritmul implică PE egal cu numărul de colțuri din hipercubul -dimensional . $p=2^{d)$ $d$

Pe tot parcursul algoritmului, fiecare PE este tratat ca un colț într-un hipercub ipotetic cu cunoașterea sumei prefixelor comune , precum și a sumei prefixelor tuturor elementelor până la sine (conform indicilor ordonați între PE), fiecare în propria sa hipercub. $\sigma$ $X$

Algoritmul începe cu presupunerea că fiecare PE este singurul colț al unui hipercub cu dimensiuni zero și, prin urmare, este egal cu suma prefixului local al propriilor elemente. $\sigma$ $X$
Algoritmul continuă prin îmbinarea hipercuburilor adiacente într-o singură dimensiune. În timpul fiecărei îmbinări, acesta este schimbat și însumat între cele două hipercuburi, ceea ce păstrează invariantul că toate PE-urile de la colțurile acestui nou hipercub stochează suma prefixului comun a hipercubului îmbinat în variabila lor . Cu toate acestea, doar un hipercub care conține PE-uri mai indexate adaugă acest lucru la variabila locală , menținând în același timp invariantul. stochează doar valoarea prefixului sumei tuturor elementelor din PE cu indici mai mici sau egali cu propriul indice. $\sigma$ $\sigma$ $\sigma$ $X$ $X$

Într -un hipercub -dimensional cu colțuri PE, algoritmul trebuie repetat o dată, astfel încât hipercuburile zero-dimensionale să fie îmbinate într-un hipercub unidimensional . Presupunând un model de comunicare duplex , în care două PE adiacente în hipercuburi diferite pot fi schimbate în ambele direcții într-un singur pas de comunicare, aceasta înseamnă că începe comunicarea. $d$ $2^{d)$ $d$ $2^{d)$ $d$ $\sigma$ $d=\log _{2}p$

i : = Indexul elementului de procesor propriu ( PE ) m : = suma prefixului elementelor locale ale acestui PE d : = numărul de dimensiuni ale hipercubului x = m ; // Invariant: suma prefixului PE în cubul imbricat curent σ = m ; // Invariant: suma prefixului tuturor elementelor din subcubul curent pentru ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Obțineți suma totală a prefixelor subcubului opus peste dimensiunea k σ = σ + y / / Prefix de sumare sume ale ambelor cuburi imbricate if ( i & 2 ^ k ){ x = x + y // Însumând suma prefixului dintr-un alt cub imbricat numai dacă acest PE este un indice mai mare } } Dimensiuni mari ale mesajelor: un arbore binar canalizat

Algoritmul Binary Tree Pipeline [16] este un alt algoritm pentru platformele de memorie distribuită care este deosebit de potrivit pentru mesaje de dimensiuni mari.

La fel ca algoritmul hipercub, acesta presupune o structură de comunicare specială. PE-urile sunt localizate ipotetic într-un arbore binar (de exemplu un arbore Fibonacci) cu numerotare infixă în funcție de indicele lor în PE. Comunicarea într-un astfel de arbore are loc întotdeauna între nodurile părinte și copil.

Numerotarea infixă asigură că, pentru orice PE j , indicii tuturor nodurilor accesibile prin subarborele său din stânga sunt mai mici decât , iar indicii tuturor nodurilor din subarborele din dreapta sunt mai mari decât . Indicele părinte este mai mare decât oricare dintre indicii din subarborele PE j dacă PE j este copilul din stânga și mai mic decât oricare dintre indicii din subarborele PE j . Acest lucru permite următorul raționament: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

Suma locală a prefixelor din subarborele din stânga trebuie combinată pentru a calcula suma locală a prefixelor PE j . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
Suma prefixului local din subarborele din dreapta trebuie să fie concatenată pentru a calcula suma prefixului local PE h al nivelului superior la care se ajunge pe calea care conține copilul din stânga (adică ). $\mathbb {\oplus [j+1..r]}$ $h>j$
Prefixul total pentru PE j este necesar pentru a calcula prefixul total în subarborele din dreapta (de exemplu, pentru cel mai înalt nod index din subarborele). $\mathbb {\oplus [0..j]}$ $\mathbb {\oplus [0..j..r]}$
PE j trebuie să includă suma prefixelor comune a primului nod de ordin superior la care se ajunge printr-o cale ascendentă care implică unirea copiilor drepti pentru a calcula suma prefixelor comune. $\mathbb {\oplus [0..l-1]}$

Observați diferența dintre suma prefixului subarbore-local și generală. Punctele doi, trei și patru le-ar putea face să formeze o dependență circulară, dar nu o fac. PE de nivel inferior pot solicita suma totală a prefixelor PE de nivel superior pentru a calcula suma prefixelor comune, dar PE de nivel superior necesită doar suma prefixelor locale a subarborelui pentru a calcula suma prefixelor comune. Nodul rădăcină, ca nod de cel mai înalt nivel, necesită doar suma locală a prefixelor din subarborele său din stânga pentru a-și calcula propria sumă de prefixe. Fiecare PE de pe calea de la PE 0 la rădăcina PE are nevoie doar de suma locală a prefixelor din subarborele său din stânga pentru a-și calcula propria sumă de prefix, în timp ce fiecare nod de pe calea de la PE p-1 (ultimul PE) la rădăcina PE are nevoie de totalul suma prefixului părintelui său pentru a calcula propria sumă totală a prefixelor.

Aceasta conduce la un algoritm în două faze:

Faza ascendentă
Propagați suma prefixelor locale a unui subarboresc la părintele său pentru fiecare PE j . $\mathbb {\oplus [l..j..r]}$

Faza descendentă
Propagarea sumei prefixului sumei exclusive (exclusiv PE j , precum și PE din subarborele său din stânga) a tuturor PE-urilor cu indice inferior care nu sunt incluse în subarborele adresat al PE j , către PE din nivelurile inferioare din stânga subarbore copil al PE j . Extinderea prefixului inclusiv sum ⊕ [0…j] la subarborele copil din dreapta PE j . $\mathbb {\oplus [0..l-1]}$

Este de remarcat faptul că algoritmul este executat pe fiecare PE și PE-urile vor aștepta până când toate pachetele de la toți copiii/părinții vor fi primite.

k := numărul de pachete dintr- un mesaj m al unui PE m @ { stânga , dreapta , părinte , aceasta } := // Mesaje către diferite PE x = m @ aceasta // Faza din amonte - Calculați suma prefixului subarboresc local pentru j = 0 la k - 1 : // Pipeline: per explozie de mesaj dacă hasLeftChild : blocarea recepției m [ j ] @ left // Înlocuirea localului m[j] cu m[ j primit ] // Suma cumulativă a prefixelor locale inclusive din PE cu indici mai mici x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : blocare primire m [ j ] @ dreapta // Nu îmbinăm m[j] într-o sumă locală de prefix, deoarece copiii corecti sunt PE indexați mai mari trimite x [ j ] ⨁ m [ j ] părintelui alt : trimite x [ j ] la părinte // Faza descendentă pentru j = 0 până la k - 1 : m [ j ] @ this = 0 if hasParent : blocking receive m [ j ] @ parent // Pentru copilul stâng, m[j] este suma prefixului exclusiv al părintelui, pentru copilul din dreapta, prefixul inclusiv sum x [ j ] = m [ j ] ⨁ x [ j ] trimite m [ j ] la stânga // Suma totală a prefixelor tuturor PE mai mici decât aceasta sau orice PE din subarborele din stânga trimite x [ j ] la dreapta // Suma totală a prefixelor tuturor PE mai mici sau egale cu acest PE Transmiterea

Canalizarea poate fi aplicată atunci când mesajul de lungime poate fi împărțit în părți și operatorul ⨁ poate fi aplicat fiecărei astfel de părți separat. [16] $m$ $n$ $k$

Dacă algoritmul este utilizat fără conducte, atunci numai două straturi (PE-ul care trimite și PE-ul de recepție) rulează în arbore la un moment dat, în timp ce restul PE-uri așteaptă. Dacă se utilizează un arbore binar echilibrat de elemente de procesare care conțin niveluri, atunci lungimea căii este de la până la , ceea ce corespunde numărului maxim de operațiuni de comunicație în amonte neparalele. În mod similar, linkurile downlink sunt, de asemenea, limitate la aceeași valoare. Având în vedere timpul de începere a comunicării și timpul de transfer al octeților, obținem că fazele sunt limitate în timp în transferul non-pipeline. La împărțirea în părți, fiecare dintre acestea având elemente și le trimite independent, prima parte va trebui să treacă la ca parte a sumei prefixului local și acest timp va fi valabil pentru ultima parte dacă . $p$ $\log _{2}p$ $PE_{0)$ $PE_{\mathbb {rădăcină} }$ $\log _{2}p-1$ $T_{\mathbb {start} }$ $T_{\mathbb {octet} }$ $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {octet} })$ $k$ ${\frac {n}{k)}$ $(\log _{2}p-1)(T_{\mathbb {start} }+{\frac {n}{k))\cdot T_{\mathbb {octet} })$ $PE_{\mathbb {rădăcină} }$ $k>\log _{2}p$

În alte părți, toate PE-urile pot funcționa în paralel și fiecare a treia operațiune de interacțiune (primire în stânga, primire în dreapta, trimite către părinte) trimite un pachet la nivelul următor, astfel încât se poate face o fază pentru operațiunile de interacțiune și ambele fazele împreună necesită , ceea ce este un indicator foarte bun pentru lungimea mesajului . $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 {octet}})$ $n$

Algoritmul poate fi optimizat suplimentar prin utilizarea unui model de comunicații full duplex sau telecomunicații și suprapunerea fazelor din amonte și din aval. [16]

Structuri de date

Dacă un set de date trebuie actualizat dinamic, acesta poate fi stocat într- un arbore Fenwick . O astfel de structură de date permite nu numai găsirea oricărei valori a sumei prefixului în timp logaritmic, ci și schimbarea oricărei valori a unui element din matrice. [17] . Întrucât termenul prefix sum nu era încă utilizat pe scară largă în 1982, a apărut lucrarea [18] , unde a fost introdusă o structură de date numită Partial Sum Tree (5.1), care a înlocuit numele arborelui Fenwick.

Pentru a calcula sumele subtarelor dreptunghiulare arbitrare pe tablouri multidimensionale, tabelul de suprafețe însumate este reprezentat de o structură de date construită pe sume de prefixe. Un astfel de tabel poate fi util în problemele de convoluție a imaginii . [19]

Aplicații

Sortarea de numărare este un algoritm de sortare întreg care utilizează suma prefixului histogramei frecvenței cheii pentru a calcula poziția fiecărei chei în matricea de ieșire sortată. Se rulează în timp liniar pentru cheile întregi care sunt mai mici decât numărul de elemente și este adesea folosit ca parte a radix sort , un algoritm rapid pentru sortarea numerelor întregi care sunt mai puțin limitate ca mărime. [unu]

Clasificarea listelor , sarcina de a transforma o listă legată într- o matrice care conține aceeași secvență de elemente, poate fi considerată ca sume de prefix pe secvențe de unele și apoi potrivirea fiecărui element cu o poziție din matrice derivată din valoarea prefixului său sumă. Multe probleme importante ale arborelui pot fi rezolvate în algoritmi paraleli combinând clasarea listelor, sumele prefixelor și traversările Euler . [patru]

Calculul paralel al sumelor de prefix este, de asemenea, utilizat în dezvoltarea sumătorilor binari , circuite logice care pot adăuga două numere binare de n biți. În acest caz, secvența de biți de transport suplimentar poate fi reprezentată ca o operație de scanare pe o secvență de perechi de biți de intrare, folosind o funcție majoritară pentru a combina transportul dat cu acești doi biți. Fiecare bit al numărului de ieșire poate fi găsit ca un disjunctor exclusiv al celor doi biți de intrare, cu bit wrap-ul corespunzător. În acest fel este posibil să se construiască un sumator care utilizează O ( n ) porți și O (log n ) pași de timp. [3] [9] [10]

În modelul mașinii de calcul cu acces aleator paralel, sumele prefixelor pot fi folosite pentru a modela algoritmi paraleli care permit mai multor procesoare să acceseze aceeași locație de memorie în același timp pe mașini paralele care interzic accesul concurent. Printr -o rețea de sortare , un set de solicitări concurente de acces la memorie poate fi ordonat într-o secvență, astfel încât accesul la aceeași celulă să fie contiguu în cadrul secvenței. Operațiile de scanare pot fi apoi utilizate pentru a determina care dintre accesele de scriere la celulele solicitate a reușit și pentru a răspândi rezultatele operațiunilor de citire a memoriei pe mai multe procesoare care solicită același rezultat. [douăzeci]

În teza de doctorat a lui Guy Blallock [21] , operațiile cu prefix paralel fac parte din formalizarea modelului de paralelism de date furnizat de mașini precum Connection Machine . Mașina de conexiune CM-1 și CM-2 au furnizat o rețea hipercub în care putea fi implementat algoritmul 1 menționat mai sus, în timp ce CM-5 a furnizat o rețea pentru implementarea algoritmului 2. [22]

Când se construiesc coduri Gray , secvențe de valori binare cu proprietatea că valorile secvențelor consecutive diferă între ele la o poziție de bit, numărul n poate fi convertit în valoarea codului Gray la poziția n prin simpla luare a XOR de n și n /2 (numărul format prin deplasarea n la dreapta cu o poziție de un bit). Operația inversă, decodând valoarea codificată Gray a lui x într-un număr binar, este mai complexă, dar poate fi exprimată ca o sumă prefixă a biților lui x , unde fiecare operație de sumă din suma prefixului este efectuată modulo doi. O sumă de prefix de acest tip poate fi realizată eficient utilizând operațiile logice pe biți disponibile pe computerele moderne, calculând un „sau” sau x exclusiv cu fiecare dintre numerele formate prin deplasarea x la stânga unui număr de biți care este o putere a doi.

Prefixul paralel (folosind înmulțirea ca principală operație asociativă) poate fi folosit și pentru a construi algoritmi de interpolare polinomială paralelă rapidă . În special, poate fi folosit pentru a calcula coeficienții de diviziune ai unei diferențe în forma lui Newton a unui polinom de interpolare. [23] Această abordare bazată pe prefix poate fi folosită și pentru a obține diferențe divizate generalizate pentru interpolarea Hermite (confluentă) , precum și algoritmi paraleli pentru sistemele Vandermonde .

Vezi și

GPGPU

Note

↑ 1 2 Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (ed. a doua), MIT Press și McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Cole, Richard & Vishkin, Uzi (1986), Deterministic coin tossing with applications to optimal parallel list ranking , 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 > Arhivat 14 iunie 2021 la 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. Algoritmi paraleli de date // Communications of the ACM . - 1986. - Decembrie ( 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 . Traducere în engleză, „Despre complexitatea algoritmică a funcțiilor discrete”, 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 . Traducere engleză în Syst. Teorie Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scanați primitive pentru calcularea GPU . Proc. Al 22-lea Simpozion ACM SIGGRAPH/EUROGRAPHICS despre hardware grafic. pp. 97-106. Arhivat din original pe 03.09.2014 . Preluat 2020-04-21 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Vișkin, Uzi (2003). Sume de prefix și o aplicare a acestora . Brevetul SUA 6.542.918. Arhivat din original pe 22.05.2013 . Preluat 2020-04-21 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Singler, Johannes MCSTL: The Multi-Core Standard Template Library . Preluat la 29 martie 2019. Arhivat din original la 3 noiembrie 2016. (nedefinit)
↑ Singler, Johannes; Sanders, Peter; Putze, Felix. MCSTL: The Multi-core Standard Template Library // Euro-Par 2007 Parallel Processing. - 2007. - T. 4641. - S. 682-694. — (Note de curs în Informatică). — ISBN 978-3-540-74465-8 . - doi : 10.1007/978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Introducere în calculul paralel . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Peter; Traff, Jesper Larsson. Algoritmi de prefix paralel (scanare) pentru MPI // Progrese recente în mașina virtuală paralelă și interfața de transmitere a mesajelor . - 2006. - Vol. 4192. - P. 49-57. — (Note de curs în Informatică). - ISBN 978-3-540-39110-4 . - doi : 10.1007/11846802_15 .
↑ Fenwick, Peter M. (1994), A new data structure for cumulative frequency tables , 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-6774(82)90013 -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), 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. Modele vectoriale pentru calculul paralel de date (catalană) . - 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.; Sf. Pierre, Margaret A. Arhitectura de rețea a mașinii de conexiune CM-5 // Journal of Parallel and Distributed Computing : journal. - 1996. - 15 martie ( vol. 33 , nr. 2 ). - P. 145-158 . — ISSN 0743-7315 . - doi : 10.1006/jpdc.1996.0033 .
↑ Eğecioğlu, O.; Gallopoulos, E. & Koç, C. (1990), A parallel method for fast and practice high-order Newton interpolation , BIT Computer Science and Numerical Mathematics vol. 30 (2): 268–288 , DOI 10.1007/BF02017348 .

Link -uri

Weisstein, Eric W. Suma cumulativă pe site- ul Wolfram MathWorld .