算子调理
调理是HLS 中的核心题目，为无时序或部门时序的输入指定时钟界限，其对终极结果质量具有很大的影响。调理会影响时钟频率、延时、吞吐率、面积、功耗等多种因素。
调理的输入是控制数据流图，其节点表示算子/操纵，有向边表示数据依赖，控制依赖，优先依赖。假如没有控制流，其基本结构就是数据流图（DFG）。
调理过程将算子映射到一个状态，每个时钟周期对应着 FSM 中的一个状态，这称为控制步。
无约束的调理方法
无约束的调理方法只思量依赖，目前，有两种常用的无约束调理方法：
ASAP
一，尽大概早的调理（ASAP），即把算子安排在尽大概早的控制步。其对应的算法伪代码如下：
ASAP G(V,E):
V’ = Topological_Sort(G)
foreach v i v_i vi in V’:
if v i ∈ P I s v_i \in PIs vi∈PIs : t i t_i ti = 1; // PIs, 主输入聚集
//假设每个算子都必要一个时钟周期
else: t i t_i ti = max( t j t_j tj + 1); // ( v j , v i ) ∈ (v_j,v_i)\in (vj,vi)∈ E
ALAP
二，尽大概迟的调理（ALAP），即把算子安排在尽大概晚的控制步。
其对应的算法伪代码如下：
ALAP (G(V,E),L): //L 是延时上限
V’ = Reverse_Topological_Sort(G)
foreach v i v_i vi in V’:
if v i v_i vi ∈ \in ∈ POs: t i t_i ti = L; // POs, 主输出聚集
//假设每个算子都必要一个时钟周期
else: t i t_i ti = min( t j t_j tj) - 1; // ( v i , v j ) ∈ (v_i,v_j) \in (vi,vj)∈ E
带约束调理方法
带约束调理题目一般是 NP-Hard 题目，目前，有两类题目，分别是资源约束的调理（Resource Constrained Scheduling，RCS），即给定面积或资源约束最小化延时；时间约束的调理（Time Constrained Scheduling，TCS），即给定延时界限最小化资源
对于带约束调理题目，可接纳精确建模方法，好比整数线性编程（Integer Linear Programming，ILP）、针对严格约束的 Hu 算法等等；也可以接纳启发式算法，包含列表调理、力量引导算法、基于SDC的调理等等。
以下以ILP方法为例，建模并求解带约束的调理题目。
ILP调理
线性编程（Linear Programming, LP）主要是解决目的函数和约束都是线性表示的题目，其在理论上和现实上都能有效求解。而整数线性编程(ILP)除了目的函数和约束都是线性组合之外，变量的取值必须是整数，其通常也是 NP-Hard 题目（0-1 ILP 除外），但是，当代 ILP 求解器可以求解一定规模的 ILP 题目。
资源约束的调理（RCS）表述为硬件功能单元（FU）资源有限，每个时钟周期每个功能单元只能执行一个算子。好比，只有 K 个加法器的时间，同一个时钟周期执行的加法数量不超过 K。
RCS题目的输入：给定每种计算范例的功能单元的数量，最小化延时。
RCS 的 ILP 建模的第一步是定义变量。
首先定义二元决议变量 x i k x_{ik} xik， x i k x_{ik} xik=1表示算子 i 在控制步 k 开始执行。i = 1,2,3,…,N，N 表示算子总数，k= 1,2,3,…,L, L 表示延时的上限。
定义 t i = ∑ k = 1 L ( k x i k ) t_i = \sum_{k=1}^{L} (kx_{ik}) ti=∑k=1L(kxik)， t i t_i ti 表示算子 i 的起始时间。
第二步是建立约束关系。主要包含以下约束：
起始时间的唯一性 ∑ k x i k = 1 , i = 1 , 2 , ⋯ , N \sum_{k}x_{ik}=1,i=1,2,\cdots,N ∑
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
