Paralel Programlama ile PI Sayısının Hesaplanması

PI sayısı küçük yaşımdan beri bana hep gizemli gelmiştir. İrrasyonel yapıda olduğu için tam değeri hesaplanamayışı, bir çok matematiksel ve geometrik hesabın temelini oluşturması, çok eski medeniyetler tarafından kullanılmış olması insanın ister istemez ilgisini çekiyor. İnternetteki bir tanıma göre (bkz: wikipedia) "çapı 1 olan dairenin çevre uzunluğu" dur PI sayısı.

(bkz: http://tr.wikipedia.org/wiki/Dosya:Pi-unrolled-720.gif)

PI sayısının önemi hakkında daha fazla yazıp çizmek isterdim fakat bu yazının konusu dışında kalmaktadır. Asıl konumuz bu sayının yaklaşık değerini Paralel Programlama yöntemlerini kullanarak nasıl hesaplarız. Yaklaşık değerini dedim çünkü tam değerini hesaplayamayacağımızı artık biliyoruz. :) Bu sayı için hesaplayacağımız basamak sayısı yapmak istediğimiz işin büyüklüğüyle doğru orantılı. Arka bahçemizdeki havuzunuz kaç m^3 su aldığını hesaplamamız için 3.1415 değeri yeterken, Ay'a bir araç göndermek isteyen NASA mühendisleri için 3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912 9833673362 4406566430 8602139494 6395224737 1907021798 6094370277 0539217176 2931767523 8467481846 7669405132 0005681271 4526356082 7785771342 7577896091 7363717872 1468440901 2249534301 4654958537 1050792279 6892589235 4201995611 2129021960 8640344181 5981362977 4771309960 5187072113 4999999837 2978049951 0597317328 1609631859 5024459455 3469083026 4252230825 3344685035 2619311881 7101000313 7838752886 5875332083 8142061717 7669147303 5982534904 2875546873 1159562863 8823537875 9375195778 1857780532 1712268066 1300192787 6611195909 2164201989 3809525720 1065485863 2788659361 5338182796 8230301952 0353018529 6899577362 2599413891 2497217752 8347913151 5574857242 4541506959 5082953311 6861727855 8890750983 8175463746 4939319255 0604009277 0167113900 9848824012 8583616035 6370766010 4710181942 9555961989 4676783744 9448255379 7747268471 0404753464 6208046684 2590694912 9331367702 8989152104 7521620569 6602405803 8150193511 2533824300 3558764024 7496473263 9141992726 0426992279 6782354781 6360093417 2164121992 4586315030 2861829745 5570674983 8505494588 5869269956 9092721079 7509302955 3211653449 8720275596 0236480665 4991198818 3479775356 6369807426 5425278625 5181841757 4672890977 7727938000 8164706001 6145249192 1732172147 7235014144 1973568548 1613611573 5255213347 5741849468 4385233239 0739414333 4547762416 8625189835 6948556209 9219222184 2725502542 5688767179 0494601653 4668049886 2723279178 6085784383 8279679766 8145410095 3883786360 9506800642 2512520511 7392984896 0841284886 2694560424 1965285022 2106611863 0674427862 2039194945 0471237137 8696095636 4371917287 4677646575 7396241389 0865832645 9958133904 7802759009 değeri yetersiz ya da yanıltıcı olabilir. Bu yüzden sıradışı ihtiyaçlar için (fezaya mekik göndermek gibi) sıradışı çözümler sunmamız gerekmektedir. Bir gün NASA mühendisleri için PI sayısı hesaplarmıyız bilemiyorum fakat gelecekte çok fazla paralel işlem bizleri bekliyor. Şimdiden kendimizi hazırlamalıyız.

Lafı fazla dolandırmadan işe koyulalım. İlk PI hesabımızı Monte Carlo yöntemiyle yapacağız. Bu yöntem oldukça basit bir olasılık hesabına dayanmaktadır.



