IA^3: An Interference Aware Allocation Algorithm for Multicore Hard Real-Time Systems

Marco Paolieri, E. Quinones, Francisco J. Cazorla, Robert I. Davis, Mateo Valero

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In multicore processors, the execution environment is defined as the environment in which tasks run and it is determined by the hardware resources they get and the workload with which they are executed. Thus, different execution environments lead to different inter-task interferences accessing
shared hardware resources due to conflicts with the other co-running tasks, making the WCET estimation of a task dependent on the execution environment in which it runs. Despite such dependency, current partitioned scheduling approaches use a single WCET estimation per task: typically the highest for all
execution environments in which a task runs. In this paper we introduce IA3: an interference-aware allocation algorithm that considers not a single WCET estimation but a set of WCET estimations per task. IA3 is based on two novel concepts: the WCET-matrix and the WCET-sensitivity. The former associates every WCET estimation with its corresponding execution environment. The latter measures the impact of changing the execution environment on the WCET estimation. This allows IA3 to reduce the number of resources required to
schedule a given taskset. In particular, our results show that in a four-core processor considering tasksets with a total utilization of 2.9, IA3 is able to schedule 70% of the tasksets using 3-cores while a classical partitioned approach with a First-Fit Decreasing heuristic is able to schedule only 5% of the tasksets using 3-cores.
Original languageEnglish
Title of host publicationIEEE Real-Time and Embedded Technology and Applications Symposium
Pages280-290
Number of pages11
DOIs
Publication statusPublished - Apr 2011

Keywords

  • real-time
  • multiprocessor
  • multicore
  • task allocation
  • WCET

Cite this