Grammatical genetic programming on heterogeneous computing platforms
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, BİLGİSAYAR MÜHENDİSLİĞİ ANABİLİM DALI, Türkiye
Tezin Onay Tarihi: 2017
Tezin Dili: Türkçe
Öğrenci: HAKAN AYRAL
Danışman: Songül Varlı
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet: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.