高层次综合

高层次综合HighLevelSynthesis陈付龙2005-11-23参考文献薛宏熙，边计年，苏明.数字系统设计自动化[M].北京：清华大学出版社，1996年10月李德新，周祖成.高层次综合[J].电子技术应用，1998年第3期苏明.高层次综合算法及其系统研究.北京：清华大学博士学位论文，1993主要内容0概述：任务和内容1编译与转换：编译方法和转换方法2调度：ASAP，ALAP，LS算法3分配：图着色算法4控制器综合5结果生成与反编译6相关研究7总结0概述——高层次综合与系统描述的关系算法级寄存器传输级逻辑级电路级版图级行为特性物理特性结构特性高层次综合：从算法级的行为描述到实现它的寄存器传输级的结构描述的综合逻辑综合版图综合高层次综合的任务找出一个满足约束条件和目标集合、花费最少的硬件结构高层次综合的优点提高设计速度，缩短设计周期描述简洁，容易编写、理解，贴近自然语言，描述错误少且容易修改高层次综合内容调度编译与转换反编译分配控制器综合功能单元库设计约束(时钟周期,操作步数(周期数),设计吞吐量,硬件资源的最大数目、面积、最大功耗等)中间表示格式数据流控制流数据通路硬连逻辑或微程序给有限状态机综合与逻辑综合结构描述给文档管理或其它逻辑综合工具算法描述1编译与转换编译：转换：优化编译逻辑级以上行为描述数据流和控制流语法分析图（树）1-1编译：生成控制数据流图CDFG三类节点操作节点表示抽象的操作运算传输节点表示数据的传输结构接点起始节点终结节点分支节点汇聚节点两类边数据相关边控制相关边起始节点终结节点Exampleentitysampleisport(in1,in2:ininteger;cond:inbit;fout:outinteger;)endsamplearchitecturebehaviorofsampleisbeginprocess/*顺序执行的程序*/variablev1,v2,v3:integer;v1:=in1;v2:=in2;while(v1v2)loopif(cond=‘1’)thenv3=:v1+v2;v2:=v1;elsev3:=v1-v2;endifendloopfout=v3;endprocessendbehavior123456789‘1’in2in1cond=:==-+:=:=v1v2v3fout(v1v2)┓(v1v2)(cond=‘1’)┓(cond=‘1’)beginendCDFD的数据结构邻接矩阵邻接表1-2转换：目的是对设计的行为描述进行优化编译优化（最基本的转换）常量代入无用码删除公因子提取与公用表达式删除代码（操作）移动：分支操作移入（出）条件分支过程体展开循环展开针对专门硬件模块，将复杂的多周期操作转换成简单操作增加操作并行度减少CDFG图中关键路径和指定路径上的操作个数常量代入和无用码删除：=++a24b123a:=2;c:=a+(4+b);c：=++4b22a123c常量代入无用码删除×其它转换将在2-3节介绍2调度功能：将操作赋给控制步（controlstep）一个控制步是一个时序单位，对应若干时钟周期输入：CDFG数据流目的：在满足约束条件（size,speed,power）下，将操作赋给各控制步，以使给定目标函数（e.g.numberofcontrolsteps,delay,power,resource,etc.)最小2-1操作类型及操作的调度类型单周期操作：一个控制步内完成单操作单周期（e.g.1）多操作单周期（链式，e.g.3，4）多周期操作（e.g.2）：多个控制步内完成单周期操作调度链式操作调度多周期操作调度+*+-1243cs1cs22-2调度算法分类依调度算法变换法(transformation)：首先找出一个初始调度方案，然后对其进行变换，即将操作从一个控制步移到另一个控制步(穷举法:分支定界法(branchandbound),启发式方法:模拟退火法(simulatedannealing))构造法(constructive)：每次选一个操作进行调度,直到所有的操作都调度完成(e.g.ListingScheduling)依约束条件时间约束：在满足时间约束(操作步数或时钟周期)的条件下，以尽可能少的硬件资源来完成操作(e.g.ALAP)硬件资源约束：在满足硬件资源约束(面积，资源数目)的条件下，以尽可能短的时间来完成操作（e.g.LS）时间约束和硬件资源约束功耗约束可测性设计约束无约束(e.g.ASAP)变换法：examplecs1cs2cs3++++++++++++++++++1234561234561234563adders,3steps3adders,2steps2adders,3steps典型调度算法（一）ASAP和ALAPASAP(assoonaspossible)：无约束算法。它将所有操作赋予最早可能调度到的控制步中，将CDFG看作有向图时,其中操作节点、起始和终止节点分别为有向图的的节点,数据相关边作为有向图的有向边,然后对该有向图进行正向分层排序。ALAP(aslateaspossible)：时间约束算法。它是将操作赋予可能最迟调度到的控制步中。其基本思路与ASAP算法类似,只是对有向图进行反向的分层排序。ASAP}|{,1)()},()({)(max的输入的输入是操作操作）（的直接前趋集，即）是操作（），的延迟时间（控制步数）为操作（其中，否则若定义为该操作的最早控制步，可以执行的最早时间为操作kiikprekkpreiikpreiiOPopkkopopopopOPopopOPopopTDopOPopTDopASAPopASAPopprei+******+--ydx3u1234567891011+******+--1234567891011cs1cs2cs3cs4cs5cs6否则若,1)},()({)(maxpreiiOPopkOPopTDopASAPopASAPprei优点：简单，快速缺点：头重！无约束ALAP数（时间约束）为所需要的最大控制步的输入的输出是操作的直接后继集，即是操作），的延迟时间（控制步数）为操作（其中，否则若定义为该操作的最迟控制步，可以执行的最迟时间为操作stepjkjksucksuciikstepksuckiOPopkkMopopopopOPopOPopopTDopTDMopOPopTDopALAPopALAPopsuci},|{)(,1)()()},()({)(min+******+--ydx3u1234567891011+******+--1234567891011cs1cs2cs3cs4cs5cs6否则若,1)()()},()({)(minkstepksuckiOPopkopTDMopOPopTDopALAPopALAPsuci优点：简单，快速缺点：脚大！不一定做到满足约束时的最优)](),([)(kkkopALAPopASAPopSA+******+--1234567891011cs1cs2cs3cs4cs5cs6ASAP+******+--1234567891011cs1cs2cs3cs4cs5cs6ALAP调整区间典型调度算法（二）列表调度算法（listscheduling）构造型，硬件资源约束(resourcerestriction)就绪队列AQ(ActiveQueue)：存放当前控制步中可以执行的操作（其前趋已被调度，自己未被调度且“其前趋的控制步+其前趋的延迟≤当前cs”的操作）优先级函数pf(priorityfunction)调整区间（最小优先）路径长度（自该操作到结束的最长延迟，最长优先）设cs1为当前cs建立AQ，按pf排序取AQ中pf最高的操作调度到cs修改AQcs←cs+1AQ中有满足rr的操作YN有操作未调度？YNendbegin+******+--1234567891011cs1cs2cs3cs4cs5cs6cs7rr:2multiplicationunits,1subtracter,1adder,1comparisonunitpf:pathlength5AQ={3,4,5,6,1}Select:3,4,1AQ={5,6,2}Select:2AQ={7,5,6,}Select:7,5AQ={6}Select:noAQ={8,6,10}Select:8,6,10AQ={}Select:noAQ={11,9}Select:11,9123467优点：算法复杂性低O(n)，速度快能在短时间内找到次优解缺点：不能进行时间约束下的调度典型调度算法（三）力定向算法(Force-DirectedScheduling)构造型、基于时间约束基本思想：尽可能均匀地在硬件功能单元之间安排操作,防止某些功能单元使用频繁,而另外一些功能单元大部分时间闲置,以便提高功能单元的总体使用效率和降低硬件成本算法：A.确定时间帧(调度周期):根据ASAP和ALAP算法确定某个操作的时间帧(即调度周期)。调度周期与设定的(或受约束的)总操作步数之比为该操作在当前控制步中的执行概率B.建立概率和分布图:首先求在每一步控制步中,每一种类型操作的执行概率之和,得到概率和的分布图,它表示了每一种相同操作的并行性C.计算“力”(force):计算某个操作可能调度到的各个控制步所对应的力,力的大小等于当前控制步的概率和时间帧内各控制步的平均概率和的差值。这样表示的力直接正比于额外的硬件花费。不均衡的概率和分布会造成较大的硬件花费,反映到力上是对应较大力的值。力的计算还应包括间接力,即在操作的当前控制步的前驱控制步和后继控制步对本操作影响时,计算前驱控制步和后继控制步的力。算出所有操作力之后,选择最小的力值的操作控制步作我们的结果。FDS算法的精确性好,但计算量较大2-3调度前的转换处理循环控制结构的处理分支控制结构的处理结构变换2-3-1循环控制结构的处理timecycletimesP1P2P3循环体执行时间timeP1P2P3控制步时间段EL(ExecutionLength)循环体执行时间循环过程完整处理一组采样数据所需要的控制步数目IL(InputdataLatency)循环体数据等待时间循环过程中两组采样数据处理过程起始节点时间之差等待时间非流水线设计方式执行速度快于采样速度IL≥EL流水线设计方式执行速度快于采样速度ILELcycletimes跨循环体（过程）的数据引用指在两组相邻数据处理过程中，前一组数据处理过程中的某个操作的输出被后一组数据处理过程中的另一个操作引用。612345798612345798反馈边非流水方式设计当IL≥EL时，操作间不存在跨循环体（过程）的数据引用，直接断开反馈边，将循环体展开进行调度612345798612345798流水线视察窗流水层1流水层2流水层3流水方式设计612345798612345798当采用流水线方式设计时，IL不能小于任意跨循环体（过程）的数据引用的两个操作的高度之差，以防止前一组操作没有为后一组操作准备好数据IL=3EL=62-3-2分支控制结构的处理:合并、移动互斥操作：不在同一条件下执行的两个操作E.g.2and3:同层不同分支8and4:不同层不同分支互斥操作不可能在同一条件下执行判断的基础是操作的条件向量的叉积或点积：操作的条件向量由各分支条件作为元素组成的向量，其维数为分支条件个数，各元素值∈{0,1,X}，其中：0：表示操作在该条件为假时执行1：表示操作在该条件为真时执行X：表示操作的执行与该条件无关关键在于合并互斥操作，以使其尽可能地共享功能单元局部合并法和全局合并法-+------++++++TFTFTFTFabcdev1v2v38123410511912613714操作条件向量操作条件向量1{0,X,X,X,X}8{1,X,X,X,X}2{