Evolutionary Testing for Timing Analysis of
Parallel Embedded Software
Muhammad Waqar Aziz and Syed Abdul Baqi Shah
Science and Technology Unit, Umm Al-Qura University,
Kingdom of Saudi Arabia
Abstract: Embedded real-time software must be verified for
their timing correctness where knowledge about the Worst-Case Execution Time
(WCET) is the building block of such verification. The WCET of embedded
software can be estimated using either static analysis or measurement-based
analysis. Previously, the WCET research assumes sequential code running on
single-core platforms. However, as computation is steadily moving towards using
a combination of parallel programming and multicore hardware, necessary
research in WCET analysis should be taken into account. While focusing on the
measurement-based analysis, the aim of this research is to find the WCET of
parallel embedded software by generating the test-data using search algorithms.
In this paper, the use of a meta-heuristic optimizing search technique-Genetic
Algorithm is demonstrated, to automatically generate such test-data. The
search-based optimization used yielded the input vectors of the parallel
embedded software that cause maximal execution times. These execution times can
be either the WCET of the parallel embedded software or very close to it. The
process was evaluated in terms of its scalability, safety and applicability.
The generated test-data showed improvements over randomly generated data.
Keywords: Embedded real-time software, worst-case
execution-time analysis, measurement-based analysis, end-to-end testing, genetic
algorithm, parallel computing.