一种使用于高时效电路设计之动态管线化方法

摘要

管线化是设计高时效数位电路的有效方法，但是传统的管线化方法很难将电路中执行时间可变的回圈管线化。本发明提出一个新的高速硬体电路管线化方法:动态管线化方法，它可以有效地将具有可变时程回圈的硬体管线化之。不同于传统管线化方法使用固定潜伏期(fixed latency)或者固定资料起始区间(data initiationinterval)来设计管线硬体，本发明使用可变潜伏期方式来管线化电路中回圈的执行，以达到最高运算速度的目标。此外，动态管线化方法所设计出来的硬体架构须要特殊的控制器加以控制。本发明也提出此特殊控制器的一般架构，它是由两个相互交谈的有限状态机(finite state machines)所组成，使得资料路径能够以可变潜伏期方式执行。实验结果显示本发明在增加少许额外面积的负担下，能够有效提升可变回圈的计算时效。

主权项

1.一种可运用于可变执行时间的回圈动态管线化方法,包括:(a)行为状态转移图(BSTG)分割,将要设计之电路的行为,利用行为状态转移图建立其所对应的模型,并且将此行为状态转移图分为两部份:一部份为固定执行时间的外层部份(BSTGo);一部份为可变执行时间的内层部份(BSTGi);(b)内层回圈之管线设计,将内层的行为状态转移图(BSTGi)做管线化之设计与处理,进而得到管线化后的行为状态转移图,以管线化内层行为状态转移图(PBSTGi)表示之;(c)-外层回圈之管线设计,将外层行为状态转移图(BSTGo)做管线化之设计与处理,而得到管线化后的行为状态转移图,以管线化外层行为状态转移图(PBSTGo)表示之;(d)-资料路径之设计,把内外层部份分别管线化处理后,便针对管线化内层行为状态转移图(PBSTGi)及管线化外层行为状态转移图(PBSTGo)做资源配置(resource allocation),以建构动态管线的资料路径(datapath);(e)-动态管线之控制器设计,接下来利用管线化内层行为状态转移图(PBSTGi)产生内层部份的控制器,再由管线化外层行为状态转移图(PBSTGo)产生外层部份的控制器,藉由此两个控制器或先整合此二控制器为一个控制器,再加上启始(start)、执行(done)、选择(run)等控制讯号组合而成动态管线化的控制电路。2.如申请专利范围第1项所述之动态管线化方法,其中行为状态转移图(BSTG)为一个有向循环图,其顶点代表状态,它的边代表状态转移,而边上的标签则代表引发状态转移的条件。3.如申请专利范围第1项所述之动态管线化方法,将回圈动作中执行时间固定的部份与执行时间不固定的部份分割开来,执行时间固定的部份分割成外层行为状态转移图(BSTGo),而执行时间不固定的部份,分割成内层行为状态转移图(BSTGi)。4.如申请专利范围第1项所述之动态管线化方法,其中管线化内层行为状态转移图(PBSTGi)是利用一般的管线化方法将内层行为状态转移图(BSTGi)做管线化的处理,在此所谓一般的管线化方法,也就是将电路中回圈的每次循环重叠执行之并藉此找到内层回圈重叠执行的部分。5.如申请专利范围第1项所述之动态管线化方法,其中管线化外层行为状态转移图(PBSTGo)是利用一般的管线化方法将外层行为状态转移图(BSTGo)做管线化的处理,但是外层部分每次循环的启动时间受到内层回圈执行次数多寡的影响,故在外层行为状态转移图(BSTGo)中插入N个运算代表执行内层回圈所需用掉的状态数(states),其中代表内层部份与外层部份可以同时执行的最大个数;再利用一般的管线化方法将插入N的外层行为状态转移图(BSTGo)管线化外层成管线化行为状态转移图(PBSTGo),以及找出外层回圈重复执行的部分。6.如申请专利范围第1项所述之动态管线化方法,其中资源配置(resource allocation)是针对内层部份以及外层部份利用一般的方法来做暂存器配置(reGister allocation)以及运算单元配置(ALU allocation)。7.如申请专利范围第1项所述的动态管线资料路径(data path)设计方法即是利用管线化内层行为状态转移图(PBSTGi)及管线化外层行为状态转移图(PBSTGo)配合资源配置(resource allocation)所产生动态管线化的电路架构。8.一种执行动态管线化控制之电路设计架构,如下图所示,其系包括一个内控制器、一个外控制及产生控制讯号启始(start)、执行(done)、选择(run)的电路,而其中外控制器即由管线化外层行为状态转移图(PBSTGo)所推导而来,内控制器由管线化内层行为状态转移图(PBSTGi)推衍而出,启始(start)及执行(done)分别由内控制器及外控制器所产生,而选择(run)讯号用来解决控制冲突,也就是避免内控制器及外控制器同时对相同的硬体发出一样的控制讯号。9.如申请专利范围第8项所述之电路设计架构,控制电路中的内控制器以及外控制器亦可结合成一个控制器,在设计控制电路时将管线化内层行为状态转移图(PBSTGi)以及管线化外层行为状态转移图(PBSTGo)同时的考虑,而以一个状态图表示之,形成结合两个控制器功能之一个控制器。图式简单说明:第一图简单管线(a)固定値(Latency)=4(b)有顺序之固定値3,4,3,4...(c)不定,随情况而变1,3,2,3,4,1...第二图插入排序电路的硬体行为描述第三图插入排序电路的初始行为状态转移图(BSTG)第四图第三图的行为状态转移图(BSTG)分割结果(a)行为状态转移图(BSTG)以及(b)内层行为状态转移图(BSTGi)第五图(a)原来的管线化内层行为状态转移图(PBSTGi)以及(b)新的管线化内层行为状态转移图(PBSTGi)第六图第五图(a)的前置体(prelude)和后置体(postlude)的状态移入后,获得的外层新行为状态转移图(BSTGo)第七图第六图的外层行为状态转移图(BSTGo)渐次展开4次的结果第八图插入排序电路最后的管线化外层行为状态转移图(PBSTGo)第九图插入排序电路最后的管线化外层行为状态转移图(PBSTGi)第十图动态管线化架构控制器的基本架构第十一图动态管线架构之二元算术编码电路layout图