GPU-BASED PARALLEL COMPUTING METHODS FOR CONSTRUCTING COVERING ARRAYS
Hanefi Mercan
Computer Science and Engineering, MSc. Thesis, 2015
Thesis Jury
Assist. Prof. Dr. Cemal Yılmaz (Thesis Advisor),
Assist. Prof. Dr. Kamer Kaya,
Assoc. Prof. Dr. Hüsnü Yenigün,
Prof. Dr. Bülent Çatay,
Assist. Prof. Dr. Hasan Sözer
Date &Time: 03.08.2015 – 10:00
Place: FENS 2019
Keywords: Combinatorial interaction testing, covering array, simulated annealing, cuda, parallel computing, combinatorial coverage measurement
Abstract
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 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 array 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 run multiple simulated annealing algorithms 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.