Force-Directed Scheduling in Automatic Data Path Synthesis
Force-Directed Scheduling in Automatic Data Path Synthesis
复制标题
DOI：
10.1145/37888.37918
复制
发表时间：
1987-10
期刊：
影响因子：
--
通讯作者：
P. Paulin;J. Knight
中科院分区：
文献类型：
--
作者：
P. Paulin;J. Knight
HAL系统使用一种新的调度算法执行数据路径合成，该算法是相互依赖的调度和分配方案的一部分。该方案使用硬件分配的估计来指导和优化调度子任务。分配信息包括硬件模块的数量、类型、速度和成本以及相关的多路复用器和互连成本。迭代强制调度算法试图平衡使用相同硬件资源的操作的分布：* 对于所有操作，在每次迭代时评估每个可行的控制步骤分配。* 考虑了对所有前置操作和后续操作的相关副作用。* 所有的决定都是全球性的。* 该算法的复杂度为O（n/sup 2/）。我们回顾和比较现有的调度技术。通过中等难度和高难度的算例说明了该方法的有效性。
The HAL system performs data path synthesis using a new scheduling algorithm that is part of an interdependent scheduling and allocation scheme. This scheme uses an estimate of the hardware allocation to guide and optimize the scheduling subtask. The allocation information includes the number, type, speed and cost of hardware modules as well as the associated multiplexer and interconnect costs. The iterative force-directed scheduling algorithm attempts to balance the distribution of operations that make use of the same hardware resources: * Every feasible control step assignment is evaluated at each iteration, for all operations. * The associated side-effects on all the predecessor and successor operations are taken into account. * All the decisions are global. * The algorithm has O(n/sup2/) complexity. We review and compare existing scheduling techniques. Moderate and difficult examples are used to illustrate the effectiveness of the approach.