Scheduling for optimum data memory compaction in block diagram oriented software synthesis

For the design of complex digital signal processing systems block diagram oriented synthesis of real time software for programmable target processors has become an important design aid The synthesis approach discussed in this paper is based on multirate block diagrams with scalable synchro nous data ow SSDF semantics For this class of data ow graphs we present scheduling techniques for optimum data memory compaction These techniques can be employed to map signals of a block diagram onto a minimum data me mory space In order to formalize the data memory com paction problem we rst derive appropriate implementa tion measures Based on these implementation measures it can be shown that optimum data memory compaction con sists of optimum scheduling as well as optimum memory allocation For the class of single appearance SA block diagrams with SSDF semantics scheduling can be reduced to an integer linear programming ILP problem Due to the computational complexity of ILP we also present a sub optimum scheduling selection criterion which can be used for SA and non SAscheduler