2020-03174 - Using statistical methods to evaluate the impact of the processor architecture on the execution times of programs.

Contract type : Internship agreement

Level of qualifications required : Graduate degree or equivalent

Fonction : Internship Research

Context

The internship  will take place at the Inria Paris Research Centre in the KOPERNIC project-team, 2 Rue Simone IFF, 75012 Paris and will be supervised by Yasmina Abdeddaim and Liliana Cucu Grosjean

The internship allowance is 500 euros per month.

The internship may be followed by a PhD thesis.

Assignment

The execution time of programs executed on multicore processors may have large time variability due to features like multiple levels of caches and pipelines, speculative branching, communicating through shared memory, etc., that introduce variations between the smallest and largest values of the program execution times. This time variability makes the use of these multicore processors unpredictable and thus unsafe for safety critical applications with real-time constraints.

The goal of the internship is to deal with the problem of time variability of programs executed on a general purpose processor, e.g., ARM Cortex-A53. In fact, some of the features of these processors are not well documented, and the algorithms used in the implementation of these features are somehow obscure.

The purpose during this internship is to use statistical methods to deduce the algorithms and tricks used by the designers in the implementation of these features by providing statisticl relations between these features and the time variability of execution times of programs.

Main activities

The stages of the internship are:

  1. Propose a set of benchmark programs that will allow us to focus in every feature of the processor and generate at set of representative execution times for each program.

  2. Use statistical methods to analyze each set of execution times with the goal of deducing a formal relation between each feature and its impact on the execution time of a program.

  3. Deduce a general formal relation between the execution time of a program and a set of features used during the execution of this program by proposing composition rules to compose the formal relations of each feature proposed in stage 2.

References:

[1] Wilhelm, Reinhard and Engblom, Jakob and Ermedahl, Andreas and Holsti,Niklas and Thesing, Stephan and Whalley, David and Bernat, Guillem and Ferdinand, Christian and Heckmann, Reinhold and Mitra, Tulika and Mueller,Frank and Puaut, Isabelle and Puschner, Peter and Staschulat, Jan and Stenstrom, The Worst-case Execution-time Problem: Overview of Methods and Survey of Tools, ACM Trans. Embed. Comput. Syst., 7(3), May 2008.

[2] R. I. Davis and A. Burns, A survey of hard real-time scheduling formultiprocessor systems, ACM Comput. Surv, 43(4), 2011.

[3] R. I. Davis and L. Cucu-Grosjean, A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems, LITES, 6(1).

Skills

Processor architecture, statistics.

Benefits package

  • Partial reimbursement of public transport costs
  • Flexible organization of working hours
  • Professional equipment available (videoconferencing, loan of computer equipment, etc.)
  • Social, cultural and sports events and activities
  • Access to vocational training