Programlama | Programlama Dilleri | C Programlama Dili |C++

Anasayfa Programlama C / C++ MPI ile Mandelbrot Setinin Paralel Olarak Hesaplanması


MPI ile Mandelbrot Setinin Paralel Olarak Hesaplanması

  1. GİRİŞ
  2. Uygulamadaki genel amaç Mandelbrot setinin MPI kütüphanesini kullanarak paralel olarak hesaplanmasıdır. Hesaplama esnasında yük dengelemesinin dinamik olarak yapılması istenmiştir.

  3. MANDEBROT SETİ
  4. Mandelbrot seti karmaşık düzlemde bir fraktalı biçimlendiren noktalar kümesidir. Mandelbrot seti z2+c formülüne göre (0,0) noktasının yörüngesinde kalan ve belirli bir uzaklığı aşmayan c karmaşık sayılar kümesidir.

    Mandelbrot seti, estetik görünümü ve kolay bir formülden hesaplanabilen karmaşık görüntüsüyle matematik dışındaki alanlarda da popüler olmuştur. Aşağıdaki basit formülden hesaplanmaktadır.

    Mandelbrot setinin karmaşık sayılarla ifade edilen denklemi,  z ve c karmaşık sayıdır.

    f fonksiyonunun sürekli olarak yeni z değerleri için hesaplanmasıyla bir c noktasının mandelbrot seti içerisinde yer alıp almadığı belirlenir. f fonksiyonunun hesaplanması esnasında eğer bir c noktası belirlenen aralıkta kalıyorsa, c noktası mandebrot seti içerisindedir.

    Mandelbrot seti hesaplanırken herhangi bir c sayısının hesaplanması sonsuza kadar gidebileceği için hesaplamanın bitmesi için maksimum iterasyon sayısı belirlenir. Eğer c noktasının belirlenen aralıktan çıkması maksimum iterasyon sayısından daha az sayıda iterasyonda gerçekleşiyorsa hesaplama durdurulur. Aksi durumda c noktası için iterasyon sayısı, maksimum iterasyon sayısı olur.

  5. MANDELBROT SETİNİN RESME AKTARILMASI
  6. Mandelbrot setinin güzel yanı iki boyutlu bir resme aktarıldığında ortaya çıkmasıdır. Bunun için resim içerisindeki x,y koordinatları belirli bir aralığa izdüşürülür. İzdüşürülen bu değerler hesaplama için gerekli c sayısını oluştururlar. c sayısı için hesaplanan iterasyon sayısı mevcut piksel için parlaklık seviyesini oluşturur.

    Mandelbrot setini [-2,-2] , [2,2] aralığına izdüşürürsek set içerisindeki tüm noktaları görebiliriz. Ayrıca belirlenen aralıktan çıkma sayısı (kaçış sayısı) sıfırdan farklı noktaları da tamamıyla görebiliriz.

    İzdüşürme sırasında 800x600 çözünürlüklü bir resim oluşturmak isteyelim. Bunun için resim piksellerinden (0,0), (-2,-2) noktasına izdüşürülür. (800,600) noktası ise (2,2) noktasına izdüşürülür. Kalan pikseller için de aşağıdaki şekilde hesaplanabilir.

    Mandelbrot hesaplamasında kullanılan iterasyon formülü

    a=minimum_x + piksel_x / sutun_sayisi * (maksimum_x – minimum_x)

    b= minimum_y + piksel_y / satır_sayisi * (maksimum_y – minimum_y)

    Üstteki formülde C iterasyon sayısını hesaplayacağımız karmaşık sayıdır. a, C sayısının gerçek kısmı; b ise imajiner kısmıdır. minimum_x ve maksimum_x değerleri sırasıyla izdüşüreceğimiz aralığın x ve y eksenindeki minimum değerleridir. Aynı şekilde maksimum_x ve maksimum_y de izdüşüm alanının maksimum koordinat değerleridir. satır_sayısı ve sütun_sayısı değerleri ise resmimizin çözünürlüğünü belirleyen değerlerdir. Resim üzerindeki her nokta için f fonksiyonunun değeri hesaplanırsa, noktalar için hesaplanan iterasyon sayıları o noktanın rengi (parlaklık seviyesi) olarak belirlenebilir.

    Mandelbrot setinin hesaplanması için aşağıdaki kod kullanılmıştır.

    1. int pixelHesapla(double x,double y)
    2. {
    3.     double zx=0.0;
    4.     double zy=0.0;
    5.     double temp;
    6.     unsigned int max=255;
    7.     unsigned int sayi=0;
    8.     double buyukluk=0.0;
    9.     do
    10.     {
    11.       temp=x+zx*zx-zy*zy;
    12.       zy=y+2*zy*zx;
    13.       zx=temp;
    14.       buyukluk=zx*zx+zy*zy;
    15.       sayi++;
    16.     }
    17.     while(sayi<max && buyukluk<4.0);
    18.     return sayi;
    19. }
    20.  

  7. MPI (Message Passing Interface)
  8. MPI paralel hesaplamalar gerçekleştirmek için geliştirilen bir mesaj geçme standartıdır. Piyasada ücretsiz veya ücretli birçok implementasyonu mevcuttur. MPI ile çalışan uygulamalar SPMD mantığına göre çalışır. Tüm işlemcilerde aynı uygulama çalışır. Program içerisindeki kontrollere göre süreçler efendi (master) veya köle (slave) süreç olarak çalışabilirler.

    MPI içerisinde paralel çalışma için birçok rutin barındırır. Bunlardan bazıları bloklanmalı, bazıları ise bloklanmasız rutinlerdir. Programda kullanılan rutinler aşağıda verilmiştir.

    MPI_Init(&argc,&argv) : MPI’ın başlatılması için gerekli komuttur. MPI ile çalışacak her program bu fonksiyonu programın başlangıcında çalıştırmalıdır. argc ve argv değerleri main fonksiyonuna gelen değişkenlerdir.

    MPI_Finalize() : Program başlarken MPI_Init fonksiyonunu çalıştırdığı gibi, icrasını sonlandırırken de bu fonksiyon çalıştırılmalıdır.

    MPI_Comm_size(MPI_COMM_WORLD,&numprocs) : Bu fonksiyon çalışan MPI süreç sayısını belirler. Referans parametresi olarak verilen numprocs değişkenine çalışan süreç sayısı atanır.

    MPI_Comm_rank(MPI_COMM_WORLD,&myid) : MPI içinde çalışan her sürecin belirli bir numarası vardır. Bunlar sıfırdan başlayıp toplam süreç sayısına kadar gider. Myid değişkenine atanan süreç numarasına göre süreçler efendi yada köle süreç olduklarını belirlerler. Genelde süreç numarası sıfır ise bu süreç efendi süreç olarak seçilir. Efendi süreç yapılacak işleri belirler ve işleri köle süreçlere dağıtır. Köle süreçler de bu işleri gerçekleştirip efendi sürece sonucu gönderirler.

    MPI_Send(buffer, count, datatype, destination, tag, communicator) : Bu fonksiyon mesaj göndermek için kullanılır. Bloklanmalı bir fonksiyondur. Mesaj göndermesi başarılı olmadığı sürece süreç fonksiyonun çağrıldığı yerde bloklanır. Buffer argümanı gönderilecek verinin adresini gösterir. Count değişkeni ise bu bellek adresinden kaç tane veri gönderileceğini belirtir. Datatype değişkeni ise gönderilecek bellekteki verilerin tipini belirtir. Bu üç argümanla istediğimiz tipte bir değişkeni veya diziyi karşı tarafa gönderebiliriz. Destination değişkeni gönderilecek süreç numarasını belirtir. Tag değişkeni mesajın tipini belirleyen bir etikettir. Gönderme işleminin başarışı olması için karşı tarafta bu mesajın aynı etiketle veya MPI_ANY_TAG etiketiyle alınması gerekir. Communicator değişkeni ise haberleşme uzayını belirler. Süreçler mpiexec programıyla çalıştırıldığında aynı haberleşme uzayı içerisinde yer alırlar. Aynı uzaydaki süreçlerle haberleşmek için MPI_COMM_WORLD tanımlaması kullanılır.

    MPI_Recv(buffer, count, datatype, source, tag, communicator, status) : Bu fonksiyon MPI_Send fonksiyonu ile gönderilen mesajları almak için kullanılır. Bu fonksiyonda bloklanmalı bir fonksiyondur. MPI_Send’ den farklı olarak source değişkeni mesajın hangi süreçten geleceğini belirler. Status değişkeni ise gelen mesaj hakkındaki durum bilgilerini tutar. Tipi MPI_STATUS olan bir struct yapısıdır. Bu yapıdan gelen mesajın etiketi, gönderen sürecin numarası gibi bilgiler elde edilebilir.

  9. MANDELBROT SETİNİN PARALEL OLARAK HESAPLANMASI
  10. Mandelbrot setinin paralel olarak hesaplanması için oluşturulacak resmin bölümlere ayrılıp köle süreçlere paylaştırılması gerekir. Bölümlere ayırma işlemi ders slaytlarında anlatıldığı gibi 2 farklı şekilde yapılabilir. Hesaplama kolaylığı açısından resmi satırlara bölüp köle süreçlere satırlar verilir. Hesaplamalar arasında herhangi bir veri bağımlılığı olmadığı için mandelbrot seti çok kolay bir şekilde paralelleştirilebilir.

    Mandelbrot seti hesaplanırken dinamik yük dengelemesi amaçlanmıştır. Dinamik yük dengelemesinde boşta olan köle süreçler efendi süreçten görev ister. Efendi süreçte kalan hesaplama bölümlerini köle süreçlere gönderir. Köle süreçler hesaplamayı tamamladıktan sonra sonucu efendi sürece gönderir ve yeni bir iş ister. Tüm işler bittiğinde efendi süreç köle süreçlere başka iş kalmadığını bildiren bir mesaj gönderir.

    Yazılan programda komut satırından girilen argümanlara göre resmin çözünürlüğü değişebilir. Aynı zamanda mandelbrot setinin istenilen herhangi bir bölümü çizdirilebilir. Bu şekilde çözünürlük sabit kalarak, set içerisindeki herhangi bir konuma yakın çekim (zoom) yapılabilir.

    Efendi Süreç Kodu :

    Başlangıçta bütün köle süreçler boş olacağı için efendi süreç tarafından bütün köle süreçlere bir iş gönderilir. Hesaplama satırlara göre olacağından, bütün köle süreçlere satır numarası gönderilir. Daha sonra efendi süreç köle süreçlerden mesaj beklemeye başlar. Burada köle süreçlerden hangi satırın değerlerini hesapladığını bildiren bir mesaj gelir. Bundan sonra da hesaplanmış değerlerin bulunduğu bellek bölgesi köle süreçler tarafından gönderilir. Alınan satır numarasına göre gelen değerler resmin bulunduğu bellekteki gerekli yere yerleştirilir ve işini bitiren köle sürece hesaplanmamış satırlardan bir tanesini gönderir. Tüm satırlar hesaplandıktan sonra bütün köle süreçlere başka iş kalmadığını bildiren boş bir mesaj gönderilir. Bu mesajın etiketi normal hesaplama mesajlarından farklı bir değer (2) olduğu için köle süreçler tarafından ayırt edilebilir.

    Tüm hesaplama bittikten sonra efendi süreç resmin bulunduğu bellek alanındaki verileri bir dosyaya yazarlar.

    Köle Süreç Kodu :

    Köle süreçler sonsuz bir döngü içerisinde efendi süreçten iş beklerler. Gelen mesajın etiketine bakıp başka iş kalıp kalmadığını belirlerler. Eğer iş varsa hesaplamayı yapıp efendi sürece gönderirler ve yeni bir iş beklemeye başlarlar. Başka iş kalmamışsa icralarını sonlandırırlar.

  11. MANDELBROT SETİNİN GÖSTERİMİ
  12. Şu ana kadar anlatılan kısımda mandelbrot setinin nasıl hesaplanacağını gördük. Kullanılan MPI implementasyonuyla Windows işletim sisteminde MFC tipi pencereler gösterilemediği için setin gösterilmesi için ayrı bir uygulama geliştirildi. Bu uygulama mandelbrot setinin hesaplandığı ana program tarafından kaydedilen resim dosyasını okuyup resmi ekrana bastırır. Bu uygulama içerisinde fareyle seçilen bölgenin değerleri hesaplanıp seti hesaplayan MPI programı uygun argümanlarla tekrar çağrılmaktadır. Böylelikle set içerisinde yakın çekim (zoom) imkanı gerçekleşmektedir.

  13. MANDELBROT SETİNİN RENKLENDİRİLMESİ
  14. Normal olarak mandelbrot setinde hesaplanan iterasyon sayıları mevcut pikselin parlaklık seviyesi olarak belirlenir. Dolayısıyla oluşan resim gri seviye bir resimdir. Daha güzel bir görünüm elde edebilmek için farklı bir renklendirme yoluna gidilmiştir. Burada kullanıcı tarafından iki renk seçilir. Mevcut pikselin rengi hesaplanan parlaklık seviyesi oranında bu iki renk arasına izdüşürülür. Setin dış kısmındaki noktaların parlaklık seviyesi az olduğu için izdüşürmedeki renk geçişleri çok fazla ayırt edilemez. Bunun için parlaklık seviyesi değişken bir ağırlıkla çarpılarak seçilen iki renkten ikincisine daha yakın bir renge izdüşürülür. Böylelikle renk geçişleri ayırt edilebilir bir hale gelir. Fakat setin sınır noktalarındaki renkler ayırt edilemez konuma gelir. Program içerisinden bu çarpan değeri değiştirilebilir. C# ile yazılan renklendirme kodu aşağıdadır.

    Color renk1 = btr1.BackColor; //Seçilen 1. renk
    Color renk2 = btr2.BackColor; //Seçilen 2. renk
    int R, G, B;
    bmp = new Bitmap(width, height);
    for (int i = 0; i < height; i++)
    for (int j = 0; j < width; j++)
    {
        int renk = 0;
        renk = br.ReadInt32(); //Renk değerini dosyadan oku
        if (cbRenklendirme.Checked)
        {
            R = renk;
            G = renk;
            B = renk;
        }
        else
        {
            R=renk1.R+Convert.ToInt32((renk2.R-renk1.R) * renk * nmCarpan.Value / 256);
            G=renk1.G+Convert.ToInt32((renk2.G-renk1.G) * renk * nmCarpan.Value / 256);
            B=renk1.B+Convert.ToInt32((renk2.B-renk1.B) * renk * nmCarpan.Value / 256);
            R = R > 255 ? 255 : R;
            G = G > 255 ? 255 : G;
            B = B > 255 ? 255 : B;
            R = R < 0 ? 0 : R;
            G = G < 0 ? 0 : G;
            B = B < 0 ? 0 : B;
       
        }
        if (renk != 255)
            bmp.SetPixel(j, i, Color.FromArgb(R % 256, G % 256, B % 256));
        else
            bmp.SetPixel(j, i, Color.FromArgb(0, 0, 0));

     

  15. PROGRAM KODU

Aşağıda mandelbrot setini paralel olarak hesaplayan programın kodu vardır.

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <stdbool.h>
  5. #include <mpi.h>
  6. int GEN; //genişlik
  7. int YUK; //yükseklik
  8. int ELEMAN_SAYISI; //piksel sayısı
  9. double xMin,yMin,xMax,yMax; //çizilecek mandelbrot aralığı
  10.  
  11. int dosyayaYaz(char * dosyaAdi,int * buffer,unsigned int boyut);
  12. int pixelHesapla(double x,double y);
  13. int dosyayaYaz(char * dosyaAdi,int * buffer,unsigned int boyut)
  14. {
  15.     int i;
  16.     FILE* fp=fopen(dosyaAdi,"wb");
  17.     int bilgi[2];//genişlik ve yüksekliği tutmak için buffer
  18.     bilgi[0]=GEN;
  19.     bilgi[1]=YUK;
  20.     fwrite(bilgi,sizeof(int),2,fp); //Genişlik,yükseklik yaz
  21.     fwrite(buffer,sizeof(int),boyut,fp); //Resim bilgilerini yaz
  22.     fclose(fp);
  23. }
  24. int pixelHesapla(double x,double y)
  25. {
  26.     double zx=0.0;
  27.     double zy=0.0;
  28.     double temp;
  29.     unsigned int max=255;
  30.     unsigned int sayi=0;
  31.     double buyukluk=0.0;
  32.     do
  33.     {
  34.       temp=x+zx*zx-zy*zy;
  35.       zy=y+2*zy*zx;
  36.       zx=temp;
  37.       buyukluk=zx*zx+zy*zy;
  38.       sayi++;
  39.     }
  40.     while(sayi<max && buyukluk<4.0);
  41.     return sayi;
  42. }
  43. int main(int argc,char *argv[])
  44. {
  45.   if(argc!=3 && argc!=7)
  46.   {
  47.     printf("argc:%d\n",argc);
  48.     printf("Usage: %s <width> <height> ,[<xMin> <yMin> <xMax> <yMax>]\n",argv[0]);
  49.     printf("Example: %s 800 600 -2.0 -2.0 2.0 2.0",argv[0]);
  50.     exit(1);
  51.   }
  52.   GEN=atoi(argv[1]);
  53.   YUK=atoi(argv[2]);
  54.   if(argc==3)
  55.   {
  56.     xMin=-2.0;
  57.     yMin=-2.0;
  58.     xMax=2.0;
  59.     yMax=2.0;
  60.   }
  61.   else
  62.   {
  63.   printf("xmin:%s ymin:%s xmax:%s ymax:%s\n",argv[3],argv[4],argv[5],argv[6]);
  64.     xMin=atof(argv[3]);
  65.     yMin=atof(argv[4]);
  66.     xMax=atof(argv[5]);
  67.     yMax=atof(argv[6]);
  68.   printf("xmin:%f ymin:%f xmax:%f ymax:%f\n",xMin,yMin,xMax,yMax);
  69.   }
  70.  
  71.  
  72.   ELEMAN_SAYISI=GEN*YUK;
  73.   int *aralik; //Gönderilecek mandelbrot aralığı
  74.   int * mandel,*mandel1;
  75.   int numprocs;
  76.   int myid;
  77.   int i,j;
  78.  
  79.   MPI_Status stat;
  80.   MPI_Init(&argc,&argv);
  81.   MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
  82.   MPI_Comm_rank(MPI_COMM_WORLD,&myid);
  83.  
  84.   if(myid == 0)
  85.   {
  86.     //Master işlemci kodu
  87.     size_t sz=sizeof(int)*ELEMAN_SAYISI;
  88.     mandel=(int *)malloc(sz);
  89.     if(!mandel) printf("Bellek ayrılamadı\n");
  90.     printf("Ayrilan bellek: %d bayt\n",sz);
  91.     aralik=malloc(sizeof(int)*2);
  92.     for(i=1;i<numprocs;i++)
  93.     {
  94.       aralik[0]=i-1;
  95.       if(MPI_Send(aralik,1,MPI_INT,i,1,MPI_COMM_WORLD)!=MPI_SUCCESS)
  96.         printf("\nİşlemci: %d -> İşlemci: %d Aralık göndermede hata var...\n",myid,i);
  97.     }
  98.     for(i=numprocs;i<=YUK;i++)
  99.     {
  100.       MPI_Recv(aralik,1,MPI_INT,MPI_ANY_SOURCE,1,MPI_COMM_WORLD,&stat);
  101.       MPI_Recv(mandel+aralik[0]*GEN,GEN,MPI_INT,stat.MPI_SOURCE,2,MPI_COMM_WORLD,&stat);
  102.       aralik[0]=i-1;
  103.       if(MPI_Send(aralik,1,MPI_INT,stat.MPI_SOURCE,1,MPI_COMM_WORLD)!=MPI_SUCCESS)
  104.         printf("\nİşlemci: %d -> İşlemci: %d Aralık göndermede hata var...\n",myid,i);
  105.     }
  106.     for(i=1;i<numprocs;i++)
  107.     {
  108.       MPI_Recv(aralik,1,MPI_INT,MPI_ANY_SOURCE,1,MPI_COMM_WORLD,&stat);
  109.       MPI_Recv(mandel+aralik[0]*GEN,GEN,MPI_INT,stat.MPI_SOURCE,2,MPI_COMM_WORLD,&stat);
  110.  
  111.       MPI_Send(aralik,1,MPI_INT,i,2,MPI_COMM_WORLD);
  112.       printf("Sending stop signal to:%d\n",i);
  113.     }
  114.     dosyayaYaz("deneme.mnd",mandel,ELEMAN_SAYISI);
  115.     fflush(stdout);
  116.   }
  117.   else
  118.   {
  119.       //Slave işlemci kodu
  120.       printf("PE:%d proses başlangıcı\n",myid);
  121.       mandel1=(int *)malloc(GEN);
  122.       if(!mandel) printf("Bellek ayrılamadı: %d\n",myid);
  123.       aralik=malloc(sizeof(int)*2);
  124.       bool isVar=true;
  125.       while(isVar)
  126.       {
  127. if(MPI_Recv(aralik,1,MPI_INT,0,MPI_ANY_TAG,MPI_COMM_WORLD,&stat)!=MPI_SUCCESS)
  128.         printf("\nİşlemci: %d -> Aralık almada hata var...\n",myid);
  129.       if(stat.MPI_TAG!=2)
  130.       {
  131.       float xArtis=(xMax-xMin)/GEN;
  132.       double x;
  133.       double y=yMin+((yMax-yMin)/YUK)*aralik[0];
  134.       for(i=0,x=xMin;i<GEN;i++,x+=xArtis)
  135.       {
  136.         mandel1[i]=pixelHesapla(x,y);
  137.       }
  138.       MPI_Send(aralik,1,MPI_INT,0,1,MPI_COMM_WORLD);
  139.       if(MPI_Send(mandel1,GEN,MPI_INT,0,2,MPI_COMM_WORLD)!=MPI_SUCCESS)
  140.         printf("\nİşlemci: %d -> Sonuç değerlerini göndermede hata var...\n",myid);
  141.         }
  142.         else
  143.         {
  144.         isVar=false;
  145.         }
  146.         }
  147.   } 
  148.   free(mandel);
  149.   free(mandel1);
  150.   fflush(stdout);
  151.   MPI_Finalize();
  152.     return 0;
  153. }
  154.  
  155.  

Programın Tamamını Aşağıdaki Linkten İndirebilirsiniz

Linki Görebilmeniz İçin Üye Olmanız Gerekmektedir...

Üye Kayıt

 

Programın c# ile hazırlanan arayüzünde, oluşturulan resimleri aşağıdaki gibi kaydedebilirsiniz.

Mandelbrot kümesinin başlangıç değerler arasındaki görünümü

Yorumlar (0)
Sadece kayıtlı kullanıcılar yorum yazabilir!
Son Güncelleme ( Perşembe, 07 Nisan 2011 21:21 )  
amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım