
COMPUTER ENGINEERING
1999  25 7 Vol.25 No.5 1999



߼ۺмĴϲо
ԬСߵԶ
ժҪ߼ۺϼоڵǰܹעڽԴʱΪ˼ٻߵĿӦ·ۺļĴкϲͨԼĴϲоһָ߼ۺеļĴϲ㷨ʵ֤㷨ٶȿ졢Чʸߵص㣬Ӧڸ߼ۺϵͳʱۺƵ
ؼʡ߼ۺϼĴϲ
A Study on Register Merging Problem for High-level Synthesis
Yuan Xiaolong Gao Deyuan
Aerospace Microelectronice CenterNorthwest Polytechnical University Xian 710072
AbstractHigh-level synthesis is an active area of research presently.Inthe process of resource allocation,the registers required in data path should be merged in order to reduce the interconnection wires.Based on the study of the register merging,a register merging algorithm is presented in this paper.This algorithm is very efficient and can improve the quality of the design in high-level synthesis.
Key wordsHigh-level synthesisRegisterMerge
߼ۺҲΪۺϣɴϵͳΪĴ伶(RTL)ƵתΪ RTLṹתɷΪ4񣬼ڲʾ͵ȡӳ䡢ۺϡڲʾΪתΪԴĻڱʾʽȽΪĲֵƲУʹһƲевһʱִСȷڸԼʵһԴӳ佫ΪеĲ洢ʼӲԪõŻܡһȡɼ·ԪѡȡϺݲȵҪӦĿʵһ״̬ԶFSM(Finite State Machine)ȼȷFSM״̬Ŀ״̬תFSM롢źţЩϢۺϳӦĿƵ·
4໥ϵ໥Ӱ졣߼ۺϵĵһǽ㷨ʽΪתΪһڲʾڴ˻֮Ϲڶڲʾģ[1]Ͳ[2][3]о֮󣬿ʼо·ۺеԴ(ӳ)⣬ǰѾᵽԴǽΪеĲ洢ʼӲԪõŻܡʹ߼ۺϵͳһڲȽ׶ξ˹ܵԪķ䣬Դ׶Ҫɴ洢Ԫ(ҪǼĴ)뻥Ԫ(ߡ·ѡ̬)ķ䣬мĴķ·ۺеһҪ񣬸߼ۺмĴķͨ3ɣÿڡĴķͼĴĺϲǰڼĴķео࣬ڼĴĺϲǰеоҪô洢ȡҪļĴʵʵоƬƾ飬Ľ̽üĴȡļĴڲӰоƬܵ¼ٻߣӶﵽСоƬۺĿġ
1
֪һVHDLϵͳΪУڲ󣬾һʱҪõЩĴǱÿһĴ⽫ƵµƵĲ˱뿼ǱԼĴĹ⡣Ҫ⣬ÿڡ
ĴڲȵĻ֮ϽеģǰᵽȵǽΪеĲֵƲУÿЧʱξȷãʱξǱڣԿƲȷʱҪעһǣΪкṹʱһṹе֦ͬʱִУڲ֦ͬвģǲͬʱʹǵصҲһĴǵֵҪǶԱڽкϲ⡣ڿһʾҲԼϵʽʾ磬iڵ2Ʋ3Ʋ͵4ƲЧ(Ҫֵб)ʱΪSi=(2,3,4)
2Ĵķ
ȷÿں󣬾ͿɽмĴķ䡣ǵڲصʱһĴ洢ǵֵĴķɲ[5]еŻ㷨(clique partitioning algorithm)ڸ㷨УһͼʾĴķ⣬ͼеĽڵʾԻͬһƲвͬʱЧıͼ1и[5]еӵVHDLΪȺ󣬸ΪҪ5ƲͿִУǰеjʾ佫ڿƲjִС

ͼ1 һVHDLΪ
ͼ1пɿΪа15ٶͼ1еVHDLΪѭִеģȷͼ2ʾıڡ

