Accelerating Sequence Covering Array Generation and Optimization via Differential Evaluation and Process-Level Parallelism

Sequence Covering Arrays (SCAs) are an extension of combinatorial testing configurations designed to catch ordering faults. An SCA guarantees that all ordered t-way interactions exist as subsequences within the configuration. Generating and optimizing SCAs is computationally expensive, which has hindered their use in practice. This work presents a novel acceleration framework tailored for SCA construction routines. The key idea is to apply algorithm restructuring to existing routines to achieve gains without modifying their underlying semantics. The acceleration framework utilizes differential evaluation to prevent redundant global computations, leverages fixed-size tensors to streamline coverage management, and employs process-level parallelism to allocate independent evaluations over multiple CPU cores. Across all test scenarios, the performance improvements were clearly evident. Phase 1 shows marginal gains from purely algorithmic acceleration but demonstrates a speedup of 2.58× to 3.80× end-to-end when implemented in its accelerated and parallel form. However, phase 2 shows significant improvement from algorithmic restructuring yielding 2.21× – 10.41× speedup. When accelerated and parallelized, phase 2 shows 80.65× – 259.70× speedup end-to-end across all configurations. Best case speedup observed was 259.70×. These speedups demonstrate that scalable SCA construction is possible through restructuring for parallel evaluation while maintaining coverage correctness.