ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



߼ۺ֤ͼȡо
ƽҵ
ժҪ Ҫ۸߼ۺϵͳRTL(register transfer level)ۺϽȷ֤Եȷ ֤ϵͳDFG(data flow graph)ȡ㷨ʵ.㷨Ҫ4 ׶ΣFSM(finite state machine)̬ȡFSMǰ״̬ͨ ЧԪͨṹDFGתDFGϵĴ 뼰ߵγ.
ؼʡ߼ۺ,Ӳ֤.
ͼšTP302
Research on Data Flow Graph Extracting Technology for
Verificat ion of High Level Synthesis Correctness
XU Qing-pingLIU Ming-yeSONG Han-tao
Department of Computer Science and EngineeringBeijing In stitute of TechnologyBeijing100081
AbstractTo verify the correctness of the RTL(register transfer level) result got from th e high level synthesis, an algorithm of DFG(data flow graph) invert extracting i s designed and realized in this paper. Four sections are included in this algori thm: analyze FSM(finite state machine) dynamically and obtain control signal; se arch the active component for current states of FSM and convert the operate note of DFG from the structure of data path; analyze the relationship between the no tes of DFG, separate the variables sharing the same register.
Key wordsHigh level synthesis, hardware design verification.
Ӳ֤ӲеһҪ.Ŀǰ,ϵͳϵӲ ֤1,2.,ӲԶо,߼ۺϼ ѸٷչӲ֤оµ.
߲ۺ㷨RTL(register transfer level)ṹʵ֮ı任. ߼ۺθ,Ҳʹƹ̵ĸ߶Զ,Ӷʹڴ ,ͬʱҲ֤.Ը߼ۺϵһЩ֤ĳЩ֮ .ǻڱѧ塱ڼƵHLS/BIT߼ۺϵͳ3,о Ӧ߼ۺص㡢ʵǿ֤ϵͳΪּ,ȷ˻ڸ߼ۺƵ ȷԲȡֲ֤Ĳ.ڲͬʵֲ,ȡ֤ͬ.㷨R TLṹʵֵȷ֤ͼ(data flow graph,DFG)ͬԼ鷽 4,RTLµĽṹʵ,Ϊɲóʽ֤.ɿ˷㷨 ײʵ̫֮.ҪDFGextȡļؼչ .йDFGͬıȽ,ǽ׫.
1Ӹ߼ۺϽȡͼĻ˼
DFGͬԼ鷽֤߼ۺϽȷ,ҪDFG,һDFGorg(Original DFG),Ǹ߼ۺеʽһDFGext(Ertracted DFG), Ǹ߼ۺϽRTLṹɵĲȫɵDFG,ͨԸ߼ۺֱ ж̬Զõ.DFGextȡĴ롢߼ۺϹ ǡǡ෴,ʽȡDFGextĹ̳ΪDFGextȡ.߼ۺϴȷʱ,Ӧ DFGextDFGorgDFGextDFGorg.Сաʾͬ ʾ̬ͬ.÷ף4,Ϊ,ף4ڶ䷽д¼ ȱݣ(1) DFGȡȻ÷ģķ.(2) ֤ĿRTLṹʵ ϴ(Ĵܹ).(3) ֹDFGͬԼ.ĵоֲȱ.
2FSM̬
ȡDFGextӦ״̬(finite state machine,FSM)Ķ̬ ,ȡFSM״̬µĿ.DFGextӲĿͨRTL ʵֲڿִвȫ--V,Լ֮ ϵȫ--EɵͼG.ĳһ״̬ͨ·ִеĲOiֱȷ.Oi һ״̬תϵ(Si,Il)(Sj)һһӦ,һķһ FSMа״̬ͿɷֱOi,̶õͨ·ִеĲ.ֻ FSM״̬µOiִͨеĲ,ľȡֵ ȷĳһ״̬תͨ·,ͬʱҲĸͨõľ,, ̲.ɴ˿,FSMתΪ״̬תͼı .ڴ,ùȱ㷨FSMķ.ڹȱ,Ը״̬ γһչѭͼ.еÿһӦһȿƲ(һʱ).ͬһ ϵ״̬ڵ·ǻֵ,״̬SiSjµOiĲʱS i Sj궨.ѭͼĽṹ֪,ùȱԱ֤һʱ ,ǰȻѾ.ڲϵķ.
3ͨǰЧͨ·
ͨеԪڿźŵЧ,ʱ,ǳЩԪΪǰЧԪ.״̬ еõĿOiǷ״̬,ͨЩԪЧ״ ̬ĸ.ڸһ,ͨеĵǰЧԪӹɵǰ ״̬µЧͨ·,Чͨ·ϵЧԪźŵĹϵΪ3ֱ ЧԪЧԪͨ·ѡԪ.
ʱ,ֱЧԪ״̬תֱȷ.ЧԪͨ ֱЧԪӹϵķ.ڴ˳ΪGetIndrctCmpnt()(ף5 ).
ͨù̵Ĵ,ȷһźͨе÷ΧӦصĸЧ Ԫ.
4ЧԪͼı任(ṹΪı任)
ǰ״̬,ЧԪȷ֮,Ԫܿɵõʹ洢ȵ·Ϊ .ֱЧԪֽз,ɻһִӦͼ.ֱ ЧԪӦһһתĿ.ЧԪе ˿ڻĴӦһݴԴ.
DFGγɹ̽Ϊýʱ.㡢ⲿ ڹɵԼûĳΪý.ۺϵͳмû ıΪʱ.,ڷʱ,ݲͬɾת Ϊý.
5ͼߵ
ǲͬǰӹϵıʾ.а ӼӣһǰֱӺ̲ ӵ.
ӵıʾ,Ӿͬʱʹ.ڽвǰӹϵ ʱ,ҲΪʱӺ.ʱָʱ,ʾ. ָý֮,Ӿʾ.Ԫȡֵ4 0 ʾijӣ 1ʾijӣ 3ʾij ӣ 2ʾijǵ.ǶԪ,ӱʾ Ȼӱ־.ͨǰ,ҪһҪ Ĵķ.о,ֵͨķһ.
6ϵͳʵн
۵DFG-extȡSUN-4/75վC++ԻBITHLS߼ۺ ϵͳʵ.ʵϵͳHLS/BITϵͳͨѡHLSynth92'߼ۺϵͳBenchMark һЩʵв,еõȡDFG.,ӦDFGorgDFGext7 ͬ.Բ˲һĲзۺϽڴ.оȷ, 㷨ʵֲ.ʵģRTLṹ68ӲԪ(൱2 ).ϵͳٶϿ,ģʵ뵽õ,ûûȴʱ .ϵͳʵֵĳ,DFGȽϽи߲ε֤,,֤ 򵥡.÷Ӧ߼ۺϳθߡԶ̶ȸߵص.

оõȻѧ͹Ԥл.
ƽ,1956,ʿ,ʦ,ҪоΪEDA,д.
ҵ, 1934,,ʿʦ,ҪоΪEDA.
,1940, ,ʿʦ,ҪоΪEDA,Ϣ,ݿ⼼.
ͨѶϵˣƽ, 100081,ѧѧϵ
ߵλ:ѧѧϵ100081
ο
[1]Camurati P. Formal verification of hardware correctness: introduction and survey of current research. IEEE Computer, 1988,21(7):816
[2],ҵ.VLSIʽ֤.ͼѧѧ,19 96,8(2):155159
(Jiang Ming, Liu Ming-ye. Survey on methods of formal verification for VLSI des ign. Journal of Computer-Aided Design and Computer Graphics, 1996,8(2):155159) 
[3]ҵ,Ŷ,ƽ.VHDL߼ۺϵͳĳЩؼļ. ѧ,1997,20(6):501509
(Liu Ming-ye, Zhang Dong-xiao, Xu Qing-ping. Technical decision on several ke y problems in VHDL high level synthesis system. Chinese Journal of Computers, 19 97,20(6):501509)
[4]Vemuri R. A transformational approach to register transfer level desig n-space exploration Ph.D. Thesis. Case Western Reserve University, 1989
[5]ƽ.߼ۺϽȷ֤оʵ֣۲ʿѧλģ. ѧ,1997
(Xu Qing-ping. Research and realization on correctness verification to high lev el synthesis result Ph.D. Thesis. Beijing Institute of Technology, 1997)
1997-12-01յԭ,1998-05-19յ޸ĸ
