Burak IŞIKLI :))

Paralel Programlama(Hesaplama) Temelleri

Posted in Distributed Systems, Parallel Computing by Burak IŞIKLI on 18 Ocak 2010

Paralel hesaplama en basit şekliyle şöyle tarif edebiliriz. Bir problemi çözmek için kaynaklaı eşzamanlı çoklu olarak kullanmaktır. Örneğin bir integrali hesaplamak için iki bilgisayarı veya iki işlemci(çekirdeği) kullanarak yapabiliriz. Bu örnekleri çoğaltabiliriz. Fakat paralel programlama yaparken dikkat edeceğimiz ilk önemli konulardan biri mimarilerdir. Bu konuda şöyle bir yasa vardır:
Moore Yasası:
Intel şirketinin kurucularından Gordon Moore’un 19 Nisan 1965 yılında Electronics Magazine dergisinde yayınlanan makalesi ile teknoloji tarihine kendi adıyla geçen yasa.
Her 18 ayda bir tümleşik devre üzerine yerleştirilebilecek bileşen sayısının iki katına çıkacacağını, bunun bilgisayarların işlem kapasitelerinde büyük artışlar yaratacağını, üretim maliyetlerinin ise aynı kalacağını, hatta düşme eğilimi göstereceğini öngören deneysel (ampirik) gözlem. Bu gözlem kendini doğrulamıştır. Bu durumda bu teoriye göre tasarım karmaşıklığı, performans artışının nasıl olacağı, ölü alanlarla ne yapacağız gibi engeller önümüze çıkıyor. İşte bu noktada paralellik önümüze çıkıyor.
Paralel sistemlerin birçok kullanım alanı vardır. Hava tahmini modelleme, termonükleer proses, fizik, kimya, biyoteknoloji, matematik, veri madenciliği, web indeksleme, veritabanları gibi birçok alanda kullanılıyor.
Paralel programlama başlamadan önce bazı dar boğazları aşmamız gerekiyor:

Bu konuyu 3 farklı şekilde çözebiliriz:
* Multiple Datapath(Çoklu Veriyolu)
* Multiple Memory Units(Çoklu Hafıza Birimleri)
* Multiple Processing Units(Çoklu İşlemci Birimleri)
Bu konuda sıkça kullanılan iki mimari mevcuttur.
1-) SIMD(Single Instruction Multiple Data): Bir kontrol birimini(bir direktif) farklı veri setlerinde işlem yapılarak sonuca ulaşılıyor. Yani bir programımız olurken, programlarımız aynı veri setini kullanıyor.
2-) MIMD(Multiple Instruciton Multiple Data): Farklı direktifleri farklı veri setlerine işlem yaparak sonuca ulaşılıyor. Yani birden fazla programımız farklı veya bölünmüş veri setinde işlem yapıyor.
Bu mimarilerden istediğimiz birini kullanarak darboğazı aşabiliriz. Programlamaya başlamadan önce bize uygun paralel mimarimizi seçtikten sonra hangi paralel algoritmayı kullanacağımıza karar vermemiz gerekiyor.

Paralel Algoritmalar:
– Data Paralel
– Task-Graph
– Work Pool
– Master Slave
– Pipeline
– Hybrid
Bu algoritmaları araştırarak detaylı bulabilirsiniz. Ben zamanı geldikçe anlatacağım. Bize uyan paralel algoritmayı da seçtikten sonra programlamaya geçebiliriz. Literatürde kullanabileceğimiz iki paralel programlama modeli vardır.
* Message-Passing
* Shared Adress Space

1-) Message-Passing
* Genelde büyük çaptaki bilgisayar sistemlerinde kullanılan program türü(Örneğin Cluster sistemlerde)
* Paylaştırılmış adres alanı
* Implicit paralelleme
* Proses etkileşimi veriyi gönderip alarak sağlanıyor
* Haberleşme mesajları gönderip alarak sağlanıyor
* Primitive
+ Send
+ Recieve
+ Blocking vs non-blocking
+ Buffered vs non-buffered
* En iyi bilinen bu konuda kullanılan kütüphanesi MPI(Message-Passing Interface)

2-) Shared Address Space
* Genelde SMP makinalarda kullanılır.(Multicore chip)
* Paylaşılmış adres alanı
* Thread
* Shmget/shmat unix operasyonları
* Explicit Paralelleştirme
* Proses/Thread haberleşmesi ile iletişim sağlanır.
* Memory oku/yaz ile haberleşme gerçekleşir.(Örnek x++;)
* En iyi bilinen bu konuda kullanılan kütüphanesi POSIX Thread(PThreads) API
+ Thread oluşumu ve silinmesi
+ Thread yönetimi
+ Senkronizasyon

