学习日志之synthesis and optimization(3)——scheduling

scheduling的任务是在硬件运行的时候优化操作的先后执行顺序，因为在执行的时候会有很多各种各样的限制，包括数据上的dependence以及各各种各样的时间上的限制，但是为了追求运行速度需要尽可能多的并行操作运行，所以这个问题又被分为了好几个小问题，对这几个问题要解决，首先就需要对问题进行描述：

> 没有约束时的调度

> 有时间约束的调度

> 有运算资源约束的调度

> 在有时间限制情况下的最小资源使用的调度

首先要解决的是最基础的问题，即没有约束下调度的方法，这里我们需要达成的目标是在最开始的操作和最后一个操作起始时间之间的这一段时间达到最小

需要对各种变量和参数进行定义，并且设定一些理想条件

1. 令sequencing graph 是一个非循环图，即从上到下执行不会有任何循环转跳
2. 上条中V为节点向量，表示这个图中所有的节点，而E代表的是连接两个节点的边
3. 每两个操作之间都有操作延迟，这个延迟是事先给出来的，并且第一个节点和最后一个节点本身都是不没有操作延迟的因为不做事，即,
4. 每个操作开始的时间为

然后根据常识可知道无约束的时候下一个操作开始执行的时间只要大于或等于前一个开始的时间加上前一个操作因为执行而延迟的时间即可：

其中

有了这些只后就可以开始描述问题了，对于无约束调度可以描述如下：

已知V,D,E，找一个调度的顺序，使得满足上面的条件，并且最顶端到最低端的用时最短。

解决这个问题有两种方式一种是ASAP另一种是ALAP

ASAP（as soon as possible）是先设最顶端的操作开始于t=0，然后中间的节点选取父节点都已经调度完的放在同一个时间并行执行，执行开始的时间是度父节点中开始最晚的开始时间加上父节点操作延迟时间，伪代码如下：

调度的结果如下两图所示：

另一种调度方式是ALAP(as late as possible)其过程是反过来的，调度的时候是先设置子节点，而中间选取的是子节点全都调度完的节点，伪代码如下所示，其中是latency的上限，第一个节点和最后一个节点开始时间不能超过这个数：

经过调度的结果如下所示：