Patent
1995-03-07
1997-02-25
Lall, Parshotam S.
G06F 945
Patent
active
056066988
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.
REFERENCES:
patent: 4571678 (1986-02-01), Chaitin
patent: 4802091 (1989-01-01), Cocke et al.
patent: 4833606 (1989-05-01), Iwasawa
patent: 4885684 (1989-12-01), Austin et al.
patent: 5109331 (1992-04-01), Ishida et al.
patent: 5146594 (1992-09-01), Iitsuka
patent: 5193190 (1993-03-01), Janczyn et al.
patent: 5202995 (1993-04-01), O'Brien
patent: 5230053 (1993-07-01), Zaiki
patent: 5265253 (1993-11-01), Yamada
patent: 5283901 (1994-02-01), Masuyama
patent: 5303357 (1994-04-01), Inoue et al.
patent: 5361354 (1994-11-01), Greyzck
"Static Rate-Optimal Scheduling of Iterative Data Flow Programs via Optimum Unfolding" Parhi et al, IEEE, vol. 40, No. 2, Feb. 1991, pp. 178-195.
"A Polynomial-Time Algorithm for the Computation of the Iteration Period Bound in Recursive Data Flow Graphs," Gerez, IEEE, vol. 39 No. 1, Jan. 1992, pp. 49-52.
Cadence Design Systems Inc.
Lall Parshotam S.
McNelis John T.
Vu Viet
LandOfFree
Method for deriving optimal code schedule sequences from synchro does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for deriving optimal code schedule sequences from synchro, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for deriving optimal code schedule sequences from synchro will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1980823