Önek toplamı - Prefix sum

Olarak bilgisayar biliminin , önek toplamı , toplam miktar , dahil tarama veya sadece tarama numaralarının bir dizinin X ₀ , x ₁ , x ₂ , ... numaralarının ikinci dizisidir y ₀ , y ₁ , y ₂ ,. .. , toplamları ve ön ekleri ( toplamlar çalışan giriş dizisinin):

y ₀ = x ₀

y ₁ = x ₀ + x ₁

y ₂ = x ₀ + x ₁ + x ₂

...

Örneğin, öneki toplamları doğal sayılar şunlardır üçgen sayılar :

giriş numaraları	1	2	3	4	5	6	...
önek toplamları	1	3	6	10	15	21	...

Önek toplamları, her bir çıktı değerini sıralı sırayla hesaplamak için y _i = y _{ben − 1} + x _i formülünü kullanarak sıralı hesaplama modellerinde hesaplamak için önemsizdir . Bununla birlikte, hesaplama kolaylıklarına rağmen, önek toplamları, sort sayma gibi belirli algoritmalarda yararlı bir ilkeldir ve işlevsel programlama dillerinde tarama üst düzey işlevinin temelini oluştururlar . Önek toplamları , hem çözülmesi gereken bir test problemi hem de diğer paralel algoritmalarda bir alt program olarak kullanılacak kullanışlı bir ilkel olarak paralel algoritmalarda çok çalışılmıştır .

Özet olarak, bir önek toplamı yalnızca bir ikili ilişkisel operatör ⊕ gerektirir , bu da onu noktaların iyi ayrılmış çift ayrıştırmalarını hesaplamaktan dizi işlemeye kadar birçok uygulama için faydalı kılar .

Matematiksel olarak, ön ek toplamları alma işlemi sonlu dizilerden sonsuz dizilere genelleştirilebilir; bu bağlamda, önek toplamı, bir dizinin kısmi toplamı olarak bilinir . Önek toplama veya kısmi toplama , sonlu veya sonsuz dizilerin vektör uzayları üzerinde lineer operatörler oluşturur ; tersleri sonlu fark operatörleridir.

Daha yüksek dereceli işlevi tarayın

Olarak fonksiyonel programlama terimleri, ön ek toplamı bir ikili işlem (sadece genelleştirilebilmektedir ekleme işlemi); yüksek sıralı fonksiyonu bu genelleme kaynaklanan bir adlandırılır tarama ve yakından ilgilidir kat işlem. Hem tarama hem de katlama işlemleri, verilen ikili işlemi aynı değer dizisine uygular, ancak taramanın ikili işlemden elde edilen tüm sonuç sırasını döndürmesi ve katlamanın yalnızca nihai sonucu döndürmesi bakımından farklılık gösterir. Örneğin, faktöriyel sayılar dizisi, toplama yerine çarpma kullanılarak doğal sayıların taranmasıyla oluşturulabilir:

giriş numaraları	1	2	3	4	5	6	...
önek ürünleri	1	2	6	24	120	720	...

Kapsamlı ve özel taramalar

Taramanın programlama dili ve kitaplık uygulamaları kapsayıcı veya dışlayıcı olabilir . Kapsamlı bir tarama, y _i (yani, ) çıkışını hesaplarken x _i girişini içerirken, özel bir tarama yapmaz (yani, ). İkinci durumda, uygulamalar ya y _0'ı tanımsız bırakır ya da taramanın tohumlanacağı ayrı bir " x _-1 " değerini kabul eder . Her iki tarama türü de diğerine dönüştürülebilir: Kapsamlı bir tarama, tarama tarafından üretilen diziyi bir öğe sağa kaydırarak ve kimlik değerini dizinin soluna ekleyerek özel bir taramaya dönüştürülebilir. Tersine, özel bir tarama, tarama tarafından üretilen diziyi sola kaydırarak ve taramanın son öğesinin toplamı ile giriş dizisinin son öğesini dizinin sağına ekleyerek kapsayıcı bir taramaya dönüştürülebilir. ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j}}$${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j}}$

Aşağıdaki tablo, birkaç programlama dili ve kitaplığı tarafından sağlanan kapsamlı ve özel tarama işlevlerinin örneklerini listeler:

Dil/kütüphane	Kapsamlı tarama	Özel tarama
Haskell	scanl1	scanl
MPI	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Skala	scan
Pas	scan

paralel algoritmalar

Paralel olarak bir önek toplamını hesaplamak için iki anahtar algoritma vardır. İlki, daha kısa bir aralık ve daha fazla paralellik sunar, ancak iş açısından verimli değildir. İkincisi, iş açısından verimlidir ancak iki kat aralık gerektirir ve daha az paralellik sunar. Bunlar sırasıyla aşağıda sunulmuştur.

Algoritma 1: Daha kısa açıklık, daha paralel

Son derece paralel 16 girişli paralel önek toplamının devre gösterimi

Hillis ve Steele aşağıdaki paralel önek toplamı algoritmasını sunar:

için için yapmak${\ Displaystyle i\ 0 alır}$ ${\displaystyle \lceil \log _{2}n\rceil -1}$

için için paralel olarak yapmak${\ Displaystyle j\ 0 alır}$ ${\görüntüleme stili n-1}$

eğer öyleyse${\görüntüleme stili j<2^{i}}$

${\displaystyle x_{j}^{i+1}\x_{j}^{i}} alır$

Başka

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

Yukarıda, gösterim değerini, j dizi inci elemanı x timestep olarak i . ${\displaystyle x_{j}^{i}}$

Tek bir işlemci ile bu algoritma O ( n log n ) zamanında çalışacaktır . Bununla birlikte, makinede iç döngüyü paralel olarak gerçekleştirmek için en az n işlemci varsa, algoritma bir bütün olarak O (log n ) zamanında, dış döngünün yineleme sayısıyla çalışır .

Algoritma 2: İş açısından verimli

İş açısından verimli 16 girişli paralel önek toplamının devre gösterimi

İş açısından verimli bir paralel önek toplamı aşağıdaki adımlarla hesaplanabilir.

1. Çiftin ilk öğesinin çift indekse sahip olduğu ardışık öğe çiftlerinin toplamını hesaplayın: z ₀ = x ₀ + x ₁ , z ₁ = x ₂ + x ₃ , vb.
2. z ₀ , z ₁ , z ₂ , ... dizisinin w ₀ , w ₁ , w ₂ , ... önek toplamını yinelemeli olarak hesaplayın .
3. y ₀ , y ₁ , y ₂ , ... son dizisinin her bir terimini bu ara dizilerin en fazla iki teriminin toplamı olarak ifade edin: y ₀ = x ₀ , y ₁ = z ₀ , y ₂ = z ₀ + x ₂ , y ₃ = w ₀ , vb. İlk değerden sonra, her ardışık y _i sayısı ya w dizisi boyunca bir konumdan yarıya kadar kopyalanır ya da önceki değer x dizisindeki bir değere eklenir .

Giriş dizisi n adıma sahipse, yineleme , aynı zamanda bu algoritmanın paralel çalışma süresine de bağlı olan O (log n ) derinliğine kadar devam eder . Algoritmanın adımları sayısıdır O ( n ) , ve bir de uygulanabilir; paralel rasgele erişim makinesi ile O ( n / log n ) için algoritmanın mermi her işlemci birden endeks vererek herhangi bir asimptotik yavaşlama olmadan işlemci işlemcilerden daha fazla öğe var.

Tartışma

Önceki algoritmaların her biri O (log n ) zamanında çalışır. Ancak, birincisi tam olarak log ₂ n adım alırken, ikincisi 2 log ₂  n − 2 adım gerektirir. Gösterilen 16 girişli örnekler için, Algoritma 1 12 yönlü paraleldir (49 birim iş bölümü 4'e bölünür), Algoritma 2 ise yalnızca 4 yönlü paraleldir (26 birim iş bölümü 6'ya bölünür). Bununla birlikte, Algoritma 2 iş açısından verimlidir—sıralı algoritmanın gerektirdiği iş miktarının yalnızca sabit bir faktörünü (2) gerçekleştirirken, Algoritma 1 iş açısından verimsizdir- asimptotik olarak gerekenden daha fazla iş (logaritmik bir faktör) gerçekleştirir sırayla. Sonuç olarak, Algoritma 1, bol paralellik mevcut olduğunda daha iyi performans gösterir, ancak Algoritma 2, paralellik daha sınırlı olduğunda daha iyi performans gösterir.

Önek toplamları için paralel algoritmalar genellikle ilişkisel ikili işlemlerde diğer tarama işlemlerine genelleştirilebilir ve ayrıca GPU gibi modern paralel donanımlarda verimli bir şekilde hesaplanabilirler . Donanımda çok parametreli önek toplamını hesaplamaya adanmış işlevsel bir birim oluşturma fikri Uzi Vishkin tarafından patentlendi .

Birçok paralel uygulama, her işlem biriminde ilk geçişte kısmi önek toplamlarının hesaplandığı iki geçişli bir prosedürü takip eder; bu kısmi toplamların ön ek toplamı daha sonra hesaplanır ve şimdi başlangıç ​​değeri olarak bilinen önek kullanılarak ikinci bir geçiş için işlem birimlerine geri yayınlanır. Asimptotik olarak bu yöntem, öğe başına yaklaşık iki okuma işlemi ve bir yazma işlemi alır.

Önek toplamı algoritmalarının somut uygulamaları

Diğer paralel algoritmalar gibi bir paralel önek toplamı algoritmasının uygulanması , platformun paralelleştirme mimarisini hesaba katmalıdır. Daha spesifik olarak, paylaşılan bellek üzerinde çalışan platformlar için uyarlanmış çoklu algoritmaların yanı sıra , süreçler arası iletişimin tek biçimi olarak mesaj geçişine dayanan dağıtılmış bellek kullanan platformlar için çok uygun algoritmalar mevcuttur .

Paylaşılan hafıza: İki seviyeli algoritma

Aşağıdaki algoritma, paylaşılan bir bellek makine modelini varsayar ; tüm işleme elemanlarının (PE'ler) aynı belleğe erişimi vardır. Bu algoritmanın bir sürümü , çeşitli algoritmaların paralel hesaplanması için uyarlanmış sürümler sağlayan C++ standart şablon kitaplığının paralel bir uygulaması olan Çok Çekirdekli Standart Şablon Kitaplığı'nda (MCSTL) uygulanır .

Eş zamanlı olarak fazla önek toplamı hesaplamak için olan veri öğeleri işleme elemanları, veri ayrılmıştır bloklar, her biri elemanlarının (basitlik için varsayılmaktadır böler ). Algoritmanın verileri bloklara ayırmasına rağmen , aynı anda yalnızca işleme öğelerinin paralel olarak çalıştığını unutmayın. ${\görüntüleme stili n}$${\görüntüleme stili p}$${\ Displaystyle p+1}$${\displaystyle {\frac {n}{p+1}}}$${\ Displaystyle p+1}$${\görüntüleme stili n}$${\ Displaystyle p+1}$${\görüntüleme stili p}$

İlk taramada, her PE kendi bloğu için yerel bir önek toplamını hesaplar. Son bloğun hesaplanmasına gerek yoktur, çünkü bu önek toplamları yalnızca sonraki blokların önek toplamlarına göre ofset olarak hesaplanır ve son blok tanım gereği başarılı değildir.

Her bloğun son pozisyonda saklanır uzaklıklar kendilerine ait bir önek toplamı birikmiş ve onların başarılı pozisyonlarda saklanır. İçin az sayıda olmak, bu büyük bir kitle için, bu sırayla yapmak hızlıdır , bu adım paralel olarak yapılması yanı edilebilir. ${\görüntüleme stili p}$${\görüntüleme stili p}$${\görüntüleme stili p}$

İkinci bir tarama yapılır. Bu sefer, bir önceki bloğun ofsetini hesaba katması gerekmediğinden, ilk bloğun işlenmesi gerekmez. Ancak, bu taramada bunun yerine son blok dahil edilir ve her blok için önek toplamları, önceki taramada hesaplanan önek toplamı blok ofsetleri dikkate alınarak hesaplanır.

function prefix_sum(elements) {
    n := size(elements)
    p := number of processing elements
    prefix_sum := [0...0] of size n
    
    do parallel i = 0 to p-1 {
        // i := index of current PE
        from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
            // This only stores the prefix sum of the local blocks
            store_prefix_sum_with_offset_in(elements, 0, prefix_sum)
        }
    }
    
    x = 0
    
    for i = 1 to p {                        // Serial accumulation of total sum of blocks 
        x +=  prefix_sum[i * n / (p+1) - 1] // Build the prefix sum over the first p blocks
        prefix_sum[i * n / (p+1)] = x       // Save the results to be used as offsets in second sweep
    }
    
    do parallel i = 1 to p {
        // i := index of current PE
        from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
            offset := prefix_sum[i * n / (p+1)]
            // Calculate the prefix sum taking the sum of preceding blocks as offset
            store_prefix_sum_with_offset_in(elements, offset, prefix_sum)
        }
    }
    
    return prefix_sum
}

İyileştirme: Blok sayısının çok fazla olması ve seri adımı tek bir işlemci dağıtarak zaman alıcı hale getirmesi durumunda, ikinci aşamayı hızlandırmak için Hillis ve Steele algoritması kullanılabilir.

Dağıtılmış bellek: Hiperküp algoritması

Hypercube Önek Toplamı Algoritması, dağıtılmış bellek platformları için iyi bir şekilde uyarlanmıştır ve işlem öğeleri arasında mesaj alışverişi ile çalışır. Algoritmaya katılan işlemci öğelerinin (PE'ler) bir boyutlu hiperküpteki köşelerin sayısına eşit olduğunu varsayar . ${\görüntüleme stili p=2^{d}}$${\görüntüleme stili d}$

Değişen sayıda düğüm için farklı hiperküpler

Algoritma boyunca, her bir PE , hem kendi başına hem de toplam önek toplamının yanı sıra (PE'ler arasındaki sıralı endekslere göre) tüm öğelerin önek toplamı bilgisine sahip hipotetik bir hiper küpte bir köşe olarak görülür. hiperküp. ${\görüntüleme stili \sigma }$${\görüntüleme stili x}$

• Her PE varsayılarak algoritma başlar, bu nedenle, bir sıfır boyutlu hiper küp ve tek köşesinde ve kendi elemanları öneğini toplamına eşittir.${\görüntüleme stili \sigma }$${\görüntüleme stili x}$
• Algoritma, bir boyut boyunca bitişik olan hiperküpleri birleştirerek devam eder. Her birleştirme sırasında , bu yeni hiper küpün köşelerindeki tüm PE'lerin değişkeninde bu yeni birleştirilmiş hiper küpün toplam önek toplamını sakladığı değişmezi tutan iki hiper küp arasında değiştirilir ve toplanır . Bununla birlikte, yalnızca daha yüksek endeksli PE'leri içeren hiper küp de bunu yerel değişkenlerine ekleyerek , endeksleri kendi endekslerine eşit veya daha küçük olan PE'lerdeki tüm öğelerin yalnızca önek toplamının değerini depolayan değişmezi korur.${\görüntüleme stili \sigma }$${\görüntüleme stili \sigma }$${\görüntüleme stili \sigma }$${\görüntüleme stili x}$${\görüntüleme stili x}$

Köşelerinde PE'ler bulunan bir boyutlu hiper küpte , sıfır boyutlu hiper küplerin tek boyutlu hiper küpte birleştirilmesi için algoritmanın defalarca tekrarlanması gerekir . Farklı hiper küplerdeki iki bitişik PE'nin tek bir iletişim adımında her iki yönde değiş tokuş edilebildiği bir çift ​​yönlü iletişim modeli varsayarsak , bu iletişim başlatmaları anlamına gelir . ${\görüntüleme stili d}$${\ Displaystyle 2^{d}}$${\görüntüleme stili d}$${\ Displaystyle 2^{d}}$${\görüntüleme stili d}$${\görüntüleme stili \sigma }$${\displaystyle d=\log _{2}p}$

i := Index of own processor element (PE)
m := prefix sum of local elements of this PE
d := number of dimensions of the hyper cube

x = m;     // Invariant: The prefix sum up to this PE in the current sub cube
σ = m;     // Invariant: The prefix sum of all elements in the current sub cube

for (k=0; k <= d-1; k++) {
    y = σ @ PE(i xor 2^k)  // Get the total prefix sum of the opposing sub cube along dimension k
    σ = σ + y              // Aggregate the prefix sum of both sub cubes

    if (i & 2^k) {
        x = x + y  // Only aggregate the prefix sum from the other sub cube, if this PE is the higher index one.
    }
}

Büyük mesaj boyutları: ardışık düzende ikili ağaç

Pipelined Binary Tree Algoritması, özellikle büyük mesaj boyutları için çok uygun olan dağıtılmış bellek platformları için başka bir algoritmadır.

Hiperküp algoritması gibi, özel bir iletişim yapısını varsayar. İşleme elemanları (PE'ler) , PE'ler içindeki indekslerine göre iç numaralandırma ile bir ikili ağaçta (örneğin bir Fibonacci Ağacı) varsayımsal olarak düzenlenir . Böyle bir ağaçta iletişim her zaman üst ve alt düğümler arasında gerçekleşir.

İnfix numaralama herhangi bir PE için sağlar _j , tüm düğümlerin endeksleri sol alt ağaç ulaşılabilir az olan ve işaretlerin sağ ağaca tüm düğümlerin daha büyüktür . Ebeveynin endeksi PE indisler ve hepsinden daha büyüktür _j PE ise alt ağaç 'ın _j PE ise sol çocuk ve küçük olan _j sağ çocuktur. Bu, aşağıdaki akıl yürütmeye izin verir: ${\displaystyle \mathbb {[l...j-1]} }$${\görüntüleme stili j}$${\displaystyle \mathbb {[j+1...r]} }$${\görüntüleme stili j}$

Ardışık İkili Ağaç Önek Toplamı algoritmasında yukarı (mavi) ve aşağı (kırmızı) aşama sırasında işleme öğeleri arasında bilgi alışverişi.

• PE _j'nin yerel önek toplamını hesaplamak için sol alt ağacın yerel önek toplamı toplanmalıdır .${\displaystyle \mathbb {\oplus [l..j-1]} }$${\displaystyle \mathbb {\oplus [l..j]} }$
• Öneğini toplamı sağ ağaca daha yüksek seviyede PE öneğini toplamını hesaplamak için toplanması gereken _saat sol çocuk bağlantı (aracı içeren bir yol üzerinde ulaşılır ).${\displaystyle \mathbb {\oplus [j+1..r]} }$${\ Displaystyle h>j}$
• Toplam ön ek toplamı PE _j sağ ağaca toplam önek toplamı hesaplamak için gerekli olan (örneğin, alt ağacı yüksek dizin düğüm için).${\displaystyle \mathbb {\oplus [0..j]} }$${\displaystyle \mathbb {\oplus [0..j..r]} }$
• PE _j'nin , toplam önek toplamını hesaplamak için, bir sağ alt bağlantı içeren bir yukarı yol yoluyla ulaşılan birinci yüksek dereceli düğümün toplam önek toplamını içermesi gerekir .${\displaystyle \mathbb {\oplus [0..l-1]} }$

Alt ağaç-yerel ve toplam önek toplamları arasındaki farka dikkat edin. İki, üç ve dört noktaları dairesel bir bağımlılık oluşturacaklarına inandırabilir, ancak durum böyle değil. Daha düşük seviyeli PE'ler, toplam önek toplamlarını hesaplamak için daha yüksek seviyeli PE'lerin toplam önek toplamını gerektirebilir, ancak daha yüksek seviyeli PE'ler, toplam önek toplamlarını hesaplamak için yalnızca alt ağaç yerel önek toplamlarını gerektirir. En üst düzey düğüm olarak kök düğüm, kendi önek toplamını hesaplamak için yalnızca sol alt ağacının yerel önek toplamını gerektirir. PE yol üzerindeki her bir PE ₀ kök PE sadece PE yolu her düğüm ise, kendi ön ek toplamını hesaplamak için sol alt ağacın öneğini miktarda gerektirir _p-1 PE (son PE) _kök gerektirir kendi toplam önek toplamını hesaplamak için ebeveyninin toplam önek toplamı.

Bu, iki aşamalı bir algoritmaya yol açar:

Yukarı Aşama Her PE _j için
alt ağaç yerel önek toplamını üst öğeye _yayar . ${\displaystyle \mathbb {\oplus [l..j..r]} }$

Aşağı doğru faz
Propagate münhasır (özel PE _j yanı sıra sol alt ağacındaki PES) toplam önek toplamı PE arasında ele alt ağacında yer almayan tüm alt endeks PE'lerle ait _j PE sol alt alt ağacındaki seviyesi PES düşürmek için _j . Kapsayıcı önek toplamını PE _j'nin sağ alt alt ağacına yayın . ${\displaystyle \mathbb {\oplus [0..l-1]} }$${\displaystyle \mathbb {\oplus [0..j]} }$

Algoritmanın her bir PE'de paralel olarak çalıştırıldığını ve PE'lerin, çocukları/ebeveynleri onlara paketleri sağlayana kadar alma sırasında bloke edeceğini unutmayın.

k := number of packets in a message m of a PE
m @ {left, right, parent, this} := // Messages at the different PEs

x = m @ this

// Upward phase - Calculate subtree local prefix sums
for j=0 to k-1: // Pipelining: For each packet of a message
    if hasLeftChild:
        blocking receive m[j] @ left // This replaces the local m[j] with the received m[j]
        // Aggregate inclusive local prefix sum from lower index PEs
        x[j] = m[j] ⨁ x[j]

    if hasRightChild:
        blocking receive m[j] @ right
        // We do not aggregate m[j] into the local prefix sum, since the right children are higher index PEs
        send x[j] ⨁ m[j] to parent
    else:
        send x[j] to parent

// Downward phase
for j=0 to k-1:
    m[j] @ this = 0

    if hasParent:
        blocking receive m[j] @ parent
        // For a left child m[j] is the parents exclusive prefix sum, for a right child the inclusive prefix sum
        x[j] = m[j] ⨁ x[j] 
    
    send m[j] to left  // The total prefix sum of all PE's smaller than this or any PE in the left subtree
    send x[j] to right // The total prefix sum of all PE's smaller or equal than this PE

boru hattı

Uzunluk mesajı paketlere bölünebiliyorsa ve operatör ⨁, karşılık gelen mesaj paketlerinin her biri üzerinde ayrı ayrı kullanılabiliyorsa, ardışık düzen mümkündür. ${\görüntüleme stili m}$${\görüntüleme stili n}$${\görüntüleme stili k}$

Algoritma ardışık düzen olmadan kullanılırsa, diğer tüm PE'ler beklerken ikili ağacın her zaman yalnızca iki düzeyi (gönderen PE'ler ve alan PE'ler) vardır. Varsa işleme elemanları ve dengeli bir ikili ağaç kullanılır, ağaç sahip olan yol uzunluğu seviyeleri için bu nedenle yukarı aşamasında paralel olmayan iletişim işlemlerinin sayısını temsil eden, aşağı doğru giden yoldan aynı şekilde, haberleşme girişimlerle de sınırlıdır . Bir iletişim başlangıç ​​zamanının ve bayt bazında iletim süresinin , yukarı ve aşağı fazın ardışık düzenlenmemiş bir senaryo ile sınırlı olduğu varsayılır . ${\görüntüleme stili p}$${\displaystyle \log _{2}p}$${\displaystyle PE_{0}}$${\displaystyle PE_{\mathbb {kök}}}$${\displaystyle \log _{2}p-1}$${\displaystyle \log _{2}p-1}$${\displaystyle T_{\mathbb {başlangıç} }}$${\displaystyle T_{\mathbb {bayt}}}$${\displaystyle (2\log _{2}p-2)(T_{\mathbb {start}}+n*T_{\mathbb {byte}})}$

Her biri büyüklükte k pakete bölündükten ve bunları ayrı ayrı gönderdikten sonra, ilk paketin hala yerel bir önek toplamının parçası olarak yayılması gerekir ve eğer . Ancak arada, yol üzerindeki tüm PE'ler paralel çalışabilir ve her üçüncü iletişim işlemi (soldan al, sağdan al, ebeveyne gönder) bir sonraki seviyeye bir paket gönderir, böylece iletişim işlemlerinde bir aşama tamamlanabilir ve Her iki faz birlikte , büyük mesaj boyutları için uygun olana ihtiyaç duyar . ${\displaystyle {\frac {n}{k}}}$${\displaystyle (\log _{2}p-1)(T_{\mathbb {start} }+{\frac {n}{k}}*T_{\mathbb {byte}})}$${\displaystyle PE_{\mathbb {kök}}}$${\displaystyle k>\log _{2}p}$${\displaystyle 2\log _{2}p-1+3(k-1)}$${\displaystyle (4*\log _{2}p-2+6(k-1))(T_{\mathbb {start}}+{\frac {n}{k}}*T_{\mathbb {bayt } })}$${\görüntüleme stili n}$

Algoritma, tam dupleks veya telefon modeli iletişiminden yararlanılarak ve yukarı ve aşağı aşamaların üst üste bindirilmesiyle daha da optimize edilebilir .

Veri yapıları

Bir veri seti dinamik olarak güncellenebildiği zaman, bir Fenwick ağaç veri yapısında saklanabilir . Bu yapı, hem herhangi bir ön ek toplam değerinin aranmasına hem de işlem başına logaritmik zamanda herhangi bir dizi değerinin değiştirilmesine izin verir. Ancak, 1982 tarihli daha önceki bir makale, Fenwick ağaçlarıyla örtüşüyor gibi görünen Kısmi Toplamlar Ağacı (bkz. Bölüm 5.1) adlı bir veri yapısı sunar; 1982'de önek toplamı terimi henüz bugünkü kadar yaygın değildi.

Daha yüksek boyutlu diziler için, toplam alan tablosu , rastgele dikdörtgen alt dizilerin toplamlarını hesaplamak için önek toplamlarına dayalı bir veri yapısı sağlar. Bu, görüntü evrişim işlemlerinde yardımcı bir ilkel olabilir .

Uygulamalar

Sayma sıralaması , sıralanmış çıktı dizisindeki her bir anahtarın konumunu hesaplamak için bir anahtar frekans histogramının önek toplamını kullanan bir tamsayı sıralama algoritmasıdır . Öğe sayısından daha küçük olan tamsayı anahtarları için doğrusal zamanda çalışır ve sıklıkla , büyüklük olarak daha az kısıtlanmış tamsayıları sıralamak için hızlı bir algoritma olan radix sort'un bir parçası olarak kullanılır .

Liste sıralaması , bağlantılı bir listeyi aynı öğe dizisini temsil eden bir diziye dönüştürme sorunu, 1, 1, 1, ... dizisinde bir önek toplamının hesaplanması ve ardından her öğenin dizi konumuna eşlenmesi olarak görülebilir. önek toplamı değeriyle verilir; Liste sıralaması, önek toplamları ve Euler turlarını birleştirerek , ağaçlardaki birçok önemli problem verimli paralel algoritmalar ile çözülebilir.

Paralel önek toplamı algoritmalarının erken bir uygulaması, iki n- bitlik ikili sayı ekleyebilen Boolean devreleri olan ikili toplayıcıların tasarımındaydı . Bu uygulamada, toplamanın taşıma bitlerinin dizisi , önceki taşımayı bu iki bit ile birleştirmek için çoğunluk işlevini kullanarak, giriş biti çiftlerinin dizisi üzerinde bir tarama işlemi olarak temsil edilebilir . Çıkış numarasının her bir biti daha sonra tekabül eden taşıma biti ile iki giriş bitinin dışlayıcısı olarak bulunabilir . Paralel önek toplamı algoritmasının işlemlerini gerçekleştiren bir devre kullanarak, O ( n ) mantık kapıları ve O ( log n ) zaman adımlarını kullanan bir toplayıcı tasarlamak mümkündür .

Olarak paralel rastgele erişim makinesi işlem modelinde, önek toplamları aynı anda izin verilmediği paralel makinelerde erişmek için birden çok işlemci yeteneği aynı zamanda aynı hafıza hücresi, kabul paralel algoritmalar simüle etmek için kullanılabilir. Bir sıralama ağı aracılığıyla , bir dizi paralel bellek erişim talebi, aynı hücreye erişimler dizi içinde bitişik olacak şekilde bir dizi halinde sıralanabilir; tarama işlemleri daha sonra hangi erişimlerin istenen hücrelere yazmada başarılı olduğunu belirlemek ve bellek okuma işlemlerinin sonuçlarını aynı sonucu talep eden birden çok işlemciye dağıtmak için kullanılabilir.

In Guy Blelloch 'ın doktora Tez, paralel önek işlemleri , Bağlantı Makinesi gibi makineler tarafından sağlanan Veri paralellik modelinin resmileştirilmesinin bir parçasını oluşturur . Bağlantı Makinesi CM-1 ve CM-2 , yukarıdaki Algoritma 1'in uygulanabileceği hiperkübik bir ağ sağlarken, CM-5, Algoritma 2'yi uygulamak için özel bir ağ sağladı.

Yapımında gri kodları , özelliği ile ikili değerler sekansları ardışık sıra değerleri, tek bir bit konumunda birbirinden bir dizi farklı olduğu , n pozisyonunda Gray kodu değerine dönüştürülebilir n sadece alarak dizisinin özel veya bir n ve n / 2 (kaydırılarak oluşan sayısı , n , tek bir bit konumuna göre sağ). Gri kodlu bir x değerinin ikili bir sayıya kodunun çözülmesini içeren ters işlem daha karmaşıktır, ancak önek toplamı içindeki her toplama işleminin modülo iki gerçekleştirildiği , x'in bitlerinin önek toplamı olarak ifade edilebilir  . Bu tip bir ön ek toplamı hesaplanmasıyla, bit Modern bilgisayarlarda kullanılabilir Boolean işlemleri kullanılarak verimli bir şekilde gerçekleştirilebilir özel veya bir x kaydırılması ile oluşan her numara ile x bir bit sayısına göre sola ikinin bir gücü olduğundan .

Paralel önek (temeldeki ilişkisel işlem olarak çarpma kullanılarak), paralel polinom enterpolasyonu için hızlı algoritmalar oluşturmak için de kullanılabilir . Özellikle, interpolasyon polinomunun Newton formunun bölünmüş fark katsayılarını hesaplamak için kullanılabilir . Bu önek tabanlı yaklaşım aynı zamanda (birleşik) Hermite enterpolasyonu için genelleştirilmiş bölünmüş farkları elde etmek için ve ayrıca Vandermonde sistemleri için paralel algoritmalar için kullanılabilir.

Ayrıca bakınız

• Grafik işleme birimlerinde genel amaçlı bilgi işlem
• Toplam alan tablosu

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Kümülatif Toplam" . Matematik Dünyası .