Joint Optimization of Data and Program Size in Embedded Software
Dr. Praveen K. Murthy
Department of Electrical Engineering and Computer Sciences
University of California at Berkeley
Berkeley, CA 94720-1772
http://ptolemy.eecs.berkeley.edu/~murthy
Tuesday, April 1st, 4:00 PM, ENS 302
Synchronous Dataflow (SDF) has proved to be a useful specification model for block-diagram design environments such as SPW from Cadence and Ptolemy from UC Berkeley. SDF possesses strong formal properties such as the ability to detect deadlock and sample rate consistency, to model multirate signal processing applications well, and to find compile-time (static) schedules.
Generating code from static schedules using threading can cause an explosion in code and buffer memory size. Digital signal processors have severe constraints on on-chip memory. Adding off-chip memory is unattractive due to increased system cost, power consumption, and execution time. We compute static schedules that simultaneously minimize the data and code size of software generated from the schedule, giving first preference to code size.
We show that our optimization problem is NP-complete, and develop heuristics instead. We give three polynomial-time algorithms: a dynamic programming algorithm that is used to postprocess schedules, and two complementary heuristics, RPMC and APGAN. We prove the APGAN is optimal for a class of SDF graphs that includes several useful DSP systems.
A list of digital signal processing seminars is available at from the ECE department Web pages under "Seminars". The Web address for the digital signal processing seminars is http://www.ece.utexas.edu/~bevans/dsp_seminars.html