Hasan Çelik

Kendini geliştirmeyi seven, tutkulu bir yazılımcı

ÖNEMLİ : Kendim için aldığım notlar. Umarım size de bir faydası olur. Kullanılan her bir makale referans olarak eklenmiştir. Rice Üniversitesi’nin hazırladığı eğitsel bir Framework olan PCDP bu ve sonraki bölümlerde kullanılacaktır. async ve finish notasyonları bu Framework’de yer almaktadır.

Java Paralel Programlama Serisi

  1. Java Paralel Programlama - Bölüm 1
  2. Java Paralel Programlama - Bölüm 2
  3. Java Paralel Programlama - Bölüm 3
  4. Java Paralel Programlama - Bölüm 4

Genel Bakış

Şu ana kadar gördüklerimizi özetlemek gerekirse, aşağıdaki görsel yeterli olacaktır.


Java async-finish example

Aslında bu bölümde bunun gibi paralel programları modellemek için hesaplama grafiği(computation graph) adı verilen bir kavramı göstermek istiyorum.


Java computation graph example

Şekilde görüldüğü gibi S1‘den sonra S2 fork edilerek yeni bir branch de çalışması sağlanıyor. S2‘ye paralel olarak S1, S3 olarak yeni bir işleme devam ediyor. Buna continue işlemi denir. S3‘ten sonra da aynı görev S4‘te devam etmek istiyor. Ama burada bu join işlemi var. Bunun için join edge adı verilen farklı bir kenarımız var.

Not:

Fork–join programları için, kenarları üç bölüme ayırmak yararlı olur:

  • Bir görevdeki adımların sırasını yakalayan continue edges‘ler’,
  • Child task’ların ilk adımına bir fork işlemi bağlayan fork edges‘ler’.
  • Bir görevin son adımını o görevdeki tüm join işlemlerine bağlayan join edges‘ler’.

Dolayısıyla, bu üç çeşit kenarla, bir paralel programın çalışmasını modelleyebileceğimizi görüyoruz. Bu yönlendirilmiş grafiğin her tepe noktası veya düğümü, bir adım olarak adlandırdığımız bir ardışık alt hesaplamayı temsil eder. Ve her edge bir sıralama kısıtlamasına karşılık gelir. Eğer fork ve join olmadan normal bir sıralı programa sahip olsaydınız, grafiğiniz sadece continue edge‘lere sahip düz bir çizgi olurdu.

Data Race Nedir?

İş parçacığı çözümleyicisi, çok iş parçacıklı bir işlem yürütülürken oluşan veri yarışlarını algılar. Bir veri yarışması(data Race) şu durumlarda gerçekleşir:

  • Tek bir işlemde iki veya daha fazla iş parçacığı aynı anda aynı bellek konumuna erişir ve
  • erişimlerin en az biri yazmak içindir ve
  • iş parçacığı bu belleğe erişimlerini denetlemek için özel kilitler kullanmaz.

Bu üç koşul geçerli olduğunda, erişimlerin sırası belirleyici değildir ve hesaplama, o sıraya bağlı olarak çalıştırmadan farklı sonuçlar verebilir. Bazı veri yarışları(data Race) iyi huylu olabilir (örneğin, hafıza erişimi meşgul olarak beklemek için kullanıldığında), ancak programdaki birçok veri yarışları(data Race) hatalıdır.

Örneğin, eğer S3’te yanlışlıkla, S2’nin hesapladığı bazı toplamları okumaya çalıştığımızı farzedelim. Ve diyelim ki o esnada S2‘de bu alan toplamına yazmaya başlıyoruz. İşte o zaman, okuma ve yazma işlemleri S2‘de paralel gidebileceğinden ve haliyle S3‘ün hesaplama grafiğinde S2 ile bir bağlantısı olmadığından dolayı bir hata alırız. Paralel programlamada bu çok zararlı bir tür hatadır. Buna data race(yani veri yarışı) denir.

Performans Ölçümü, Work, Span ve Ideal Paralellik

Hesaplama grafiklerinin bir başka ilginç özelliği de, paralel programınızın performansını düşünmek için onları kullanabilmemizdir. Varsayalım ki, S1 ve S4, 1 birim zaman alacak, S3 ve S2 ise 10 birim zaman alacak iş yapsın.


Java computation graph performans ölçümü

Performansla ilgili olarak çalışacağımız iki önemli ölçüm bulunmaktadır. İlki WORK olarak adlandırılır. Aslında bu sadece tüm düğümlerin yürütme zamanlarının toplamıdır. Yani bu durumda, 1 + 10 + 10 + 1 olur. Yani 22. Gerçekten önemli olan başka bir ölçüm ise SPAN olarak adlandırılıyor. Ve bu en uzun yolun uzunluğudur. Programcılar ayrıca bunu “kritik yol uzunluğu” olarak da adlandırırlar.


Java span kritik yol uzunluğu

Ideal Parallelism

Bu iki ölçüm, programdaki paralellik hakkında akıl yürütmemize yardımcı olur. Örneğin bu iki ölçümü kullanarak ideal parelellik kavramını öğreneceğiz.

  • Ideal Parallelism = WORK / SPAN

  • Ideal Parallelism = 22/12 = 1.83

Bu, hesaplama grafiğinde ne kadar paralellik olduğuna dair çok somut bir ölçü vermektedir. Sıralı bir algoritma için, bu sadece 1 olacaktır, çünkü span ile work aynı olacaktır(herhangi bir çatallanma olmayacağından). İdeal paralellik, hesaplama grafiğinde düğümlerin paralel olarak yürütülmesinden elde edilebilecek hızlanma faktörü üzerindeki üst sınırdır. İdeal paralelliğin sadece paralel programın bir işlevi olduğunu ve fiziksel bilgisayarda mevcut olan gerçek paralelliğe bağlı olmadığını unutmayın.

Referanslar :

  1. What is a Data Race?
  2. Asynchronous method invocation
  3. Analysis of parallel algorithms
  4. Class RecursiveAction
  5. Class RecursiveTask
  6. Class ForkJoinPool
  7. Package java.util.stream
  8. Interface Stream
  9. Fork/Join
  10. Java VisualVM
  11. Parallel Programming in Java
  12. PCDP parallel programming framework
  13. Şekil 1,2,3,4 - lucidchart ile hazırlanmıştır.

Bunlar ilginizi çekebilir: