高層次綜合課件

高層次綜合

HighLevelSynthesis陳付龍2005-11-23高層次綜合

HighLevelSynthesis陳付龍1參考文獻(xiàn)薛宏熙，邊計(jì)年，蘇明.數(shù)字系統(tǒng)設(shè)計(jì)自動化[M].北京：清華大學(xué)出版社，1996年10月李德新，周祖成.高層次綜合[J].電子技術(shù)應(yīng)用，1998年第3期蘇明.高層次綜合算法及其系統(tǒng)研究.北京：清華大學(xué)博士學(xué)位論文，1993參考文獻(xiàn)薛宏熙，邊計(jì)年，蘇明.數(shù)字系統(tǒng)設(shè)計(jì)自動化[M].北京2主要內(nèi)容0概述：任務(wù)和內(nèi)容1編譯與轉(zhuǎn)換：編譯方法和轉(zhuǎn)換方法2調(diào)度：ASAP，ALAP，LS算法3分配：圖著色算法4控制器綜合5結(jié)果生成與反編譯6相關(guān)研究7總結(jié)主要內(nèi)容0概述：任務(wù)和內(nèi)容30概述——

高層次綜合與系統(tǒng)描述的關(guān)系算法級寄存器傳輸級邏輯級電路級版圖級行為特性物理特性結(jié)構(gòu)特性高層次綜合：從算法級的行為描述到實(shí)現(xiàn)它的寄存器傳輸級的結(jié)構(gòu)描述的綜合邏輯綜合版圖綜合0概述——

高層次綜合與系統(tǒng)描述的關(guān)系算法級寄存器傳輸級邏4高層次綜合的任務(wù)找出一個滿足約束條件和目標(biāo)集合、花費(fèi)最少的硬件結(jié)構(gòu)高層次綜合的優(yōu)點(diǎn)提高設(shè)計(jì)速度，縮短設(shè)計(jì)周期描述簡潔，容易編寫、理解，貼近自然語言，描述錯誤少且容易修改高層次綜合的任務(wù)5高層次綜合內(nèi)容調(diào)度編譯與轉(zhuǎn)換反編譯分配控制器綜合功能單元庫設(shè)計(jì)約束(時鐘周期,操作步數(shù)(周期數(shù)),設(shè)計(jì)吞吐量,硬件資源的最大數(shù)目、面積、最大功耗等)中間表示格式數(shù)據(jù)流控制流數(shù)據(jù)通路硬連邏輯或微程序給有限狀態(tài)機(jī)綜合與邏輯綜合結(jié)構(gòu)描述給文檔管理或其它邏輯綜合工具算法描述高層次綜合內(nèi)容調(diào)度編譯與轉(zhuǎn)換反編譯分配控制器綜合功能單元庫設(shè)61編譯與轉(zhuǎn)換編譯：轉(zhuǎn)換：優(yōu)化編譯邏輯級以上行為描述數(shù)據(jù)流和控制流語法分析圖（樹）1編譯與轉(zhuǎn)換編譯：編譯邏輯級以上數(shù)據(jù)流和控制流71-1編譯：生成控制數(shù)據(jù)流圖CDFG三類節(jié)點(diǎn)操作節(jié)點(diǎn)表示抽象的操作運(yùn)算傳輸節(jié)點(diǎn)表示數(shù)據(jù)的傳輸結(jié)構(gòu)接點(diǎn)起始節(jié)點(diǎn)終結(jié)節(jié)點(diǎn)分支節(jié)點(diǎn)匯聚節(jié)點(diǎn)兩類邊數(shù)據(jù)相關(guān)邊控制相關(guān)邊起始節(jié)點(diǎn)終結(jié)節(jié)點(diǎn)1-1編譯：生成控制數(shù)據(jù)流圖CDFG三類節(jié)點(diǎn)起始節(jié)點(diǎn)終結(jié)節(jié)點(diǎn)8Exampleentitysampleisport(in1,in2:ininteger;cond:inbit;fout:outinteger;)endsamplearchitecturebehaviorofsampleisbeginprocess/*順序執(zhí)行的程序*/variablev1,v2,v3:integer;v1:=in1;v2:=in2;while(v1<v2)loopif(cond=‘1’)thenv3=:v1+v2;v2:=v1;elsev3:=v1-v2;endifendloopfout<=v3;endprocessendbehavior123456

