Static Rate-Optimal Scheduling of Multirate DSP Algorithms via Retiming and Unfolding
Static Rate-Optimal Scheduling of Multirate DSP Algorithms via Retiming and Unfolding
复制标题
DOI：
10.1109/rtas.2012.15
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Xue-Yang Zhu;M. Geilen;T. Basten;S. Stuijk
中科院分区：
文献类型：
--
作者：
Xue-Yang Zhu;M. Geilen;T. Basten;S. Stuijk
本文提出了一种以同步数据流图（SDFGs）表示的实时多速率DSP算法的静态速率最优多处理器调度的精确方法和启发式方法。通过探索SDFG自定时执行（STE）所产生的状态空间，我们的精确方法可以找到一个通过显式重定时和隐式展开的静态速率最优调度。通过限制并发触发STE参与者的数量，可以限制调度中使用的处理器数量。在此基础上，提出了一种基于处理器约束的sdfg速率最优调度的启发式方法。这两种方法都没有显式地将SDFG转换为其等效的同质SDFG。实验结果表明，与现有的方法相比，精确的方法有了明显的改进，我们的启发式方法进一步减少了处理器的使用数量。
This paper presents an exact method and a heuristic method for static rate-optimal multiprocessor scheduling of real-time multi rate DSP algorithms represented by synchronous data flow graphs (SDFGs). Through exploring the state-space generated by a self-timed execution (STE) of an SDFG, a static rate-optimal schedule via explicit retiming and implicit unfolding can be found by our exact method. By constraining the number of concurrent firings of actors of an STE, the number of processors used in a schedule can be limited. Using this, we present a heuristic method for processor-constrained rate-optimal scheduling of SDFGs. Both methods do not explicitly convert an SDFG to its equivalent homogenous SDFG. Our experimental results show that the exact method gives a significant improvement compared to the existing methods, our heuristic method further reduces the number of processors used.