Code placement with selective cache activity minimization for embedded real-time software design

Many embedded system designs usually impose (hard) read-time constraints on tasks. Thus, computing a tight upper bound of the worst case execution time (WCET) of a software is a critically important, but difficult task. The difficulty arises particularly when the code is executed on processors with cache-based memory systems. In this paper, we propose a new code placement technique under cache activity consideration for real-time software design. Specifically, unlike the previous approaches which have tried to minimize total cache misses, which is not necessarily the best way to meet all timing constraints of tasks, we minimizes the cache misses in a selective way for tasks according to the degree of tightness (or urgency) of their timing constraints. Based on a concept of selective cache activity minimization, we propose a new approach which solves the code placement problem in two steps: (Step 1) We transform the code placement problem into so called an interval selection problem, which then we formulate into a 0-1 integer linear programming (ILP); (Step 2) We apply an efficient approximation algorithm, called Code-map, to solve the exact code placement formulation obtained in Step 1.