高层次综合ppt课件.ppt

高层次综合High Level Synthesis,陈付龙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,三类节点操作节点 表示抽象的操作运算传输节点 表示数据的传输结构接点起始节点 终结节点分支节点 汇聚节点两类边数据相关边控制相关边,起始节点,终结节点,Example,entity sample isport(in1,in2:in integer ;cond:in bit;fout:out integer;)end samplearchitecture behavior of sample isbegin process /*顺序执行的程序*/ variable v1,v2,v3:integer; v1:=in1; v2:=in2; while(v1v2)loop if(cond=1)then v3=:v1+v2; v2:=v1; else v3:=v1-v2; endif endloop fout=v3; end processend behavior,123456789,CDFD的数据结构,邻接矩阵邻接表,1-2转换：目的是对设计的行为描述进行优化,编译优化（最基本的转换）常量代入无用码删除公因子提取与公用表达式删除代码（操作）移动：分支操作移入（出）条件分支过程体展开循环展开针对专门硬件模块，将复杂的多周期操作转换成简单操作增加操作并行度减少CDFG图中关键路径和指定路径上的操作个数,常量代入和无用码删除,a:=2;c:=a+(4+b);,c,其它转换将在2-3节介绍,2调度,功能：将操作赋给控制步（control step）一个控制步是一个时序单位，对应若干时钟周期输入：CDFG数据流目的：在满足约束条件（size,speed,power）下，将操作赋给各控制步，以使给定目标函数（e.g.number of control steps,delay,power, resource,etc.)最小,2-1操作类型及操作的调度类型,单周期操作：一个控制步内完成单操作单周期（e.g.1）多操作单周期（链式，e.g.3，4）多周期操作（e.g.2）：多个控制步内完成,单周期操作调度,链式操作调度,多周期操作调度,+,*,+,-,1,2,4,3,cs1,cs2,2-2调度算法分类,依调度算法变换法(transformation)：首先找出一个初始调度方案，然后对其进行变换，即将操作从一个控制步移到另一个控制步(穷举法:分支定界法(branch and bound),启发式方法:模拟退火法(simulated annealing)构造法(constructive)：每次选一个操作进行调度, 直到所有的操作都调度完成(e.g.Listing Scheduling)依约束条件时间约束：在满足时间约束(操作步数或时钟周期)的条件下，以尽可能少的硬件资源来完成操作(e.g.ALAP)硬件资源约束：在满足硬件资源约束(面积，资源数目)的条件下，以尽可能短的时间来完成操作（e.g.LS）时间约束和硬件资源约束功耗约束可测性设计约束无约束(e.g.ASAP),变换法：example,cs 1,cs 2,cs 3,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,3 adders ,3 steps,3 adders ,2 steps,2 adders ,3 steps,典型调度算法（一）ASAP和ALAP,ASAP(as soon as possible)：无约束算法。它将所有操作赋予最早可能调度到的控制步中，将CDFG看作有向图时, 其中操作节点、起始和终止节点分别为有向图的的节点, 数据相关边作为有向图的有向边, 然后对该有向图进行正向分层排序。ALAP(as late as possible)：时间约束算法。它是将操作赋予可能最迟调度到的控制步中。其基本思路与ASAP 算法类似, 只是对有向图进行反向的分层排序。,ASAP,+,*,*,*,*,*,*,+,-,-,y,d,x,3,u,1,2,3,4,5,6,7,8,9,10,11,优点：简单，快速缺点：头重！无约束,ALAP,+,*,*,*,*,*,*,+,-,-,y,d,x,3,u,1,2,3,4,5,6,7,8,9,10,11,优点：简单，快速缺点：脚大！不一定做到满足约束时的最优,调整区间,典型调度算法（二）列表调度算法（list scheduling）,构造型，硬件资源约束(resource restriction) 就绪队列AQ(Active Queue )：存放当前控制步中可以执行的操作（其前趋已被调度，自己未被调度且“其前趋的控制步+其前趋的延迟当前cs”的操作）优先级函数pf (priority function)调整区间（最小优先）路径长度（自该操作到结束的最长延迟，最长优先）,+,*,*,*,*,*,*,+,-,-,1,2,3,4,5,6,7,8,9,10,11,cs1,cs2,cs3,cs4,cs5,cs6,cs7,rr:2 multiplication units,1 subtracter ,1 adder, 1 comparison unit pf :path length,5,AQ=3,4,5,6,1Select:3,4,1,AQ=5,6,2Select:2,AQ=7,5,6,Select:7,5,AQ=6Select:no,AQ=8,6,10Select:8,6,10,AQ=Select:no,AQ=11,9Select:11,9,1,2,3,4,6,7,优点：算法复杂性低O(n)，速度快 能在短时间内找到次优解缺点：不能进行时间约束下的调度,典型调度算法（三）力定向算法(Force- Directed Scheduling),构造型、基于时间约束基本思想：尽可能均匀地在硬件功能单元之间安排操作, 防止某些功能单元使用频繁, 而另外一些功能单元大部分时间闲置, 以便提高功能单元的总体使用效率和降低硬件成本算法：确定时间帧(调度周期):根据ASA P 和ALAP算法确定某个操作的时间帧(即调度周期)。调度周期与设定的(或受约束的) 总操作步数之比为该操作在当前控制步中的执行概率 建立概率和分布图:首先求在每一步控制步中, 每一种类型操作的执行概率之和, 得到概率和的分布图, 它表示了每一种相同操作的并行性 计算“力”(force):计算某个操作可能调度到的各个控制步所对应的力, 力的大小等于当前控制步的概率和时间帧内各控制步的平均概率和的差值。这样表示的力直接正比于额外的硬件花费。不均衡的概率和分布会造成较大的硬件花费, 反映到力上是对应较大力的值。力的计算还应包括间接力, 即在操作的当前控制步的前驱控制步和后继控制步对本操作影响时, 计算前驱控制步和后继控制步的力。算出所有操作力之后, 选择最小的力值的操作控制步作我们的结果。,FDS 算法的精确性好, 但计算量较大,2-3调度前的转换处理,循环控制结构的处理分支控制结构的处理结构变换,2-3-1循环控制结构的处理,time,cycle times,P1,P2,P3,循环体执行时间,time,P1,P2,P3,控制步时间段,EL(Execution Length)循环体执行时间循环过程完整处理一组采样数据所需要的控制步数目IL(Input data Latency)循环体数据等待时间循环过程中两组采样数据处理过程起始节点时间之差,等待时间,非流水线设计方式执行速度快于采样速度ILEL,流水线设计方式执行速度快于采样速度ILEL,cycle times,跨循环体（过程）的数据引用,指在两组相邻数据处理过程中，前一组数据处理过程中的某个操作的输出被后一组数据处理过程中的另一个操作引用。,反馈边,非流水方式设计,当ILEL时，操作间不存在跨循环体（过程）的数据引用，直接断开反馈边，将循环体展开进行调度,6,1,2,3,4,5,7,9,8,6,1,2,3,4,5,7,9,8,流水方式设计,6,1,2,3,4,5,7,9,8,6,1,2,3,4,5,7,9,8,当采用流水线方式设计时，IL不能小于任意跨循环体（过程）的数据引用的两个操作的高度之差，以防止前一组操作没有为后一组操作准备好数据,IL=3,EL=6,2-3-2分支控制结构的处理:合并、移动,互斥操作：不在同一条件下执行的两个操作E.g.2 and 3:同层不同分支8 and 4:不同层不同分支互斥操作不可能在同一条件下执行判断的基础是操作的条件向量的叉积或点积：操作的条件向量由各分支条件作为元素组成的向量，其维数为分支条件个数，各元素值0,1,X，其中：0：表示操作在该条件为假时执行1：表示操作在该条件为真时执行X：表示操作的执行与该条件无关关键在于合并互斥操作，以使其尽可能地共享功能单元局部合并法和全局合并法,-,+,-,-,-,-,-,-,+,+,+,+,+,+,T,F,T,F,T,F,T,F,a,b,c,d,e,v1,v2,v3,8,1,2,3,4,10,5,11,9,12,6,13,7,14,条件向量a,b,c,d,e,局部合并法规则1.（1）从带有嵌套分支结构的最内层分支结构开始，逐层向外进行分支操作的合并处理，（2）或者根据操作间的条件向量的叉积来判断是否为互斥操作，来进行合并2.两个仅被条件分支内操作引用的变量可以合并，而一个被分支外操作引用的变量不能与一个仅被分支内引用的变量合并3.常用穷举法或启发式策略进行,局部合并法中互斥操作的判定,设两个相同类型的操作op1和op2，其条件向量为n维，分别为cv1和cv2，通过叉积运算来判断两个同类型操作是否互斥若cv1(i)cv2(i)的结果中除了0，1，X外，有且仅有一个q,则cv=cv1cv2,其中cv1(i)cv2(i)=q时，cv(i)=Xcv1(i)cv2(i)q时，cv(i)= cv1(i)cv2(i)否则，cv=若条件向量的运算结果为 ，则两个操作不互斥；否则，它们是互斥操作，可以按互斥操作合并处理,cv1(i),cv2(i),cv (i),条件向量的叉积运算规则,e.g.cv12 =1,0,X,X,1,cv13=1,0,X,X,1, cv12cv13=1,0,X,X,q,cv=1,0,X,X,X,互斥,可以合并cv13=1,0,X,X,0,cv14=1,X,X,X,X, cv13 cv14=1,m,X,X,m,cv=，不互斥,不可合并cv5=1,1,X,1,X,cv12=1,0,X,X,1, cv5cv12=q,q,X,X,X,cv= ,不互斥,不可合并,v3,10,CDFG,合并c,d,e,合并c,d,e,合并b,v3,v3,合并b,局部合并法的缺点,合并时没有考虑操作移入或移出分支，不能合并在不同层次上的不同分分支操作,全局合并法,统一考虑各嵌套层次条件分支上互斥操作的合并，以便充分共享功能单元,全局合并法中互斥操作的判定,设两个相同类型的操作op1和op2，其条件向量为n维，分别为cv1和cv2，通过点积运算来判断两个同类型操作是否互斥若cv1(i)cv2(i)的结果出现q,则cv=cv1cv2,其中cv1(i)cv2(i)=q时，cv(i)=Xcv1(i)cv2(i)q时，cv(i)= cv1(i)cv2(i)否则，cv=若条件向量的运算结果为 ，则两个操作不互斥；否则，它们是互斥操作，可以按互斥操作合并处理,cv1(i),cv2(i),cv (i),点积运算规则,e.g.cv12 =1,0,X,X,1,cv13=1,0,X,X,1, cv12 cv13=1,0,X,X,q,cv=1,0,X,X,X,互斥，可以合并cv13=1,0,X,X,0,cv14=1,X,X,X,X, cv13 cv14=1,X,X,X,X,cv=，不互斥，不可合并cv5=1,1,X,1,X,cv12=1,0,X,X,1, cv5 cv12=1,q,X,X,X,cv=1,X,X,X,X,互斥,可以合并,合并操作可能带来的问题路径长度的增加,+,-,+,-,1,2,3,4,CDFG,分支操作移动,CDFG中，操作的顺序严格遵循数据相关性关系，但除汇聚节点附近的反馈边（用于循环控制）外的其它控制相关性关系，并不严格地规定操作的顺序，所以条件分支上操作可以移出条件分支条件分支外操作可以移入条件分支目的：减少所需控制步数目,条件分支上操作移出条件分支,指条件分支上的操作可以在分支条件确定前执行（当然，有可能执行的结果无用）,1 个+,1个(-,):6步,条件分支外操作移入条件分支,须保证不论分支条件取值如何，都要在条件分支上执行，即将分支外操作复制到每个条件分支上。移入的操作分别与条件分支中的其它操作进行互斥操作的资源共享，从而在不增加硬件资源的条件下达到减少控制步数的目的。,+,-,-,+,-,+,+,-,1,9,2,5,3,6,4,7,8,1 个+,1个(-,):5步,条件分支外操作移入条件分支的原则：（1）操作的移入不能增加条件分支的长度；（2）操作的移入不能引起硬件资源的冲突。,2-3-3结构变换关键路径优化,根据算术操作与逻辑操作的结合律和分配律，在满足硬件资源约束条件和不改变CDFG语义的基础上，将CDFG关键路径上的操作转换到相关非关键路径上去，以减少关键路径上的操作个数，提高系统速度。两种主要变换规则：结合律的变换规则；分配律的变换规则,结合律的变换规则,结合律的变换只影响CDFG的局部结构,a,b,c,I,a,c,b,II,b,II,a,c,变换操作类型可能引起硬件资源需求变化,分配律的变换规则,a,b,阴影部分为关键路径,引用变量问题,控制步i,a,b,c,引用变量,定义变量,当一个变量在某一个控制步中定义，则该变量在其后的控制步中称为可用变量理想情况：引用变量总是可用变量实际情况：引用变量不总是可用变量,操作的输出变量被其它操作所引用问题(1),当两个操作满足结合律变换条件，但是，由于操作1的输出不仅被操作2引用，还被其它操作引用，若直接进行结合律变换，会破坏原有数据相关性，此时，可先复制操作1，然后变换,a,b,c,1,2,3,经过复制后，CDFG中操作个数增加了，可能增大硬件资源需求，但如果增加的操作不会增大同时执行操作的操作数目，则不会导致硬件资源需求增加e.g.,操作的输出变量被其它操作所引用问题(2),*,+,+,*,*,a,b,c,d,e,x,y,1 adder,2 multiplications,3（数据通路）分配,功能：（1）将操作赋给相应的功能单元运算，（2）将变量（值）赋给相应的存储单元进行存放，（3）将数据传输通道赋给相应的硬件进行数据传输输入：数据流输出：控制流和数据通路目的：建立一个功能块级模块组成的数据通路，使所占用的硬件资源（功能单元，存储单元，互连线网）花费最少，尽量共享,数据通路基本硬件模块,功能单元存储单元互连线网,and,FU,register,memory,in,out,in,in,data,address,out,out,out,select,enable,enable,in,out,select,multiplexer,bus,select,in,out,分配与调度的关系,调度过程影响执行速度、响应延迟等时间特性和硬件资源费用等空间特性，分配过程则只对硬件资源费用起决定作用，尽可能降低硬件成本调度结果是分配过程的约束和输入,变量的生存期：变量从产生到最后一次被引用之间的控制步,d,u,+,*,*,*,*,*,*,+,-,-,1,2,3,4,5,6,7,8,9,10,11,cs1,cs2,cs3,cs4,cs5,cs6,cs7,x,y,a,*括号中数字表示两次相邻循环的轮次,分配算法,启发式分配算法每次选取一个待分配的元素，将它赋给相应硬件单元，在元素选取过程中用启发式策略模拟退火贪婪全局费用函数线性规划方法(Linear Programming)将分配问题形式化为线性规划问题求解01线性规划混合整数线性规划(mixed integer linear programming)整数规划图论算法团规划算法(clique partitioning)图着色算法(Node Coloring)二部图匹配算法,图着色算法,I利用冲突图来分配操作II利用冲突图来分配变量III分配互连线路IV分配控制器的输出信号,I利用冲突图来分配操作,根据调度结果，建立操作的冲突图进行冲突图着色根据冲突图中节点的颜色，分组并给操作分配功能单元,操作冲突图由二元式组成：G=(V,E)V=opi ，E=(opi, opj)| opi与 opj非互斥且调度到同一控制步中,3,2,1,4,5,7,6,10,8,11,9,y,d,操作冲突图着色在冲突图中任取一个未着色的节点；对该点着以与其相邻已着色点不同的颜色；重复，直到所有节点均着色,分配,1,2,10,11=+,-3,5,6,9=*,+4,7,8=*,II利用冲突图来分配变量,根据调度结果，建立变量生存期表建立变量的冲突图对冲突图着色根据冲突图中节点的颜色，分组并给变量分配存储单元,建立变量的冲突图由二元式组成：G=(V,E)V=变量vi ，E=(vi, vj)| vi与 vj非互斥且其生存期重叠,根据调度结果，建立变量生存期表,因a,d,x始终存在，故与所有变量均冲突,对冲突图着色在冲突图中任取一个未着色的节点；对该点着以与其相邻已着色点不同的颜色；重复，直到所有节点均着色,分配,III分配互连线路,对每个功能单元和存储单元的各个输入端口，重复如下步骤：若连线个数m大于1，分配一个m输入端的多路器；将m根连线分别连接在多路器的m个输入端上；将多路器的输出连接在功能单元或存储单元的输入端口上总线的分配可在多路器分配前或后，根据某些（经验）规则将相关的连线合并成总线,综上，产生如下数据通路,M1,M2,M3,M4,M5,M6,R2,R3,R1,R4,R6,R5,R7,3,a,d,y,x,Ctrl,不含控制信号的数据通路,IV分配控制器的输出信号,控制器的输出信号包括功能单元在每个控制步执行哪些操作；哪些存储单元加载；每个多路器的哪个输入端数据被选中,信号：X=不顾功能单元：1=启动寄存器：0=保持，1=加载多路器：0=左，1=右，2=中间,基于图着色的分配方法结论,能够保证功能单元和寄存器的需求量最小该算法对功能单元的分配和对寄存器的分配是相互独立的，没有考虑相互影响,4控制器综合,功能：综合按调度要求驱动数据通路的控制器输入：控制流输出：硬连逻辑或微程序方法：硬连线：有限状态机固件：微程序（一个控制步=一条微指令）,example,Step 1MUX(1)FU(+)R1(w),Step 2MUX(2)FU(-)R2(w),R1,R2,R3,MUX,1,2,controller,data path,FU(+,-),5结果生成与反编译,功能：将设计转换成硬件结构的物理实现输入：控制器：硬连逻辑或微程序数据通路功能单元存储单元互连线网输出：结构描述目的：产生低层次设计工具可接受的结果格式（结构描述）,6相关研究,AT 专用微处理器综合路径。IBM HIS SystemIMES的 CATHEDRAL - II 系统Stanford 大学的Olympus System台湾清华大学的ALPS/LYRA/ARYL System,商用系统,Synopsys 公司的Behavioral Compiler可以完成调度、分配、生成RTL 级的HDL 代码, 支持多周期操作、链接操作、流水线、先机执行和FSM 设计, 特别是进行多模式的I/O 设计;Cadence公司的Visual Architecture 可以完成调度、分配、生成RTL 级的HDL代码, 支持多周期操作、链接操作和流水线, 可接受资源和时间(调度步数、时钟周期) 约束条件。,7总结,高层次综合的主要问题（调度，分配）已得到较好解决还有有许多问题未解决设计空间的有效搜索算法异步系统（接口电路）的设计系统划分（划分为相关过程）人的因素在高层次综合中的作用（如专家干预）高层次综合的可测性设计高层次综合与逻辑综合的衔接高层次综合不如逻辑综合具有完整的理论基础,THE END,Thank you,