Supercomputing and grid computing on the verification of covering arrays

The final publication is available at Springer via http://dx.doi.org/10.1007/s11227-012-0763-0The 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 Nxk matrix over an alphabet v s.t. each Nxk 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.The authors thankfully acknowledge the computer resources and assistance provided by Spanish Supercomputing Network (TIRANT-UV). This research work was partially funded by the following projects: CONACyT 58554, Calculo de Covering Arrays; 51623 Fondo Mixto CONACyT y Gobierno del Estado de Tamaulipas.Avila George, H.; Torres Jimenez, J.; Rangel Valdez, N.; Carrión Collado, AA.; Hernández García, V. (2012). Supercomputing and grid computing on the verification of covering arrays. Journal of Supercomputing. 62(2):916-945. doi:10.1007/s11227-012-0763-0S91694562