University of Twente Student Theses


Accelerating mixed-level coverage array generation

Veenstra, A. (2021) Accelerating mixed-level coverage array generation.

[img] PDF
Abstract:The computation of optimum Mixed-level Covering Arrays (MCAs) has various competing algorithms approaching the optimal solution. The IPOG algorithm is a widely used variant and generally produces a small result in a short amount of time. However, generating MCAs of complex SUTs takes a long time, even when using IPOG. In this report we explain how we accelerate the IPOG algorithm. We employed various techniques to obtain this acceleration, and created prototypes using each technique to evaluate its efficiency. We add an additional representation of the MCA to efficiently detect don’t-cares using bitwise operations, which provides a geometric mean speedup of 1.52 on unconstrained SUTs. We divide the work performed by IPOG using multithreading, resulting in a geometric mean speedup of 1.46 for unconstrained SUTs, and 1.18 for constrained SUTs. As an alternative, we create a partial implementation of IPOG using GPGPU. From the results so far, we can conclude that acceleration of the IPOG algorithm can potentially be obtained by creating a GPGPU version of the algorithm. We also discuss the various data structures used, and provide an argumentation as to why said structure was used.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page