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.

References

[1] Betts A., Bernat G., Kirner R., Puschner P., and Wenzel I., “WCET Coverage For Pipelines,” Real Time Systems Research Group-University of York and Institute of Computer Engineering- Vienna University of Technology, Technical Report, 2006.

[2] Binkert N., Beckmann B., Black G., Reinhardt S., Saidi A., Basu A., Hestness J., Hower D., Krishna T., Sardashti S., Sen R., Sewell K., Shoaib M., Vaish N., Hill M., and Wood D., “The Gem5 Simulator,” ACM SIGARCH Computer Architecture News, vol. 39, no. 2, pp. 1-7, 2011.

[3] Ding Y. and Zhang W., “Multicore-Aware Code Co-Positioning to Reduce WCET on Dual-Core Processors with Shared Instruction Caches,” Journal of Computing Science and Engineering, vol. 6, no. 1, pp. 12-25, 2012.

[4] Gross H., “An Evaluation of Dynamic, Optimisation-Based Worst-Case Execution Time Analysis,” in Proceedings of the International Conference on Information Technology: Prospects and Challenges in the 21st Century, Kathmandu, 2003.

[5] Guan N., Stigge M., Yi W., and Yu G., “Cache- Aware Scheduling and Analysis for Multicores,” in Proceedings of the 17th ACM International Conference on Embedded Software, Grenoble, pp. 245-254, 2009.

[6] Gustafsson J., Betts A., Ermedahl A., and Lisper B., “The Mälardalen WCET Benchmarks: Past, Present and Future,” in Proceedings of 10th Workshop on Worst-Case Execution Time Analysis, Brussels, 2010.

[7] Gustavsson A., Ermedahl A., Lisper B., and Pettersson P., “Towards WCET analysis of Multicore Architectures Using Uppaal,” in Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis, Dagstuhl, pp. 101-112, 2010.

[8] Gustavsson A., Gustafsson J., and Lisper B., “Toward Static Timing Analysis of Parallel Software,” in Proceedings of 12th International Workshop on Worst-Case Execution Time Analysis, Dagstuhl, 2012.

[9] Guthaus M., Ringenberg J., Ernst D., Austin T., Mudge T., and Brown R., “Mibench: A Free, Commercially Representative Embedded Benchmark Suite,” in Proceedings of the 4th Annual IEEE International Workshop on Workload Characterization, Austin, pp. 3-14, 2001.

[10] Heckmann R. and Ferdinand C., “Worst-Case Execution Time Prediction By Static Program Analysis,” in Proceedings of 18th International Parallel and Distributed Processing Symposium, Santa Fe, pp. 26-30, 2004.

[11] Iqbal S., Liang Y., and Grahn H., “ParMibench- an Open-Source Benchmark for Embedded Multiprocessor Systems,” IEEE Computer Architecture Letters, vol. 9, no. 2, pp. 45-48, 2010.

[12] Kästner D., Schlickling M., Pister M., Cullmann C., Gebhard G., Heckmann R., and Ferdinand C., “Meeting Real-Time Requirements with Multi- Core Processors,” in Proceedings of International Conference on Computer Safety, Reliability and Security, Berlin, pp. 117-131, 2012.

[13] Khan U. and Bate I., “WCET Analysis of Modern Processors Using Multi-Criteria Optimization,” in Proceedings of 1st International Symposium on Search Based Software Engineering, Windsor, pp. 103-112, 2009.

[14] Koziolek H., Becker S., Happe J., Tuma P., and Gooijer T., “Towards Software Performance Engineering for Multicore and Manycore Systems,” ACM SIGMETRICS Performance Evaluation Review, vol. 41, no. 3, pp. 2-11, 2014.

[15] Liang Y., Ding H., Mitra T., Roychoudhury A., Li Y., and Suhendra V., “Timing Analysis of 422 The International Arab Journal of Information Technology, Vol. 16, No. 3, May 2019 Concurrent Programs Running on Shared Cache Multi-Cores,” Real-Time Systems, vol. 48, no. 6, pp. 638-680, 2012.

[16] Mansour N., Awad M., and El-Fakih K., “Incremental Genetic Algorithm,” The International Arab Journal of Information Technology, vol. 3, no. 1, pp. 42-47, 2006.

[17] Ozaktas H., Rochange C., and Sainrat P., “Automatic WCET Analysis of Real-Time Parallel Applications,” in Proceedings of 13th Workshop on Worst-Case Execution Time Analysis, Paris, pp. 11-20, 2013.

[18] Pinho L., Quinones E., Bertogna M., Marongiu A., Carlos J., Scordino C., and Ramponi M., “P- Socrates: A Parallel Software Framework for Time-Critical Many-Core Systems,” in Proceedings of 17th Euromicro Conference on Digital System Design, Verona, pp. 214-221, 2014.

[19] Pitter C. and Schoeberl M., “A Real-Time Java Chip-Multiprocessor,” ACM Transactions on Embedded Computing Systems, vol. 10, no. 1, 2010.

[20] Potop-Butucaru D. and Puaut I., “Integrated Worst-Case Response Time Evaluation of Multicore Non-Preemptive Applications,” PhD Dissertation, Institut National de Recherche en Informatique et en Automatique, 2013.

[21] Rochange C., Bonenfant A., Sainrat P., Gerdes M., Wolf J., Ungerer T., Petrov Z., and Mikulu F., “WCET Analysis of A Parallel 3D Multigrid Solver Executed on the Merasa Multi-Core,” in Proceedings of OASIcs-OpenAccess Series in Informatics, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, pp. 90-100, 2010.

[22] Rosen J., Andrei A., Eles P., and Peng Z., “Bus Access Optimization for Predictable Implementation Of Real-Time Applications on Multiprocessor Systems-on-Chip,” in Proceedings of 28th IEEE International Real- Time Systems Symposium, Tucson, pp. 49-60, 2007.

[23] Ungerer T., Cazorla F., Casse H., Uhrig S., Guliashvili I., Houston M., Kluge F., Metzlaff S., Mische J., Sainrat P., Bernat G., Petrov Z., Rochange C., Quinones E., and Gerdes M., “Merasa: Multicore Execution of Hard Real- Time Applications Supporting Analyzability,” IEEE Micro, vol. 30, no. 5, pp. 66-75, 2010.

[24] Wegener J. and Mueller F., “A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints,” Real-Time Systems, vol. 21, no. 3, pp. 241-268, 2001.

[25] Wegener J., Sthamer H., Jones B., and Eyres D., “Testing Real-Time Systems Using Genetic Algorithms,” Software Quality Journal, vol. 6, no. 2, pp. 127-135, 1997.

[26] Wilhelm R., Engblom J., Ermedahl A., Holsti N., Thesing S., Whalley D., Bernat G., Ferdinand C., Heckmann R., Mitra T., Mueller F., Puaut I., Puschner P., Staschulat J., and Stenstrom P., “The Worst-Case Execution-Time Problem- Overview of Methods and Survey of Tools,” ACM Transactions on Embedded Computing Systems, vol. 7, no. 3, 2008.

[27] Wu L. and Zhang W., “Bounding Worst-Case Execution Time for Multicore Processors Through Model Checking,” in Proceedings of 16th IEEE Real-Time and Embedded Technology and Applications Symposium, Stockholm, pp. 17- 20, 2010.

[28] Yan J. and Zhang W., “WCET Analysis for Multi-Core Processors with Shared L2 Instruction Caches,” IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 80-89, 2008.

[29] Yip E., Roop P., Biglari-Abhari M., and Girault A., “Programming and Timing Analysis of Parallel Programs on Multicores,” in Proceedings of 13th International Conference on Application of Concurrency to System Design, Barcelona, pp. 160-169, 2013.

[30] Yip E., Roop P., and Biglari-Abhari M., “Predictable Parallel Programming Using PRET- C,” Report, University of Auckland, Faculty of Engineering, 2010.

[31] Zhang W. and Yan J., “Accurately Estimating Worst-Case Execution Time For Multi-Core Processors With Shared Direct-Mapped Instruction Caches,” in Proceedings of 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Beijing, pp. 455-463, 2009. Evolutionary Testing for Timing Analysis of Parallel Embedded Software 423 Muhammad Waqar Aziz is an Assistant Professor in Umm Al- Qura University, Makkah, Saudi Arabia. He received his Ph.D (Computer Science) from Universiti Teknologi Malaysia, Malaysia in 2013, MS-Software Engineering from City University of Science and Technology, Pakistan in 2009 and MSc- Computer Science from University of Peshawar, Pakistan in 2001. Previously, he has almost eight years of teaching experience as Lecturer at Institute of Management Studies, University of Peshawar. He published more than 20 research articles in indexed and well reputed journals and Conference Proceedings. The research areas of his interest are Embedded Real-Time Software modeling, verification and development and smart environment development. Syed Abdul Baqi Shah is a Lecturer at Science and Technology Unit, Umm Al Qura University, Makkah, Saudi Arabia. He received a B.S. degree in Electronic Engineering from International Islamic University, Islamabad, Pakistan in 2007. He completed his MS in Information and Mechatronics from Gwnangju Institute of Science and Technology, Republic of Korea in 2010. His research interests include timing analysis of real-time systems and applications, as well as design and implementation of low-power embedded system.