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

Hata
  • XML Parsing Error at 1:82. Error 9: Invalid character
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 )  
404 Not Found

404

Not Found

The resource requested could not be found on this server!


Proudly powered by LiteSpeed Web Server

Please be advised that LiteSpeed Technologies Inc. is not a web hosting company and, as such, has no control over content found on this site.