Java Paralel Programlama - Bölüm 4

Ö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.

Genel Bakış

Bir önceki bölümde hesaplama grafiklerini görmüştük. Şimdi ise gerçek çok çekirdekli bilgisayarlarda nasıl haritalandıklarını görebiliriz. Bir önceki bölümde resmettiğimiz hesaplama grafiğini tekrar göz önüne getirelim ve her bir işleme bazı yürütme zamanlarını verelim. S₆ dışında bütün işlemlere 1 birim çalışma zamanı verdiğimizi varsayalım. S₆ ise 10 olsun.

Burada ilgilendiğimiz şey, P kadar işlemci olduğunda T yürütme zamanını bilmek istiyoruz. Yani, P işlemcili çok çekirdekli bir makinemiz varsa: Örn; 2, 4, 8, 16 çekirdekli, verilen bir hesaplama grafiği için hangi işlem zamanını alabiliriz?

• T_p = P işlemcilerinde yürütme süresidir (Execution time on P processors)

Hesaplama grafiğindeki bu adımların aslında işlemcilerde nasıl zamanlandığını düşünecek olursak, aşağıdaki gibi bir gösterim yapabiliriz. Fakat bunu bilgisayarlar arka planda kendi yaptıkları için endişelenmemizi gerektirecek bir durum yoktur. Hesaplama grafiğindeki adımları işlemciler arasında programlamak, çalışma zamanı yazılımı ve donanımının işidir.

2 işlemcili bir durumu ele aldığımızı varsayalım ve bu adımların nasıl programlanabileceğini görelim.

Dolayısıyla, ne olursa olsun S₁‘in ilk önce gerçekleştirilmesi gerektiğini görüyoruz, çünkü grafiğin asıl amacı, sıralama ilişkilerini gösterir ve S₁ işini bitirene kadar başka hiçbir şey çalışmaz. S₁‘i rastgele olarak P₀‘da başlattığımızı varsayalım. Sonrasında S₂ ve S₄ ve S₆ hepsi çalıştırılabilir. Ama iki işlemci olduğu için 3 işlemden 2‘sini seçmemiz gerekli.

Farzedelim ki, S₂ ve S₄‘ü seçtik. P₀, S₂‘yi, P₁ ise S₄‘ü çalıştırdı. Şimdi S₂ ve S₄ birbirleriyle paralel olarak çalışıyorlar. Akabinde, P₀, S₃‘ü, P₁ ise S₅‘i hesaplama grafiğindeki gibi çalıştırmaya devam eder. Şimdi, bundan sonra S₇‘yi uygulayamıyoruz çünkü S₆ hâlâ bitirilmeyi bekliyor.

Her iki işlemci de boşa çıktığı için ikisinden birinde S₆ çalıştırılabilir. Farzedelim ki bu görevi P₀ aldı. Artık son işlem olan S₇‘ye geçebiliriz. Bunu da S₆‘da olduğu gibi boşta olan herhangi bir işlemci alabilir. Yine P₀‘ın aldığını varsayalım. Yukarıda görüldüğü üzere işlemciler üzerinde ilgili planlama yapıldı. Şimdi ise bu işlemcilerin çalışma zamanlarını üzerinde tekrar düşünebiliriz.

Planlama bu şekilde olduğunda 2 işlemcideki çalışma süresini 14(yani T₂ = 14) olarak hesapladık. Dikkat edilecek olursa 2 adet de IDLE(atıl) slot göze çarpmaktadır. Yani bu slotların boşta olduğunu, yapacak bir işlerinin olmadığını göstermektedir. Ancak, grafiği programlamanın tek yolu bu değildir. Başka bir yaklaşım da izleyebiliriz. Çünkü S₆ bir darboğaz oluşturuyor ve P₁ işlemcisinin belirli durumlarda boşta(IDLE) kalmasına neden oluyor. Dolayısıyla, şimdi ikinci planlamadaki hedefimiz S₆‘yı mümkün olan en kısa sürede çalıştırmak olacaktır.

Bu planlama örneğinde S₁‘i yine ilk olarak başlatmak zorundayız. Tabii S₁ başladığında P₁ bir öncekinde olduğu gibi başlangıçta boş kalır. S₁ işlemi bittiğinde, P₀‘da S₆‘yı önceliklendirebiliriz. Böylece S₆, 10 birim zaman boyunca P₀ üzerinde çalışırken, P₁‘de S₂, S₃, S₄, S₅ işlemlerini rahatlıkla ele alabiliriz. Sıra önemli değil çünkü bunlar, hangi sırayla yapılırsa yapsınlar toplamda dört iş birimi ile çalışırlar. Yani 10 birim zamana sahip S₆‘yı düşünürsek, işlemlerini S₆‘dan önce bitirecekleri kesindir. S₆‘da işlemini sonlandırdıktan sonra S₇‘yi işleme alabiliriz. S₇ herhangi bir işlemci de başlayabilir. Varsayalım ki P₀‘da başladı. Peki, şimdi bu planlama için yürütme süresi ne oldu?. Burada S₁‘in 1, S₆‘nın 10 ve S₇‘nin 1 birim süresi olduğu için toplamda 12 birim çalışma süresi olduğunu görüyoruz.

