The problem of optimal ocmpile-time multiprocessor scheduling of iterative data-flow programs with feedback is addressed in this paper, unlike the earlier studies assumed the availability fo a large number of processors and complete interconnection among them along with the interprocessor communication to be non-negligible to be more realistic. We first explain the effects of incluidng IPC in non-overlapped, overlapped, fully-static, and cyclo-sttic multiprocessor schedules with LMS filter as a realistic example. The effect of IPC in the rate-optimla schedules with the transfformation techniues viz. unfoldig and retiming in scheduling data-flwo programs with optimal unfolding is discussed with an example. We then propose an algorithm, based on the well-known A sup * algorithm, for optimal schedulign of data-flow programs onto multiprocessors, which uses only minimum number of processors. To alleviate the impediments of large requirements of memory space and Cpu time ofr hte optimal scheduling algorithm, we present an effective technique, branch join path isomorphism which relies on our previously defined processor isomorphism, task isomorphism, and node isomorphism apart form the lower bound theory and upper bound on the completion time. The schedules produced by our algorithm are superior to those obtained by the earlier algorithms despite considering IPC as non-negligible and also not completely connected multiporcessor ssytem.
展开▼
