|
Genetik programlama nüfus tabanlı, stokastik bir küresel optimizasyon algoritması olup, test-vakaları şeklinde temsil edilmiş davranış spesifikasyonlarını gerçekleyen "programlar" bulmayı amaçlamaktadır. Programlar, değişkenler ve sabitler kullanan bir aritmetik ifade kadar basit olabilir, veya durum değişkenleri, döngüler ve koşullar içeren tam bir fonksiyon kadar karmaşık olabilir. Gramer yönlendirmeli genetik programlama, genetik programlamanın gramer temelli bir alt türüdür; burada arama uzayı ve arama metodolojisi, arama uzayını formel bir gramer tarafından tanımlanan dilin üyeleri ile sınırlandıracak şekildedir. Bu yaklaşım, arama uzayının küçültülmesini ve tüm adayların, yazımsal (syntactic) açıdan geçerli bir sözdizimsel biçimine sahip olmasını sağlar. Kullanılan formel gramer cevabı evrimleştirilmek istenen soruya özel olarak tasarlanır, ancak aranan cevabın şeklinin yeterince bilinmediği problemlerde daha genel bir gramer kullanılabilir; bu durumla benzetim, sınıflandırma, yol bulma ve ikilik fonksiyonlar gibi kategorik problemlerin aksine daha çok genel amaçlı program sentezi ile ilgili problemlerde karşılaşılır.
Konvansiyonel hesap platformları, her çekirdeğin diğerleriyle aynı olduğu, çok çekirdekli ve çok işlemcili bilgisayarlar gibi homojen bir hesap donanımına dayanır. Öte yandan, heterojen bir hesap platformu, her biri kendi mimarisi ve avantajlarıyla birlikte birden çok hesaplama elemanı kullanır. Bunun en yaygın örneği CPU'ların her biri derin bir pipeline mimarisi ve büyük cache'lere sahip yüksek karmaşıklık ve yüksek saat hızlarında çalışan çekirdekleri ile, GPU'nun çok sayıda (binler mertebesinde) ama daha düşük saat hızında ve daha basit, sadece sınırlı miktarda ALU ve register içeren, kontrol ünitesi ve önbelleği 32'li gruplar halinde paylaşmak zorunda olduğu çekirdeklerin bir arada kullanılmasıdır.
Bu tezin temel amacı, bahsedilen tür heterojen hesap platformlarında paralelleştirme yoluyla gramer genetik programlamanın hızlandırılması için yeni yöntemler araştırmak ve önermektir.
Bu tez çalışmasında öncelikle genetik programlama için benchmark uygulamalarında yakın zamanda yaşanan bir kaymaya genel bir bakış sunuyoruz, ve genel amaçlı program sentezi sınıfında yeni bir benchmark problemi öneriyoruz. Ardından, gramer genetik programlama için paralelleştirme tasarımını etkileyen bazı evrimsel parametrelerin bağımlılıklarını ve etkileşimlerini değerlendiriyoruz. Daha sonra, genetik programlama bireylerinin GPU için derlenmesini önce işleç içine çeken ve ardından bunu da paralelleştirmeye dayanan yeni bir yöntem sunuyoruz. Sunduğumuz bu yöntemin literatürdeki önceki çalışmalara kıyasla bir mertebe daha yüksek derleme hızları sağladığı görülmektedir. Son olarak önceden sabitlenmemiş bir gramer ile gramer tabanlı genetik programlama gerçekleştirebilmek ve bu sayede genel amaçlı program sentezi problemlerinde GPU'yu daha verimli kullanabilmek için, GPU üstünde çalışan genel amaçlı bir yorumlayıcı sunuyoruz; bu, literatürde GPU üstünde gramer tabanlı evrim için yorumlama yöntemini önceden sabitlenmemiş herhangi bir gramer ile kullanabilen ilk çalışma olma özelliğini taşımaktadır.
|
|
Genetic programming is a population based, stochastic global optimization algorithm which aims to find "programs" fulfilling certain behavioral specifications provided as test cases. The programs may be as simple as arithmetic expressions on some variables or complex as a complete function involving state variables, loops and conditionals. Grammatical genetic programming (a.k.a. grammatical evolution) is a grammar based variant of genetic programming where the search space and methodology is modified to limit the search space to members of a language defined by a formal grammar. This approach provides the benefit of having a smaller search space, and of all the candidates having a valid syntactic form in respect to defined grammar. Grammars used are generally customized to the program at hand, but they can be more generic when the form of the solution is not obvious, which usually is the case with general program synthesis, in contrast to categorical problems like regression, classification, path finding and boolean problems.
Conventional computing platforms consist of homogeneous processor hardware, like the case of a computer with multi-core multi-processor setup, where each core is identical to others. On the other hand a heterogeneous computing platform simultaneously uses multiple types of processing elements each with their own unique architecture and strengths. The most prevalent example today is the combined use of CPU and GPU, where CPU provides high frequency, high complexity processing cores with deep pipelining and large local cache per core, while the GPU provides vast numbers (in the order of thousands) of simpler cores with lower frequency each consisting of some ALU and register file for state keeping, but missing per core cache or control units, which have to be shared by groups of 32 cores.
The aim of this dissertation is to investigate and propose new methods to accelerate grammatical genetic programming by parallelization on mentioned types of computing platforms.
In this dissertation we first present an overview of a recent shift in benchmarking practices for genetic programming and propose a new benchmark problem targeting general program synthesis. Then we investigate the interaction of some evolutionary parameters which ultimately affect the parallelization design for grammatical genetic programming. Afterwards we present a new technique which first brings the GPU compilation of individuals in-process, then further parallelizes this compilation. The method we present achieves an order of magnitude faster compilation speed over prior work on literature. Lastly we present a GPU based interpreter for grammatical genetic programming with arbitrary grammars in order to target general program synthesis; this is the first work in literature to present grammatical evolution on GPU with a general purpose interpreter to accommodate arbitrary grammars. |
