Accepted: Optimal Program Partitioning for Predictable Performance

Friday, 30 March 2012

My paper, co-authored with Neil Audsley, has been accepted to appear at the ECRTS 2012 conference. This is a paper about algorithms for partitioning programs for use with scratchpad memory (SPM). It's the result of several months of research effort to find a good algorithm for this problem, which turned out to be more difficult than I expected, because the usual graph partitioning algorithms were not suitable.


Scratchpad memory (SPM) provides a predictable 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. This allows 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.