Thursday, 19 July 2012

Optimal Program Partitioning for Predictable Performance

Conference paper: Optimal Program Partitioning for Predictable Performance by Jack Whitham and Neil Audsley, in Proc. ECRTS, pages 122-131, 2012, DOI 10.1109/ECRTS.2012.18.
@inproceedings{ffec,
 abstract = {
and energy efficient way to store program instructions and data.
It would be ideal for embedded real-time systems if not for
the practical difficulty that most programs have to be modified
in source or binary form in order to use it effectively. This
modification process is called partitioning, and it splits a large
program into sub-units called regions that are small enough to
be stored in SPM.

Earlier papers on this subject have only considered regions
formed around program structures, such as loops, methods and
even entire tasks. Region formation and SPM allocation are
performed in two separate steps. This is an approximation that
does not make best use of SPM.

In this paper, we propose a k-partitioning algorithm as a new
way to solve the problem. These allow us to carry out region
formation and SPM allocation simultaneously. We can generate
optimal partitions for programs expressed either as call trees
or by a restricted form of control-flow graph (CFG). We show
that this approach obtains superior results to the previous two-
step approach. We apply our algorithm to various programs and
SPM sizes and show that it reduces the execution time cost for
executing those programs relative to execution with cache.},
 author = {Jack Whitham and Neil Audsley},
 blog = {http://blog.jwhitham.org/2012/03/accepted-optimal-program-partitioning.html},
 booktitle = {Proc. ECRTS},
 date = {20120719},
 doi = {10.1109/ECRTS.2012.18},
 pages = {122--131},
 sw = {csearch-1.tar.bz2},
 title = {{Optimal Program Partitioning for Predictable Performance}},
 year = {2012},
}