Geri Dön

GPU-based parallel computing methods for constructing covering arrays

GPU tabanlı paralel hesaplama yontemleri ile kapsayan diziler oluşturma

PDF İndir

  1. Tez No: 418628
  2. Yazar: HANEFİ MERCAN
  3. Danışmanlar: YRD. DOÇ. DR. CEMAL YILMAZ, YRD. DOÇ. DR. KAMER KAYA
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 104

Özet

Yazılım sistemleri daha karmaşık hale geldikçe, bu tip sistemleri düşük maliyetli test etmek için etkili tekniklere olan talep de artmaktadır. Bunlara örnek olarak web sunucuları (Apache vb.) ve veritabanları (MsSQL vb.) gibi yapılandırılabilirliği yüksek yazılım sistemleri verilebilir. Bu sistemler birbiriyle etkileşim içinde olan birçok yapılandırabilir parametrelere sahiptir ve bu etkileşimler üstel büyüme hızıyla parametre konfigürasyonla- rının sayısının artmasına yol açar. Bundan dolayı, bu tip yazılım sistemleri parametrelerin etkileşimlerinden dolayı oluşabilecek hatalara karşı daha çok eğilimlidir. Bu soruna bir çözüm olarak konfigürasyon uzayını sistematik şekilde kümeleyip ve bu kümeleri ayrı ayrı test eden kombinatoryal etkileşim testi (combinatorial interaction testing) verilebilir. Kombinatoryal etkileşim testi, az sayıda parametre konfigürasyonları içeren test senaryoları olarak kullanılması için kapsayan diziler adı verilen objeleri üretir. Bir \textit{t-yollu kapsayan dizisi} (t-way covering array) test edilecek sistemin bütün t-yollu parametrelerinin değer kombinasyonlarını en küçük sayıda konfigürasyon kullanarak kapsamayı hedefler. Yapılan birçok araştırmanın kayda değer çoklukta hataların küçük sayıda parametre etkileşimlerinden kaynaklandı{g}ını göstermesinin ardından, kapsayan dizinin uygulamalarına özellikle teşvik edilmiştir. Yine de, özellikle de konfigürasyon uzayı büyük olduğunda ve sistem içinde parametreler arasında bazı konfigürasyonları geçersiz kılan kısıtlamalar olduğunda, minimum sayıda konfigürasyon içeren kapsayan diziler oluşturmak kolay bir iş değildir. Bundan ötürü, bu çalışma alanı farklı alandan birçok araştırmacıların ilgisini çekmektedir. çoğu çalışma ölçeklendirme konusunda sorun yaşamasına rağmen, kapsayan dizi oluşturma konusunda bazı başarılı çalışmalarda yapılmıştır. Fakat, konfigürasyon uzayı büyüdükçe, çoğu yaklaşım zorlanmaya başlar. Kombinatorik problemler, bizim durumda kapsayan dizi oluşturmak, çoğunlukla etkili sayma teknikleri kullanılarak çözülür. Bu varsayımı baz alarak, sayma problemlerinin kolay bir iş olmasından ve paralel programlama teknikleri kullanılarak verimli bir şekilde çözülebileceğinden dolayı, kapsayan dizilerin paralel algoritmalar kullanılarak etkili bir şekilde oluşturulabileceğine dair öngörüde bulunuyoruz. Farklı mimariler farklı araştır- ma alanlarında daha etkili olabileceğinden dolayı, biz GPU tabanlı paralel programlama teknikleri kullanmaya karar verdik. çünkü GPU'ların aritmetik hesaplama birimleri küçük olmasına karşın, yüzlerce çekirdekleri, hatta bazen binlerce çekirdekleri olabilir. Bu çekirdeklerin kapasiteleri kısıtlı ve sınırlı olmalarına rağmen, bizim tek yapmak istedi- ğimiz defalarca basit sayma işlemleri olduğu için bizim çalışmamızda amacımıza çok iyi hizmet ederler. Bu fikrimizi hesaplama zamanını azaltmak için daha önce birçok defa kapsayan dizi oluşturmada kullanılmış ve çoğu zaman en küçük boyutlarda sonuçlar vermiş olan benzetilmiş tavlama algoritması (simulated annealing) üzerinde uyguladık. Bunlara ek olarak, benzetilmiş tavlama algoritmasının her adımında paralel olarak çoklu sayıda komşu durumları üretebilen bir teknik geliştirdik. Son olarak da, uzayı tamamen rastgele aramanın kötü etkisini düşürmek ve kapsayan dizilerin boyutunu daha da azaltmak için SAT (SATisfiability) algoritması ve paralel programlama teknikleri kullanarak melez bir yaklaşım öne sürdük.

Özet (Çeviri)

As software systems becomes more complex, demand for efficient approaches to test these kind of systems with a lower cost is increased highly, too. One example of such applications can be given highly configurable software systems such as web servers (e.g. Apache) and databases (e.g. MySQL). They have many configurable options which interact each other and these option interactions lead having exponential growth of option configurations. Hence, these software systems become more prone to bugs which are caused by the interaction of options. A solution to this problem can be combinatorial interaction testing which systematically samples the configuration space and tests each of these samples, individually. Combinatorial interaction testing computes a small set of option configurations to be used as test suites, called covering arrays. A \textit{t-way covering array} aims to cover all t-length option interactions of system under test with a minimum number of configurations where t is a small number in practical cases. Applications of covering arrays are especially encouraged after many researches empirically pointed out that substantial number of faults are caused by smaller value of option interaction. Nevertheless, computing covering arrays with a minimal number of configurations in a reasonable time is not easy task, especially when the configuration space is large and system has inter-option constraints that invalidate some configurations. Therefore, this study field attracts various researchers. Although most of approaches suffer in scalability issue, many successful attempts have been also done to construct covering arrays. However, as the configuration scape gets larger, most of the approaches start to suffer. Combinatorial problems e.g., in our case constructing covering arrays, are mainly solved by using efficient counting techniques. Based on this assumption, we conjecture that covering arrays can be computed using parallel algorithms efficiently since counting is an easy task which can be carried out with parallel programming strategies. Although different architectures are effective in different researches, we choose to use GPU-based parallel computing techniques since GPUs have hundreds even sometimes thousands of cores however with small arithmetic logic units. Despite the fact that these cores are exceptionally constrained and limited, they serve our purpose very well since all we need to do is basic counting, repeatedly. We apply this idea in order to decrease the computation time on a meta-heuristic, search method simulated annealing, which is well studied in construction of covering arrays and, in general, gives the smallest size results in previous studies. Moreover, we present a technique to generate multiple neighbour states in each step of simulated annealing in parallel. Finally, we propose a novel hybrid approach using SAT solver with parallel computing techniques to decrease the negative effect of pure random search and decrease the covering array size further. Our results prove our assumption that parallel computing is an effective and efficient way to compute combinatorial objects.

Benzer Tezler

  1. Tez No

    383363

    Hybrid meta-heuristic algorithms for the resource constrained multi-project scheduling problem

    Kaynak kısıtlı birden fazla projenin iş programlanması problemi için üst-sezgisel yöntemler geliştirilmesi

    FURKAN UYSAL

    Doktora

    İngilizce

    İngilizce

    2014

    İnşaat MühendisliğiOrta Doğu Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. RİFAT SÖNMEZ

  2. Tez No

    608098

    Çelik çerçeve sistemlerin GPU tabanlı optimizasyonu

    GPU based optimization of steel frame structure

    TEVFİK OĞUZ ÖRMECİOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Mühendislik BilimleriAkdeniz Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İBRAHİM AYDOĞDU

  3. Tez No

    652928

    Identification of tea plantation areas using Google cloud based random forest and deep learning

    Google bulut servise dayalı rastgele orman ve derin öğrenme ile çay tarım alanlarının belirlenmesi

    BERKAY ÖZEN

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Geomatik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ESRA ERTEN

  4. Tez No

    885474

    Investigating conjugate heat transfer in a square cylinder via Lattice boltzmann method

    Lattice boltzmann yaklaşımıyla kare silindirde birleşik ısı transferinin incelenmesi

    AANIF HUSSAIN

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Havacılık ve Uzay Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    PROF. DR. BAYRAM ÇELİK

  5. Tez No

    397130

    Çoklu otonom insansız hava araçları için paralel programlama tabanlı yol planlaması

    Parallel programming based path planning for multi autonomous unmmaned vehicles

    ÖMER ÇETİN

    Doktora

    Türkçe

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHava Harp Okulu Komutanlığı

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜRAY YILMAZ

Geri Dön