Bu olasılık hesabını yapmak için C++ programlama dili üzerinden openMP kütüphanesini kullandım. Paylaşımlı bellek üzerinden paralel programlama yapmak için geliştirilmiş olan bu kütüphane kullanması oldukça basittir. Mevcut kodunuza hiç dokunmadan (elbetteki paylaşımlı bellek paralel program mantığı güdülerek yazılmış kod olamalı) doğrudan programınızı paralel çalıştırabilirsiniz. Bu yazacağımız program dağıtık mimariler için değil tek bir süper bilgisayar için programlanmıştır. Makine üzerindeki çekirdek sayısıyla doğru orantılı olarak performans artışı sağlanacaktır.

Programımızı yazmadan önce Visual Studio 2010 üzerinden projemizin openMP desteğini açalım. Project -> Properties ...


(DÜZELTME)








Şimdi programımızı yazalım. Programda açıklamak istediğim tüm noktaları yorum satırı olarak ekledim. Bir göz atalım sonra sonuçları değerlendirelim.

/*
 Monte Carlo yöntemiyle PI sayısının yaklaşık değerinin hesaplanması.

 C++ / openMP

 Ramazan Bellek - Kasım 2010
*/

#include <iostream>
#include <ctime>
#include <math.h>

#define MAX_ITERATION 1000000 // tekrarlama sayısı
#define r 500 // yarıçap
#define R r*2+1 // çap + 1

int main(int argc, char **argv)
{
 srand(time(0));
 clock_t start = clock();

 bool iceride[MAX_ITERATION]; // doğruluk tablomuz
 double x,y;

 /*
  openMP ile birbirinden bağımsız olan hesaplama kısmını işlemciye paralel olarak işletiyoruz.
  x ve y değişkenleri her bir iş parçacığı için kişisel olarak tanımlandı, böylelikle bir iş parçacığı
  diğerinin konum bilgisini görememektedir. Doğruluk tablosunu belirten değişkeni ise ortak olarak
  kullanacaklardır.
 */
#pragma omp parallel for private(x,y) shared(iceride)
 for(int i=0;i<MAX_ITERATION; i++)
 {
  // uzayda bir noktayı (sözde) keyfi seçiyoruz.
  x = rand()%R;
  y = rand()%R;

  double fark = sqrt(pow(x-r,2)+pow(y-r,2)); // seçtiğimiz noktanın dairenin merkezine olan uzaklığını alıyoruz.

  if (fark<=r) // eğer bu uzaklık dairenin yarıçapından küçük ya da eşit ise nokta dairenin içerindedir.
   iceride[i]=true;
  else
   iceride[i]=false;
 }

 long toplamIceride = 0;
 // daire içerisine düşen toplam sayı 
 for(int i=0;i<MAX_ITERATION; i++){
  if (iceride[i]==true)
   toplamIceride++;
 }

 /*
  daire_icine_dusen/toplam = (pi*r^2)/(4*r^2)
         => pi = 4 * daire_icine_dusen/toplam
 */
   std::cout<<"PI ~= "<<4*(double)toplamIceride/MAX_ITERATION<<std::endl;

 printf("Gecen Sure: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
 system("pause");
 return 0;
}

Programımızı çalıştırıyoruz.



Sonuç aslında pek istediğim gibi çıkmadı. Beklentim en azından ilk 4 basamağı (3.1415) bulmak üzereydi. İterasyonları arttırarak tekrar denenebilir, ayrıca burada ürettiğimiz rastgele sayılar sözde olduğu için bize tam bir sonuç vermesi beklenemez. İterasyonu arttırarak işlemcinin çekirdeklerindeki değişimi göstermek istiyorum.



Gördüğünüz gibi PI sayısını bir süper bilgisayarda nasıl hesaplayacağımızı basit olarak da olsa görmüş olduk. Daha detaylı görsel uygulama için http://www.eveandersson.com/pi/monte-carlo-demo adresindenki java applete göz atabilirler.

Bir sonraki paralel programlama yazımda paylaşımsız bellekli dağıtık mimari kullaranak PI sayısını hespalamaya çalışacağım. Küçük bir bilgisayar kümesi kurarak dev işlemleri basitleştirmeye çalışacağız. Gelecekteki bir bilgisayar ordusunun komutanı olmanız ümidiyle. Hoşçakalın...