Dolayısıyla, bir öncekine kıyasla daha küçük bir yürütme zamanımız var. Bu nedenle, P kadar işlemcide yürütme süresinin bu tanımı aslında tasarlanan bu plana bağlıdır. Ancak bu yürütme süresi hakkında belirleyebileceğimiz belirli özellikler vardır. Birincisi, P –> 1‘e eşit olsaydı ne olurdu? Eğer sadece 1 işlemcimiz olsaydı, T₁'in --> WORK'e eşit olduğunu iddia edebilirdik. Bunu neden söylüyoruz? Çünkü bir işlemcide çalışıyorsanız, temel olarak bu işlemcinin, hesaplama grafiğindeki tüm işleri yapması gerekir. Bu işlem, tüm yürütme zamanlarını eklediğinizde elde ettiğiniz şeydir.

• P = 1 —> T1 = WORK

Örneği düşünecek olursak tüm çalışma zamanlarının toplamı;

1
2
3
S1 + S2 + S3 + S4 + S5 + S6 + S7 = ?
1  + 1  + 1  + 1  + 1  + 10 + 1  = 16
T1 = 16

Düşünebileceğimiz diğer bir şey ise, pratikte olmasa da, sonsuz sayıda işlemcimiz olsaydı ne olurdu? Cevap daha önce öğrendiğimiz, yani hesaplama grafiğindeki en uzun yolun uzunluğunu temsil eden SPAN olurdu. Çünkü yeterli işlemcimiz varsa, en uzun yolda olmak ve kendinden sonra gelecek işlemleri beklemek dışında bir adım dahi beklemenin bir sebebi yoktur.

Şekil 1’e bakacak olursak, başta hesaplama grafiğini çizdiğimizde 3 tane paralel çalışan işlemi düşünmüştük. İşlemin uzunluğu da haliyle bu dallanmalardan en son hangisi biterse ona göre belirlenir. Çünkü diğer işlemler önce bitse de, en son join işlemi yapılacağı zaman birbirlerini beklemek zorundalar. Paralel çalışacak yeterli sayıda işlemcimiz olacağı için 3 dallanmaya da yeterli sayıda işlemci olacaktır. S₃, S₂‘den sonra gelen bir işlem, S₅ de S₄‘den sonra gelen bir işlem olduğu için onlar yeni bir işlemci de çalışmaz.

Paralel programlar hakkında konuşurken çok ilginç bir diğer kavram ise hızlanmadır(SPEEDUP). Bu yüzden, paralelliğin asıl amacı, donanım üreticilerinin bize verdiği tüm bu çekirdeklerle programınızın daha hızlı çalışmasını sağlamaktır.

• SPEEDUP = T₁ / T_P

Öyleyse bunu düşünelim. T₁ sıralı yürütme süresidir. T_P, P işlemcide aldığımız yürütme süresidir. Ve bu oran, paralel versiyonun ne kadar hızlı çalışabildiğinin faktörü olacaktır. Bu yüzden, hızlanmanın P‘ye küçük eşit olması gerektiğini görebiliyoruz.

• SPEEDUP ≤ P

Speedup(P) must be ≤ the number of processors P.

Aynı şekilde, SPEEDUP aşağıdaki gibi de olmalı;

• SPEEDUP ≤ WORK/SPAN = IDEAL PARALLELISM

Speedup(P) must be ≤ the ideal parallelism, WORK/SPAN.

Dolayısıyla, hızlanmanın elbette kaç işlemcinin mevcut olduğuna bağlı olduğunu ve aynı zamanda “ideal paralellik” olan hesaplama grafiğinin bu gerçekten önemli özelliği ile de sınırlandığını görüyoruz. Paralel algoritmalarda hedefimiz, sahip olduğunuz işlemci sayısından çok daha büyük olan ideal paralelliğe sahip hesaplama grafikleri oluşturmaktır, böylece, bu paralel programı çok sayıda işlemcide çalıştırma esnekliğine sahip olursunuz.

• IDEAL PARALLELISM ≥ P

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.