DFG @ scheduling Algorithm..

在High level synthesis flow 中, Scheduling Algorithm 扮演了很重要的角色, 這決定了HW Architecture 跟 Control Flow...而這幕後的功臣要取決於良好的Data flow definition, 底下介紹最常聽到的Design flow @ Graph theory (DFG). 在之前的 research 中,我們提到幾個high level 的synthesis tools. 如 Behavior Synthesizer tool @sister , Design Automation Tool from Behavior Level to Transaction Level for Virtual Bus-Based Platforms , 中都採用 DFG(data flow graph) 當 Data Based. 好處是比較容易understand跟implement. 底下就用個sample來講解DFG的架構. 假設底下的macro為一個 SystemC 的 Process 且 trigger type 跟 sensitive type 都已知.首先透過 code analysis 的方式來分析語法跟 keywords && tokens.這邊可以考慮用 lex && yacc 當 filter 跟 structure set. 分析語法後根據每個section依序建立起各自的Graph.因為 DFG 是以 control 來切的,所以遇到每個condition判斷時就會切成一組新的Graph.而每組Graph 中又細分出子空間的 DFG, ctrl Graph. 最後用linklist 把每張 Graph 的前後關係建起個 link list 成為 Top Graph. 在最底成的 DFG Graph 大致長的像這樣,裡面會 NxtNode, PreNode 跟 OperType 的 Definition. 最後 Top Graph 大概長如此. 一層Graph list 底下又有一層 Graph list. 因為我們是ACycle Design for Verilog,所以在最TOP層的 Section(s) 是 Cycle by Cycle的.你可以想成彼此是互相獨立的,只有在下個Clock edge 打起來後Data 才會發生變化.在此前提下我們又可以對每個 Section 做 constrain 跟 Scheduling 的動作. 如 HW Operator Number constrains, or Operator Delay set, or ASAP/ALAP scheduling... Refs: Scheduling Algorithms For High-Level Synthesis 15 References [1 ...[PDF] AEON: Synthesizing Scheduling Algorithms from High-Level Models[PDF] Scheduling (computing)