Method and apparatus for establishing a bound on the effect of task interference in a cache memory
View Patent ↗A method and apparatus are disclosed for establishing a bound on the effect of task interference in an instruction cache shared by multiple tasks. The bound established by the present invention is the maximum number of “live” frames of a given task that are coexistent during the execution of an application. A “live cache frame” contains a block that is accessed in the future without an intervening eviction. The eviction of blocks from a live frame by an interrupt causes a future miss that would not otherwise occur and evictions from live frames are the only evictions that cause misses that would not otherwise occur. The invention provides a more accurate estimate of the maximum additional execution time of a task that results from servicing an interrupt during its execution. Additional accuracy is obtained by exploiting knowledge of the character of an intervening task to achieve a tighter bound, when possible.
1. A method for establishing a bound on the execution time of an application due to task interference in an instruction cache shared by a plurality of tasks, said method comprising the steps of:
determining a number of live frames of said application that are coexistent during execution of said application; and
establishing said bound based on said number of live frames of a set-associative cache, wherein said bound is suitable for use in allocating processing resources, wherein one or more steps of said method are performed by at least one hardware device, wherein said step of establishing said bound further comprises the steps of determining an effect of an interrupt at each possible interrupt point and establishing said bound based on a maximum of said effect of an interrupt at each possible interrupt point.
2. The method of claim 1 , wherein said number of live frames is a number of cache frames that contain a block that is accessed by said application in the future without an intervening eviction.
3. The method of claim 1 , wherein said number of live frames is determined by a post-execution analysis of cache access patterns of said application.
4. The method of claim 1 , wherein said number of live frames is determined by a run-time analysis of cache access patterns of a simulation of said application.
5. A system for establishing a bound on the execution time of an application due to task interference in an instruction cache shared by a plurality of tasks, said system comprising:
a memory that stores computer-readable code; and
a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to:
determine a number of live frames of said application that are coexistent during, execution of said application; and
establish said bound based on said number of live frames of a set-associative cache, wherein said bound is suitable for use in allocating processing resources, wherein said step of establishing said bound further comprises the steps of determining an effect of an interrupt at each possible interrupt point and establishing said bound based on a maximum of said effect of an interrupt at each possible interrupt point.
6. The system of claim 5 , wherein said number of live frames is a number of cache frames that contain a block that is accessed by said application in the future without an intervening eviction.
7. The system of claim 5 , wherein said number of live frames is determined by a post-execution analysis of cache access patterns of said application.
8. The system of claim 5 , wherein said number of live frames is determined by a run-time analysis of cache access patterns of a simulation of said application.
9. An article of manufacture for establishing a bound on the execution time of an application due to task interference in an instruction cache shared by a plurality of tasks, comprising:
a tangible computer readable recordable storage medium having computer readable code means embodied thereon, said computer readable program code means comprising:
a step to determine a number of live frames of said application that are coexistent during execution of said application;
a step to establish said bound based on said number of live frames of a set associative cache, wherein said bound is suitable for use in allocating processing resources;
a step to determine an effect of an interrupt at each possible interrupt point and establish said hound based on a maximum of said effect of an interrupt at each possible interrupt point.
10. A system for establishing a bound on an effect of task interference on an application in an instruction cache shared by a plurality of tasks, said system comprising:
means for determining a number of live frames of said application that are coexistent during execution of said application;
means for establishing said bound based on said number of live frames of a set-associative cache, wherein said bound is suitable for use in allocating processing resources; and
means for determining an effect of an interrupt at each possible interrupt point and establish said bound based on a maximum of said effect of an interrupt at each possible interrupt point.
11. The system of claim 10 , wherein said number of live frames is determined by a post-execution analysis of cache access patterns of said application.
12. The system of claim 10 , wherein said number of live frames is determined by a run-time analysis of cache access patterns of a simulation of said application.