Cache Aware Pre-Runtime Scheduling

We present a novel pre-runtime scheduling method for uniprocessors which precisely takes the effects of task switching on the processor cache into consideration. Tasks are modelled as a sequence of non preemptable segments with precedence constraints. The cache behavior of each task segment is statically determined by abstract interpretation. For the sake of efficiency, the scheduling algorithm uses a heuristically guided search strategy. Each time a new task segment is added to a partial schedule, its worst case execution time is calculated based on the cache state at the end of the preceding partial schedule.