Bu site emekli olmuştur. Arşiv amaçlı olarak BT AKADEMİ sponsorluğunda yayın hayatına devam etmektedir.




C#nedir?com
  Ana Sayfa .net TV Makaleler Kaynak Kod Haberler Serbest Köşe Canlı Köşe Forum C#nedir? Ekibimiz RSS RSS
YAZAR HAKKINDA
Özkan Eren
Özkan Eren
http://www.csharpnedir.com/
İletişme geçmek için tıklayın.
6 Makalesi yayınlanmakta.
Yazar hakkında detaylı bilgi için tıklayın.
Yayınlanan diğer makaleleri için tıklayın.
İlgili etiketler: algoritma algoritmalar algoritmalari arasinda dinamik durumda gereksiz islemi makine paralel proses prosesler proseslere yukarida zamanda C++ / C++.NET Özkan Eren
 
YAZI HAKKINDA
Türü : Makale
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
Seviyesi : İleri
Kategori : C++ / C++.NET
Yayınlanma Tarihi : 17.5.2005
Okunma Sayısı : 44298
Yorum Sayısı : 1     yorum yaz
Site İçi AramaSİTE İÇİ ARAMA
Üye Girişini AçÜye GİRİŞİ
Üye girişi için tıklayın.
Kullanıcı Adı
Şifre
 
Beni her zaman hatırla
Bir hafta boyunca kullanıcı bilgilerinizi kullanıcı çıkışı yapana kadar hatırlar. (Paylaşılan bilgisayarlarda önerilmez.)
 
Şifremi / Kullanıcı Adımı unuttum.
 
.net TV RSS Serbest KÖŞE (?)
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
emre TAŞ
Silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
Makale Gönder Bende Yazmak İstiyorum
.net TV RSSBlogroll
Turhal Temizer
Conda install environment.yml Package 23.11.2024
Turhal Temizer
Mac OS/X Removing CUDA 23.11.2024
Burak Selim Şenyurt
Rust ile ECS Yaklaşımını Anlamak 23.11.2024
Burak Selim Şenyurt
Birlikte Rust Öğrenelim Serisi 23.11.2024
  Diğer Herşey
» Makaleler RSS
» Video Gönder
» Makale Gönder
» Serbest Köşeye Yazı Gönder
» Yazar Başvurusu
» C#nedir? Ekibinde Olmalıyım!
Sponsorlar
BT Akademi
Medya Portakal
Video Hosting Sponsoru
Csharpnedir.com bir Ineta üyesidir
Uzman Abi
Her Yönüyle C# - Sefer Algan
Ana Sayfa / Makaleler / Özkan Eren / C++ / C++.NET / MPI İle Paralel Programlama - 3
MPI İle Paralel Programlama - 3
arkadaşıma gönder
Arkadaşınızın email adresi:
 
Mesajınız:
Kapat
Sayfayı Yazdır Sık Kullanılanlara Ekle Arkadaşıma Gönder MySpace Del.Ico.Us Digg Facebook Google Mixx Reddit StumbleUpon
MPI ile programlama serimizde 3. yazımıza gelmiş bulunmaktayız. Bu yazımızda genel olarak Paralel Algoritmaları inceleyeceğiz. İlk yazılarımızda çok basit örneklerle Paralel Kodlar geliştirmiştik. Bu yazımızda ise makineler arası işlemleri daha da etkin hale getiren paralel algoritmaları anlatacağım. 

Algoritmalarda Verimsizlik 

Diyelim siz de bir makine var ve işlemi 1 birim zamanda hallediyor. Siz N tane makine kullanarak kodunuzu çalıştırıyorsunuz ve 6/N gibi bir zamanda hallediyor. Bu durumda siz işinizi daha hızlı bitirmiş sayılmazsınız. Makine başına N*6/N=6 birim zaman eder, bu durumda paralel bilgisayarları kullanmanın ve kodları bunlara göre yazmanın hiçbir anlamı olmaz.

Peki neden en fazla 1/N kadar zamanda işimiz bitmesi gerekirken 1/N den daha fazla bir zamanda işimiz bitmektedir? Bunun en önemli nedeni kullanılan yanlış algoritmalardır.İlk iki yazımıza bakacak olursanız haberleşme fonksiyonlarının doğru kullanılmaması durumunda deadlock, yanlış veri alış-verişi, gereksiz yere çok fazla veri transferi gibi problemler oluşabildiğinden bahsetmiştik.

