首页> 外文会议>High-performance computing and networking >Optimal Scheduling of iterative Data-Flow programs onto Multiprocessors with non-negligible Interprocessor COmmunication
【24h】

Optimal Scheduling of iterative Data-Flow programs onto Multiprocessors with non-negligible Interprocessor COmmunication

机译:具有不可忽略的处理器间通信的迭代数据流程序在多处理器上的最佳调度

获取原文
获取原文并翻译 | 示例

摘要

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.
机译:本文解决了带有反馈的迭代数据流程序的最佳时空多处理器调度问题,这与早期的研究不同,它假定大量处理器的可用性以及它们之间的完全互连以及处理器间的通信是不可行的。可以忽略不计。我们首先以LMS过滤器为例,说明IPC在不重叠,重叠,全静态和循环多处理器计划中的作用。 IPC在采用转化技术的最佳速率计划中的作用。通过一个示例讨论了在调度具有最佳展开功能的数据流程序中的展开和重定时。然后,我们基于著名的A sup *算法提出一种算法,用于将数据流程序最佳调度到多处理器上,该处理器仅使用最少数量的处理器。为了减轻对最佳调度算法的内存空间和Cpu时间的大量需求的障碍,我们提出了一种有效的技术,即分支连接路径同构,它依赖于我们先前定义的处理器同构,任务同构和节点同构(除了下界理论以外)和完成时间的上限。尽管我们认为IPC是不可忽略的,并且也不是完全连接的多处理器系统,但我们的算法产生的调度表优于早期算法所获得的调度表。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号