Yüksek boyutlu model gösterilimi ile veri bölüntüleme yönteminin koşutlaştırılması
Data partitioning via high dimensional model representation by using paralel computing
Yazar: MEHMET ENGİN KANAL
Danışman: PROF. DR. METİN DEMİRALP
İstanbul Teknik Üniversitesi / Bilişim Enstitüsü / Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
Derece: Doktora, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Yalnızca uzaydaki belli noktalardaki de˘gerleri verilmi¸s çok de˘gi¸skenli bir
f (x1;x2;    ;xN) i¸slevine alı¸sılagelmi¸s yöntemlerle içde˘gerbiçim i¸slemi yapılması
boyut sayısı arttı˘gında birer ba¸sbelası durumuna gelir. Bu tür i¸slevler için do˘grudan
bilgisayar programcılı˘gı ile çözüm aramak yerine ilk olarak bu i¸slevleri bilgisayar
programlaması açısından daha kolay ele alınacak, matematiksel olarak, etkili bir yapıya
getirmek gerekir. Bu amaçla bu i¸sleve yakla¸stırım yapan bir böl–ve–yönet algoritması
geli¸stirilmi¸stir. Bu yakla¸stırım sayesinde çok de˘gi¸skenli f i¸slevi çok daha dü¸sük
boyutlu terimlerle ifade edilebilmektedir. Bu yakla¸stırıma Yüksek Boyutlu Model
Gösterilimi (YBMG) adı verilmektedir. Bu yöntem çe¸sitli çalı¸smalarla ba¸sarılı bir
¸sekilde uygulanmı¸stır. Fakat bu yöntem bu haliyle büyük veri hacmine sahip problemler
üzerinde uygulanamaz. Problemdeki boyut sayısı ve boyutlardaki dü˘güm noktaları
sayıları arttı˘gında veri hacmi öyle büyür ki alı¸sılagelmi¸s PC'ler verinin gereksinim
duydu˘gu yüksek RAM sı˘gasını kar¸sılayamaz. Di˘ger bir önemli problem de YBMG
terimlerini hesaplamakta kullanılan e¸sitliklerin yapılarıdır. E¸sitlikler için yazılmı¸s
algoritmadaki döngü sayıları problemdeki boyut sayısına ba˘gımlıdır. Bu çalı¸smada
ilk olarak YBMG terimlerini hesaplamakta kullanılan e¸sitlikler iyile¸stirilmi¸stir. Bu
iyile¸stirme sonucunda e¸sitliklerin problemdeki boyut sayısına ba˘gımlılı˘gı ortadan
kaldırılmı¸stır. ˙Iyile¸stirilmi¸s e¸sitlikler sayesinde yöntem ko¸sutla¸stırmaya uygun
bir hale getirilmi¸stir. Çalı¸smada ko¸sutla¸stırma için MPI ve CUDA kütüphaneleri
kullanılmı¸stır. Ko¸sutla¸stırma için iyile¸stirilen e¸sitlikler sayesinde MPI kullanarak
yapılan ko¸sutla¸stırmada istemciler arasında neredeyse haberle¸smesiz ko¸sutla¸stırma
(ing: embarrassingly parallel) elde edilmi¸stir. Bu sayede yüksek ba¸sarım elde edilmi¸stir.
CUDA ile yapılan ko¸sutla¸stırma ile de CPU ba¸sarımına göre daha yüksek bir GPU
ba¸sarımı elde edilmi¸stir. CUDA ile ko¸sutla¸stırma çalı¸smasında CUDAReduction'a
alternatif olacak ve daha çe¸sitli problemlere çözüm getirecek algoritmalar elde
edilmi¸stir.

Abstract:
If the values of a multivariate function f (x1;x2;    ;xN) are given at only a finite number
of points in the space of its arguments and an interpolation which employs continuous
functions is considered standard multivariate routines may become cumbersome as
the dimensionality grows. This urges us to develop a divide–and–conquer algorithm
which approximates the function. The given multivariate data is partitioned into
low-variate data. This approach is called High Dimensional Model Representation
(HDMR). However the method in its current form is not applicable to problems having
huge volumes of data. With the increasing dimension number and the number of the
corresponding nodes, the volume of data in question reaches such a high level that it is
beyond the capacity of any individual PC because huge volume of data requires much
higher RAM capacity. Another aspect is that the structure of equalities used in the
calculation of HDMR terms varies according to the dimension number of the problem.
The number of loops in the algorithm increases with the increasing dimension number.
In this work, as a first step, the equations used are modified in such a way that their
structure does not depend on the dimension number. With the newly obtained equalities,
the method becomes appropriate for parallelization. Due to the parallelization, the
RAM problem arising from problems with high volume of data is solved. Finally, the
performance of the parallelized method is analyzed.