Diğer bir önemli sebep ise makineler arası iletişimin fazla olmasıdır. Algoritma geliştirilirken bilgisayarlar arasında gereksiz haberleşmeleri en aza indirgemek gerekmektedir. Bunun yanında haberleşmeler azaltılırken bilgisayarlar en fazla işlemi yapacak şekilde algoritma geliştirilmelidir. Gereksiz yere veri transferi, gereksiz yere haberleşme, bazı proseslerin az iş yapması, bir proses cevap beklerken diğer prosesin o işleme daha yeni başlaması vb... gibi problemler paralel işlemlerden beklediğimiz performansı almamıza engel olmaktadır

Aşağıda tipik bir MPI kodunun işlemcileri nasıl kullandığını görüyorsunuz. Dikkat ederseniz prosesler yukarıda saydığım problemlerden dolayı verimsiz çalışmaktadır.Eğer algoritmamızı düzgün geliştirirsek bütün prosesler arasında eşgüdüm oluşur ve işlemciler aynı oranda kullanılır. Bunun için ileri algoritmalar kullanmamız gerekmektedir.



İleri Algoritmalar : Scheduling ( işleri sıraya sokma )

Bu algoritmada işlemlerimiz değişik parçalara bölünmektedir ve proseslerin alacağı işlemler tanımlanarak gereksiz yere bekleme veya gereksiz yere fazla iş yapma gibi problemlerin önüne geçilmektedir.



Yukarı da gördüğünüz gibi 2 tane işlemcimiz var ve bunlardan 1. işlemci 4 nolu işlemi yapmıyor ve 5. işleme geçerken başka iş yapıyor.İkinci prosesimiz ise 2 nolu işlemi 1.prosesimizdan daha hızlı yapıyor ve 4 nolu prosese geçmek için sonucu 1.prosesten alıyor. Böylece hem zaman kaybını hem de kaynak kaybını önlemiş oluyoruz. 

İleri Algoritmalar : Decomposition ( İndirgeme )

Bu yöntemimiz birden fazla birbirine bağımlı işlemlerde sonuçları tek parça yerine parça parça göndermeye dayalıdır. 



Yukarıda gördüğünüz gibi bir işlemimiz olsun ve bu işlemden sonuç almak için 4 tane ara işlemimiz daha olsun. Decomposition yöntemi ile sonuçları bütün olarak yollamak yerine her sonuç çıktıkça parça parça ileri proseslere göndeririz. Ancak bu yöntem az sayıda ( FFT gibi ) işlemlerde geçerlidir. Özellikle ileri matematik uygulamaları için kullanılan bir tekniktir. 





Gördüğünüz gibi 10 birimlik datayı parçalayarak gönderebiliriz. Böylece 10 datanın tamamını almadan 2.proses işlemine başlayabilmektedir. Böylece 40 birim zamanda yapılacak iş 13 birimlik zamanda yapılabilmektedir.

İleri Algoritmalar : Yük Dağılımı(yönetimi)

Yük yönetimi yukarıda saydığım algoritmalar arasında en kolay olanıdır ve uygulaması diğerlerine kıyasla daha pratiktir. Yük dağılımları 2 türlüdür. Birincisi statik kontrol dediğimiz yöntemdir. Bu durumda algoritmayı geliştiren, programın akışını önceden kestirerek hangi bilgisayara ne kadarlık iş yükleyeceğini hesap etmiştir. Bunun dışında Dinamik olarak yük dağılımını kontrol edebiliriz. Dinamik yük dağılımında efendi-köle ilişkisinde prosesler oluşturup efendilerin belirlediği kadar köle prosesler çalıştırılmaktadır. Hali ile dinamik yönetim statik yönetimden daha karmaşıktır. Basit olarak dinamik yönetimde ana proses sonuçları toplamaktadır ve birim zamanda gelen veri sayısına göre proseslere daha az veya daha çok iş yüklemektedir.Böylece prosesler arasında eşgüdüm oluşmaktadır.



Aşağıda gördüğünüz dinamik proseslerde kullanabileceğimiz bir ana proses ve diğer gördüğünüz grafik ise ana prosesten gelen emirler doğrultusunda çalışan bir "köle" prosestir. Aşağıda ki olayları basit olarak açıklayalım. Elimizde bir tane ana proses var ve n tane de köle proses var.Ana proseste köle proseslerden veriler alınıyor ve alınan verilerin yoğunluğuna göre o proseslere ek iş veriliyor veya daha az iş veriliyor. Köle prosesler ise sadece kendilerine verilen işleri yapıyor ve başka hiçbir işlem yapmıyor. Örneğimizde de bu algoritmayı kullanacağız.  



Dinamik Yük Yönetimi





Uygulama : Mandelbrot ve Fraktallar

Şimdi yukarı da ki örneğe uygun şekilde bir algoritma geliştirelim ve uygulayalım. Bu örneğimiz "mandelbrot" uygulaması olacak.Mandelbrot setleri ilginç görüntüler üreten çok ilginç bir matematiksel buluştur. Herkesin muhakkak bir şekilde gördüğü bu ilginç görüntülerin altında ki matematiği kısaca size anlatayım.