7

89‘1’in2in1cond<=<:==-+:=:=v1v2v3fout(v1<v2)┓(v1<v2)(cond=‘1’)┓(cond=‘1’)beginendExampleentitysampleis1‘1’in29CDFD的數(shù)據(jù)結(jié)構(gòu)鄰接矩陣鄰接表CDFD的數(shù)據(jù)結(jié)構(gòu)鄰接矩陣101-2轉(zhuǎn)換：目的是對設(shè)計(jì)的行為描述進(jìn)行優(yōu)化編譯優(yōu)化（最基本的轉(zhuǎn)換）常量代入無用碼刪除公因子提取與公用表達(dá)式刪除代碼（操作）移動：分支操作移入（出）條件分支過程體展開循環(huán)展開針對專門硬件模塊，將復(fù)雜的多周期操作轉(zhuǎn)換成簡單操作增加操作并行度減少CDFG圖中關(guān)鍵路徑和指定路徑上的操作個數(shù)1-2轉(zhuǎn)換：目的是對設(shè)計(jì)的行為描述進(jìn)行優(yōu)化編譯優(yōu)化（最基本的11常量代入和無用碼刪除：=++a24b123a:=2;c:=a+(4+b);c：=++4b22a123c常量代入無用碼刪除×其它轉(zhuǎn)換將在2-3節(jié)介紹常量代入和無用碼刪除：=++a24b123a:=2;c：=+122調(diào)度功能：將操作賦給控制步（controlstep）一個控制步是一個時序單位，對應(yīng)若干時鐘周期輸入：CDFG數(shù)據(jù)流目的：在滿足約束條件（size,speed,power）下，將操作賦給各控制步，以使給定目標(biāo)函數(shù)（e.g.numberofcontrolsteps,delay,power,resource,etc.)最小2調(diào)度功能：將操作賦給控制步（controlstep）132-1操作類型及操作的調(diào)度類型單周期操作：一個控制步內(nèi)完成單操作單周期（e.g.1）多操作單周期（鏈?zhǔn)?，e.g.3，4）多周期操作（e.g.2）：多個控制步內(nèi)完成

單周期操作調(diào)度鏈?zhǔn)讲僮髡{(diào)度多周期操作調(diào)度+*+-1243cs1cs22-1操作類型及操作的調(diào)度類型單周期操作：一個控制步內(nèi)完成單142-2調(diào)度算法分類依調(diào)度算法變換法(transformation)：首先找出一個初始調(diào)度方案，然后對其進(jìn)行變換，即將操作從一個控制步移到另一個控制步(窮舉法:分支定界法(branchandbound),啟發(fā)式方法:模擬退火法(simulatedannealing))構(gòu)造法(constructive)：每次選一個操作進(jìn)行調(diào)度,直到所有的操作都調(diào)度完成(e.g.ListingScheduling)依約束條件時間約束：在滿足時間約束(操作步數(shù)或時鐘周期)的條件下，以盡可能少的硬件資源來完成操作(e.g.ALAP)硬件資源約束：在滿足硬件資源約束(面積，資源數(shù)目)的條件下，以盡可能短的時間來完成操作（e.g.LS）時間約束和硬件資源約束功耗約束可測性設(shè)計(jì)約束無約束(e.g.ASAP)2-2調(diào)度算法分類依調(diào)度算法15變換法：examplecs1cs2cs3++++++++++++++++++1234561234561234563adders,3steps3adders,2steps2adders,3steps變換法：examplecs1cs2cs3+++++++16典型調(diào)度算法（一）

ASAP和ALAP

ASAP(assoonaspossible)：無約束算法。它將所有操作賦予最早可能調(diào)度到的控制步中，將CDFG看作有向圖時,其中操作節(jié)點(diǎn)、起始和終止節(jié)點(diǎn)分別為有向圖的的節(jié)點(diǎn),數(shù)據(jù)相關(guān)邊作為有向圖的有向邊,然后對該有向圖進(jìn)行正向分層排序。ALAP(aslateaspossible)：時間約束算法。它是將操作賦予可能最遲調(diào)度到的控制步中。其基本思路與ASAP

算法類似,只是對有向圖進(jìn)行反向的分層排序。典型調(diào)度算法（一）

ASAP和ALAP

ASAP(asso17ASAPASAP18+******<+--ydx3u1234567891011+******<+--1234567891011cs1cs2cs3cs4cs5cs6優(yōu)點(diǎn)：簡單，快速缺點(diǎn)：頭重！無約束+******<+--ydx3u1234567891011+19ALAPALAP20+******<+--ydx3u1234567891011+******<+--1234567891011cs1cs2cs3cs4cs5cs6優(yōu)點(diǎn)：簡單，快速缺點(diǎn)：腳大！不一定做到滿足約束時的最優(yōu)+******<+--ydx3u1234567891011+21+******<+--1234567891011cs1cs2cs3cs4cs5cs6ASAP+******<+--1234567891011cs1cs2cs3cs4cs5cs6ALAP調(diào)整區(qū)間+******<+--1234567891011cs1cs222典型調(diào)度算法（二）

列表調(diào)度算法

（listscheduling）

構(gòu)造型，硬件資源約束

(resourcerestriction)就緒隊(duì)列AQ(ActiveQueue)：存放當(dāng)前控制步中可以執(zhí)行的操作（其前趨已被調(diào)度，自己未被調(diào)度且“其前趨的控制步+其前趨的延遲≤當(dāng)前cs”的操作）優(yōu)先級函數(shù)pf(priorityfunction)調(diào)整區(qū)間（最小優(yōu)先）路徑長度（自該操作到結(jié)束的最長延遲，最長優(yōu)先）設(shè)cs1為當(dāng)前cs建立AQ，按pf排序取AQ中pf最高的操作調(diào)度到cs修改AQcs←cs+1AQ中有滿足rr的操作YN有操作未調(diào)度？YNendbegin典型調(diào)度算法（二）

列表調(diào)度算法

（listschedul23+******<+--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優(yōu)點(diǎn)：算法復(fù)雜性低O(n)，速度快 能在短時間內(nèi)找到次優(yōu)解缺點(diǎn)：不能進(jìn)行時間約束下的調(diào)度+******<+--1234567891011cs1cs224典型調(diào)度算法（三）

力定向算法(Force-DirectedScheduling)構(gòu)造型、基于時間約束基本思想：盡可能均勻地在硬件功能單元之間安排操作,防止某些功能單元使用頻繁,而另外一些功能單元大部分時間閑置,以便提高功能單元的總體使用效率和降低硬件成本算法：確定時間幀(調(diào)度周期):根據(jù)ASAP和ALAP算法確定某個操作的時間幀(即調(diào)度周期)。調(diào)度周期與設(shè)定的(或受約束的)總操作步數(shù)之比為該操作在當(dāng)前控制步中的執(zhí)行概率

建立概率和分布圖:首先求在每一步控制步中,每一種類型操作的執(zhí)行概率之和,得到概率和的分布圖,它表示了每一種相同操作的并行性

計(jì)算“力”(force):計(jì)算某個操作可能調(diào)度到的各個控制步所對應(yīng)的力,力的大小等于當(dāng)前控制步的概率和時間幀內(nèi)各控制步的平均概率和的差值。這樣表示的力直接正比于額外的硬件花費(fèi)。不均衡的概率和分布會造成較大的硬件花費(fèi),反映到力上是對應(yīng)較大力的值。力的計(jì)算還應(yīng)包括間接力,即在操作的當(dāng)前控制步的前驅(qū)控制步和后繼控制步對本操作影響時,計(jì)算前驅(qū)控制步和后繼控制步的力。算出所有操作力之后,選擇最小的力值的操作控制步作我們的結(jié)果。FDS算法的精確性好,但計(jì)算量較大

典型調(diào)度算法（三）

力定向算法(Force-Directe252-3調(diào)度前的轉(zhuǎn)換處理循環(huán)控制結(jié)構(gòu)的處理分支控制結(jié)構(gòu)的處理結(jié)構(gòu)變換2-3調(diào)度前的轉(zhuǎn)換處理循環(huán)控制結(jié)構(gòu)的處理262-3-1循環(huán)控制結(jié)構(gòu)的處理timecycletimesP1P2P3循環(huán)體執(zhí)行時間timeP1P2P3控制步時間段EL(ExecutionLength)循環(huán)體執(zhí)行時間 循環(huán)過程完整處理一組采樣數(shù)據(jù)所需要的控制步數(shù)目IL(InputdataLatency)循環(huán)體數(shù)據(jù)等待時間 循環(huán)過程中兩組采樣數(shù)據(jù)處理過程起始節(jié)點(diǎn)時間之差等待時間非流水線設(shè)計(jì)方式執(zhí)行速度快于采樣速度IL≥EL流水線設(shè)計(jì)方式執(zhí)行速度快于采樣速度IL<ELcycletimes2-3-1循環(huán)控制結(jié)構(gòu)的處理timecycletimesP27跨循環(huán)體（過程）的數(shù)據(jù)引用指在兩組相鄰數(shù)據(jù)處理過程中，前一組數(shù)據(jù)處理過程中的某個操作的輸出被后一組數(shù)據(jù)處理過程中的另一個操作引用。612345798612345798反饋邊跨循環(huán)體（過程）的數(shù)據(jù)引用指在兩組相鄰數(shù)據(jù)處理過程中，前一組28非流水方式設(shè)計(jì)當(dāng)IL≥EL時，操作間不存在跨循環(huán)體（過程）的數(shù)據(jù)引用，直接斷開反饋邊，將循環(huán)體展開進(jìn)行調(diào)度612345798612345798非流水方式設(shè)計(jì)當(dāng)IL≥EL時，操作間不存在跨循環(huán)體（過程）的29流水線視察窗流水層1流水層2流水層3流水方式設(shè)計(jì)612345798612345798當(dāng)采用流水線方式設(shè)計(jì)時，IL不能小于任意跨循環(huán)體（過程）的數(shù)據(jù)引用的兩個操作的高度之差，以防止前一組操作沒有為后一組操作準(zhǔn)備好數(shù)據(jù)IL=3EL=6流水線流水層1流水層2流水層3流水方式設(shè)計(jì)612345798302-3-2分支控制結(jié)構(gòu)的處理:合并、移動互斥操作：不在同一條件下執(zhí)行的兩個操作E.g.2and3:同層不同分支8and4:不同層不同分支互斥操作不可能在同一條件下執(zhí)行判斷的基礎(chǔ)是操作的條件向量的叉積或點(diǎn)積：操作的條件向量由各分支條件作為元素組成的向量，其維數(shù)為分支條件個數(shù)，各元素值∈{0,1,X}，其中：0：表示操作在該條件為假時執(zhí)行1：表示操作在該條件為真時執(zhí)行X：表示操作的執(zhí)行與該條件無關(guān)關(guān)鍵在于合并互斥操作，以使其盡可能地共享功能單元局部合并法和全局合并法2-3-2分支控制結(jié)構(gòu)的處理:合并、移動互斥操作：不在同一條31-+------++++++TFTFTFTFabcdev1v2v38123410511912613714操作條件向量操作條件向量1{0,X,X,X,X}8{1,X,X,X,X}2{1,1,X,X,X}9{1,0,X,X,X}3{1,0,X,X,X}10{0,0,X,X,X}4{0,1,X,X,X}11{1,1,X,0,X}5{1,1,X,1,X}12{1,0,X,X,1}6{1,0,X,X,0}13{1,0,X,X,0}7{1,0,X,X,X}14{1,X,X,X,X}條件向量{a,b,c,d,e}-+------++++++TFTFTFTFabcdev1v32局部合并法規(guī)則1.（1）從帶有嵌套分支結(jié)構(gòu)的最內(nèi)層分支結(jié)構(gòu)開始，逐層向外進(jìn)行分支操作的合并處理，（2）或者根據(jù)操作間的條件向量的叉積來判斷是否為互斥操作，來進(jìn)行合并2.兩個僅被條件分支內(nèi)操作引用的變量可以合并，而一個被分支外操作引用的變量不能與一個僅被分支內(nèi)引用的變量合并3.常用窮舉法或啟發(fā)式策略進(jìn)行局部合并法規(guī)則33局部合并法中互斥操作的判定設(shè)兩個相同類型的操作op1和op2，其條件向量為n維，分別為cv1和cv2，通過叉積運(yùn)算來判斷兩個同類型操作是否互斥若cv1(i)×cv2(i)的結(jié)果中除了0，1，X外，有且僅有一個q,則cv=cv1×cv2,其中cv1(i)×cv2(i)=q時，cv(i)=Xcv1(i)×cv2(i)≠q時，cv(i)=cv1(i)×cv2(i)否則，cv=φ若條件向量的運(yùn)算結(jié)果為φ，則兩個操作不互斥；否則，它們是互斥操作，可以按互斥操作合并處理局部合并法中互斥操作的判定設(shè)兩個相同類型的操作op1和op23401X01X0qmq1mmmXcv1(i)cv2(i)cv(i)條件向量的叉積運(yùn)算規(guī)則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,m,X,X,m},cv=Φ，不互斥,不可合并cv5={1,1,X,1,X},cv12={1,0,X,X,1},

cv5×cv12={q,q,X,X,X},cv=Φ,不互斥,不可合并01X0035v310d-+------++++++TFTFFTFabcev1v2v38123410511912613714TFTCDFG-+------+++++TFTFabv1v28123451196{12,13}714合并c,d,ev310d-+------++++++TFTFFTFabce36-+------+++++TFTFabv1v28123451196{12,13}714合并c,d,e1-+----++++TFav1v28{2,3}411{5,9}6{12,13}{7,11}14合并bv3v3-+------+++++TFTFabv1v28123451371-+----++++TFav1v28{2,3}411{5,9}6{12,13}{7,11}14合并b+---++v1v28{1,2,3}6{12,13}{7,10,11}{4,14}{5,9}+合并a1-+----++++TFav1v28{2,3}411{5,38局部合并法的缺點(diǎn)合并時沒有考慮操作移入或移出分支，不能合并在不同層次上的不同分分支操作局部合并法的缺點(diǎn)合并時沒有考慮操作移入或移出分支，不能合并在39全局合并法統(tǒng)一考慮各嵌套層次條件分支上互斥操作的合并，以便充分共享功能單元全局合并法40全局合并法中互斥操作的判定設(shè)兩個相同類型的操作op1和op2，其條件向量為n維，分別為cv1和cv2，通過點(diǎn)積運(yùn)算來判斷兩個同類型操作是否互斥若cv1(i)·cv2(i)的結(jié)果出現(xiàn)q,則cv=cv1·cv2,

其中cv1(i)·cv2(i)=q時，cv(i)=Xcv1(i)·cv2(i)≠q時，cv(i)=cv1(i)·cv2(i)否則，cv=φ若條件向量的運(yùn)算結(jié)果為φ，則兩個操作不互斥；否則，它們是互斥操作，可以按互斥操作合并處理全局合并法中互斥操作的判定設(shè)兩個相同類型的操作op1和op24101X01X0qXq1XXXXcv1(i)cv2(i)cv(i)點(diǎn)積運(yùn)算規(guī)則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},互斥,可以合并01X0042合并操作可能帶來的問題——路徑長度的增加+-+-1234+-+1{2，3}4Scheme1:1adder,1subtracter+/-+/-{1,3}{2，4}Scheme2:1ALUCDFG合并操作可能帶來的問題——路徑長度的增加+-+-1234+-43分支操作移動CDFG中，操作的順序嚴(yán)格遵循數(shù)據(jù)相關(guān)性關(guān)系，但除匯聚節(jié)點(diǎn)附近的反饋邊（用于循環(huán)控制）外的其它控制相關(guān)性關(guān)系，并不嚴(yán)格地規(guī)定操作的順序，所以條件分支上操作可以移出條件分支條件分支外操作可以移入條件分支目的：減少所需控制步數(shù)目分支操作移動CDFG中，操作的順序嚴(yán)格遵循數(shù)據(jù)相關(guān)性關(guān)系，但44條件分支上操作移出條件分支

指條件分支上的操作可以在分支條件確定前執(zhí)行（當(dāng)然，有可能執(zhí)行的結(jié)果無用）+->-+-++-1925364781個+,1個(-,>):6步+->-+-++-192536478操作5和6的相應(yīng)條件向量為X1個+,1個(-,>):5步條件分支上操作移出條件分支

指條件分支上的操作可以在分支條件45條件分支外操作移入條件分支須保證不論分支條件取值如何，都要在條件分支上執(zhí)行，即將分支外操作復(fù)制到每個條件分支上。移入的操作分別與條件分支中的其它操作進(jìn)行互斥操作的資源共享，從而在不增加硬件資源的條件下達(dá)到減少控制步數(shù)的目的。條件分支外操作移入條件分支須保證不論分支條件取值如何，都要在46+->-+-++-1925364781個+,1個(-,>):5步9-+>-+-++-12536478-10操作10為9的復(fù)制，相應(yīng)條件向量分別為0和1，{9，7}共享+,{4,10}共享(-,>)1個+,1個(-,>):4步條件分支外操作移入條件分支的原則：（1）操作的移入不能增加條件分支的長度；

（2）操作的移入不能引起硬件資源的沖突。+->-+-++-1925364781個+,1個(-,>)472-3-3結(jié)構(gòu)變換——關(guān)鍵路徑優(yōu)化根據(jù)算術(shù)操作與邏輯操作的結(jié)合律和分配律，在滿足硬件資源約束條件和不改變CDFG語義的基礎(chǔ)上，將CDFG關(guān)鍵路徑上的操作轉(zhuǎn)換到相關(guān)非關(guān)鍵路徑上去，以減少關(guān)鍵路徑上的操作個數(shù)，提高系統(tǒng)速度。兩種主要變換規(guī)則：結(jié)合律的變換規(guī)則；分配律的變換規(guī)則2-3-3結(jié)構(gòu)變換——關(guān)鍵路徑優(yōu)化根據(jù)算術(shù)操作與邏輯操作的結(jié)48結(jié)合律的變換規(guī)則類型IIIIII1a+(b+c)(a+c)+b(a+b)+c2a*(b*c)(a*c)*b(a*b)*c3a+(b-c)(a-c)+b(a+b)-c4a*(b/c)(a/c)*b(a*b)/c5a-(b-c)(a+c)-b(a-b)+c6a/(b/c)(a*c)/b(a/b)*c7a-(b+c)(a-c)-c(a-b)-c8a/(b*c)(a/c)/b(a/b)/c結(jié)合律的變換只影響CDFG的局部結(jié)構(gòu)abcIacbIIbIIac結(jié)合律的變換規(guī)則類型IIIIII1a+(b+c)(a+c)+49變換操作類型可能引起硬件資源需求變化--+-abcdef1adder,2subtraterscdf-++-abe1adder,1subtraterd----abcef2subtracters變換操作類型可能引起硬件資源需求變化--+-abcdef150分配律的變換規(guī)則類型III1(a+b)*ca*c+b*c2(a-b)*ca*c-b*c3(a+b)/ca/c+b/c4(a-b)/ca/c-b/c正變換逆變換IIIab陰影部分為關(guān)鍵路徑+*+cdd*++abc**++abcd*分配律的變換規(guī)則類型III1(a+b)*ca*c+b*c2(51引用變量問題控制步iabc引用變量定義變量當(dāng)一個變量在某一個控制步中定義，則該變量在其后的控制步中稱為可用變量理想情況：引用變量總是可用變量實(shí)際情況：引用變量不總是可用變量IacbIIbIIIacabce.g.當(dāng)(I)中a,(II)中b,(III)中c在控制步I中可用，三種形式方等價(jià)引用變量問題控制步iabc引用變量定義變量當(dāng)一個變量在某一個52操作的輸出變量被其它操作所引用問題(1)當(dāng)兩個操作滿足結(jié)合律變換條件，但是，由于操作1的輸出不僅被操作2引用，還被其它操作引用，若直接進(jìn)行結(jié)合律變換，會破壞原有數(shù)據(jù)相關(guān)性，此時，可先復(fù)制操作1，然后變換abc123復(fù)制1abc1‘231變換abc311‘2操作的輸出變量被其它操作所引用問題(1)當(dāng)兩個操作滿足結(jié)合律53經(jīng)過復(fù)制后，CDFG中操作個數(shù)增加了，可能增大硬件資源需求，但如果增加的操作不會增大同時執(zhí)行操作的操作數(shù)目，則不會導(dǎo)致硬件資源需求增加e.g.操作的輸出變量被其它操作所引用問題(2)*++**abcdexy1adder,2multiplications+*++**cdabexy1adder,1multiplication經(jīng)過復(fù)制后，CDFG中操作個數(shù)增加了，可能增大硬件資源需求，543（數(shù)據(jù)通路）分配功能：（1）將操作賦給相應(yīng)的功能單元運(yùn)算，（2）將變量（值）賦給相應(yīng)的存儲單元進(jìn)行存放，（3）將數(shù)據(jù)傳輸通道賦給相應(yīng)的硬件進(jìn)行數(shù)據(jù)傳輸輸入：數(shù)據(jù)流輸出：控制流和數(shù)據(jù)通路目的：建立一個功能塊級模塊組成的數(shù)據(jù)通路，使所占用的硬件資源（功能單元，存儲單元，互連線網(wǎng)）花費(fèi)最少，盡量共享3（數(shù)據(jù)通路）分配功能：（1）將操作賦給相應(yīng)的功能單元運(yùn)算，55數(shù)據(jù)通路基本硬件模塊功能單元存儲單元互連線網(wǎng)andFUregistermemoryinoutinindataaddressoutoutoutselectenableenableinoutselectmultiplexerbusselectinout數(shù)據(jù)通路基本硬件模塊功能單元andFUregistermem56分配與調(diào)度的關(guān)系調(diào)度過程影響執(zhí)行速度、響應(yīng)延遲等時間特性和硬件資源費(fèi)用等空間特性，分配過程則只對硬件資源費(fèi)用起決定作用，盡可能降低硬件成本調(diào)度結(jié)果是分配過程的約束和輸入分配與調(diào)度的關(guān)系調(diào)度過程影響執(zhí)行速度、響應(yīng)延遲等時間特性和硬57變量的生存期：變量從產(chǎn)生到最后一次被引用之間的控制步du變量產(chǎn)生時間最后引用時間備注x1(1)1(2)循環(huán)變量y7(1)7(2)循環(huán)變量u7(1)5(2)循環(huán)變量a07外部輸入d07外部輸入o323操作的輸出變量（中間變量）o423o545o667o745o867o1057+******<+--1234567891011cs1cs2cs3cs4cs5cs6cs7xya*括號中數(shù)字表示兩次相鄰循環(huán)的輪次變量的生存期：變量從產(chǎn)生到最后一次被引用之間的控制步du變量58分配算法啟發(fā)式分配算法

每次選取一個待分配的元素，將它賦給相應(yīng)硬件單元，在元素選取過程中用啟發(fā)式策略模擬退火貪婪全局費(fèi)用函數(shù)線性規(guī)劃方法(LinearProgramming)

將分配問題形式化為線性規(guī)劃問題求解0——1線性規(guī)劃混合整數(shù)線性規(guī)劃(mixedintegerlinearprogramming)整數(shù)規(guī)劃圖論算法團(tuán)規(guī)劃算法(cliquepartitioning)圖著色算法(NodeColoring)二部圖匹配算法分配算法啟發(fā)式分配算法

每次選取一個待分配的元素，將它賦給相59圖著色算法I利用沖突圖來分配操作II利用沖突圖來分配變量III分配互連線路IV分配控制器的輸出信號圖著色算法I利用沖突圖來分配操作60I利用沖突圖來分配操作根據(jù)調(diào)度結(jié)果，建立操作的沖突圖進(jìn)行沖突圖著色根據(jù)沖突圖中節(jié)點(diǎn)的顏色，分組并給操作分配功能單元I利用沖突圖來分配操作根據(jù)調(diào)度結(jié)果，建立操作的沖突圖61操作沖突圖由二元式組成：G=(V,E)V={opi}，E={(opi,opj)|opi與opj非互斥且調(diào)度到同一控制步中}u+******<+--1234567891011xa3214576108119yd操作沖突圖u+******<+--123456789101162操作沖突圖著色在沖突圖中任取一個未著色的節(jié)點(diǎn)；對該點(diǎn)著以與其相鄰已著色點(diǎn)不同的顏色；重復(fù)，直到所有節(jié)點(diǎn)均著色3*2<1+4*5*7*6*10-8*11-9+分配{1,2,10,11}={+,<,-}{3,5,6,9}={*,+}{4,7,8}={*}3*2<1+4*5*7*6*10-8*11-9+(+,<)*1*2—操作沖突圖著色3*2<1+4*5*7*6*10-8*11-963II利用沖突圖來分配變量根據(jù)調(diào)度結(jié)果，建立變量生存期表建立變量的沖突圖對沖突圖著色根據(jù)沖突圖中節(jié)點(diǎn)的顏色，分組并給變量分配存儲單元II利用沖突圖來分配變量根據(jù)調(diào)度結(jié)果，建立變量生存期表64建立變量的沖突圖

由二元式組成：G=(V,E)

V={變量vi}，E={(vi,vj)|vi與vj非互斥且其生存期重疊}

adxyo3o4uo7o5o10o8o6根據(jù)調(diào)度結(jié)果，建立變量生存期表

變量產(chǎn)生時間最后引用時間備注x1(1)1(2)循環(huán)變量y7(1)7(2)循環(huán)變量u7(1)5(2)循環(huán)變量a07外部輸入d07外部輸入o323操作的輸出變量（中間變量）o423o545o667o745o867o1057因a,d,x始終存在，故與所有變量均沖突建立變量的沖突圖

由二元式組成：G=(V,E)

V={變量v65對沖突圖著色

在沖突圖中任取一個未著色的節(jié)點(diǎn)；

對該點(diǎn)著以與其相鄰已著色點(diǎn)不同的顏色；

重復(fù)，直到所有節(jié)點(diǎn)均著色adxyo3o4uo7o5o10o8o6變量顏色號存儲單元a1R1x2R2d3R3y4R4u5R5o36R6o47R7o56R6o66R6o77R7o87R7o105R5分配對沖突圖著色

在沖突圖中任取一個未著色的節(jié)點(diǎn)；

對該點(diǎn)著以與66III分配互連線路對每個功能單元和存儲單元的各個輸入端口，重復(fù)如下步驟：若連線個數(shù)m大于1，分配一個m輸入端的多路器；將m根連線分別連接在多路器的m個輸入端上；將多路器的輸出連接在功能單元或存儲單元的輸入端口上總線的分配可在多路器分配前或后，根據(jù)某些（經(jīng)驗(yàn)）規(guī)則將相關(guān)的連線合并成總線綜上，產(chǎn)生如下數(shù)據(jù)通路III分配互連線路對每個功能單元和存儲單元的各個輸入端口，重67(+,<)*1*2—M1M2M3M4M5M6R2R3R1R4R6R5R73adyxCtrl不含控制信號的數(shù)據(jù)通路(+,<)*1*2—M1M2M3M4M5M6R2R3R1R68IV分配控制器的輸出信號控制器的輸出信號包括功能單元在每個控制步執(zhí)行哪些操作；哪些存儲單元加載；每個多路器的哪個輸入端數(shù)據(jù)被選中IV分配控制器的輸出信號控制器的輸出信號包括69u+******<+--1234567891011xaydS1S2S3S4S5S6S7輸入當(dāng)前狀態(tài)S1S2S3S4S5S6S7CtrlX01XXXXX輸出次狀態(tài)S2ENDS3S4S5S6S7S1(+,<)1XX1X1XXXXXXXX1X*11XX1X1XX*21XX1X1XX-XXXXX1X1R1:a0X000000R2:x1X000000R3:d0X000000R4:y0X0000X1R5:u,o100X000101R6: