Bölüm 14: Paralel Algoritmalar

14.1Paralel algoritma fikri

Bir sınıfın 1000 sınav kâğıdını tek bir öğretmen okusun. Kâğıt başına yaklaşık 36 saniye harcanırsa iş 10 saat sürer. Aynı kâğıtlar 10 öğretmen arasında paylaştırılırsa her öğretmen 100 kâğıt okur ve iş yaklaşık 1 saatte biter. Ama bu hesap eksiktir. Kâğıtları öğretmenlere dağıtmak zaman alır. Herkes bitirdikten sonra notları tek bir listede toplamak da zaman alır. Bir öğretmen geç kalırsa öteki dokuzu onu bekler. Paralel algoritmaların bütün konusu bu küçük örnekte gizlidir. İş bölünür, parçalar aynı anda yapılır ve sonuçlar birleştirilir. Bölmenin ve birleştirmenin bedeli ise kazancın bir kısmını geri alır.

14.1.1Neden paralellik?

Bazı işler tek bir işlemcide çok uzun sürer. Milyarlarca satırlık bir veri kümesini çözümlemek, bir hava durumu modelini günlerce ileri doğru çalıştırmak, binlerce görüntü üzerinde bir sinir ağını eğitmek bu türdendir. Bu işlerin süresini kısaltmanın iki yolu vardır: tek işlemciyi hızlandırmak ya da işi birden çok işlemciye bölmek.

Uzun yıllar boyunca birinci yol yeterli oldu. İşlemcilerin saat hızı her birkaç yılda bir katlanıyordu ve aynı program hiçbir değişiklik yapılmadan daha hızlı çalışıyordu. 2000'lerin ortasından bu yana bu artış neredeyse durdu. Saat hızını yükseltmek ısınmayı ve güç tüketimini kabul edilemez ölçüde artırıyor. Üreticiler bunun yerine tek bir yongaya birden çok çekirdek yerleştirmeye başladı. Bugün başarım artışı büyük ölçüde çekirdek sayısından gelir. Bir program bu artıştan ancak işini çekirdeklere bölebiliyorsa yararlanır.

Tanımdaki “aynı anda” ifadesi önemlidir. Tek çekirdekli bir bilgisayar da birden çok programı “aynı anda” çalıştırıyor gibi görünür. Gerçekte işletim sistemi programlar arasında hızla geçiş yapar ve herhangi bir anda yalnız biri çalışır. Paralel algoritmada ise birden çok işlemci gerçekten aynı saat diliminde iş yapar. Bu notta işlemci, çekirdek ve iş parçacığı sözcükleri bağlama göre aynı anlamda, yani “bağımsız çalışabilen bir hesap birimi” anlamında kullanılır.

14.1.2Böl, ata, çöz, birleştir

Paralel bir algoritmanın iskeleti çoğunlukla dört adımdan oluşur. Problem önce birbirinden olabildiğince bağımsız parçalara bölünür. Parçalar farklı işlemcilere atanır. İşlemciler parçalarını aynı anda çözer. Son olarak kısmi sonuçlar birleştirilerek asıl problemin sonucu elde edilir. Şekil 14.1 bu akışı dört işlemci için gösterir.

Bu yapı, böl ve fethet yöntemini andırır. Böl ve fethette de problem alt problemlere ayrılır ve sonuçlar birleştirilir. Fark, alt problemlerin çözülme biçimindedir. Sıralı böl ve fethette alt problemler birbiri ardına çözülür. Paralel algoritmada ise bağımsız alt problemler aynı anda çözülür. Bu yüzden böl ve fethet algoritmaları paralelleştirmeye en elverişli algoritmalar arasındadır.

Bir grup insanın ortak bir işi yürütmesi iyi bir benzetmedir. Bir ev taşınırken bir kişi kitapları, bir kişi mutfağı, bir kişi giysileri toplar. Herkes kendi işini bitirince kutular aynı kamyona yüklenir. İşin hızlanması için iki koşul gerekir. Birincisi, parçalar gerçekten bağımsız olmalıdır: mutfağı toplayan kişi kitapları toplayanı beklememelidir. İkincisi, parçalar kabaca eşit büyüklükte olmalıdır: kitaplar iki saat, giysiler on dakika sürüyorsa giysileri toplayan kişi çoğu zaman boş kalır.

Paralel hesaplama, yüksek başarımlı hesaplamanın (high-performance computing, HPC) temelidir. Büyük veri çözümlemesi, bilimsel benzetim ve makine öğrenmesi gibi alanlar bugün büyük ölçüde paralel algoritmalara dayanır.

14.1.3Kazanımlar ve zorluklar

Paralelliğin üç temel kazanımı vardır:

• Hızlanma. Aynı iş daha kısa sürede biter. Bir hava tahmini modeli yarın sabaha değil bu akşama hazır olur.
• Ölçeklenebilirlik. Tek bir makinenin belleğine ya da diskine sığmayan büyük problemler, birçok makineye dağıtılarak çözülebilir.
• Donanımın verimli kullanımı. Bilgisayardaki bütün çekirdekler ve grafik işlemcisi (GPU) iş yapar; boşta bekleyen donanım azalır.

Bu kazanımların bedeli de vardır:

• Bölme ve birleştirme ek çaba ister. Problemi parçalara ayırmak ve kısmi sonuçları birleştirmek sıralı algoritmada olmayan ek işlemlerdir.
• İletişim ve senkronizasyon ek yük getirir. İşlemciler veri alışverişi yapmak ve birbirini beklemek zorundadır. Bu süre boyunca yararlı iş yapılmaz.
• Yük dengeleme gerekir. İş, işlemcilere eşit dağıtılmalıdır. En uzun süren parça, bütün işin süresini belirler.
• Hata ayıklama zordur. Paralel programlarda yarış durumu ve kilitlenme (deadlock) gibi hatalar ortaya çıkar. Bu hatalar her çalıştırmada görülmeyebilir.
• Bazı problemler yapısı gereği sıralıdır. Bir adım bir önceki adımın sonucuna muhtaçsa o adımlar aynı anda yapılamaz.

Son madde paralelliğin kuramsal sınırını çizer. x_k = f(x_k−1) biçimindeki bir yinelemeyi düşünelim; f herhangi bir fonksiyon olsun. x₅'i hesaplamak için x₄ bilinmelidir, x₄ için de x₃. Bu bir veri bağımlılığı zinciridir. İşlemci sayısı ne olursa olsun zincirin halkaları birer birer hesaplanır. Böyle bir hesap paralelleştirilemez.

Her zincir ise bu kadar katı değildir. y_i = y_i−1 + x_i yinelemesi de ilk bakışta aynı yapıdadır. Ama toplama birleşmeli bir işlem olduğu için parantezler yeniden düzenlenebilir ve hesap ağaç biçiminde paralel yapılabilir. Bu fikir, önek toplamı kesiminde ayrıntılı işlenir. Bir zincirin paralelleştirilip paralelleştirilemeyeceği, zincirdeki işlemin cebirsel özelliklerine bağlıdır.

14.1.4Uygulama alanları

Paralelliğin işe yaradığı problemlerde ortak bir özellik vardır: işin büyük bir bölümü, birbirinden bağımsız küçük parçalara ayrılabilir. Dört tipik örnek şunlardır:

• Matris çarpımı. Bilimsel hesaplamanın temel işlemidir. C = A · B çarpımında sonuç matrisinin her satırı, hatta her hücresi ötekilerden bağımsız hesaplanabilir. Bu notun sonunda satır başına bir görevle çalışan bir Java çözümü verilir.
• Görüntü işleme. Kenar bulma, bulanıklaştırma ve nesne tanıma gibi işlemlerde her piksel ya da her piksel bloğu için aynı hesap yapılır. Bu, veri paralelliğinin en açık örneğidir. Grafik işlemcileri tam da bu tür iş için binlerce küçük çekirdek barındırır.
• Hesaplamalı akışkanlar dinamiği. Uçak, gemi ya da araba tasarımında hava ve su akışının benzetimi yapılır. Akış alanı bir ızgaraya bölünür ve her bölge bir işlemciye verilir. İşlemciler her zaman adımında yalnız komşu bölgelerle sınır değerlerini paylaşır.
• Genetik algoritmalar. Bir popülasyondaki bireylerin uygunluk değerleri birbirinden bağımsızdır ve aynı anda hesaplanabilir. Çizelgeleme ve rota bulma gibi problemlerde bu değerlendirme işin en pahalı kısmıdır.

14.2Paralel hesaplama modelleri

Paralel bir algoritmayı tasarlamak ve çözümlemek için önce hangi tür makinede çalışacağı belirlenmelidir. Sıralı algoritmalarda bu soru pek sorulmaz. Her bilgisayar aşağı yukarı aynı biçimde çalışır: bir işlemci komutları sırayla yürütür ve belleğe erişir. Paralel makineler ise birbirinden çok farklıdır. İşlemcilerin aynı komutu mu yoksa farklı komutları mı çalıştırdığı, belleği paylaşıp paylaşmadığı ve birbirleriyle nasıl haberleştiği değişir. Bu kesim paralel makineleri sınıflandıran iki bakış açısını ve kuramsal çözümlemede kullanılan PRAM modelini anlatır.

14.2.1Flynn sınıflandırması

Michael Flynn 1966'da bilgisayarları iki soruya göre sınıflandırdı. Birinci soru, aynı anda kaç komut akışının yürütüldüğüdür. İkinci soru, aynı anda kaç veri akışının işlendiğidir. Her sorunun yanıtı “tek” ya da “çok” olabildiği için dört sınıf ortaya çıkar. Tablo 14.1 bu sınıfları özetler. Sınıf adları İngilizce baş harflerden oluşur: S tek (single), M çok (multiple), I komut (instruction), D veri (data) anlamındadır.

SISD, sıralı algoritmaların varsaydığı klasik makinedir. Her saat adımında tek bir komut tek bir veri üzerinde yürütülür.

SIMD makinede tek bir denetim birimi vardır ama bu birim aynı komutu birçok veri üzerinde aynı anda uygular. Modern işlemcilerin vektör komutları bu türdendir. Örneğin AVX komut kümesindeki bir toplama komutu, sekiz tane 32 bitlik kayan noktalı sayıyı tek adımda başka sekiz sayıyla toplar. Grafik işlemcileri de aynı fikri çok daha büyük ölçekte uygular. SIMD, bir dizinin her öğesine aynı işlemin uygulandığı işlerde çok etkilidir. Öğeye göre farklı yollar izleyen dallanmalı kodda ise verimi düşer.

MISD uygulamada nadirdir. Aynı veri farklı komutlarla işlenir. Uçak denetim sistemleri gibi hata toleranslı sistemlerde aynı girdi birkaç ayrı birimde bağımsız olarak hesaplanır ve sonuçlar karşılaştırılır. Bu düzen MISD sınıfına örnek gösterilir.

MIMD en genel sınıftır. Her işlemci kendi programını kendi verisi üzerinde, ötekilerden bağımsız çalıştırır. Çok çekirdekli kişisel bilgisayarlar ve birçok bilgisayarın ağla bağlandığı kümeler MIMD makinelerdir.

Flynn sınıflandırması iki paralellik biçimini de ayırt etmeye yarar. Veri paralelliğinde aynı işlem verinin farklı parçalarına aynı anda uygulanır; bu SIMD tarzıdır. Görev paralelliğinde ise farklı görevler aynı anda yürütülür; bu MIMD tarzıdır. Bir web sunucusunun aynı anda farklı istemcilere farklı sayfalar hazırlaması görev paralelliğidir. Bir görüntünün bütün piksellerinin parlaklığının aynı oranda artırılması veri paralelliğidir.

14.2.2Bellek mimarileri

MIMD makineler belleği düzenleme biçimlerine göre ikiye ayrılır. Şekil 14.2 iki düzeni yan yana gösterir.

Paylaşımlı bellek (shared memory) düzeninde bütün işlemciler aynı adres uzayını görür. Bir işlemcinin belleğe yazdığı değeri öteki işlemci doğrudan okuyabilir. İletişim bu yüzden ucuzdur: veri taşımak yerine ortak bir değişken kullanmak yeter. Bedeli, eşzamanlı erişimin denetlenmesidir. İki işlemci aynı değişkeni aynı anda değiştirmeye çalışırsa sonuç bozulabilir; bu yüzden erişimler bir senkronizasyon düzeneğiyle sıraya konmalıdır. Java'nın iş parçacıkları ve ForkJoinPool sınıfı, C ve Fortran için OpenMP bu düzene yönelik araçlardır. Tek bir bilgisayarın çekirdekleri paylaşımlı bellekle çalışır.

Dağıtık bellek (distributed memory) düzeninde her düğümün kendi belleği vardır. Bir düğüm başka bir düğümün belleğine doğrudan erişemez. Veri gerekiyorsa sahibi onu bir ileti (message passing) olarak ağ üzerinden gönderir. Bu düzen çok iyi ölçeklenir: binlerce düğüm aynı problemi çözebilir. Ama iletişim pahalıdır. Ağ üzerinden bir ileti göndermek, yerel bellekten okumaktan yüzlerce kat uzun sürebilir. Bu düzen için yazılan programlar ileti sayısını en aza indirmeye çalışır. Bilimsel hesaplamada yaygın kullanılan MPI (Message Passing Interface) kütüphanesi ve Hadoop MapReduce dağıtık bellek araçlarıdır.

Bu notta Java örnekleri paylaşımlı bellekte çalışır. Boru hattı ve boru hatlı ağaç örnekleri ise işlemcilerin yalnız komşularıyla ileti alışverişi yaptığı dağıtık bir düzeni varsayar. MapReduce de aslen dağıtık bellek için tasarlanmıştır; buradaki Java örneği aynı fikri tek makinede gösterir.

14.2.3PRAM modeli

Sıralı algoritmaları çözümlerken gerçek bir bilgisayar yerine basitleştirilmiş bir model kullanılır: RAM (Random Access Machine) modeli. Bu modelde her temel işlem ve her bellek erişimi bir birim zaman sürer. Önbellek, sanal bellek ve boru hattı gibi ayrıntılar yok sayılır. Model gerçeği tam yansıtmaz ama algoritmaları karşılaştırmak için yeterince doğrudur. Paralel algoritmalar için de benzer bir model gerekir.

Modelin en güçlü varsayımı, iletişimin bedava olmasıdır. Gerçek bir makinede iki işlemcinin bir değeri paylaşması zaman alır; PRAM'da bir işlemcinin yazdığı değer bir sonraki adımda bütün işlemcilerce okunabilir. İşlemcilerin ortak saatle çalışması da senkronizasyonu bedava kılar. Bir tur bittiğinde bütün işlemcilerin o turu bitirdiği kesindir. Bu varsayımlar gerçekçi değildir, ama bir amaca hizmet eder. Model, iletişim ve donanım ayrıntılarını kenara bırakarak algoritmanın içsel paralelliğini ölçer. Bir algoritma PRAM'da bile paralel çalışamıyorsa gerçek bir makinede hiç çalışamaz. PRAM'da hızlı çalışan bir algoritma ise gerçek makinede iletişim maliyeti ölçüsünde yavaşlar.

Ortak bellekte bir sorun daha vardır: birden çok işlemci aynı adımda aynı bellek hücresine erişirse ne olur? PRAM'ın türleri bu soruya verilen yanıta göre adlandırılır. Tablo 14.2 üç yaygın türü gösterir.

Dışlayıcı erişim, aynı hücreye bir adımda yalnız tek işlemcinin erişebileceği anlamına gelir. Eşzamanlı erişimde birden çok işlemci aynı hücreye aynı adımda erişebilir. EREW en kısıtlı, CRCW en güçlü türdür. Eşzamanlı okuma zararsızdır: herkes aynı değeri okur. Eşzamanlı yazma ise bir kural gerektirir. Üç işlemci aynı hücreye 5, 7 ve 9 yazmaya çalışırsa hücrede hangi değer kalır? Yaygın kurallar şunlardır:

• Ortak değer kuralı: Yazma ancak bütün işlemciler aynı değeri yazıyorsa geçerlidir.
• Rastgele kural: İşlemcilerden biri rastgele seçilir ve onun değeri yazılır.
• Öncelik kuralı: En küçük numaralı (en yüksek öncelikli) işlemcinin değeri yazılır.

Bir algoritma EREW'de çalışıyorsa CREW ve CRCW'de de çalışır, çünkü güçlü model zayıf modelin her işlemine izin verir. Tersi her zaman doğru değildir. Bu yüzden bir algoritmanın hangi modelde çalıştığı belirtilirken olabildiğince zayıf model seçilir. Bu notta incelenen ağaç toplamı ve önek toplamı algoritmaları EREW ile yetinir.

14.3Başarım ölçütleri

Paralel bir algoritmanın iyi olup olmadığı tek bir sayıyla söylenemez. Algoritma hızlı olabilir ama bunun için çok fazla işlemci harcıyor olabilir. Çok işlemciyle hızlı olabilir ama işlemci sayısı arttıkça kazancı duraksayabilir. Bu kesim, paralel algoritmaları karşılaştırmak için kullanılan ölçütleri tanıtır.

14.3.1Hızlanma, verimlilik, maliyet

Ölçütlerin hepsi iki süreye dayanır. T₁, problemi tek işlemcide çözen en iyi sıralı algoritmanın süresidir. T_p ise paralel algoritmanın p işlemcideki süresidir. Tablo 14.3 bu iki süreden türetilen üç ölçütü verir.

Hızlanma, işlemci eklemenin işi kaç kat kısalttığını söyler. p işlemciyle en iyi durumda p kat hızlanma beklenir; buna doğrusal hızlanma denir. Verimlilik, işlemcilerin zamanının ne kadarının yararlı işe gittiğini gösterir. E = 1 ise hiçbir işlemci boşa vakit harcamamıştır. E = 0,5 ise işlemci zamanının yarısı bekleme, iletişim ya da gereksiz işle geçmiştir.

Maliyet, paralel algoritmanın toplam olarak ne kadar “işlemci-saniye” tükettiğini ölçer. Sıralı algoritma T₁ işlemci-saniye harcar. Paralel algoritma ondan daha az harcayamaz; çünkü öyle olsaydı paralel algoritmanın adımları tek işlemcide sırayla yürütülerek T₁'den kısa süren bir sıralı algoritma elde edilirdi. Bu, T₁'in en iyi sıralı süre olmasıyla çelişir. Demek ki her zaman C ≥ T₁, dolayısıyla S ≤ p ve E ≤ 1'dir. Maliyet-optimal bir algoritma, sıralı algoritmanın yaptığı işi en fazla sabit bir çarpanla artırarak işlemcilere dağıtır.

Hızlanmanın p'nin altında kalmasının dört yaygın nedeni vardır. Birincisi iletişimdir: işlemciler veri alışverişi yaparken hesap yapmaz. İkincisi beklemedir: bir işlemci başka bir işlemcinin sonucunu beklerken boştadır. Üçüncüsü yük dengesizliğidir: işi erken bitiren işlemciler en yavaşını bekler. Dördüncüsü sıralı kısımlardır: programın paralelleştirilemeyen bölümü, işlemci sayısından bağımsız olarak hep aynı süreyi alır. Son nedenin etkisi Amdahl yasasıyla hesaplanır.

14.3.2Amdahl yasası ve Gustafson yasası

Gerçek programların neredeyse hepsinde paralelleştirilemeyen bir bölüm vardır. Girdiyi diskten okumak, ayarları yüklemek, kısmi sonuçları tek bir çıktıda birleştirmek bu türden işlerdir. Gene Amdahl 1967'de bu sıralı bölümün hızlanmaya getirdiği sınırı basit bir hesapla gösterdi.

Programın tek işlemcide süresi T₁ olsun. Bu sürenin f kesri paralelleştirilebilir, 1 − f kesri sıralıdır. p işlemcide sıralı kısım yine (1 − f) T₁ sürer. Paralel kısım ise en iyi durumda p'ye tam bölünür ve f T₁ / p sürer. Toplam paralel süre

T_p = (1 − f) T₁ + f T₁ / p

olur. Hızlanma T₁ / T_p olduğundan T₁ sadeleşir ve aşağıdaki sonuç elde edilir.

Yasanın asıl mesajı limittedir. İşlemci sayısı ne kadar artarsa artsın f / p terimi sıfıra yaklaşır, ama 1 − f terimi yerinde kalır. Sıralı kısım hızlanmayı sınırlar. Programın %10'u sıralıysa (f = 0,9) sonsuz sayıda işlemciyle bile hızlanma 10'u geçemez. %5'i sıralıysa sınır 20'dir.

Şekil 14.5'deki eğriler bu etkiyi gösterir. f = 0,9 eğrisi 4 işlemcide yaklaşık 3,1'e, 16 işlemcide 6,4'e, 64 işlemcide 8,8'e ulaşır. 1024 işlemcide ise yalnız 9,9'dur. 64'ten 1024'e çıkmak işlemci sayısını 16 katına çıkarır ama hızlanmayı yalnız %13 artırır. Bir programı çok işlemciye taşımadan önce sıralı kısmı küçültmek bu yüzden daha kârlıdır. Sıralı kısmı %10'dan %1'e indirmek, 1000 işlemcide hızlanmayı yaklaşık 10'dan 91'e çıkarır.

Amdahl yasası bir varsayıma dayanır: problemin boyutu sabittir ve yalnız işlemci sayısı artar. Uygulamada çoğu zaman böyle olmaz. Daha çok işlemci bulan bir araştırmacı aynı problemi daha hızlı çözmek yerine daha büyük bir problem çözer. Hava tahmini daha ince bir ızgarayla yapılır, benzetim daha çok parçacıkla çalıştırılır. Bu durumda sıralı kısım çoğunlukla aynı kalır ama paralel kısım işlemci sayısıyla birlikte büyür.

John Gustafson 1988'de bu bakış açısını formüle döktü. Paralel çalıştırmanın süresi 1 birim olsun. Bunun 1 − f kesri sıralı, f kesri paraleldir. Aynı iş tek işlemcide yapılsaydı sıralı kısım yine 1 − f sürerdi. Paralel kısım ise p işlemcinin yaptığı işi tek başına yapmak zorunda kalır ve f · p sürer. Ölçeklenmiş hızlanma

S = (1 − f) + f · p

olur. Buna Gustafson yasası denir. f = 0,9 ve p = 8 için S = 0,1 + 7,2 = 7,3 bulunur. Aynı değerlerle Amdahl yasası 4,71 vermişti. İki yasa çelişmez; farklı soruları yanıtlar. Amdahl yasası “aynı problemi kaç kat hızlı çözerim?” sorusunu, Gustafson yasası “aynı sürede kaç kat büyük problem çözerim?” sorusunu yanıtlar. Gustafson yasasına göre büyük problemlerde paralellik daha kârlıdır, çünkü sıralı kısmın toplam işteki payı küçülür.

14.3.3İş, derinlik ve Brent teoremi

Hızlanma ve verimlilik belirli bir işlemci sayısı için hesaplanır. Bir algoritmanın paralelliğini işlemci sayısından bağımsız olarak anlatmak için iki büyüklük kullanılır: iş ve derinlik. İkisi de algoritmanın işlemlerini bir bağımlılık çizgesi olarak görmeye dayanır. Çizgenin her düğümü bir temel işlemdir. u → v kenarı, v işleminin u'nun sonucunu kullandığını, yani u bitmeden başlayamayacağını gösterir. Döngü olamaz; çünkü bir işlem kendi sonucunu bekleyemez.

Şekil 14.6'teki çizgede yedi işlem vardır; tek işlemci bunları yedi adımda bitirir. Sınırsız işlemci olsa bile kırmızı yol üzerindeki dört işlem birbirini bekler ve dört adımdan önce bitemez. Derinlik, işlemci sayısıyla aşılamayan bir sınırdır. Paralellik 7 / 4 = 1,75'tir: ortalama olarak her adımda 1,75 işlem aynı anda yapılabilir. İkiden fazla işlemci bu çizgeye neredeyse hiç yarar sağlamaz.

Paralellik, yararlı biçimde kullanılabilecek en fazla işlemci sayısı olarak yorumlanır. İşlemci sayısı paralelliği aşarsa bazı işlemciler çoğu adımda boş kalır. İki temel alt sınır şöyledir:

• T_p ≥ W / p: p işlemci bir adımda en çok p işlem yapar; W işlem en az W / p adım ister.
• T_p ≥ D: en uzun zincirdeki işlemler birbirini bekler; işlemci sayısı bunu değiştirmez.

Bir üst sınır da vardır ve paralel algoritmaların çözümlemesinde çok kullanılır.

Alt ve üst sınırlar birlikte okunduğunda max(W / p, D) ≤ T_p ≤ W / p + D elde edilir. Üst sınır alt sınırın en çok iki katıdır. Bu yüzden W ve D bilinince herhangi bir işlemci sayısı için süre iki kat yakınlıkla kestirilebilir. p paralellikten çok küçükse W / p terimi baskındır ve hızlanma neredeyse doğrusaldır. p paralellikten büyükse D terimi baskındır ve yeni işlemciler süreyi kısaltmaz.

Bir paralel algoritmanın işi, aynı problemin en iyi sıralı algoritmasının süresiyle aynı mertebedeyse algoritmaya iş-verimli (work-efficient) denir. İş-verimli olmayan bir algoritma işlemci az olduğunda sıralı algoritmadan bile yavaş kalabilir. Önek toplamı kesimi bunun somut bir örneğini verir.

14.4PRAM ile toplama

Paralel algoritmaların en basit ve en öğretici örneği n sayının toplamıdır. Problem çok basittir ama paralel çözüm, bu notun geri kalanında tekrar tekrar karşılaşılacak bir fikri içerir: birleşmeli bir işlemle kurulan zincir, dengeli bir ağaca çevrilebilir.

14.4.1Problem ve birleşmeli işlem

Girdi n sayıdır; çıktı bu sayıların toplamıdır. Sıralı algoritma bir toplam değişkenini sıfırdan başlatır ve her sayıyı ona ekler. n − 1 toplama yapar ve O(n) sürer. Bu sıralı döngünün bağımlılık çizgesi bir zincirdir: her toplama, bir önceki toplamanın sonucunu bekler. Zincirin uzunluğu n − 1'dir; derinlik işe eşittir ve paralellik yoktur.

Zinciri kıran şey toplamanın birleşmeli (associative) olmasıdır: (a + b) + c = a + (b + c). Birleşmeli bir işlemde parantezler istenildiği gibi yerleştirilebilir. Sekiz sayının toplamı sıralı döngüde

((((((2 + 3) + 5) + 1) + 7) + 6) + 8) + 4

biçiminde hesaplanır. Aynı toplam şöyle de yazılabilir:

((2 + 3) + (5 + 1)) + ((7 + 6) + (8 + 4))

İkinci yazılış dengeli bir ikili ağaçtır. En içteki dört toplama birbirinden bağımsızdır ve aynı anda yapılabilir. Onların sonuçlarını kullanan iki toplama da birbirinden bağımsızdır. En dıştaki toplama son olarak yapılır. Ağacın her düzeyindeki toplamlar aynı turda paralel yapılır. Şekil 14.7 bu ağacı gösterir.

Aynı fikir her birleşmeli işlem için çalışır: en büyük, en küçük, çarpım, mantıksal VE (AND), mantıksal VEYA (OR). Bir diziyi birleşmeli bir işlemle tek bir değere indiren bu genel işleme indirgeme (reduction) denir. Toplama ağacında toplama yerine Math.max kullanılırsa aynı turlarda en büyük öğe bulunur.

14.4.2Ağaç toplamı adım adım

Örnek dizi 2, 3, 5, 1, 7, 6, 8, 4'tür; toplamı 36'dır. Sekiz işlemci p₀ … p₇ birer sayı tutar. Algoritma turlar hâlinde ilerler:

1. Başlangıç. Sekiz sayı sekiz işlemciye birer birer dağıtılır.
2. Tur 1. Dört işlemci aynı anda komşu çiftleri toplar: 2 + 3 = 5, 5 + 1 = 6, 7 + 6 = 13, 8 + 4 = 12. Sonuçlar çiftin solundaki işlemcide (p₀, p₂, p₄, p₆) kalır.
3. Tur 2. İki işlemci, aralarındaki uzaklık 2 olan kısmi toplamları birleştirir: p₀'da 5 + 6 = 11, p₄'te 13 + 12 = 25.
4. Tur 3. p₀, 11 + 25 = 36 sonucunu bulur.

Sekiz sayı log₂ 8 = 3 turda toplandı. Sıralı algoritma 7 adım sürerdi. Toplama sayısı ise değişmedi: 4 + 2 + 1 = 7. Paralel algoritma fazladan iş yapmadan yalnız sırayı değiştirdi. Bu yüzden ağaç toplamı iş-verimlidir.

Turlardan dikkat çeken bir şey daha görülür. Tur 1'de dört, tur 2'de iki, tur 3'te bir işlemci çalışır. Öteki işlemciler boşta bekler. Sekiz işlemcinin hiçbir turda hepsi çalışmaz; hatta ilk tur için bile dört işlemci yeterlidir. Bu gözlem, maliyet çözümlemesinde önemli olacaktır.

14.4.3Kod izleme

Ağaç toplamı Java'da aşağıdaki gibi yazılır. Kod sıralı bir programdır; ama iç döngünün yinelemeleri aynı turda birbirinden bağımsızdır ve PRAM'da paralel yürütülür. Dış döngünün her yinelemesi bir turdur.

int[] a = {2, 3, 5, 1, 7, 6, 8, 4};
int n = a.length;
for (int adim = 1; adim < n; adim *= 2) {
  // aynı turdaki tüm i'ler paralel
  for (int i = 0; i + adim < n; i += 2 * adim)
    a[i] = a[i] + a[i + adim];
}  // tur sonu: senkronizasyon
// toplam a[0]'da

Kodun parçaları şöyle çalışır:

• adim, bir turda toplanan iki hücrenin arasındaki uzaklıktır. 1'den başlar ve her turda iki katına çıkar: 1, 2, 4. adim en az n olunca döngü biter.
• İç döngüde i, 2 * adim'in katlarını gezer. Turda iş yapan hücreler bunlardır. Tur 1'de 0, 2, 4, 6; tur 2'de 0, 4; tur 3'te yalnız 0.
• a[i] = a[i] + a[i + adim], sağdaki kısmi toplamı soldakine ekler. Her turdan sonra a[i], i'den başlayan 2 * adim uzunluğundaki bloğun toplamını tutar.
• i + adim < n koşulu, eşi olmayan hücrenin dizi dışını okumasını engeller. n ikinin kuvveti değilse bazı hücreler bir tur boyunca eşsiz kalır ve bir sonraki tura beklemeden geçer.
• Tur sonundaki yorum, senkronizasyonu hatırlatır. Bir sonraki tur, önceki turun bütün yazmaları bittikten sonra başlamalıdır.

Aynı turdaki yazmalar ayrı hücrelere yapılır. Okunan hücreler de turdan tura farklıdır: tur 1'de a[1], a[3], a[5], a[7] okunur ve bunlara yazılmaz. Hiçbir hücreye aynı turda iki işlemci erişmez. Bu yüzden EREW PRAM yeterlidir. Tablo 14.4 kodun izlemesidir; değerler programın çalıştırılmasıyla doğrulanmıştır.

Son dizide a[4] = 25 ve a[2] = 6 gibi ara toplamlar durur. Algoritma diziyi bozar; yalnız a[0] anlamlıdır. Asıl dizi gerekiyorsa algoritma bir kopya üzerinde çalıştırılmalıdır.

14.4.4Analiz ve maliyet-optimal sürüm

Ağaç toplamının süresi tur sayısıdır: ⌈log₂ n⌉. İşi n − 1 toplamadır; sıralı algoritmayla aynıdır. İşlemci sayısı ilk turdaki toplama sayısı kadar, yani n / 2 olmalıdır. Çözümlemede kolaylık için çoğu zaman n işlemci yazılır; mertebe değişmez. Maliyet ise iyi değildir: (n / 2) · log₂ n = Θ(n log n). En iyi sıralı süre Θ(n) olduğuna göre algoritma maliyet-optimal değildir.

Maliyetin yüksek olmasının nedeni turlarda görülmüştü. İşlemcilerin yarısı tur 1'den sonra, dörtte üçü tur 2'den sonra boştur. Boş bekleyen işlemciler de maliyete sayılır; çünkü maliyet işlemci sayısını sürenin tamamıyla çarpar.

Çözüm, işlemci sayısını azaltıp her işlemciye daha çok iş vermektir. p = n / log₂ n işlemci kullanılsın. Algoritma iki evreden oluşur:

1. Yerel toplam. Dizi p bloğa bölünür; her blokta log₂ n sayı vardır. Her işlemci kendi bloğunu sıralı olarak toplar. Bu evre O(log n) sürer.
2. Ağaçla birleştirme. p = n / log₂ n kısmi toplam, ağaç toplamıyla birleştirilir. Bu evre ⌈log₂ p⌉ ≤ log₂ n tur, yani O(log n) sürer.

Toplam süre yine O(log n)'dir. Maliyet ise (n / log n) · O(log n) = Θ(n) olur. Algoritma artık maliyet-optimaldir. Tablo 14.5 iki sürümü karşılaştırır.

Bu teknik, Brent teoreminin somut bir uygulamasıdır. Ağaç toplamında W = n − 1 ve D = log₂ n'dir. p = n / log₂ n için Brent üst sınırı W / p + D ≈ log₂ n + log₂ n = 2 log₂ n verir. Süre yalnız iki katına çıkar, işlemci sayısı ise log₂ n kat azalır. Örneğin n = 1024 için işlemci sayısı 1024'ten yaklaşık 102'ye iner.

Algoritmanın doğru çalışması için her turun sonunda bir bariyer (barrier) gerekir. Bariyer, bütün işlemciler ona ulaşmadan hiçbirinin geçemediği bir eşgüdüm noktasıdır. PRAM ortak saatle çalıştığı için bariyeri bedava sağlar. Gerçek bir makinede ise her bariyerin bir bedeli vardır; bu yüzden tur sayısının az olması gerçek makinede de önemlidir.

14.5Paralel önek toplamı

Ağaç toplamı yalnız tek bir sonuç üretir: dizinin toplamını. Birçok problemde ise her konum için ayrı bir toplam gerekir. Bir banka hesabının her işlemden sonraki bakiyesi, bir histogramın birikimli değerleri, sayarak sıralamada her öğenin yerleşeceği konum bu türdendir. Bu kesim, bütün bu değerleri aynı anda hesaplayan iki paralel algoritmayı anlatır.

14.5.1Problem

2 3 5 1 7 6 8 4 dizisinin kapsayıcı önek toplamı 2 5 10 11 18 24 32 36'dır. Dışlayıcı önek toplamı ise bir konum sağa kaymış hâlidir: 0 2 5 10 11 18 24 32. Biri ötekinden kolayca elde edilir. Kapsayıcıdan dışlayıcıya geçmek için her konumdan kendi öğesi çıkarılır; ters yönde her konuma kendi öğesi eklenir.

Sıralı algoritma tek bir döngüdür: y_i = y_i−1 + x_i. n − 1 toplama yapar ve O(n) sürer. Ama tamamen zincirlemedir: her adım bir öncekinin sonucunu bekler. İlk bakışta paralel bir çözüm olanaksız görünür, çünkü y₇, y₆'ya; y₆ de y₅'e bağlıdır.

Ağaç toplamı bu zinciri kırmanın yolunu göstermişti. Ağaç toplamında da her ara toplam bir bloğun toplamıdır. Fark şudur: ağaç toplamı yalnız son hücrede, yani bütün dizinin toplamında durur. Önek toplamında ise her hücrenin kendi önekini öğrenmesi gerekir. Ağaçtaki ara toplamlar bu bilginin parçalarıdır; geriye onları doğru biçimde dağıtmak kalır.

14.5.2Hillis–Steele algoritması

W. Daniel Hillis ve Guy Steele'in 1986'da yayımladığı algoritma çok basit bir kurala dayanır. d = 1, 2, 4, … değerleri için her turda, i ≥ d olan her konum kendi değerine d soldaki değeri ekler:

x[i] ← x[i] + x[i − d] (her i ≥ d için, aynı turda paralel)

Turdaki bütün okumalar, o turun yazmalarından önceki değerleri görmelidir. PRAM'da bütün işlemciler önce okur, sonra yazar; bu koşul kendiliğinden sağlanır. Sıralı bir benzetimde ise her turda eski dizinin bir kopyası tutulur ve okumalar kopyadan yapılır.

Algoritmanın neden doğru olduğu bir değişmezle görülür. d turu bittiğinde her x[i], i'de biten ve en çok 2d öğe içeren pencerenin toplamını tutar. Başta (d = 1 turundan önce) her hücre yalnız kendisini, yani 1 öğelik pencereyi tutar. d turunda x[i]'ye x[i − d] eklenir. Turdan önce x[i], i − d + 1 … i aralığını; x[i − d] ise i − 2d + 1 … i − d aralığını tutar. İki aralık bitişiktir ve toplamları i − 2d + 1 … i aralığını verir. Pencere dizinin başına dayanınca kesilir. ⌈log₂ n⌉ turdan sonra pencere boyu n'yi geçer ve her hücre kendi önekinin tamamını tutar.

Tablo 14.6 örnek dizi için her turun sonucunu verir. Değerler bir Java programıyla, kopyalı benzetimle doğrulanmıştır.

Tablonun bir satırını açıkça kontrol edelim. d = 2 turunun sonunda x[5] = 19'dur. Bu değer, 5'te biten 4 öğelik pencerenin, yani x₂ + x₃ + x₄ + x₅ = 5 + 1 + 7 + 6 = 19'un toplamıdır. Hesap şöyle yapılmıştır: turdan önce x[5] = 13 (6 + 7) ve x[3] = 6 (1 + 5); 13 + 6 = 19.

Algoritma log₂ 8 = 3 turda bitti. Derinlik D = ⌈log₂ n⌉'dir. Ama toplama sayısı 7 + 6 + 4 = 17'dir; sıralı algoritma 7 toplama yapar. Genel olarak d turunda n − d toplama yapılır. n ikinin kuvvetiyse toplam iş

W = Σ_{d = 1, 2, 4, …, n/2} (n − d) = n log₂ n − (n − 1)

olur. n = 8 için 24 − 7 = 17. İş Θ(n log n)'dir ve sıralı algoritmanın Θ(n) işinden fazladır. Hillis–Steele iş-verimli değildir. İşlemci sayısı çoksa bu önemsizdir; çünkü fazladan işlemler aynı turda bedavaya yapılır. İşlemci azsa fazladan iş doğrudan süreye eklenir. Örneğin tek işlemcide Hillis–Steele n log n sürer, sıralı tarama ise n sürer.

14.5.3Blelloch algoritması

Guy Blelloch'un 1990'da yaygınlaştırdığı algoritma önek toplamını O(n) işle ve O(log n) derinlikle hesaplar. Diziyi örtük bir ikili ağaç gibi kullanır ve iki evrede çalışır. Yukarı süpürme (up-sweep) evresi, ağaç toplamının aynısıdır: yapraklardan köke doğru kısmi toplamlar kurulur. Aşağı süpürme (down-sweep) evresi kökten yapraklara doğru iner ve her düğüme “solundaki bütün öğelerin toplamını” taşır.

// yukarı süpürme; x = 2 3 5 1 7 6 8 4
for (int d = 1; d < n; d *= 2)
  for (int i = 2*d - 1; i < n; i += 2*d)
    x[i] += x[i - d];
x[n - 1] = 0;
// aşağı süpürme (iç döngüler paralel)
for (int d = n / 2; d >= 1; d /= 2)
  for (int i = 2*d - 1; i < n; i += 2*d) {
    int t = x[i - d];
    x[i - d] = x[i];
    x[i] += t;
  }
// x: dışlayıcı önek toplamları

Kodun parçaları şöyle çalışır:

• Yukarı süpürme. d = 1, 2, 4 için i = 2d − 1, 4d − 1, … hücrelerinde x[i] += x[i - d] yapılır. Ağaç toplamından tek farkı, toplamların bloğun soluna değil sağına, yani son hücresine yazılmasıdır. Evre sonunda x[n - 1] bütün dizinin toplamını tutar.
• Kök sıfırlanır. x[n - 1] = 0. Kökün solunda hiçbir öğe yoktur; solundakilerin toplamı 0'dır.
• Aşağı süpürme. d = n/2, …, 2, 1 için her (i − d, i) çiftinde üç satır çalışır. t, sol çocuğun eski değerini, yani sol alt ağacın toplamını saklar. Sol çocuk ebeveynin değerini alır: sol alt ağacın solundaki öğeler, ebeveynin solundakilerle aynıdır. Sağ çocuk ebeveynin değerine sol alt ağacın toplamını ekler: sağ alt ağacın solunda, ebeveynin solundakilere ek olarak sol alt ağaç da vardır.
• Bir turdaki çiftler birbirinden ayrık hücrelere dokunur; iç döngü paralel çalışır ve EREW yeterlidir.

Tablo 14.7 örnek dizi için iki evrenin bütün turlarını verir. Değerler kodun çalıştırılmasıyla doğrulanmıştır.

Son turu tek tek açalım. Çift (0, 1): t = x[0] = 2; x[0] = x[1] = 0; x[1] = 0 + 2 = 2. Çift (2, 3): t = 5; x[2] = 5; x[3] = 5 + 5 = 10. Çift (4, 5): t = 7; x[4] = 11; x[5] = 11 + 7 = 18. Çift (6, 7): t = 8; x[6] = 24; x[7] = 24 + 8 = 32. Sonuç 0 2 5 10 11 18 24 32'dir; bu, dışlayıcı önek toplamıdır. Kapsayıcı sonuç gerekiyorsa her hücreye girdideki kendi değeri eklenir ya da dizi bir konum sola kaydırılıp sona toplam (36) yazılır.

Algoritmanın maliyeti şöyle sayılır. Yukarı süpürme ağaç toplamıyla aynıdır: n − 1 toplama, log₂ n tur. Aşağı süpürmede her iç düğüm için bir işlem yapılır: yine n − 1 işlem, log₂ n tur. Toplam iş 2(n − 1)'dir; örnekte 14 işlem. Derinlik 2 log₂ n'dir; örnekte 6 tur. İş O(n) olduğu için Blelloch algoritması iş-verimlidir. Hillis–Steele'e göre iki kat tur harcar ama toplam işi log n kat azdır.

14.5.4İki algoritmanın karşılaştırması

Hangi algoritmanın seçileceği işlemci sayısına bağlıdır. İşlemci sayısı n düzeyindeyse, örneğin bir GPU'da bir blok içinde, Hillis–Steele'in az turu avantajdır. İşlemci sayısı n'den çok küçükse Blelloch'un az işi belirleyicidir. Brent teoremine göre p işlemcide Hillis–Steele O(n log n / p + log n), Blelloch O(n / p + log n) sürer.

Önek toplamı paralel algoritmaların en çok kullanılan yapı taşlarından biridir. Paralel sayarak sıralamada her anahtarın çıktıdaki konumu önek toplamıyla bulunur. Bir diziden belirli bir koşulu sağlayan öğeleri seçip sıkıştırmak (filter) için her öğeye koşulu sağlıyorsa 1, sağlamıyorsa 0 yazılır. Bu 0/1 dizisinin dışlayıcı önek toplamı, seçilen her öğenin yeni dizideki konumunu verir. Java'da Arrays.parallelPrefix(dizi, Integer::sum) metodu bir diziyi kapsayıcı önek toplamıyla yerinde değiştirir. Örnek dizi için 2 5 10 11 18 24 32 36 sonucunu verir.

14.6Boru hattı

Şimdiye kadarki algoritmalar işlemcilerin ortak belleği paylaştığını varsaydı. Bu kesimde işlemciler bir zincir biçiminde bağlıdır ve yalnız komşularıyla ileti alışverişi yapar. Böyle bir düzende paralelliğin önemli bir kaynağı boru hattıdır.

14.6.1Boru hattı fikri

Fabrikadaki montaj hattı iyi bir benzetmedir. Bir otomobil gövdesi kaynak bölümünden boya bölümüne geçtiğinde kaynak bölümü bir sonraki gövdeye başlar. Tek bir otomobilin hattan çıkma süresi kısalmaz; her gövde bütün aşamalardan geçmek zorundadır. Ama hattan birim zamanda çıkan otomobil sayısı, yani verim (throughput), aşama sayısı kadar artar.

k aşamalı bir boru hattında m iş yapılsın; her aşama bir zaman adımı sürsün. Sıralı yürütmede her iş k adım sürer ve işler birbiri ardına yapılır: k · m adım. Boru hattında ilk iş k adımda biter. Sonraki her iş, öncekinden bir adım sonra biter. Toplam süre k + m − 1 adımdır.

Şekil 14.12 üç aşama ve dört iş için hattı gösterir. Başta hat dolarken (t₁ ve t₂) ve sonda boşalırken (t₅ ve t₆) bazı aşamalar boştur. Hat yalnız t₃ ve t₄ anlarında doludur; o anlarda üç aşamanın üçü de çalışır. İş sayısı aşama sayısına göre çok büyükse dolma ve boşalma süresi önemsizleşir ve süre m'ye yaklaşır.

14.6.2Zincirde satır toplamları

Boru hattının paralel algoritmalardaki kullanımını somut bir problem gösterir. Beş işlemci p₀ … p₄ doğrusal bir zincir oluşturur. Her işlemci yalnız sağ komşusuna ileti gönderebilir. Her p_j, 4 değerlik bir sütun tutar; satırlar 0'dan 3'e numaralıdır. İşlemcilerin sütunları yan yana konunca 4 satırlık, 5 sütunluk bir tablo oluşur.

Amaç şudur: her satır r için p_j'deki değer, p₀ … p_j'nin o satırdaki değerlerinin toplamı olsun. Bu, her satırda ayrı bir önek toplamıdır. Sonunda p₄ her satırın toplamını tutar. Bir adımda her işlemci sağ komşusuna bir değer gönderebilir; alıcı onu kendi değerine ekler. p₀'ın değerleri zaten sonuçtur, çünkü solunda kimse yoktur.

Saf yöntem satırları birer birer işler. Önce satır 0 zincir boyunca taşınır: p₀ → p₁, sonra p₁ → p₂ ve böyle sürer. Bu, dört bağlantıdan geçtiği için 4 adım alır. Sonra satır 1 taşınır, sonra satır 2. Toplam 4 · 4 = 16 adım sürer. Her adımda dört bağlantıdan yalnız biri kullanılır.

Boru hattı yöntemi satırları zincirde arka arkaya akıtır. p_j, satır r'yi t = r + j anında gönderir. Satır 0 yola çıktıktan bir adım sonra satır 1 yola çıkar; satır 0 o sırada bir bağlantı ileridedir. Satırlar dalga gibi ilerler ve bağlantıların çoğu aynı anda çalışır.

14.6.3Adım adım çalıştırma

Örnekte işlemcilerin sütunları şöyledir: p₀ = (2, 1, 7, 4), p₁ = (3, 7, 2, 9), p₂ = (3, 4, 7, 3), p₃ = (6, 1, 0, 2), p₄ = (8, 6, 3, 5). Her adımda hangi bağlantının hangi satırı taşıdığı Tablo 14.9'de verilmiştir.

Tablo çapraz bir desen gösterir. Satır 0 birinci adımda yola çıkar ve dördüncü adımda p₄'e ulaşır. Satır 3 dördüncü adımda yola çıkar ve yedinci adımda ulaşır. Dördüncü adımda hat doludur: dört bağlantının dördü de çalışır. Öncesinde hat dolar, sonrasında boşalır.

Sonucu bir satır için doğrulayalım. Satır 2'nin değerleri soldan sağa 7, 2, 7, 0, 3'tür. Toplamları 7 + 2 + 7 + 0 + 3 = 19'dur. Boru hattında bu satır p₀'dan 3. adımda çıkar (9), 4. adımda p₂'ye (16), 5. adımda p₃'e (16) ve 6. adımda p₄'e (19) ulaşır. Ara değerler de doğrudur: p₂'deki 16, satırın ilk üç değerinin toplamıdır.

14.6.4Kod izleme ve analiz

Boru hattının zamanlaması kısa bir döngüyle yazılır. x[j][r], p_j'nin satır r'deki değeridir. Dış döngünün her yinelemesi bir zaman adımıdır; iç döngünün yinelemeleri aynı adımda paralel çalışır.

for (int t = 0; t < m + p - 2; t++)
  // tüm j'ler aynı anda
  for (int j = 0; j < p - 1; j++) {
    int r = t - j;
    if (r >= 0 && r < m)
      x[j + 1][r] += x[j][r];
  }

• t, sıfırdan başlayan zaman adımıdır. Döngü m + p − 2 kez döner; örnekte 4 + 5 − 2 = 7.
• j, p_j → p_j+1 bağlantısını gösterir; p − 1 bağlantı vardır.
• r = t - j, bu bağlantının t anında taşıdığı satırdır. p_j satır r'yi t = r + j anında gönderir.
• if (r >= 0 && r < m) koşulu, satırın henüz yola çıkmadığı (r < 0, hat dolarken) ya da bütün satırların geçtiği (r ≥ m, hat boşalırken) durumları eler.
• x[j + 1][r] += x[j][r], gönderilen değeri alıcının değerine ekler.

Zamanlamanın doğru olduğunu iki gözlem gösterir. Birincisi, p_j satır r'yi gönderdiğinde değeri hazırdır. Bu değeri p_j−1, bir adım önce, t − 1 = r + j − 1 anında güncellemiştir. İkincisi, aynı adımdaki işlemler çakışmaz. t anında j bağlantısı x[j][r]'yi okur. j − 1 bağlantısı ise aynı sütunda x[j][r + 1]'e yazar. Okunan ve yazılan hücreler farklıdır.

Tablo 14.10 kodun her adımda yaptığı toplamaları ve p₄'ün sütununu verir. Değerler kodun çalıştırılmasıyla doğrulanmıştır; Tablo 14.9 ile aynıdır, yalnız zaman sıfırdan sayılır.

Adım sayısının genel formülü şöyle bulunur. Son satır r = m − 1'dir ve son bağlantı j = p − 2'dir. Son satır son bağlantıdan t = (m − 1) + (p − 2) anında geçer. Zaman sıfırdan sayıldığı için adım sayısı

m + p − 2

olur. Örnekte 4 + 5 − 2 = 7'dir. Saf yöntem her satırı p − 1 bağlantıdan ayrı ayrı geçirir: m(p − 1) = 16 adım. Bu sonuç boru hattı fikrindeki k + m − 1 formülüyle aynıdır: burada aşama sayısı k = p − 1 bağlantıdır.

Verimlilik de hesaplanabilir. Yararlı iş, yapılan toplamaların sayısıdır: her satır her bağlantıdan bir kez geçer, toplam m(p − 1) toplama. Kullanılan kaynak, p − 1 bağlantının m + p − 2 adım boyunca açık kalmasıdır. Verimlilik

E = m(p − 1) / ((p − 1)(m + p − 2)) = m / (m + p − 2)

olur. Örnekte 4 / 7 ≈ 0,57, yani yaklaşık %57'dir. Satır sayısı işlemci sayısına göre çok büyükse (m ≫ p) verimlilik 1'e yaklaşır. Örneğin p = 5 ve m = 1000 için 1000 / 1003 ≈ 0,997'dir. Boru hattı, çok sayıda bağımsız veri öğesi aynı aşamalardan geçecekse etkilidir.

14.7Boru hatlı ağaç

Boru hattı fikri yalnız zincirlere değil ağaçlara da uygulanır. Bu kesimde işlemciler bir ağaç biçiminde bağlıdır ve her işlemci bir vektör tutar. Amaç, vektörlerin bileşen bileşen toplamını kökte toplamaktır.

14.7.1Ağaçta indirgeme

İşlemciler köklü bir ağaç oluştursun. Her düğüm değerini ebeveynine gönderebilir; ebeveyn gelen değeri kendi değerine ekler. Yapraklar değerlerini gönderir, iç düğümler çocuklarından gelenleri ekleyip yukarı iletir ve sonunda toplam kökte birikir. Bu, ağaç toplamının ileti alışverişiyle yapılan biçimidir. Ağacın derinliği h ise tek bir değerin indirgenmesi h aşama sürer.

Örnekte yedi işlemci vardır. Kök p₀'ın çocukları p₁ ve p₅'tir. p₁'in çocukları p₂ ve p₄, p₂'nin çocuğu p₃, p₅'in çocuğu p₆'dır. En uzun yol p₃ → p₂ → p₁ → p₀'dır; derinlik h = 3'tür.

Şimdi her işlemcide tek bir sayı değil, k bileşenli bir vektör olsun. Örnekte k = 3'tür ve bileşenler yeşil, mavi ve kırmızı renklerle gösterilir. Her bileşen ayrı ayrı toplanacaktır. Bir ileti tek bir bileşen taşır ve kuralı şudur: bir düğüm bir turda en fazla bir ileti alabilir; aynı turda bir ileti de gönderebilir.

Saf yöntem bileşenleri sırayla indirger. Önce yeşil bileşen köke çıkarılır, sonra mavi, sonra kırmızı. Her bileşen h = 3 turda köke çıkar; saf yöntem toplam k · h = 9 tur ister. Boru hatlı ağaç (pipelined tree) yönteminde bir bileşen yukarı çıkarken bir sonraki bileşen yapraklardan yola çıkar.

14.7.2Adım adım çalıştırma

Her bileşen köke üç aşamada çıkar:

1. Aşama 1: p₃ → p₂, p₄ → p₁, p₆ → p₅.
2. Aşama 2: p₂ → p₁, p₅ → p₀.
3. Aşama 3: p₁ → p₀.

p₁ iki çocuğundan ileti alır: aşama 1'de p₄'ten, aşama 2'de p₂'den. p₀ da aşama 2'de p₅'ten, aşama 3'te p₁'den alır. Aşamalar bu yüzden ayrı turlarda yapılmak zorundadır. Bir bileşenin aşama 1'i ile bir sonraki bileşenin aşama 1'i arasında da en az iki tur olmalıdır. Aksi hâlde p₁ aynı turda hem p₄'ten yeni bileşeni hem p₂'den eski bileşeni almak zorunda kalır. Bu nedenle yeni bileşen iki turda bir yola çıkar. Tablo 14.11 turları verir.

Tur 3, boru hattının işe yaradığı ilk turdur. Yeşil bileşen kökte tamamlanırken mavi bileşen yapraklardan yola çıkar. O turda p₀ yalnız p₁'den, p₁ yalnız p₄'ten, p₂ yalnız p₃'ten, p₅ yalnız p₆'dan ileti alır. Kural çiğnenmez. p₁ aynı turda hem alır (mavi, p₄'ten) hem gönderir (yeşil, p₀'a).

Sonuç yeşil 35, mavi 33, kırmızı 31'dir. Doğrulama için yeşil bileşenlerin hepsi toplanır: 3 + 3 + 8 + 9 + 7 + 3 + 2 = 35. Burada sıra p₀, p₁, …, p₆'dır.

14.7.3Analiz

Her bileşen köke h = 3 turda çıkar. Yeni bileşen iki turda bir başlar. Son bileşen (k − 1) · 2 tur sonra başlar ve h turda biter. Toplam tur sayısı

h + (k − 1) · 2 = 3 + 2 · 2 = 7

olur. Saf yöntem k · h = 9 tur ister. Kazanç küçük görünür, ama k büyüdükçe artar. Boru hatlı ağaç 2k + 1, yani yaklaşık 2k tur sürer; saf yöntem 3k tur sürer. Örneğin k = 10 için 21 ve 30 tur.

Yedi turun bu ağaç için en iyi sonuç olduğu basit bir sayımla görülür. Kökün iki çocuğu vardır ve üç bileşenin her biri için her çocuktan bir ileti almalıdır: toplam 6 ileti. Kök bir turda bir ileti alabildiğine göre en az 6 tur ileti alır. İlk ileti en erken 2. turda gelebilir; p₅'in göndereceği değer önce p₆'nın katkısını almalıdır, p₁'in değeri ise daha da derin bir alt ağaca bağlıdır. 2. turdan başlayan altı tur, en erken 7. turda biter.

Genel olarak tur sayısı yaklaşık h + (k − 1) · c'dir; burada c, bir düğümün en fazla çocuk sayısıdır. Çok çocuklu bir düğüm bir bileşeni almak için c tur harcar ve hattın hızını o belirler. Ağaç bir zincirse (c = 1), formül h + k − 1'e iner; bu, boru hattının k + m − 1 formülünün aynısıdır.

14.8Paralel algoritma türleri ve Java

Önceki kesimlerdeki algoritmalar PRAM ya da ileti alışverişi yapan işlemciler gibi soyut modellerde çalıştı. Bu kesim aynı fikirleri gerçek bir dilde, Java'da kurar. Java programları paylaşımlı bellekli bir makinede çalışır. İş parçacıkları ortak nesnelere erişebilir. İş parçacıklarını doğrudan yönetmek yerine çoğunlukla görev tabanlı araçlar kullanılır.

14.8.1Üç tür paralellik

Uygulamada karşılaşılan paralel algoritmaların çoğu üç kalıptan birine uyar:

• Böl ve fethet. Problem bağımsız alt problemlere bölünür. Alt problemler farklı çekirdeklerde aynı anda çözülür ve sonuçlar birleştirilir. Paralel birleştirme sıralaması, paralel hızlı sıralama ve blok blok matris çarpımı bu kalıptadır.
• MapReduce. Büyük bir veri kümesi birçok düğümde işlenir. Map adımı her parçadan ara anahtar–değer çiftleri üretir; reduce adımı aynı anahtarın değerlerini birleştirir. Hadoop ve Spark bu kalıbın yaygın uygulamalarıdır. Kelime sayma, arama motorları için dizin kurma ve günlük kaydı çözümlemesi tipik kullanım alanlarıdır.
• Veri paralelliği. Aynı hesaplama verinin farklı parçalarına aynı anda uygulanır. SIMD komutları ve GPU'lar bu kalıp için tasarlanmıştır. Bilimsel benzetim, görüntü işleme ve sayısal hesaplama bu kalıbı kullanır.

Böl ve fethet kalıbının Java'daki karşılığı Fork/Join yapısıdır. Şekil 14.16 yapının fikrini gösterir. Bir görev alt görevlere çatallanır (fork). Alt görevler paralel çalışır. Ana görev alt görevlerin bitmesini bekler (join) ve sonuçlarını birleştirir.

14.8.2Fork/Join ile paralel birleştirme sıralaması

Birleştirme sıralaması böl ve fethetin en tanıdık örneğidir. Dizi ikiye bölünür, iki yarı ayrı ayrı sıralanır, sonra sıralı iki yarı birleştirilir. İki yarının sıralanması birbirinden bağımsızdır; paralel yapılmaları için yalnız ayrı görevlere verilmeleri gerekir.

class SiralamaGorevi extends RecursiveTask<int[]> {
  private final int[] dizi;
  SiralamaGorevi(int[] dizi) { this.dizi = dizi; }

  protected int[] compute() {
    if (dizi.length <= 1) return dizi;
    int orta = dizi.length / 2;
    var sol = new SiralamaGorevi(
        Arrays.copyOfRange(dizi, 0, orta));
    var sag = new SiralamaGorevi(
        Arrays.copyOfRange(dizi, orta, dizi.length));
    sol.fork();               // paralel başlat
    sag.fork();
    return birlestir(sol.join(), sag.join());
  }
}
// kullanım:
int[] s = new ForkJoinPool().invoke(
    new SiralamaGorevi(dizi));

Kodun öğeleri şunlardır:

• RecursiveTask<int[]>, sonuç döndüren bir Fork/Join görevidir. Görevin işi compute() metodunda yazılır. Sonuç döndürmeyen görevler için RecursiveAction kullanılır.
• Taban durumu: bir öğeli dizi zaten sıralıdır ve olduğu gibi döner.
• Dizi orta noktasından ikiye ayrılır. Arrays.copyOfRange her yarının bir kopyasını çıkarır; böylece iki görev aynı diziyi paylaşmaz.
• fork(), alt görevi havuza verir ve hemen döner. Görev başka bir iş parçacığında çalışabilir; çağıran görev beklemeden ilerler. Bu işlem eşzamansızdır (asynchronous).
• join(), alt görevin bitmesini bekler ve sonucunu döndürür.
• birlestir, iki sıralı diziyi tek bir sıralı diziye çeviren bilinen sıralı birleştirmedir; O(n) sürer.
• new ForkJoinPool().invoke(...), kök görevi bir havuzda çalıştırır ve sonucunu bekler.

ForkJoinPool, bir iş parçacığı havuzudur. Havuzdaki her iş parçacığının kendi görev kuyruğu vardır. Bir iş parçacığı fork() ettiği görevi kendi kuyruğuna koyar. Kuyruğu boşalan iş parçacığı boş beklemez; başka bir iş parçacığının kuyruğunun öbür ucundan bir görev alır. Bu düzene iş çalma (work stealing) denir. İş çalma, yük dengelemeyi kendiliğinden sağlar: hangi görevin ne kadar süreceği önceden bilinmese de boşta kalan çekirdek iş bulur.

Tablo 14.12 örnek dizi 2 3 5 1 7 6 8 4 için görevlerin düzey düzey yaptıklarını gösterir. Yukarıdan aşağı bölme, aşağıdan yukarı birleştirme yapılır.

Program 12 mantıksal çekirdekli bir makinede JDK 21 ile 11 kez çalıştırıldı ve her seferinde [1, 2, 3, 4, 5, 6, 7, 8] sonucunu verdi. Birleştirmelerin hangi iş parçacığında ve hangi sırayla yapıldığı ise çalıştırmaya göre değişti. On çalıştırmalık bir dizide ilk biten birleştirme beş kez [8, 4], ikişer kez [2, 3] ve [7, 6], bir kez [5, 1] oldu. Dört taban birleştirmesini dört ayrı iş parçacığı yürüttü. Paralel programın sonucu belirlenimlidir, ama yürütme sırası belirlenimli değildir. Bunun güvencesi, görevlerin ortak bir veriyi değiştirmemesidir: her görev kendi kopyası üzerinde çalışır ve sonucunu döndürür.

Kodda küçük bir iyileştirme daha yapılabilir. sol.fork(); sag.fork(); yerine sol.fork(); int[] y = sag.compute(); int[] x = sol.join(); yazılsın. Çağıran görev sağ yarıyı kendisi hesaplar; yalnız sol yarı havuza verilir. Böylece çağıran iş parçacığı join()'de boş beklemez ve havuza verilen görev sayısı yarıya iner.

14.8.3Paralel sıralamanın analizi

Paralel birleştirme sıralamasının işi sıralı sürümle aynıdır: her düzeyde toplam n öğe birleştirilir ve log₂ n düzey vardır. W = Θ(n log n). Derinlik ise yinelemeyle bulunur. İki yarı paralel sıralandığı için derinliğe yalnız birinin derinliği katılır. Birleştirme sıralıdır ve Θ(n) derinlik ekler:

D(n) = D(n / 2) + Θ(n) = Θ(n)

Yineleme açılınca n + n/2 + n/4 + … ≤ 2n elde edilir. Paralellik W / D = Θ(n log n) / Θ(n) = Θ(log n)'dir.

Paralellik yalnız Θ(log n)'dir ve bu oldukça azdır. n = 10⁶ için log₂ n ≈ 20'dir; bu kodla 20 civarından fazla çekirdek pek yarar sağlamaz. Darboğaz, kök görevin yaptığı son birleştirmedir. O birleştirme bütün diziyi tek başına gezer ve bu sırada öteki çekirdekler boştur.

Darboğazı kaldırmak için birleştirmenin kendisi de paralelleştirilir. Fikir şöyledir: büyük yarının ortanca öğesi seçilir, öteki yarıda bu öğenin yeri ikili aramayla bulunur. Böylece iki yarı ikişer parçaya ayrılır ve parçalar birbirinden bağımsız olarak, yine paralel birleştirilir. Bu sürümün derinliği Θ(log³ n)'e iner ve paralellik Θ(n / log² n) olur. Ayrıntısı Cormen ve arkadaşlarının kitabında verilir. Java'da hazır bir çözüm de vardır: Arrays.parallelSort(dizi), büyük dizileri Fork/Join ile paralel sıralar.

14.8.4MapReduce

MapReduce, Google'da 2004'te büyük veri kümelerini binlerce makinede işlemek için geliştirilen bir programlama modelidir. Programcı yalnız iki fonksiyon yazar; verinin dağıtılması, hata durumunda işin yeniden yapılması ve sonuçların toplanması çerçeve tarafına bırakılır. Model üç adımdan oluşur:

1. Map. Girdi parçalara bölünür. Her parça bağımsız işlenir ve ara anahtar–değer çiftleri üretir. Kelime saymada çift “kelime → adet” biçimindedir.
2. Karıştırma (shuffle). Aynı anahtara sahip çiftler aynı indirgeyiciye (reducer) gönderilir.
3. Reduce. Her anahtarın değerleri birleştirilir; kelime saymada toplanır.

Örnekte 13 kelime vardır: apple, banana, apple, orange, banana, apple, banana, banana, orange, apple, cherry, banana, apple. Dört iş parçacığı kullanılır. Parça boyu ⌊13 / 4⌋ = 3'tür; ilk üç parça üçer kelime alır, son parça kalan dört kelimeyi alır. Şekil 14.18 akışı gösterir.

Java'da map görevleri Fork/Join görevleri olarak yazılır. Her görev bir kelime listesini (parca) alır ve kendi sayım haritasını döndürür.

// Map: bir parçadaki kelimeleri say
protected Map<String, Integer> compute() {
  Map<String, Integer> sonuc = new HashMap<>();
  for (String kelime : parca)
    sonuc.merge(kelime, 1, Integer::sum);
  return sonuc;
}
// Ana akış
for (MapGorevi g : mapGorevleri) g.fork();
List<Map<String, Integer>> ara = new ArrayList<>();
for (MapGorevi g : mapGorevleri) ara.add(g.join());
// Reduce: ara sonuçları birleştir
Map<String, Integer> toplam = new HashMap<>();
for (Map<String, Integer> m : ara)
  m.forEach((k, v) -> toplam.merge(k, v, Integer::sum));

Kodun parçaları şöyle çalışır:

• compute(), yeni bir HashMap oluşturur. Bu harita yalnız bu göreve aittir.
• sonuc.merge(kelime, 1, Integer::sum), kelime haritada yoksa 1 değeriyle ekler. Varsa eski değerle 1'i toplar. Tek satırda “yoksa ekle, varsa artır” işlemini yapar.
• Ana akışta önce bütün map görevleri fork() edilir; görevler havuzda paralel çalışmaya başlar. Ardından her görevin sonucu join() ile alınır ve ara listesine eklenir. Bütün görevler fork edildikten sonra join edilir. Her görev fork edilir edilmez join edilseydi görevler sırayla çalışırdı.
• Reduce adımı ara haritaları sırayla gezer. Her (anahtar, değer) çifti toplam.merge(k, v, Integer::sum) ile toplam haritasına eklenir.

Tablo 14.14 programın çalıştırılmasından elde edilen ara sonuçları ve reduce adımlarını verir. Haritaların yazdırılma sırası HashMap'in iç düzenine bağlıdır. Bu sıra anahtarların değerlerine göre belirlenir; aynı anahtarlarla her çalıştırmada aynı çıkar ama alfabetik değildir.

Bu tasarımın en önemli özelliği paylaşılan durumun olmamasıdır. Her map görevinin kendi HashMap'i vardır. Görevler birbirinin verisine dokunmaz; bu yüzden kilit gerekmez ve yarış durumu oluşamaz. Birleştirme, bütün görevler bittikten sonra tek bir yerde yapılır. Aynı fikir ağaç toplamında da vardı: her işlemci kendi kısmi toplamını üretir, kısmi sonuçlar sonra birleştirilir.

Örnekte reduce tek bir görevdir ve bütün anahtarları o işler. Gerçek bir MapReduce sisteminde anahtarlar birçok indirgeyiciye bölüştürülür. Bölüştürme için çoğunlukla hash(k) mod r kullanılır; r indirgeyici sayısıdır. Aynı anahtar her zaman aynı indirgeyiciye gider. Böylece reduce adımı da paralel çalışır.

Örnekteki parça boyları dengesizdir: son görev dört kelime, ötekiler üçer kelime alır. Küçük bir örnekte bu önemsizdir. Ama milyonlarca kelimede bir görevin ötekilerden çok daha fazla iş alması, öteki görevlerin onu beklemesine yol açar. Gerçek sistemler girdiyi görev sayısından çok daha fazla parçaya bölerek yükü dengeler.

14.8.5Veri paralelliği: matris çarpımı

n × n boyutlu iki matrisin çarpımı C = A · B'de her hücre C[i][j] = Σ_k A[i][k] · B[k][j] ile hesaplanır. Sonuç matrisinin her satırı, A'nın yalnız bir satırına ve B'nin tamamına bağlıdır. Satırlar birbirinden bağımsızdır; her satır ayrı bir görev olarak hesaplanabilir.

// her satır ayrı bir görev
class SatirGorevi extends RecursiveAction {
  protected void compute() {
    for (int j = 0; j < n; j++) {
      C[satir][j] = 0;
      for (int k = 0; k < n; k++)
        C[satir][j] += A[satir][k] * B[k][j];
    }
  }
}
try (var havuz = new ForkJoinPool()) {
  for (int i = 0; i < n; i++)
    havuz.submit(new SatirGorevi(i));
}   // close(): tüm görevleri bekler

• SatirGorevi, sonuç döndürmeyen bir görevdir (RecursiveAction). Hesapladığı değerleri doğrudan C matrisine yazar. satir alanı görevin hangi satırı hesaplayacağını tutar; kurucusu kısalık için gösterilmemiştir.
• İç içe iki döngü bir satırın n hücresini hesaplar. Her hücre n çarpma ve toplama ister.
• try (var havuz = new ForkJoinPool()) bloğu her satır için bir görevi havuza verir (submit). Java 19'dan beri ForkJoinPool kapatılabilir bir kaynaktır. Blok bitince çağrılan close(), havuzdaki bütün görevlerin bitmesini bekler.

Örnekte A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ve B = [[9, 8, 7], [6, 5, 4], [3, 2, 1]]'dir. Program çalıştırıldığında C = [[30, 24, 18], [84, 69, 54], [138, 114, 90]] sonucunu verdi. Tablo 14.15, satır 1 görevinin yaptığı her işlemi gösterir.

Algoritmanın işi ve derinliği şöyledir. n görevin her biri Θ(n²) işlem yapar; toplam iş W = Θ(n³)'tür ve sıralı algoritmayla aynıdır. Görevler paralel çalıştığı için derinlik tek bir görevin süresidir: D = Θ(n²). Paralellik W / D = Θ(n)'dir. Satır sayısından fazla çekirdek bu tasarıma yarar sağlamaz. Daha fazla paralellik gerekiyorsa her hücre ayrı görev yapılabilir ya da matris bloklara bölünebilir.

Bu kodda yarış durumu yoktur, çünkü her görev yalnız kendi satırına yazar. A ve B bütün görevlerce okunur ama hiçbir görev onlara yazmaz. Eşzamanlı okuma zararsızdır. C'nin her satırına ise tek bir görev yazar. Görevlerin yazdığı bölgeler ayrık olduğu sürece paylaşılan bir matris güvenle kullanılabilir.

14.9Paylaşılan durum ve yarış

Şimdiye kadarki Java örneklerinde görevler ya kendi verilerinde çalıştı ya da ayrık bölgelere yazdı. Bu bir rastlantı değil, bilinçli bir tasarım kararıydı. Birden çok iş parçacığı aynı veriyi değiştirince programın davranışı öngörülemez hâle gelir. Bu kesim sorunun kaynağını gösterir ve çözüm yollarını anlatır.

14.9.1Yarış durumu

İki iş parçacığı paylaşılan bir sayac değişkenini artırsın. Java'da sayac++ tek bir ifade gibi görünür. Ama işlemci düzeyinde üç adımdır: bellekten oku, yerel kopyayı artır, belleğe yaz. İki iş parçacığının adımları iç içe geçerse bir artış kaybolabilir. Tablo 14.16 böyle bir iç içe geçişi gösterir.

İki iş parçacığı da 0 okudu ve 1 yazdı. Beklenen sonuç 2'dir, ama sayaç 1'dir. İkinci yazma birincinin sonucunu ezdi. Bu hataya kayıp güncelleme (lost update) denir.

Yarış durumunu gerçek bir programda görmek için aşağıdaki kod yazıldı. İki iş parçacığının her biri paylaşılan sayac'ı bir milyon kez artırır.

public class SayacYarisi {
  static int sayac = 0;                       // paylaşılan durum

  public static void main(String[] args) throws InterruptedException {
    Runnable is = () -> {
      for (int i = 0; i < 1_000_000; i++)
        sayac++;                              // oku → artır → yaz
    };
    Thread t1 = new Thread(is), t2 = new Thread(is);
    t1.start(); t2.start();
    t1.join();  t2.join();
    System.out.println(sayac);                // beklenen 2000000
  }
}

Runnable, bir iş parçacığının yürüteceği işi tanımlar; burada bir lambda ifadesidir. start() iş parçacığını başlatır ve hemen döner; iki iş parçacığı bu noktadan sonra aynı anda çalışır. join(), ana iş parçacığının o iş parçacığı bitene kadar beklemesini sağlar. Böylece println, iki döngü de bittikten sonra çalışır.

Program JDK 21 ile 12 mantıksal çekirdekli bir Windows makinesinde, her seferinde yeni bir JVM başlatılarak 30 kez çalıştırıldı. Sonuç çalıştırmaya göre değişti. 30 çalıştırmanın hiçbirinde beklenen 2 000 000 çıkmadı. En küçük değer 1 049 868, en büyük değer 1 920 460 oldu; bazı çalıştırmalarda artışların yaklaşık yarısı kayboldu. Bu sayılar başka bir makinede, başka bir JDK sürümünde ya da aynı makinede başka bir anda farklı çıkar. Değişmeyen tek şey, sonucun 2 000 000'u geçememesidir: kayıp güncelleme bir artışı siler ama hiçbir zaman fazladan artış eklemez.

Aynı deney iş parçacığı başına 1000 artışla da yapıldı. Bu kez 20 çalıştırmanın hepsinde doğru sonuç (2000) çıktı. Neden şudur: 1000 artış o kadar kısa sürer ki birinci iş parçacığı çoğu zaman ikincisi başlamadan biter. İki iş parçacığı hiç çakışmaz. Ama bu, programın doğru olduğu anlamına gelmez. Makine meşgulse ya da zamanlama değişirse aynı program yanlış sonuç verebilir. Yarış durumlarının ayıklanmasını zorlaştıran da budur: hata sınamada görünmeyebilir ve ancak gerçek kullanımda, rastlantısal olarak ortaya çıkar. İş parçacığı başına 100 000 artışla yapılan 20 çalıştırmada ise sonuçlar 109 546 ile 161 741 arasında değişti; beklenen değer 200 000'dir.

14.9.2Yarışı önlemek

Yarış durumunu önlemenin üç temel yolu vardır.

Kilit. synchronized (kilit) { sayac++; } bloğuna aynı anda yalnız bir iş parçacığı girebilir. Öteki iş parçacığı kilit serbest kalana kadar bekler. Oku, artır ve yaz adımları böylece bölünmez bir bütün olur. Kilitli sürüm 20 çalıştırmanın hepsinde 2 000 000 verdi.

Atomik işlem. java.util.concurrent.atomic paketindeki sınıflar, işlemcinin özel komutlarıyla bölünmez işlemler sunar. AtomicInteger.incrementAndGet() oku, artır ve yaz adımlarını tek bir atomik adımda yapar.

import java.util.concurrent.atomic.AtomicInteger;

public class SayacAtomik {
  static final AtomicInteger sayac = new AtomicInteger();

  public static void main(String[] args) throws InterruptedException {
    Runnable is = () -> {
      for (int i = 0; i < 1_000_000; i++)
        sayac.incrementAndGet();              // tek atomik adım
    };
    Thread t1 = new Thread(is), t2 = new Thread(is);
    t1.start(); t2.start();
    t1.join();  t2.join();
    System.out.println(sayac.get());          // her zaman 2000000
  }
}

Atomik sürüm 10 ayrı çalıştırmanın hepsinde 2 000 000 yazdı. Eşzamanlı yapılar da aynı ilkeyle çalışır. ConcurrentHashMap, birçok iş parçacığının aynı haritaya güvenle yazmasına izin verir.

Paylaşılan durumdan kaçınmak. En iyi çözüm, paylaşılan değişkeni hiç kullanmamaktır. Her görev kendi kısmi sonucunu üretir; sonuçlar görevler bittikten sonra birleştirilir. Ağaç toplamı, MapReduce ve satır görevleri bu ilkeyle çalışır. Sayaç örneğinde her iş parçacığı kendi yerel sayacını artırır ve join()'den sonra iki yerel sayaç toplanır. Bu çözüm hem doğrudur hem en hızlısıdır, çünkü iş parçacıkları hiç beklemez.

Kilitler bedelsiz değildir. Kilitli bir bölgede aynı anda yalnız bir iş parçacığı çalışır; bölge sıralı hâle gelir. Amdahl yasasına göre bu sıralı kısım hızlanmayı sınırlar. Ayrıca birden çok kilit kullanılınca kilitlenme riski doğar. İP1 A kilidini tutup B'yi, İP2 B kilidini tutup A'yı beklerse ikisi de sonsuza kadar bekler.

14.9.3Eşzamanlı çizge gezinme

Yarış durumu yalnız sayaçlarda değil, daha karmaşık veri yapılarında da ortaya çıkar. Derinlik öncelikli gezinmenin paralel bir sürümünü düşünelim. Her ziyaret edilmemiş komşu için yeni bir gezinme görevi fork() edilir ve alt ağaçlar paralel gezilir. Şekil 14.20'deki çizgede 1'den başlayan gezinme 2 ve 3 için iki görev açar; bu görevler de kendi komşuları için yeni görevler açar.

Görevler, hangi düğümlerin ziyaret edildiğini tutan ortak bir kümeyi paylaşır. Bu kümede iki ayrı sorun vardır. Birincisi, küme sıradan bir HashSet ise eşzamanlı yazmalarda iç yapısı bozulabilir. İkincisi, küme güvenli olsa bile “içinde var mı?” sorusu ile “ekle” işlemi iki ayrı adımdır. İki görev aynı düğümü aynı anda sorabilir, ikisi de “yok” yanıtı alabilir ve ikisi de düğümü ziyaret eder. Doğru kod şudur:

Set<Dugum> ziyaret = ConcurrentHashMap.newKeySet();
if (!ziyaret.add(komsu)) continue; // atomik kontrol+ekle

ConcurrentHashMap.newKeySet(), eşzamanlı erişime dayanıklı bir küme döndürür. add metodu öğe eklendiyse true, öğe zaten varsa false döndürür. Kontrol ile ekleme tek bir atomik işlemdir. İki görev aynı düğümü eklemeye çalışırsa yalnız biri true alır ve düğümü yalnız o ziyaret eder.

Bu farkı görmek için bir deney yapıldı. Sekiz iş parçacığının her biri 0'dan 99 999'a kadar aynı 100 000 düğümü sırayla “ziyaret” etmeye çalıştı. Her iş parçacığı bir düğümü yalnız “ilk ziyaret eden” olduğuna karar verirse saydı. Doğru bir küme 100 000 ziyaret vermelidir. Her yöntem 20 kez çalıştırıldı ve sonuçlar çalıştırmaya göre değişti:

HashSet sürümünde kümede yalnız 100 000 farklı sayı olabileceği hâlde size() bu sayıyı aştı. Bu, kümenin iç sayacının da yarışa girdiğini gösterir. İkinci satır, güvenli bir kümenin tek başına yetmediğini gösterir: iki adımlı kontrol yine yarışa açıktır. Yalnız üçüncü satırdaki atomik kontrol ve ekleme her çalıştırmada doğru sonucu verdi.

Çizgelerde başka bir paralel gezinme biçimi de kullanılır: düzey eşzamanlı genişlik öncelikli arama. Her düzeyin bütün düğümleri paralel genişletilir ve düzey sonunda bir bariyer konur. Sonraki düzey, önceki düzeyin bütün düğümleri işlendikten sonra başlar. Düzey sayısı çizgenin çapı kadar olduğundan derinlik O(çap)'tır. Çapı küçük, düğüm sayısı büyük çizgelerde, örneğin sosyal ağlarda, bu yöntem çok paralellik sunar.

14.9.4Java'da paralellik araçları

Java, farklı düzeylerde paralellik araçları sunar. Tablo 14.18 hangisinin ne zaman kullanılacağını özetler.

Tablonun üst satırlarındaki araçlar daha çok denetim verir ama daha çok kod ister. Alt satırlardaki araçlar işi tek bir metot çağrısına indirir. Örneğin kelime sayma, akış (stream) arayüzüyle tek bir ifadeye sığar:

Map<String, Long> adet = kelimeler.parallelStream()
    .collect(Collectors.groupingByConcurrent(k -> k, Collectors.counting()));

parallelStream(), listeyi parçalara bölüp ortak ForkJoinPool üzerinde işler. groupingByConcurrent, kelimeleri eşzamanlı bir haritada gruplar ve her grubun öğelerini sayar. Bu ifade 13 kelimelik örnekte banana 5, orange 2, apple 5, cherry 1 sonucunu verdi. MapReduce kodunun bütün işi, yani parçalama, map, karıştırma ve reduce, tek ifadede yapılmış olur. Ortak havuzun paralellik düzeyi varsayılan olarak çekirdek sayısının bir eksiğidir; deneyin yapıldığı makinede 11'di.

14.10Sık yapılan hatalar

• p işlemcinin p kat hız getireceğini sanmak. Sıralı kısım, iletişim ve bekleme yüzünden hızlanma p'nin altında kalır. Programın %10'u sıralıysa Amdahl yasasına göre hızlanma 10'u geçemez.
• Hızlanmayı yanlış tabana göre hesaplamak. T₁, paralel algoritmanın tek işlemcideki süresi değil, en iyi sıralı algoritmanın süresidir.
• Paylaşılan HashSet ya da sayaç kullanmak. Eşzamanlı yazma yarış durumuna yol açar. ConcurrentHashMap, AtomicInteger ya da yerel sonuç ile sonradan birleştirme kullanılmalıdır. Güvenli bir kümede bile “kontrol et, sonra ekle” iki adımdır; tek adım olan add'in dönüş değerine bakılmalıdır.
• Çok ince taneli görevler. Her öğe için fork() yapmak, görev oluşturma yükünü kazancın üstüne çıkarır. Bir eşiğin altındaki parçalar sıralı işlenmelidir.
• Turlar arası senkronizasyonu unutmak. PRAM toplamada tur t + 1, tur t'nin bütün yazmaları bitmeden başlarsa eski değerler okunur. Hillis–Steele'in sıralı benzetiminde aynı hata tur başı kopyanın unutulmasıyla ortaya çıkar.
• Yalnız derinliğe bakmak. Hillis–Steele O(log n) turda biter ama O(n log n) iş yapar; az işlemcide sıralı taramadan yavaş kalabilir. Algoritma seçilirken iş ve derinlik birlikte değerlendirilir.
• Boru hattının adım sayısını yanlış saymak. Hattın dolma süresi unutulur. m satır ve p işlemci için adım sayısı m değil, m + p − 2'dir.
• Birleşmeli olmayan işlemi ağaçla indirgemek. Çıkarma ya da bölme ağaçla indirgenirse sonuç değişir. Kayan noktalı toplamada da paralel sonuç son basamaklarda sıralı sonuçtan farklı olabilir.
• Bir kez doğru çalışan paralel programı doğru sanmak. Yarış durumu her çalıştırmada görülmez. İş parçacığı başına 1000 artışlı sayaç deneyi 20 çalıştırmanın hepsinde doğru sonucu verdi; aynı kod bir milyon artışla 30 çalıştırmanın hiçbirinde doğru sonuç vermedi.

14.11Özet

• Paralel algoritma problemi parçalara böler, parçaları işlemcilere atar, aynı anda çözer ve sonuçları birleştirir. Bedeli iletişim, senkronizasyon ve yük dengelemedir. Veri bağımlılığı zinciri paralelleştirilemez; ama zincirdeki işlem birleşmeliyse zincir ağaca çevrilebilir.
• Flynn sınıflandırması makineleri komut ve veri akışlarına göre SISD, SIMD, MISD ve MIMD diye ayırır. Bellek paylaşımlı ya da dağıtık olabilir. PRAM, ortak bellekli ve ortak saatli kuramsal modeldir; EREW, CREW ve CRCW türleri aynı hücreye eşzamanlı erişime göre ayrılır.
• Hızlanma S = T₁ / T_p, verimlilik E = S / p, maliyet C = p · T_p'dir. Maliyet-optimal algoritmada C = Θ(T₁)'dir. Amdahl yasası S ≤ 1 / (1 − f) sınırını verir. Gustafson yasası problem büyüdükçe ölçeklenmiş hızlanmanın (1 − f) + f · p olduğunu söyler.
• İş W toplam işlem sayısı, derinlik D en uzun bağımlılık zinciridir. max(W / p, D) ≤ T_p ≤ W / p + D (Brent). Paralellik W / D, yararlı kullanılabilecek en fazla işlemci sayısıdır.
• PRAM ağaç toplamı log₂ n turda, n − 1 toplamayla çalışır ve EREW'de yeterlidir. n / log n işlemciyle maliyet-optimal olur.
• Önek toplamında Hillis–Steele log₂ n tur ve n log₂ n − (n − 1) iş harcar; iş-verimli değildir. Blelloch yukarı ve aşağı süpürmeyle 2(n − 1) iş ve 2 log₂ n turda dışlayıcı önek toplamını bulur.
• Boru hattında p işlemci ve m satır için adım sayısı m + p − 2'dir (saf yöntem m(p − 1)), verimlilik m / (m + p − 2)'dir. Boru hatlı ağaçta tur sayısı h + (k − 1) · c'dir; örnekte 7 tur (saf 9).
• Java'da böl ve fethet ForkJoinPool ile yazılır: fork() alt görevi havuza verir, join() sonucunu bekler; iş çalma yükü dengeler. Sıralı birleştirmeli paralel birleştirme sıralamasının derinliği Θ(n), paralelliği Θ(log n)'dir.
• MapReduce map, karıştırma ve reduce adımlarından oluşur. Her map görevi kendi haritasını kullandığı için kilit gerekmez. Satır görevleriyle matris çarpımında da görevler ayrık bölgelere yazar.
• Yarış durumunda sonuç zamanlamaya bağlıdır ve çalıştırmaya göre değişir. Çözümler kilit, atomik işlem, eşzamanlı yapılar ve en iyisi paylaşılan durumdan kaçınmaktır.

14.12Kavram listesi

• paralel algoritma parallel algorithm
• PRAM modeli PRAM model
• hızlanma speedup
• verimlilik efficiency
• Amdahl yasası Amdahl's law
• iş / derinlik work / span
• önek toplamı prefix sum (scan)
• boru hattı pipelining
• ileti message passing
• iş çalma work stealing
• yarış durumu race condition
• maliyet-optimal cost-optimal
• iş-verimli work-efficient
• Brent teoremi Brent's theorem
• Gustafson yasası Gustafson's law
• indirgeme reduction
• bariyer barrier
• kayıp güncelleme lost update
• kilitlenme deadlock

14.13Kendini Dene

1. n = 32 sayı PRAM ağaç toplamıyla toplanıyor. Kaç tur sürer, ilk turda kaç toplama yapılır, toplam kaç toplama yapılır? 16 işlemciyle maliyet nedir; algoritma maliyet-optimal midir?

   Cevap

   log₂ 32 = 5 tur. İlk turda 16 toplama yapılır; toplam 16 + 8 + 4 + 2 + 1 = 31 = n − 1. 16 işlemciyle maliyet 16 · 5 = 80'dir; sıralı algoritma 31 adım sürer. Oran log₂ n / 2 gibi büyür ve n arttıkça sınırsız artar; algoritma maliyet-optimal değildir. n / log₂ n ≈ 6 işlemciyle önce bloklar sıralı toplanırsa maliyet Θ(n)'e iner.

2. Programın %95'i paralelleştirilebiliyor. 16 işlemcide Amdahl hızlanması ve verimliliği nedir? İşlemci sayısı sonsuza giderken sınır kaçtır? Problem boyutu işlemci sayısıyla büyütülürse Gustafson yasası ne verir?

   Cevap

   S = 1 / (0,05 + 0,95 / 16) = 1 / (0,05 + 0,059375) ≈ 9,14. Verimlilik 9,14 / 16 ≈ 0,57. Sınır 1 / 0,05 = 20. Gustafson: 0,05 + 0,95 · 16 = 15,25.

3. Bir iş en iyi sıralı algoritmayla 200 s sürüyor. 10 işlemcili paralel sürüm 25 s sürüyor. Hızlanma, verimlilik ve maliyet nedir? Kaç işlemci-saniye ek yüke gitmiştir?

   Cevap

   S = 200 / 25 = 8, E = 8 / 10 = 0,8, C = 10 · 25 = 250 s. Ek yük 250 − 200 = 50 işlemci-saniyedir; işlemci başına 5 s.

4. [1, 2, 3, 4] dizisine Blelloch algoritması uygulanıyor. Yukarı süpürmenin, kökün sıfırlanmasının ve aşağı süpürmenin her turundan sonra dizi nedir? Kaç işlem ve kaç tur yapılır?

   Cevap

   Yukarı d = 1: [1, 3, 3, 7]; d = 2: [1, 3, 3, 10]. Kök: [1, 3, 3, 0]. Aşağı d = 2, çift (1, 3): t = 3, x[1] = 0, x[3] = 0 + 3 → [1, 0, 3, 3]. Aşağı d = 1, çift (0, 1): x[0] = 0, x[1] = 0 + 1; çift (2, 3): x[2] = 3, x[3] = 3 + 3 → [0, 1, 3, 6]. Bu dışlayıcı önek toplamıdır. 2(n − 1) = 6 işlem, 2 log₂ 4 = 4 tur.

5. Üç işlemcili bir zincirde p₀ = (1, 2, 3, 4, 5), p₁ = (1, 1, 1, 1, 1), p₂ = (2, 2, 2, 2, 2) sütunları var. Boru hattı kaç adım sürer, saf yöntem kaç adım sürer, verimlilik nedir? Sonunda p₂ ne tutar ve satır 4 p₂'ye hangi adımda ulaşır?

   Cevap

   m + p − 2 = 5 + 3 − 2 = 6 adım; saf yöntem m(p − 1) = 10 adım. Verimlilik 5 / 6 ≈ 0,83. p₁ (2, 3, 4, 5, 6) olur, p₂ (4, 5, 6, 7, 8) olur. Satır 4'ü p₁, t = 4 + 1 = 5 anında gönderir; bu altıncı ve son adımdır.

6. Dört işlemci p₃ → p₂ → p₁ → p₀ biçiminde bir zincir (tek çocuklu ağaç) oluşturuyor ve her biri 5 bileşenli bir vektör tutuyor. Kök p₀. Boru hatlı indirgeme kaç tur sürer, saf yöntem kaç tur sürer?

   Cevap

   h = 3, k = 5, her düğümün en çok bir çocuğu var (c = 1). Yeni bileşen her turda yola çıkabilir; çünkü her düğüm bir turda yalnız bir ileti alır. Tur sayısı h + (k − 1) · 1 = 7; saf yöntem k · h = 15 tur.

7. n = 2²⁰ sayı ağaçla toplanıyor ve 1024 işlemci var. İş, derinlik ve paralellik nedir? Brent teoremi süre için hangi aralığı verir; hızlanma en az kaçtır?

   Cevap

   W = 2²⁰ − 1 = 1 048 575, D = 20, paralellik ≈ 52 429. Alt sınır W / p ≈ 1024; üst sınır W / p + D ≈ 1044 adım. Hızlanma en az 1 048 575 / 1044 ≈ 1004'tür; 1024 işlemciyle neredeyse doğrusal. İşlemci sayısı paralellikten çok küçük olduğunda derinlik terimi önemsizleşir.

8. 1000 × 1000 matrisler satır görevleriyle çarpılıyor. İş, derinlik ve paralellik nedir? 2000 çekirdekli bir makinede hızlanma en fazla kaç olabilir?

   Cevap

   W = n³ = 10⁹ çarpma-toplama, D = n² = 10⁶ (tek satırın süresi), paralellik W / D = 1000. Yalnız 1000 görev olduğu için çekirdeklerin en çok yarısı çalışır; T_p ≥ D olduğundan hızlanma en fazla 1000'dir. Daha fazla paralellik için hücre ya da blok görevleri gerekir.

9. Bir öğrenci bir listenin toplamını long toplam = 0; değişkeni ve liste.parallelStream().forEach(x -> toplam += x) ile bulmak istiyor. Bu neden yanlıştır? Java bu kodu derler mi? Doğrusu nasıl yazılır?

   Cevap

   Java bu kodu derlemez: lambda içinden yalnız fiilen değişmez (effectively final) yerel değişkenler kullanılabilir. Değişken bir alan (field) yapılırsa kod derlenir ama toplam += x oku, topla, yaz adımlarından oluşur ve iş parçacıkları arasında kayıp güncelleme oluşur. Sonuç çalıştırmaya göre değişir. Doğrusu paylaşılan durum kullanmayan bir indirgemedir: liste.parallelStream().mapToLong(Long::longValue).sum(). Her iş parçacığı kendi kısmi toplamını üretir, kısmi toplamlar sonra birleştirilir.

14.14İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 26: iş, derinlik ve paralellik kavramları ile açgözlü zamanlayıcı sınırı burada işlenir. Paralel birleştirmenin ve paralel birleştirme sıralamasının ayrıntılı çözümlemesi de bu bölümdedir.
• J. JáJá, An Introduction to Parallel Algorithms (1992): PRAM modeli, maliyet-optimal ağaç toplamı, önek toplamı ve PRAM türleri arasındaki ilişkiler için kapsamlı bir kaynaktır.
• A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing (2. baskı, 2003): boru hattı, iletişim maliyetleri, ölçeklenebilirlik ve MPI ile programlama gibi uygulamaya yakın konuları işler.
• D. Lea, “A Java Fork/Join Framework” (2000): Java'daki ForkJoinPool'un tasarımını ve iş çalma düzeneğini, onu yazan kişinin anlatımıyla verir.

14.15Kaynaklar

1. G. M. Amdahl, “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities”, AFIPS Spring Joint Computer Conference, 1967.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 26: Parallel Algorithms).
3. J. Dean, S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters”, OSDI, 2004.
4. A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, 2. baskı, Addison-Wesley, 2003.
5. J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
6. D. Lea, “A Java Fork/Join Framework”, ACM Java Grande Conference, 2000.

İlgili sayfalar: Bölüm 14 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.