Algorithmic optimization and parallelization of Eppstein's synchronizing heuristic
Eppsteın'ın sıfırlama sezgiselinin algoritmik eniyilemesi ve paralelleştirilmesi
- Tez No: 507383
- Danışmanlar: DOÇ. DR. HÜSNÜ YENİGÜN, DR. ÖĞR. ÜYESİ KAMER KAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 52
Özet
Karmaşık sistemlerin geliştirilmesinde, test etme en pahalı ve en çok zaman alan evredir. Model tabanlı testler yüksek kaliteli deney kurgusunu otomatik üretmede kullanılan yaklaşımlardan birisidir. Deney kurgusunu otomatik üretme test etmenin en zorlu parçalarından biridir. Sonlu durum makineleri ya da özdevinimler gibi biçimsel modeller, otomatik deney grubunu üretmek için kullanılmaktadır. Sistem belirli bir duruma senkronize edildikten sonra testler uygulanır ve bu belirli duruma gelebilmek için sıfırlama kelimeleri kullanılmaktadır. Daha kısa deney süreleri için en kısa sıfırlama kelimesini hesaplamak önemlidir, ancak en kısa sıfırlama kelimesini hesaplamak NP– hard bir problemdir. Bu nedenle kısa sıfırlama kelimelerini hesaplamak için sezgisel yöntemler kullanılmaktadır. GREEDY algoritması bu alanda bilinen en hızlı sezgisel algoritmadır. Bu tezde, GREEDY algoritmasını hızlandıran yaklaşımlar sunulmaktadır. İlk olarak GREEDY algoritmasının paralelleştirilmesine odaklanılmaktadır. İkinci olarak ise tembel bir yaklaşım önererek sıfırlama kelimesinin üretilmesi için gerekli bilgilerin hazırlanma süreci ertelenmektedir. Aynı zamanda, GREEDY algoritması için benzer algoritmik iyileştirilmeler önerilmektedir. Deney sonuçlarımız özdevinim büyüklügüne bağlı olarak GREEDY algoritmasının 500 kat daha hızlı hale getirilebileceğini göstermektedir. Önerilen geliştirmeler özdevinim büyüklügü arttıkça daha etkili hale gelmektedir.
Özet (Çeviri)
Testing is the most expensive and time consuming phase in the development of complex systems. Model–based testing is an approach that can be used to automate the generation of high quality test suites, which is the most challenging part of testing. Formal models, such as finite state machines or automata, have been used as specifications from which the test suites can be automatically generated. The tests are applied after the system is synchronized to a particular state, which can be accomplished by using a synchronizing word. Computing a shortest synchronizing word is of interest for practical purposes, e.g. for a shorter testing time. However, computing a shortest synchronizing word is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. GREEDY is one of the fastest synchronizing heuristics currently known. In this thesis, we present approaches to accelerate GREEDY algorithm. Firstly, we focus on parallelization of GREEDY. Second, we propose a lazy execution of the preprocessing phase of the algorithm, by postponing the preparation of the required information until it is to be used in the reset word generation phase. We suggest other algorithmic enhancements as well for the implementation of the heuristics. Our experimental results show that depending on the automata size, GREEDY can be made 500⇥ faster. The suggested improvements become more effective as the size of the automaton increases.
Benzer Tezler
- Data distribution and performance optimization models for parallel data mining
Koşut veri madenciliği için veri dağıtımı ve başarım optimizasyon modelleri
ERAY ÖZKURAL
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Gene set-based classification models for cancer biology
Kanser biyolojisi için gen kümesi tabanlı sınıflandırma modelleri
AREZOU RAHIMI
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
DOÇ. DR. MEHMET GÖNEN
- Parçacık sürü ve karınca koloni optimizasyon algoritmalarının aç gözlü bilgi takası stratejisi kullanılarak paralelleştirilmesi
Parallelization of the particle swarm and ant colony optimization algorithms by using the greedy information swap strategy
ŞABAN GÜLCÜ
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALİFE KODAZ
- Yusufçuk optimizasyon algoritmasının dağıtık ve paylaşımlı bellek mimarileri üzerinde paralelizasyonu
Parallelization of Dragonfly optimization algorithm on distributed and shared memory architects
RAMAZAN POLAT
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMersin ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ AKDAĞLI
- Effective and efficient parallelization of string matching algorithms using GPGPU accelerators
Dizgi eşleme algoritmalarırnın GPGPU hızlandırıcıları kullanılarak etkili ve verimli hızlandırılması
MENGÜ NAZLI
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ADNAN ÖZSOY