University of Twente Student Theses
Accelerating mixed-level coverage array generation
Veenstra, A. (2021) Accelerating mixed-level coverage array generation.
|
PDF
999kB |
| 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: | https://purl.utwente.nl/essays/88437 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page