23 Ağustos 2013 Cuma

Unrar Kütüphanesiyle Paralel Şifre Bulucu #2


Unrar kütüphanesi beş tane fonksiyonuyla (aslında yedi ancak ben beşini anlattım) programcıya kolaylıkla .rar dosyaları için arabirim sağlıyor. Kütüphanenin bazı kısıtları var, bunun en başında hız geliyor. Hız kısıtlaması .rar dosyaların yapısından kaynaklı olabilir. Programı yazarken karşıma çıkan sıkıntı her şifre denemesi için dosyanın kapatılıp yeniden açılması oldu. Bu her defasında arşiv dosyası için gerekli bellek yapılarının silinip bellekte yeniden ayrılması demek. Belki gelecekte kodu daha da hızlandırmak için kendi .rar kütüphanemi yazmam gerekebilir. Yazının bu kısmında paralel programlama ve MPI paralel programlama kütüphanesini anlatacağım.

Büyük işlem gücü gerektiren işlemlerin küçük parçalara ayrılarak paralel olarak işlenmesi fikri yeni değil. Paralel hesaplamayı popüler hale getiren SETI@Home projesi bundan 15 yıl önce başladı. Daha sonra United Devices'ın kanser ve şarbona karşı ilaç için molekül araştırma projeleri geldi. Diğer yandan 2000'lerin başında 3DS MAX render işlerini küçük parçalara bölüp şebeke üzerinden birbirine bağlı makinalara gönderebiliyordu. 3DS MAX'i çalıştıran ve render işini başlatan bir ana makina vardı. Diğer makinalarda hesaplama işleri için istemciler kuruluydu. Ana makina iş parçalarını diğer makinalara dağıtıyor, sonuçları alıyor, işleyip renderi tamamlıyordu. Günümüzdeyse küme bilgisayarlar (Cluster Computing) artık yüksek performanslı hesaplama işlerinin vazgeçilmez bir parçası. Birçok araştırma merkezinde bu bilgisayarlardan kurulu ve bilgisayarların konfigürasyonları basit ve eski masaüstü Pentium 4'lerden 16 MB cep belleğe (cache) sahip son teknoloji Xeon'lara kadar geniş bir yelpazede yer alıyor. Üstelik düşük bütçeli araştırma merkezleri bile ikinci el bilgisayarlarla Beowulf kümeleri kurabiliyorlar. Son olarak bu konuda nerd'lüğün en uç noktası Flash Mob Computing geliyor. Büyükçe bir merkezde bir araya gelen ve bilgisayarlarını getiren katılımcılar dağıtılan bir linux CD'siyle bilgisayarlarını açıyorlar. Dağıtımda, gerekli istemci programlar kurulu geliyor. Katılım sağlandıktan sonra bütün bilgisayarların işlem gücü ana makinada toplanıyor. Gerekli hesaplama yapılıp bittikten yada akşam olduktan sonra herkes bilgisayarını alıp tekrar evine dönüyor.

MPI (Message Passing Interface) bilgisayar kümelerinde artık standart hale gelmiş bir arayüz. MPI, dağıtık bilgisayarlarda basit bir programlama arayüzüyle TCP/IP yada sunucu/istemci kodlarıyla uğraşmadan belli sayıda bilgisayarda çalışarak işleri paralel olarak çalıştırmaya olanak veriyor. Kütüphanenin mantığı oldukça basit: Bütün işler aynı anda programı çalıştıran kişinin belirttiği sayıda spawn ediliyor. Aslında bütün makinalarda çalışan kod birbirinin aynı. MPI dilinde bu makinalara artık "işlemci" (processor) deniyor. Her işlemcinin kendine ait bir numarası bulunuyor. Makinaların birbirinden farklı davranması bu numaraya göre sağlanabiliyor. Aynı zamanda toplam kullanılabilen makina sayısı da alınabiliyor.

Örneğin MPI ile 8 işlemci kullanılarak [a, b] aralığında integral alınacak olsun. Bu durumda işlemci sayısı n olmak üzere her bir işlemciye t = (b - a) / n kadarlık bir aralık düşecektir. Her işlemcinin numarası p olursa, işlemciler (a + p * t)'den (a + (p + 1) * t)'ye kadar olan bölümü integral alacaklar demektir. İntegral alma işleminde parçalar birbirine bağlı olmadığından işlemciler arası herhangi bir haberleşme olmadan birbirlerinden bağımsız hesaplamayı tamamlayabilirler. Hesaplama bittiğinde her işlemcinin bulduğu sonuç bir bilgisayara gönderilir ve orada toplanır. İntegralin sonucu, bulunan bu toplamdır. Bu örnekte .rar şifresini bulurken de herhangi bir veri bağımlılığı bulunmadığından veri bağımlılığı bulunan karmaşık örneklerden kaçınmaya çalıştım.

Arşivin şifresini bulmak için sözlük tabanlı deneme yapan başka programlar da piyasada kolayca bulunabilir. (Mesela RAR Password Cracker) Bunun yanında MPI tabanlı MD5 reverse hash algoritması yada Paralel John the Ripper bulabilmek de mümkün. Ancak MPI tabanlı RAR çözücü ben rastlamadım, bu nedenle yazdığım bu programın piyasada ilk olduğunu iddia edebilirim.

Elbette ki bütün MPI kütüphanesini burada anlatmam mantıklı olmayacağından ben sadece programda kullandığım fonksiyonları anlatacağım.

int MPI_Init( int *argc, char ***argv ): Bu fonksiyonla bütün işlemciler paralel işlem yapmaya hazırlanır, başka bir deyişle işlemcilere hazır olmalarını, diğer MPI fonksiyonlarının çağırılacağını bildirir. Fonksiyonun argümanları main(int argc, char *argv[]) fonksiyonunun argümanlarıyla aynıdır (gösterici olmaları dışında). Hemen her MPI programı ilk olarak bu fonksiyonu çağırmak zorundadır.


int MPI_Comm_size( MPI_Comm comm, int *size ): MPI_Init çağırıldığında bir haberleşme dünyası oluşturulur. Haberleşme dünyası tüm işlemcileri kapsayan bir üst küme olarak düşünülebilir.
http://nf.nci.org.au/training/MPIProg/slides/slides.028.html

MPI_Init çağırılır çağırılmaz oluşturulan default haberleşme dünyasının handleMPI_Comm türünde bir sabit olan MPI_COMM_WORLD'dür ve bu haberleşme dünyası bütün işlemcileri içerir. Daha sonra istenirse bunun alt kümesi olan yeni haberleşme dünyaları da oluşturulabilir. MPI_Comm_size fonksiyonu verilen comm haberleşme dünyasının içerdiği işlemci sayısını size adı verilen değişkene yazar. Yandaki resimde fonksiyon size değişkeninde 7 değerini döndürecektir. Bu fonksiyonun aynı haberleşme dünyası içerisindeki bütün işlemciler için aynı değeri döndüreceği açıktır.


int MPI_Comm_rank( MPI_Comm comm, int *rank ): Bu fonksiyon comm ile belirtilen haberleşme dünyasında her işlemciye özgü olan sıra numarasını rank değişkeninde döndürür. Bu fonksiyonun aynı haberleşme dünyası içerisinde bütün işlemciler için farklı değeri döndüreceği açıktır.


int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm): MPI_Send fonksiyonu işlemcilerin kendi arasında haberleşmeyi sağlayabilmeleri için gerekli en basit fonksiyondur. buf ile belirtilen bellek bölgesinden başlayarak, count tane MPI_Datatype türündeki datatype'ı, dest ile belirtilen işlemciye tag etiketiyle comm haberleşme dünyası içerisinde yollar.

İfade biraz açılacak olursa; buf önceden bellekte ayrılmış herhangi bir değer yada dizi olabilir. count bu dizinin büyüklüğüdür. MPI'da C'deki veri tiplerine karşılık gelen veri tipleri MPI_Datatype türünde kodlanmıştır. datatype değişkeni MPI_INT, MPI_DOUBLE, MPI_CHAR vb. yada bunlardan türetilmiş bir veri türü olabilir. Bu türün büyüklüğü count ile çarpılarak toplamda kaç byte veri gönderileceği hesaplanır. Örneğin count = 16 ve MPI_INT'in büyüklüğü 4 byte ise toplamda 64 byte veri gönderilecektir. MPI'ın derlendiği makinanın mimarisine ve derleme parametrelerine bağlı olarak MPI_INT'in büyüklüğü değişebilir.

dest haberleşme dünyası içerisindeki herhangi bir işlemci numarasıdır. Sıfırdan MPI_Comm_size'ın döndürdüğü size değişkeninin bir eksiğine kadar herhangi bir değer olabilir. Bu değerden daha büyük yada sıfırdan küçük değerler programın yanlış çalışmasına ve çökmesine yol açabilir. Burada bir açıklama daha gerekiyor. MPI'ın bir standardı ve bu standartlara göre üreticiler tarafından yazılmış uyarlamaları (implementation) bulunmaktadır. Standartlar konunun ana hatlarını tamamlasa da bazı noktaları bilerek (örneğin esneklik açısından) yada bilmeyerek boş bırakmış olabilir. Bu boşluklardan biri kendine veri göndermeye çalışan program hakkındadır. MPI'ın Intel uyarlaması buna kesinlikle izin vermez ve program kendi kendine veri göndermeye kalkıştığında çöker. OpenMPI uyarlaması ise sorunsuz çalışır ve program kendi kendine veri gönderip alabilir. (En son hatırladığım bu şekildeydi. Sonradan uyarlamalar yada standartlar değişmiş olabilir.)

tag gönderilen mesajlara etiket vermeye yarayan bir sayıdır ve kaç olduğunun bir önemi yoktur sadece gönderme ve almada (MPI_Recv) aynı sayı olmalıdır. Karmaşık ve ardarda gönderilen birden fazla mesaj bulunduğu durumlarda işleri oldukça kolaylaştırır. Ve son olarak dest ile bildirilen işlemcinin hangi haberleşme dünyasına ait olduğunu bilebilmek için comm değişkeni haberleşme dünyasını tutar.


int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status): MPI_Send ile gönderilen veri bir başka işlemci tarafından MPI_Recv çağırılarak belleğe alınır. Bu fonksiyonda benzer biçimde buf ile belirtilen adrese count tane datatype türünde değişken source numaralı işlemciden tag etiketiyle comm haberleşme dünyası içerisinde okunur. MPI_Send'den tek farkı burada MPI_Status türünde bir durum döndürülür ancak genellikle bu değer MPI_STATUS_IGNORE değeriyle görmezden gelinir.

buf adresi MPI_Recv çağırılmadan önce bellekte ayrılmış olmalıdır. datatype, MPI_Send'in veri türüyle uyumlu olmak zorunda değilse de bunlar her zaman birbirinin aynı verilir. source yine gönderici işlemcinin sıra numarasıdır. Sıra numarasının bilinmediği yada fark etmediği durumlarda MPI_ANY_SOURCE kullanılabilir. Yine benzer şekilde etiket numaraları birbirini mutlaka tutmak zorundadır ancak etiket numarasının önemsenmediği durumlarda MPI_ANY_TAG kullanılabilir.


int MPI_Bcast( void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm ): MPI_Bcast fonksiyonu comm haberleşme dünyasında root numaralı işlemcinin buffer adresindeki count tane datatype türündeki veriyi diğer işlemcilere de kopyalar. Fonksiyon çağırılmadan önce bütün işlemciler buffer bellek adresini bellekte ayırmış olmalıdırlar.

http://www.mathcs.emory.edu/~cheung/Courses/355/Syllabus/92-MPI/group-comm.html

Peki bir MPI_Bcast çağrısının, 0'dan (size - 1)'e kadar olan bir for döngüsü içerisindeki MPI_Send'den farkı nedir? Yapılan iş aynı olmakla birlikte nasıl yapıldığı farklıdır. MPI_Send yaklaşımında haberleşme dünyasındaki işlemci sayısı kadar MPI_Send çağrısı gerçekleşir. Öte yandan MPI_Bcast'in çalışma prensibi şöyledir: Haberleşme dünyasında sekiz işlemci olduğunu ve root'u 0. işlemci olan bir MPI_Bcast çağrısı yapıldığını varsayalım. İlk adımda 0. işlemci buffer'ının tamamını 4. işlemciye gönderir. İkinci adımda 0. ve 4. işlemciler buffer'larının tamamını sırasıyla 2. ve 6. işlemcilere gönderirler. Son adımdaysa 0., 2., 4. ve 6. işlemciler buffer'larının tamamını sırayla 1., 3., 5. ve 7. işlemcilere yolladıkları zaman işlem üç adımda tamamlanır. Yani işlemci sayısı p olmak üzere MPI_Send ile p adımda yaptığımız işlemi MPI_Bcast bize log2(p) adımda tamamlamaya olanak sağlar. p sayısının en az 1 olacağını düşünürsek her durumda sayının logaritması kendisinden küçüktür. 

MPI_Bcast kullanırken dikkat edilmesi gereken bütün işlemcilerin MPI_Bcast fonksiyonunu çağırma zorunluluğudur. Yani fonksiyon, rank değişkeni işlemci numarasını göstermek üzere if(rank == 3) yada if(rank % 2) gibi bir ifade içerisinde çağırılamaz. Bunun yerine ikinci ifade için tek ve çift sayılı işlemcilerden oluşan yeni bir haberleşme dünyası tanımlanmalıdır.


int MPI_Abort(MPI_Comm comm, int errorcode): MPI_Abort çağrısı bir işlemcinin hatayla karşılaşması durumunda bütün haberleşme dünyasını sonlandırmak ve programdan çıkmak için kullanılır.


int MPI_Finalize( void ): Bu fonksiyon diğer işlemcileri öldürür. Genellikle main()'den çıkılmadan hemen önce kullanılır ve bütün MPI kodları bu fonksiyonla bitmek zorundadır. Bu fonksiyondan sonra yapılacak herhangi bir MPI fonksiyon çağrısı hataya sebep olur.


Son olarak MPI kurmak için bir hesaplama kümesi sahibi olmaya gerek yoktur. Herkes makinasına MPI kurabilir. Makinaların dağıtık olmasına gerek olmaksızın MPI tek bir makinadaki işlemcileri ve çekirdekleri ayrı işlemciler olarak etkin biçimde kullanabilir. MPI ile yazılmış kodları derlemek için, MPI kurulurken icc yada cc için kendi wrapper derleyicisini mpiicc yada mpicc adında kurar. mpicc kullanırken -L, -I gibi parametreleri ayrıca vermeye gerek kalmaz. MPI kodu mpi derleyicisiyle derlendikten sonra mpirun yada mpiexec komutlarıyla çalıştırılır. Örneğin mpirun -np 4 ./deneme.x biçiminde bir komut deneme.x çalıştırılabilir dosyasını 4 işlemcide çalıştırır. Çalıştırılan makinada 4 işlemci olmasa bile mpirun 4 işlemci varmış gibi çalışıp çıktı üretecektir. Ancak dört çekirdekli bir makinada programın 4 işlemciyle çalışma süresi 2 işlemciyle çalışma süresinin yarısı olacakken tek çekirdekli bir makinada herhangi bir fark görülmez hatta 4 işlemciyle daha uzun sürede çalışacaktır. MPI ile ilgili kod örneklerine burada değinmeyeceğim ancak internette bunlarla ilgili bir sürü örnek bulmak olası. Bir sonraki bölümde yayınlayacağım kod ve açıklamaları zaten bu fonksiyonlara ve bir önceki bölümde anlattığım fonksiyonlara bir örnek olacaktır.

Hiç yorum yok:

Yorum Gönder