Yukarıda gördüğünüz fraktal aslında X(j+1)=X(j)*X(j) + c tarzında bir denklemin sonuçlarından başka birşey değildir.Bu fraktalın böyle gözükmesine sebep olan şey ise j nin sonsuza doğru giderken X değerinin 0 veya sonsuzdan farklı bir değere gitmesi ile oluşan bir görüntüdür  ( reel kısımları X ekseni sanal kısımları Y ekseni olarak düşünürsek ). Örnek olarak c = i+1 (burada ki i kompleks sayı olan i) olsun ve X(0)=0 olsun.

1.adım : X(1)=0*0+i+1  --- >> X(1)=i+1 
2.adım : X(2)=(i+1)*(i+1)+i+1  --- >> X(2)=3i+2
3.adım : X(3)=(3i+2)*(3i+2)+i+1 --- >> X(3)=13i -4
....................................................
Gördüğünüz gibi X adım adım artmaktadır. Bazı c değerleri için bu artmamaktadır ve belirli değerler arasında kalmaktadır. Eğer bu X değerleri karmaşık kısmı ve gerçek kısmı 2 eksen oluşturacak şekilde çizilirse yukarıda gördüğünüz fraktallar oluşmaktadır. Konumuz fraktallar olmadığı için daha detayına girmeyeceğim ve algoritmamıza geçeceğim.

Dinamik Paralel Algoritma

Yukarıda ki yönteme uygun bir şekilde fraktalları tek bir makinede basit bir fraktal hesaplayan kod yazmak eminim çok zor olmaz. Bu kodu paralel hale getirince yazımın girişinde bahsettiğim problemlerle karşılacağız. Çünkü her bölgede eşit bir şekilde hesaplama olmayacak bazı kısımlarda hiç hesap olmazken bazı kısımlarda yoğun hesaplamalar olacak. Bunu engellemek için dinamik yük ayarlaması yapmamız gerekecek. Kodumuzda her adımda hesaplanan alanların büyüklüğü bir önceki işlemin yoğunluğuna göre büyüyecek veya küçülecek bu durumda makineler bütün yükleri eşit olarak paylaşacak. Aşağıda 4*5 lik alana bölünmüş fraktalı görüyorsunuz. 



kod biraz uzun olduğu için sizi kodla boğmak yerine genel hatlarını yazacağım  

int main ( ) {
...........................

// değerlerin tanımı, MPI kodunun başlatılması
// işlem yoğunluğuna tahminine göre alanlarihesapla() fonksiyonu ile makinelere eşit yük dağıtılıyor
alanlarihesapla();
// Master yani Ana Prosesin başlatılması
....................................
// Master kod alanlarihesapla fonksiyonun sonuçlarını diğer proseslere dağıtmaktadır
// Köle proseslerinin çalışması
........................................
// Köle prosesler yukarıda açıkladığımız "z" değerlerini hesaplamaktadır.
........................................
// MPI’ın sonlandırılması
Eğer kodu merak ediyorsanız buradan indirebilirsiniz. Elbette gördüğümüz bu çalışma en basit düzeyde dinamik yük algoritmasını kullanmıştır ileri düzeyde dağıtık sistemler veya paralel kodlamalarda daha karışık ve zor dinamik yük algoritmaları kullanılmaktadır.

Kıyaslama ve Sonuç

Yazımın en başında paralel kodlamalarda algoritma hatalarından bahsetmiştim ve 1/N lik zamanı yakalayamazsak makineyi verimsiz kullandığımızı söylemiştim. Yukarıda ki kodu eğer 2 ve 30 makine ile çalıştırırsak çalışma zamanını 12.4/1 gibi bir sonuç buluruz ki başarılı bir sonuçtur. Aslında 15/1 olmasını beklerdik ama bilgisayarlar arasında haberleşmede kaybedilen zamanı da hesaba katarsak 15/1 lik oran daha da aşağılara düşmektedir.

özkan eren
[email protected]
Makale:
MPI İle Paralel Programlama - 3 C++ ve C++.NET dili Özkan Eren
  • Yazılan Yorumlar
  • Yorum Yaz
KAS
23
2012
 "Eğer kodu merak ediyorsanız buradan indirebilirsiniz" yazmışsınız ama indiremedim. bi de bu algoritma paralel algoritma mı?
Sayfalar : 1 
Yorum yazabilmek için üye girişi yapmalısınız. Üye girişi için tıklayın.
Üye değilseniz Üyel Ol linkine tıklayarak üyeliğinizi hemen başlatabilirisniz.
 
  • Bu Konuda Son 10
  • Eklenen Son 10
  • Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor