Supercomputing and grid computing on the verification of covering arrays

Autores UPV
Revista Journal of Supercomputing


The Covering Arrays (CAs) are mathematical objects with minimal coverage and maximum cardinality that are a good tool for the design of experiments. A covering array is an N¿k matrix over an alphabet v s.t. each N¿k subset contains at least one time each combination from {0,1,¿,v-1} t, given a positive integer value t. The process of ensuring that a CA contains each of the v t combinations is called verification of CA. In this paper, we present an algorithm for CA verification and its implementation details in three different computation paradigms: (a) sequential approach (SA); (b) parallel approach (PA); and (c) Grid approach (GA). Four different PAs were compared in their performance of verifying a matrix as a CA; the PA with the best performance was included in a different experimentation where the three paradigms, SA, PA, and GA were compared in a benchmark composed by 45 possible CA instances. The results showed the limitations of the different paradigms when solving the verification of CA problem, and points out the necessity of a Grid approach to solve the problem when the size of a CA grows. © 2012 Springer Science+Business Media, LLC.