Paralel Programlama Görünmez Tehlikeleri(Pitfalls)
– Senkronizasyon
+ Deadlock
+ Livelock
+ Fairness
– Verimlilik
+ Paralelleştirmeyi maksimum hale getirmek
– Güvenilirlik
+ Doğruluk
+ Debugging

Google App Engine Java İpuçları

Posted in Java by Burak IŞIKLI on 14 Ağustos 2009

Google, geçtiğimiz günlerde app engine yani uygulama sunucusunu piyasaya sürdü. İlk izlenimlerimin ardından app engine ile ilgili birkaç detay vermek istedim. Yemek tarzındaki kurulumu birçok sitede kurulumun nasıl yapılacağını bulmanız mümkün. Ben de ayrıca java programcıları ve teknolojileri derneği tarafından yayınlanmış sitenin pdf dosyasını veriyorum.

Kurulumu yapıp örnek bir proje oluşturduktan sonra uygulamanın nasıl çalıştığını anlayalım. Öncelikle deploy yapmadan projeniz web’e atılmaz. Bu nedenle de yerel alanda istediğiniz kadar değişiklik yaparken asıl sayfanız(belirttiğinizad.appspot.com) herhangi bir değişiklik olmaz.

Her zaman belirttiğiniz proje isminin servlet’i oluşturuluyor. Örneğin deneme diye proje oluşturuyorsanız servlet’inizin adı otomatik olarak denemeServlet oluyor. Peki bunu nasıl değiştireceğiz? Refactor kullanmanız ismini değiştirmek için yeterli gelmiyor. Bunu deneyip deploy ederseniz karşınıza boş bir sayfa çıkacaktır. Bildiğiniz üzere bu servlet’imizin bağlı olduğu web.xml dosyası olması gerekiyor. İşte bu dosya war klasörünün altındaki web-inf klasöründedir. Aşağıdakine benzer bir dosya karşınıza gelecektir.

web.xml


<?xml version="1.0" encoding="utf-8"?>
<web-app xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xmlns="http://java.sun.com/xml/ns/javaee"
xmlns:web="http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"
xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd" version="2.5">
 <servlet>
 <servlet-name>Deneme</servlet-name>
 <servlet-class>edu.burakkk.google.app.DenemeServlet</servlet-class>
 </servlet>
 <servlet-mapping>
 <servlet-name>Deneme</servlet-name>
 <url-pattern>/deneme</url-pattern>
 </servlet-mapping>
 <welcome-file-list>
 <welcome-file>index.html</welcome-file>
 </welcome-file-list>
</web-app>

Buradan servlet-class ismini de değiştirerek servlet isminde kolayca değişiklik yapabilirsiniz. Ayrıca url-pattern ile servletinizin çalışacağı uzantıyı da değiştirebilirsiniz. deneme yerine deneme.do yapabilirsiniz. Başlangıçta google app engine tarafından oluşturulan index.html yerine de welcome-file değiştirerek de kendi istediğiniz dosyayı hatta çalıştıracağınız servlet’i yapabilirsiniz. Bunun anlamı xxx.appspot.com sayfasını açtığınızda kendi tarafından oluşturulmuş index sayfası yerine sizin sayfanız çıkabilir.

Eğer uygulama ismini veya versiyonu değiştirmek istiyorsanız aynı dizindeki(war/web-inf) appengine-web.xml dosyasından yapacaksınız.

appengine-web.xml


<?xml version="1.0" encoding="utf-8"?>
<appengine-web-app xmlns="http://appengine.google.com/ns/1.0">
 <application>bisikli</application>
 <version>1</version>

 <!-- Configure java.util.logging -->
 <system-properties>
<property name="java.util.logging.config.file" value="WEB-INF/logging.properties"/>
 </system-properties>

</appengine-web-app>

Application kısmından uygulama ismini versiyon kısmından da versiyonunu değiştirebilirsiniz.

Bunları dikkate alarak anasayfamızda gerçek ip’nizi çıkaran bir servlet yapalım.

edu.burakkk.google.app isimli paket ipAlma isimli servlet yaratıyoruz.

ipAlma.java


package edu.burakkk.google.app;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.http.*;

@SuppressWarnings("serial")
public class ipAlma extends HttpServlet {
 public void doGet(HttpServletRequest req, HttpServletResponse resp)
 throws IOException {
 resp.setContentType("text/html");
 PrintWriter out = resp.getWriter();
 out.println("IP: " + req.getRemoteHost());
 out.flush();
 out.close();
 }
}

web.xml


<?xml version="1.0" encoding="utf-8"?>
<web-app xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xmlns="http://java.sun.com/xml/ns/javaee"
xmlns:web="http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"
xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd" version="2.5">
 <servlet>
 <servlet-name>ipAlma</servlet-name>
 <servlet-class>edu.burakkk.google.app.ipAlma</servlet-class>
 </servlet>
 <servlet-mapping>
 <servlet-name>ipAlma</servlet-name>
 <url-pattern>/ipAlma</url-pattern>
 </servlet-mapping>
 <welcome-file-list>
 <welcome-file>ipAlma</welcome-file>
 </welcome-file-list>
</web-app>

Bu projeyi deploy ettiğinizde anasayfanızda IP: XXXXX şeklinde ip’nizi yazan bir web sayfası çıkacaktır. Örnek sayfaya http://bisikli.appspot.com/(sizinUygulamaAdınız.appspot.com) adresinden ulaşabilirsiniz. Ayrıca aynı sayfaya servlet’mize http://bisikli.appspot.com/ipAlma bu adresle de ulaşabiliriz.

Dinamik Programlama(Dynamic Programming)

Posted in Algorithm, C/C++ by Burak IŞIKLI on 14 Ağustos 2009

Dinamik programlama bir problemi çözerken aynı alt-problemi birden fazla çözmemiz gereken durumlarda bu alt-problemi birden fazla kez çözmemizi engelleyen bir tekniktir. Dinamik programalama, matematik ve bilgisayar bilimlerinde karmaşık problemleri çözmek için kullanılan bir metottur. Overlapping subproblems ve optimal substructure denilen problemlerde uygunabiliyor.

Eğer problemimiz kendi içinde alt problemlere ayrılabiliyorsa overlapping subproblems’dir. Buna en iyi örnek Fibanicci serisidir. Daha önceden bu yazımda fibonacci serisini anlatmıştım.

Shortest Path Optimal SubstructureFakat problemimiz kendi içinde alt problemlere ayrıldığında daha iyi bir performans sağlıyorsa buna optimal substructure deniliyor. Buna en iyi örnek ise greedy algoritmasıdır. Dinamik programlamada geçen programlama sözcüğü sadece bilgisayar programlarını kapsamamaktadır, çünkü burada kullandığımız program sözcüğü “matematiksel programlama” dan gelmektedir, ki bu da kısaca sıkça kullandığımız optimizasyon(bir nevi iyileştirme demek optimizasyon belki kullanmayan da vardır :) kelimesine denk gelmektedir.

Dinamik programlama uygulamalarımızda temel olarak 3 teknikten faydalanacağız:

  • Çözümü aynı olan alt-problemler
  • Büyük bir problemi küçük parçalara bölmek ve bu küçük parçaları kullanarak baştaki büyük problemimizin sonucuna ulaşmak
  • Çözdüğümüz her alt-problemin sonucunu bir yere not almak ve gerektiğinde bu sonucu kullanarak aynı problemi tekrar tekrar çözmeyi engellemek.

Şimdi örneğimiz olan fibonacci dizimize başlayalım. Fibonacci dizimizi kısaca bir hatırlayalım.

Eğer herhangi bir sayının Fibonacci karşılığına F(n) dersek,

F(0) = F(1) = 1 olmak üzere

F(n) = F(n-1) + F(n-2)’dir.

İlk yaptığımız prosesimizin fonksiyonunu hatırlayalım:

fib.cpp

// Recursive Function
int fib(int num) {
 if ((num == 0) || (num == 1))
 return num;
 else
 return (fib(num - 1) + fib(num - 2));
}

Bu kadar kısa bir kod yazarak çözümü sağlamıştık. Ancak bu yöntem kodun kısa olmasına rağmen performans açısından kötü bir yöntemdir.  Nedenine gelirsek mesela F(3)’ü adım adım hesaplayalım:

F(4) = (F(2) + F(1)))

= ((F(1) + F(0)) + F(1)) + F(2)

= ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

Görüldüğü gibi F(4) değerini hesaplarken F(1)’ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık. Prosesimizi değiştirerek bir de şu hale getirelim.

fib2.cpp

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Burada yaptığımız işlem ise şu. Hesapladığımız Fibonacci sayılarını bir diziye kaydediyoruz. Daha sonra lazım olunca bu değerleri direkt diziden hazır bi şekilde alıyoruz. Böylece aynı işlemi tekrar tekrar yapmaktan kurtuluyoruz.

Performans karşılaştırması yapacak olursak kendi bilgisayarımda fibonacci(50) 8dk. 36 sn'de sonuç verirken fibonacci2(50) 0.003 sn'de sonuç veriyor. Daha bilimsel konuşacak olursak problemi temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2^n) iken ikincisi O(n) zamanda çözmektedir.

Kaynaklar:

http://en.wikipedia.org/wiki/Dynamic_programming

http://en.wikipedia.org/wiki/Optimal_substructure

http://e-bergi.com/2008/Mart/Dinamik-Programlama

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Takip Et

Her yeni yazı için posta kutunuza gönderim alın.