Method for deriving optimal code schedule sequences from synchronous dataflow graphs

Abstract

Abstract A method is disclosed for deriving code schedule sequences for a target code generator from an input ordering of nodes and prime factors of their respective ordered invocation rates from an SDF graph representative of a system. The method involves first creating a loop set for each prime factor wherein the elements of each loop set are the actors, the invocation frequency from which are factorable by that prime factor and are ordered. The redundant created loop sets are merged so as to eliminate those sets with identical nodes. The merged loop sets are then sorted in decreasing order by the total number of node elements in each set. A determination is then made as to whether each loop set is a proper subset of its sorted ordered predecessor loop set with which it intersects and, if not, then breaking the non-disjoint sets into sublists of sets which are proper subsets of their predecessor sets and then determining whether the parent sets of the broken sublists are then disjoint from one another. If they are not then repeating these two substeps. The next step of the present method then involves extracting a loop schedule for each sublist and combining the extracted loop schedules in accordance with the sorted precedence ordering of the nodes in each of said loop sets to produce the code schedule sequences. In such a manner, the code schedule sequences generated corresponds to every potential type of actor or block in the system and can then be used to minimize both program and data memory requirements of the scheduled systems.

Inventors

• 👤 Douglas B. Powell

Bibliographic Details