ͼ2 ڱ
ͼ2УviʾiбʾƲбʾl(live)ʾviڸÿƲеֵЧd(dead)ʾviڸÿƲеֵЧ(Ҫֵ)Ȼ15ÿһĴʱҪ15Ĵ˷ӲԴʵϣ15Ҫ8Ĵr1-r8Ƿֱr1(v1,v14)r2(v2,v7,v9,v15)r3(v3,v8,v13)r4(v4)r5 (v5,v11)r6(v6)r7(v10)r8(v12)ȷ·ۺļĴ󣬽ۼĴĺϲ⡣
3Ĵĺϲ㷨
ÿĴ·ۺϹУҪĳЩܵԪӣԽֵĴ䣬ӶȷʵΪĹܡÿӶʵ֣ĳЩƣߵĿǷǳġΪ˼ߺƵɶԼĴкϲʵߵĹݶԼĴĶдϵɽĴϲΪһĴ飬ÿ麬ж˿ںд˿ڣоƬУĴĶ˿ںд˿ڷֿƣҪֵĴʱŽЩ˿йصĵԪڼĴĺϲУҪǵҳԺϲһļĴ飬ʹÿܶļĴڶԸ߼ۺϼоĹз֣ĴеĶ˿ںд˿ĿȽ϶ʱÿĴɰļĴ˿ƿ෴ĴеĶ˿ںд˿ĿȽʱÿĴɰļĴͱȽ٣ƿȽСڶ΢MPPоƬƾ飬ΪÿĴһд˿ں˿ǱȽϺʵġڼĴϲҪȷԺϲһĴеļĴϡڽмĴĺϲʱɺϲһĴļĴϣȻٴʣļĴɺϲһĴļĴϣظùֱʣһĴеļĴѱ䵽ĴУʣһĴʱɸݶĶдϵصԪӼɡɺϲһĴеļĴϵ㷨
ÿĴ2˿ں1д˿ڣȺ󣬲ȵkƲִУs1--skмĴΪеıҪyĴֵr1--ryĴiڼĴRGʱXiΪ1XiΪ0ҵɺϲһĴRGĴĿɶΪµ0-1Թ滮⣺

(1)
Լ£

j=1,...,k
cijʾĴiڵjƲҪж
dijʾĴiڵjƲҪд
ͨԸ0-1Թ滮⣬ͿҵɺϲһĴRGеĿļĴϡ
4ʵ
ڶԼĴϲоҸӦ㷨֮Cʵ˸㷨[5]5.6ڸ֤иĺϲ㷨Чԡͼ3(a)˼Ĵϲǰ·([5]еͼ1)ɿ·а8ĴñĸķмĴϲ󣬲3Ĵ飬(v1,v3)(v2)(v4,v5,v6,v10,v12) ,ɵ·ͼ3(b)ʾɿ²·ߵĿˣұȽϹˡ


ͼ3 ϲǰ·ͼĴϲ·мĴϲߵĿ࣬ĽֹƵȫһ¡
ñи㷨LS MPPеĴԪ(һALUһλ·һ8Ĵ)мĴϲ󣬻ߵĿ࣬ĽֹƵȫһ¡
5
ʵ֤ĵļĴϲ㷨ܺܺõؽ߼ۺеļĴϲ⡣ͨĴĺϲߵĿʹоƬСˣʹ·ȽϹֳVLSIеģ黯˼룬ڶоƬĲԡ
ܡ塱Ԥר⺽ջ97F53133
߼飺ԬС У28꣬ʿоΪEDA
ߵλҵѧ΢710072
ο
1Yuan XiaolongShen Xubang.A New Control and Data  Flow Graph Model.in Proceedings of International Workshop on Advanced Parallel Processing TechnologyBeijing, 1995107
2ԬС.һµĲ㷨.ѧ199720(3):193
3ԬС.һֻ·ĵ㷨.о뷢չ199835(3)193
4Tseng C J,Siewiorek D P.Automated Synthesis of Data Paths in Digital Systems.IEEE Trans.on CADCAD-5(3)1986-07
ոڣ1998-11-02
