367_088-116CP-TW

跳到主要內容區

:::

367_088-116CP-TW

發佈日期 : 2009-04-29

發明專利說明書
	※申請案號：
	※申請日期：　　　　　　　　　　※ＩＰＣ分類：

一、發明名稱： (中文/英文)
	一種使用於高時效電路設計之動態管線化方法 (全文下載) Dynamic Pipelining Approach for High Performance Circuit Design
二、申請人：共人
	指定為應受送達人

三、發明人：

◎專利代理人：


四、聲明事項

	□主張專利法第二十七條第一項國際優先權：
	□主張專利法第二十九條第一項國內優先權：
	□ 主張專利法第二十六條微生物：
□ 熟習該項技術者易於獲得，不須寄存

五、中文發明摘要：
	管線化是設計高時效數位電路的有效方法，但是傳統的管線化方法很難將電路中執行時間可變的迴圈管線化。本發明提出一個新的高速硬體電路管線化方法:動態管線化方法，它可以有效地將具有可變時程迴圈的硬體管線化之。不同於傳統管線化方法使用固定潛伏期 (fixed latency)或者固定資料起始區間(data initiation interval)來設計管線硬體，本發明使用可變潛伏期方式來管線化電路中迴圈的執行，以達到最高運算速度的目標。此外，動態管線化方法所設計出來的硬體架構須要特殊的控制器加以控制。本發明也提出此特殊控制器的一般架構，它是由兩個相互交談的有限狀態機(finite state machines) 所組成，使得資料路徑能夠以可變潛伏期方式執行。實驗結果顯示本發明在增加少許額外面積的負擔下，能夠有效提昇可變迴圈的計算時效。

六、英文發明摘要：
	Pipelining is a well-known efficient technique for optimally designing high performance digital circuits. Howeve, conventional pipelining techniques are difficult to pipeline the execution of a loop with variant iteration execution lengths in a circuit. The invention presents a new pipeline design approach, called dynamic pipelining, to design and pipeline this kind of loop in a circuit efficiently. Instead of assuming a fixed latency (or data initiation interval), the approach pipelines the loop using run-time determined latencies to achieve a high performance. The general controller architecture of it is also introduced. It consists of two interactive finite state machines to allow the pipeline datapath to execute at variant latencies. Experimental results show that the approach can obtain about 2 times speedup with acceptable area overhead.

七、指定代表圖：
（一）本案指定代表圖為：
（二）本代表圖之元件代表符號簡單說明：


八、本案若有化學式時，請揭示最能顯示發明特徵的化學式：


九、發明說明：
	[發明內容] 產業上之利用領域本發明提出一個新的高速硬體電路管線化方法，運用該動態管線化方法(dynamic pipelining method)，可以有效地將具有可變時程迴圈的硬體管線化，達到最高運算速度的目標。背景高時效是設計特殊用途積體電路(application specific integrated circuits)的重要目標之一。然而，自從1987年E. M. Circzyc，於Proc. of the ISCAS第382-385頁提出迴圈繞 (Loop Winding)概念後，在特殊用途積體電路的行為指令中經常包含了耗時的迴圈，例如編碼、解碼器，數位濾波器，以及影像及語音處理器等皆是如此。為了提昇時效，電路中隱藏於重覆執行迴圈中的潛在平行性(parallelism) 就必須檢測出來並加以管線化。至1996年M. Rim等人於 IEEE Trans. on Parallel and Distributed Systems，第7卷，第 4期第399-410頁之資料，以及發明人在1991年Proc. of the ISCAS第1769-1772頁所揭示的傳統管線化方法，均可顯示，在過去幾年中已經有許多的管線化方法被提出以增進硬體電路上所執行之迴圈中的平行性。事實上在絕大多數存在的管線化方法中，如1996年H. S. Jun等人於IEEE Trans. on VLSI Systems，第4卷第2期第 279-285頁報導管線潛伏期(pipeline latency，或data initial interval)皆被設為固定值或是某些固定值。然而在許多特殊用途積體電路的迴圈中，由於迴圈每一次執行時間可變以及時間相關的資料相依性(time-relative data dependencies) 等因素使得事先無法知道其管線潛伏期之大小，而不能以傳統固定潛伏期的方法有效地管線化或者根本無法被管線化。為了解決這個問題，傳統管線化硬體設計法中固定潛伏期的局限必須加以克服。管線化(pipelining)及平行化(parallelizing)是設計高時效數位電路兩個最知名的方法。比較兩者，管線化具有低面積、高彈性，並可獲得不錯的時效提昇等優點，因此已成為高時效電路最常用的設計方法。目前已有許多篇文獻及專利如美國專利第4,677,549號、第4,742,453號、 5,079,736號、第5,428,756號、第5,684,422號，提出不同的管線化方法以提高電路的時效。所謂之管線化方法，也就是將電路中迴圈的每次循環(iteration)重疊執行之，並縮短總執行的時間。雖然這些管線化方法都各有所長且各具用途，但是這些方法中的管線潛伏期是固定的或是有幾個順序固定之常數值，例如潛伏期(latency)為4，或3與 4，這樣只能處理一般簡單管線的情形如圖1(a)與1(b)所示，一旦遇到執行工作中有些動作之執行時間不固定的情形，例如潛伏期不固定，就無法利用傳統管線方法進行管線化的設計來提昇執行效能如圖1(c)。一旦執行工作內部有些動作之執行時間不固定，譬如一個內有不對稱IF THEN ELSE結構的迴圈(loop)程式；又如一個迴圈內部有執行次數不定之內迴圈等，這些例子都無法事先確知其主迴圈之每一循環需要多少執行時間，這樣將不能有效地用固定潛伏期方式管線化或者根本無法管線化這種迴圈。而這種可變時程之迴圈又經常出現在許多多媒體和數位訊號處理的特殊用途積體電路中。例如一般的硬體排序電路、適應性二元算術編碼電路、以及模糊邏輯色彩修正電路等中皆含有類似特性的主迴圈，這些都可運用本發明「動態管線化方法」獲得理想之處理。本發明更適合應用在工作中執行時間不固定的情形，及執行次數事先無法預知的狀況。傳統的管線化方法根本無法處理這一類的問題，利用本發明能夠使用可變潛伏期(variant latency)的方式有效地將電路中執行時間不定的迴圈工作管線化，並且獲得相當大的時效提升。然而本方法所付出之硬體設計代價和一般傳統的管線化硬體設計方法是相當的：會增加暫存器之數量、可能增加某些硬體元件，及控制電路複雜度的提高。這些額外增加的硬體是隨著設計對象之不同而有所變化；無法以固定量化的方式說明，然而一般而言都是可接受的，就如同傳統管線化硬體設計已廣為大家所接受般。這亦可由後面實驗數據驗證得知。發明目標本發明之主要目的，揭示一種新穎適用於高速硬體電路的管線化方法，運用該動態管線化方法(dynamic pipelining method)，可以有效地將具有可變時程迴圈的硬體加以管線化，以達到最高運算速度的目標。此外，本發明也提出一種搭配動態管線化方法 (dynamic pipelining method)所設計的控制器；其係由兩個相互交談的有限狀態機(finite state machines)所組成，使得資料路徑(硬體電路)能夠以可變潛伏期方式執行。凡是熟悉該技藝的人士在閱讀下列經由不同圖解所展示之較佳實施例詳細說明後，無疑地將非常清楚本發明所揭示之目的和優點。表列之說明：表1循序架構及動態管線架構對於二元算數編碼電路的比較結果表2循序架構及動態管線架構對於排序電路的比較結果表3循序架構及動態管線架構對於模糊邏輯色彩修正電路之比較結果發明之詳細說明本發明提出一個新的迴圈管線化硬體設計法，亦即動態管線化方法(dynamic pipelining method)，它使用可變潛伏期(variant latency)的方式有效地將執行時間可變的迴圈加以管線化，並且藉由適當的控制訊號處理達成雙層管線化的效應，因而獲得相當大的時效提升，而其所需要付出的代價只是增加少許額外的面積。動態管線化方法之圖形模形(graph model) 首先說明動態管線化方法(dynamic pipelining method)中電路之迴圈行為表示模型，稱為行為狀態轉移圖(behavioral state transition graph，BSTG)。行為狀態轉移圖(BSTG)是一個有向循環圖，它的頂點(vertices)代表狀態，它的邊 (edges)則代表狀態轉移。行為狀態轉移圖(BSTG)的每一個頂點有兩個標籤：狀態S_i及條件-運算對[c：ε]，它們分別代表行為狀態轉移圖(BSTG)的第i個狀態，以及假如條件c成立則在集合ε中的運算將在此狀態被執行。假若此狀態中所有的ε皆為空集合，則此狀態為無運算狀態(Noop state，no-operation state)。行為狀態轉移圖(BSTG)中每個邊上的標籤則是引發狀態轉移的條件。在同一個狀態中的運算將在同一個時鐘周期(clock cycle)中被啟動。最初的行為狀態轉移圖(BSTG)係1974年由T.L.Adam等人於 Communication of the ACM第17卷第12期第685-690頁報導可以藉由進行行為描述的列表定序(list scheduling)而獲得。在行為狀態轉移圖(BSTG)中，假如存在一個邊S_i→S_j，則S_i稱為S_j的母狀態(parent state)而S_j稱為S_i的子狀態 (child state)。若一狀態擁有兩個或以上的子狀態則稱為分支狀態(branch state)。將動態管線化方法運用於迴圈的管線化硬體，必須考慮連續迴圈的兩個重覆執行循環(iteration)在一個稱為潛伏期(latency)的時間間隔後被起動。為了區分行為狀態轉移圖(BSTG)中不同重覆執行體的狀態，在行為狀態轉移圖 (BSTG)中第j 個重覆執行體的狀態S_i被加上另一個下標j 成為S_ij。管線化以後迴圈的行為被表示為一個管線化行為狀態轉移圖(pipelined BSTG，PBSTG)。在管線化行為狀態轉移圖(PBSTG)中的每一個狀態都有一個標籤PS_i代表它是管線化行為狀態轉移圖(PBSTG)的第i個狀態，並且 PS_i是由一些行為狀態轉移圖(BSTG)的狀態所組成的。下面使用一個插入排序電路(insertion sorter)說明行為狀態轉移圖(BSTG)模型，和本發明之動態管線化方法(dynamic pipelining method)。此插入排序電路的動作以類似C語言方式描述如下：此描述首先轉成如圖2的硬體行為描述。下面設計過程中本發明都假設每一個運算都可以在一個時鐘周期內完成，並且使用一個可以同時讀寫的多埠記憶體(multiport memory)- -這些假設並不會影響本發明的設計程序。在圖2 中，r_add和w_add分別表示記憶體的讀寫位址，在第i行的運算以o_i表示，運算o_i將在每一行最前端所標示的狀態中被啟動。圖3是圖2的行為描述所對應的初始行為狀態轉移圖(initial BSTG)。圖3中的L1外(主)迴圈內部有一個執行時間可變的L2內迴圈，其中控制條件co和ci是運算o₂和運算o₁₀的相反結果，也就是。當條件co為真，則插入排序電路中之外迴圈將繼續執行，當條件ci為真，則插入排序電路中之內迴圈將繼續執行，否則將終止執行。其初始狀態標示”Init”。由於具有不確定執行時間的內迴圈，無法使用傳統固定潛伏期的方法管線化此插入排序電路之行為狀態轉移圖(BSTG)，甚至於不可能獲得對應之管線化硬體，因此需要動態管線化方法進行設計。所謂動態管線化方法(dynamic pipelining method)，係指將電路中執行時間固定與不固定部份分割，分別加以管線化，再利用適當的控制訊號處理達成雙層管線化的效應。為了克服此難題，本發明先將L2：內迴圈(while loop)從外層L1：迴圈(while loop)中分離出來，此即為動態管線化方法之步驟1；再重疊處理L2迴圈之每一循環的執行，亦即管線化內層之L2迴圈，請看插入排序電路行為描述；此為步驟2；如此被管線化處理過之已管線化(pipelined) L2內迴圈(loop)，被視為L1中之一個複雜的運算(operation) 而以數個狀態(state)表之。然後重疊處理L1之每一循環，即管線化外層之L1迴圈；此為步驟3；在重疊執行L1迴圈(while loop)之每次循環時，連續兩L1循環彼此不能重疊執行其內部已管線化之L2迴圈。因為這兩個L2內迴圈本身都已經重疊執行它們的每一循環，亦即這兩個L2內迴圈 (while loops)本身皆已經被重覆地管線化了，因此無法重疊再重疊。導致這兩個L1迴圈循環在上述限制下，又因其內部已管線化(pipelined)的L2內迴圈(loop)執行時間不定，而無法固定他們執行下次迴圈之時間間隔(即潛伏期)，此現象被稱為動態管線，亦即動態潛伏期。最後以兩個交談式控制器；一個控制L2：迴圈(while loop)之重疊執行，另一個控制L1：迴圈(while loop)之管線化，再透過二者之間交談式訊號啟始(start)與執行(done) 彼此適當的聯繫；此即為步驟5，因而達成動態地改變管線潛伏期，獲得提升時效之效果。其中啟始(start)訊號，當start=1代表內層迴圈L2要開始動作；執行(done)訊號done=1代表外層迴圈L1要開始動作。動態管線化方法為了要設計動態管線化硬體架構，首先本發明用行為狀態轉移圖(BSTG)將ASIC中執行時間可變的迴圈建立其對應模型，然後將此行為狀態轉移圖(BSTG)模型分割成兩個部份：一個是內層部份，一個是外層部份。迴圈中執行時間可變的運算組合成內層部份，迴圈的其餘運算則劃歸到外層部份。然後由這兩個部份建立相互對應的行為狀態轉移圖(BSTG)模型。行為狀態轉移圖分割完之後，在外層之行為狀態轉移圖中將內層部份視為空運算(no-operation)來代表，進行管線化設計；該狀態亦可反向行之。行為狀態轉移圖(BSTG)分割完之後，內層和外層之行為狀態轉移圖均分別管線化成兩個管線化的行為狀態轉移圖，以BSTG’s 或PBSTG來表示管線化行為狀態轉移圖，接著整合它們以建立一個動態管線化架構。在動態管線化後，只要不違反彼此間資料或控制相依的關係，就可以將這兩個管線化的行為狀態轉移圖(BSTG’s)同時管線化執行，而執行之管線潛伏期和每一次內迴圈的執行時間有關，而此值是隨時可變的，所以潛伏期自然就會不固定，因此達成動態管線化方法之目的一應因潛伏期動態變化而管線化進而增進執行效能。依據上述觀念與說明，設定一個特殊用途積體電路迴圈的初始行為狀態轉移圖(initial BSTG)，按照以下幾個步驟運用動態管線硬體設計法來設計一個動態管線化電路結構。步驟1-行為狀態轉移圖(BSTG)分割：將要設計之電路的初始行為狀態轉移圖分割成兩個子圖。外層迴圈行為狀態轉移圖(BSTG_o)及內層迴圈行為狀態轉移圖 (BSTG_i)；亦即固定執行時間的外層部份(BSTG_o)和可變執行時間的內層部份(BSTG_i)。步驟2-內層迴圈之管線設計：將內層迴圈行為狀態轉移圖 (BSTG_i)進行管線化形成一個管線化之內層行為狀態轉移圖(PBSTG_i)。步驟3-外層迴圈之管線設計；將外層迴圈行為狀態轉移圖 (BSTG_o)進行管線化形成一個管線化之外層行為狀態轉移圖(PBSTG_o)。步驟4-資料路徑之設計：依據管線化之內層行為狀態轉移圖(PBSTG_i)，管線化之外層行為狀態轉移圖 (PBSTG_o)，及硬體成本限制進行資源配置(resource allocation)以設計動態管線化資料路徑(dynamic pipelined data path)。步驟5-動態管線之控制器設計：根據上述結果設計動態管線化控制器以控制資料路徑中硬體單元的運作。以上的每一個設計步驟將運用上述之插入排序電路例子，詳細說明於下。步驟1--行為狀態轉移圖(BSTG)分割首先本發明用行為狀態轉移圖(BSTG)，將ASIC中所要執行的迴圈動作建立為一個對應模型，然後將此行為狀態轉移圖模型分割成兩個部份：一個是內層部份(inner loop，1)，一個是外層部份。迴圈中可變執行時間的運算組合成內層部份，迴圈的其餘運算則劃歸到外層部份。然後由這兩個部份建立為一個相互對應的行為狀態轉移圖 (BSTG)模型。以上述插入排序電路為例以動態管線化方法設計硬體，首先分割如圖3所示原始行為狀態轉移圖成兩個行為狀態轉移圖(BSTG)，如圖4所示為(a)外層行為狀態轉移圖 (BSTG_o)，和(b)內層行為狀態轉移圖(BSTG_i)，同時加入兩個互動的訊號啟始(start)與執行(done)於其中，以進行它們於動態管線動作時之通訊；有關設定啟始(start)與執行(done)部份，將在下面的敘述加以說明。分割行為狀態轉移圖(BSTG)的目的，主要是分開內外層迴圈，同時使得它們能夠在相同的資源限制(resource constraint)下分別地被管線化，而後再整合成一個動態管線架構。在插入排序電路之外層行為狀態轉移圖(BSTG_o)中，原來內層迴圈的位置以一個新的無運算狀態取代之，稱為內層無運算狀態Noop_i(15)。內層無運算狀態(Noop_i，15) 是一個分支(branch)狀態，在它的兩個邊上分別標上條件執行(done，12)及已經執行。執行訊號(done，12) 被內層行為狀態轉移圖(BSTG_i)設定為1時表示內層迴圈完成，同時告知外層行為狀態轉移圖(BSTG_o)這個狀況；當為 0時表示內層迴圈尚未完成。再者，加入另一個啟始(start， 14)訊號，它在外層行為狀態轉移圖(BSTG_o)的內層無運算狀態(Noop_i，15)的母狀態(parent state)中設為1，以啟動內層行為狀態轉移圖(BSTG_i)的執行，並且在其他的外層行為狀態轉移圖(BSTG_o)狀態中被設為0。另一方面，在內層行為狀態轉移圖(BSTG_i)中，原來外層迴圈的位置也以另外一個外層無運算狀態(Noop_o，16)取代之。外層無運算狀態 (Noop_o，16)也是一個分支(branch)狀態，在它的兩個邊上分別標上條件啟始(start，14)和已經啟始。藉由訊號啟始(start)與執行(done)的彼此溝通，整個外層行為狀態轉移圖(BSTG_o)和內層行為狀態轉移圖 (BSTG_i)的行為將保持與原來的行為狀態轉移圖(BSTG)一致。如圖3所示排序器的行為狀態轉移圖(BSTG)經分割成如圖4所示結果。為了便於瞭解，除了訊號啟始(start，14) 與執行(done)的運算動作外，有關圖4中每一個狀態所啟動的其他運算都沒有標示出來，而其中控制訊號執行 (done，12)等於排序電路行為描述中的控制條件ci的補數。步驟2--內層迴圈之管線設計分割原來行為狀態轉移圖(BSTG)後，內層行為狀態轉移圖(BSTG_i)，和外層行為狀態轉移圖(BSTG_o)便可以各別地在相同的資源限制下被管線化；注意在內層行為狀態轉移圖(BSTG_i)，和外層行為狀態轉移圖(BSTG_o)管線化後的組合管線存在著可變的潛伏期。管線化設計內層迴圈比管線化設計外層迴圈容易，這是因為管線化內層迴圈時，可以暫時不必考慮內外層迴圈間的互動以及先行限制 precedence constraints)。因此，內層迴圈可以直接使用發明人在1991年Proc. of the ISCAS第1769-1772頁所揭示的傳統管線化方法進行管線化。在內層迴圈管線化之後，產生的管線化內層行為狀態轉移圖(PBSTG_i)則由包括前置體(Prelude)、重複管線化體(repeating pipeline body，2) 以及後置體(postlude)三部分所組成。在排序電路的例子中前置體和後置體的狀態可以從管線化內層行為狀態轉移圖(Pipeline BSTG_i，PBSTG_i)中移到外層行為狀態轉移圖 (BSTG_o)，以進一步如圖5所示提昇管線化內層行為狀態轉移圖(pBSTG_i)的執行速度。而在前置體和後置體的狀態移入外層行為狀態轉移圖(BSTG_o)之後，如圖6所示排序電路的外層行為狀態轉移圖(BSTG_o)中設定訊號啟始(start)為1 的運算必須被移到內層無運算狀態(Noop_i，15)的母狀態 (parent state)，以正確的啟動管線化內層行為狀態轉移圖 (PBSTG_i)。此外，一旦管線化內層行為狀態轉移圖(PBSTG_i) 進入外層無運算狀態(Noop_o，16)即表示它已完成執行，因此排序電路其管線化內層行為狀態轉移圖(PBSTG_i)的外層無運算狀態(Noop_o，16)如圖9所示必須加入設定執行 (done)為1的運算。圖4(b)為排序電路其內層行為狀態轉移圖(BSTG_i)的內層迴圈，經管線化為如圖5(a)所示管線化內層行為狀態轉移圖(PBSTG_i)，將圖5(a)的前置體(prelude)和後置體 (postlude)中所有狀態移除後，獲得如圖5(b)所示排序電路新的管線化內層行為狀態轉移圖(PBSTG_i)。將圖5(a)的前置體(prelude)和後置體(postlude)中所有狀態移到外層行為狀態轉移圖(BSTG_o)後，獲得如圖6所示排序電路新的外層行為狀態轉移圖(BSTG_o)。步驟3--外層迴圈之管線設計外層迴圈管線化比內層迴圈管線化更重要且更困難，這是因為不同迴圈間的相依關係必須被考慮，並且其內層無運算狀態(Noop_i)的執行次數是無法預知的；亦即內層行為狀態轉移圖(BSTG_i)執行的時間區間，由於存在著資料的相依性因此無法預知。設定一個外層行為狀態轉移圖 (BSTG_o)，其外層迴圈管線化的目標是要尋找一個滿足整體先行關係，及資源限制的管線化外層行為狀態轉移圖 (PBSTG_o)。本發明採用類似於1990年R. Potasman，等人於ACM/IEEE Design Automation Conference，第444-448頁揭示之過濾排序法(percolation based scheduling)，漸次展開(incrementally unwind)迴圈的方法來管線化外層迴圈。當新的循環(iteration)展開時，運算(operations)被允許在管線化外層行為狀態轉移圖(PBSTG_o)的狀態間移動，以獲得較好的設計，運算的移動受限於資源限制以及運算間的先行關係。在少數的循環被展開並管線化以後，即可找出重複管線化體(repeating pipeline body，2)。將找到的重複管線化體(2)取代原來的迴圈體(loop body)即可獲得原迴圈管線化以後的表示式。除了傳統的處理方式，管線化外層迴圈時有一些特殊的考量。當重覆執行迴圈時，運算不能移入內層無運算狀態 (Noop_i，15)；有時則要加入新的狀態以延遲某些運算，使得它們符合限制。再者，由於內層行為狀態轉移圖(BSTG_i) 的執行週期是未知的，使得外層行為狀態轉移圖(BSTG_o)的內層無運算狀態(Noop_i，15)的執行次數也是未知的，這使得外層行為狀態轉移圖(BSTG_o)的管線化十分困難。要使管線化變為可能，亦即找出重複管線化體(repeating pipeline body，2)，並確保滿足迴圈間的先後執行關係，外層行為狀態轉移圖(BSTG_o)中的內層無運算狀態(Noop_i)必須首先被展開，形成它的連續α份拷貝N₁，N₂，...，Nα。內層無運算狀態(Noop_i)的拷貝數目α，可用以下的方法加以決定。本發明首先定義外層行為狀態轉移圖(BSTG_o)中狀態x至初始狀態(initial state)的距離(distance)D(x)如下：其中p(x)是狀態x的母狀態(parent state)所組成之集合。在找D(x)之前必須將外層行為狀態轉移圖(BSTG_o)中所有的反饋邊(feedback edges)移除。再者令集合Ω_j+1代表，外層行為狀態轉移圖(BSTG_o)的第j+1個循環(iteration)中由於某些受到資料相依性，或者資源限制之類限制而必須在i+j層無運算狀態(Noop_i,j)之後所有執行狀態的集合。假如外層行為狀態轉移圖(BSTG_o)的第j+1個循環(iteration)，在第j個循環啟動後L個狀態(時鐘週期)後啟動，並且假設距離狀態S_i,j+1是集合Ω_j+1的所有狀態中具有最小距離(distance)者，α＞1則α由以下的方程式決定：請注意集合Ω_j+1必然不會是空集合，這是因為至少i+ (j+1)層無運算狀態(Noop_i,j+1)必須在i+j層無運算狀態 (Noop_i,j)之後啟動，以避免同時執行不同循環(iteration)的內層迴圈，所以此至少為1。若α算出的值為負或是等於零時，均用α=1來代替，因為此時內層迴圈與外層迴圈有資料相依的情形，故外層迴圈並沒有辦法提前的動作，要等到內層迴圈動作完成後，外層迴圈才能再繼續動作。上述管線化外層行為狀態轉移圖(PASTG_o)係利用一般的管線化方法將行為外層狀態轉移圖(BSTG_o)做管線化的處理，但是外層部分每次循環的啟動時間受到內層迴圈執行次數多寡的影響，故在外層行為狀態轉移圖中插入N 個運算，代表執行內層迴圈所需用掉的狀態數(states)，其中α代表內層部份與外層部份可以同時執行的最大個數。再利用一般的管線化方法將插入Nα的外層行為狀態轉移圖(BSTG_o)進行管線化成為一種管線化外層行為狀態轉移圖(PBSTG_o)，以及找出外層迴圈重複執行的部分。利用上述的方法將排序電路外層迴圈的重複管線化體 (repeating pipeline body，2)找到以後，所有在相同時間執行的不同循環(iteration)之排序電路，如圖7所示其外層行為狀態轉移圖(BSTG_o)狀態形成一個管線化外層行為狀態轉移圖(PBTG_o)的狀態。隨後，排序電路的管線化外層行為狀態轉移圖和管線化內層行為狀態轉移圖(PBSTG_i)必須做某些修正以保持原來電路的行為。首先，在排序電路的設計中本發明規畫在管線化外層行為狀態轉移圖 (PBSTG_o)到達包含N₁的狀態時，必須啟動管線化內層行為狀態轉移圖(PBSTG_i)。因此，設定啟始(Start)為1的運算必須被移到包含N₁的母狀態(parent state)以正確地啟動管線化內層行為狀態轉移圖(PBSTG_i)。第二，因為管線化內層行為狀態轉移圖的執行長度是未知的，所以必須在管線化外層行為狀態轉移圖(PBSTG_o)中包含N_α的狀態和它的子狀態(child state)之間加入一個新的狀態亦即X層無運算狀態(Noop_x)以等待管線化內層行為狀態轉移圖 (PBSTG_i)結束它的執行，使得迴圈間的先後執行的關係可以被滿足。修正之後，即產生一個最後的管線化外層行為狀態轉移圖(PBSTG_o)。最後，當排序電路其管線化外層行為狀態轉移圖 (PBSTG_o)的重複管線化體(repeating pipeline body，2)中所有的狀態皆包含某一個N_i(1＜i＜α)時，管線化外層行為狀態轉移圖(PBSTG_o)中設定啟始(start)為1的運算必定在X層無運算狀態(Noop_x)中執行。這使得管線化內層行為狀態轉移圖(PBSTG_i)必須具備完成執行後不進入外層無運算狀態(Noop_o)而能夠立刻被啟動的能力。因此，原來的排序電路其管線化內層行為狀態轉移圖(PBSTG_j)必須做以下的修改。首先，狀態PS_x到X層無運算狀態(Noop_x) 的子狀態(child state)之間必須加入一個標示條件 (donestart)的邊，其中PS_x是管線化內層行為狀態轉移圖 (PBSTG_i)中具有標示條件執行(done，12)及已經執行邊之分支狀態。此外，管線化內層行為狀態轉移圖(PBSTG_i)中具有執行(done)之邊(edge)的標籤必須以新標籤取代之，使得它能被工確地啟動如圖9 所示。圖6中排序電路的外層行為狀態轉移圖(BSTG_o)的初始潛伏期是3，圖7則列出圖6漸次展開4次的結果。在排序電路的外層行為狀態轉移圖(BSTG_o)中，i+(j+1)層無運算狀態(Noop_i,j+1)必須在i+j層無運算狀態(Noop_i,j)之後啟動，因此原來排序電路的無運算狀態(Noop)必須展開為α= 3+5-5=3個連續的無運算狀態如圖7所示之N₁，N₂和N₃。最後排序電路的外層管線化行為狀態轉移圖(PBSTG_o)如圖8 所示。因為圖8的管線化外層行為狀態轉移圖(PBSTG_o)的重複管線化體(repeating pipeline body，2)中所有的狀態皆包含某一個N_i，圖5(b)中原來排序電路的內層管線化行為狀態轉移圖(PBSTG_i)必須被修改為圖9。步驟4--資料路徑之設計發明人在1991年Prac. of the ISCAS第1769-1772頁所揭示的技巧可以被進一步拓展來配置動態管線化資料路徑。在描述配置之前，本發明先定義管線化外層行為狀態轉移圖(PBSTG_o)和管線化內層行為狀態轉移圖(PBSTG_i) 間的協同狀態對(concurrent state pair)。若一個管線化外層行為狀態轉移圖(PBSTG_o)的狀態PS_m包含一個行為狀態轉移圖(BSTG_o)的無運算狀態(Noop)N_i，則它將與管線化內層行為狀態轉移圖(PBSTG_i)中的某一狀態PS_n同時被啟動，本發明稱狀態PS_m和PS_n是一個協同狀態對(concurrent state pair)。在動態管線中，除了在協同狀態對中或者在相同狀態中的運算不能共用相同的硬體單元外，所有管線化外層行為狀態轉移圖(PBSTG_o)及管線化內層行為狀態轉移圖 (PBSTG_i)的不同狀態中的運算皆能共用相同的硬體單元。因此，在找出所有協同狀態對(concurrent state pair)之後，即可使用發明人在1991年上述資料所揭示的方法進行配置工作。所有管線化外層行為狀態轉移圖(PBSTG_o)和管線化內層行為狀態轉移圖(PBSTG_i)間的協同狀態對(concurrent state pair)可以藉由建構管線化內層行為狀態轉移圖 PBSTG_i)的執行串列(execution linked lists)T’s來找出。每一個執行串列T’s的元素(element)對應到一個管線化內層行為狀態轉移圖(PBSTG_i)的狀態。令管線化內層行為狀態轉移圖的外層無運算狀態(Noop_o)其中的子狀態(child state)對應到每個執行串列T的第一個元素，則建構執行串列的步驟是先移除管線化內層行為狀態轉移圖(PBSTG_i)的外層無運算狀態(Noop_o)，然後從第一個元素開始列舉出管線化內層行為狀態轉移圖(PBSTG_i)中所有可能的執行路徑直到路徑長度為α-1為止。假設執行串列第一個元素的程度 (level)為1，則每一個串列在它的最後一個元素的程度為 α時被終止。在所有執行串列T’s建構完成以後，若管線化外層行為狀態轉移圖(PBSTG_o)的狀態PS_m包含外層行為狀態轉移圖(BSTG_o)的無運算狀態(Noop)N_i，則它與每一個執行串列T其中程度(level)為i的狀態PS_n成為一個協同狀態對(concurrent state pair)，以表示之。在插入排序器的例子中唯一的執行串列是PS₁-PS₂-PS₁，因此找出的協同狀態對(concurrent state pair)是步驟5--動態管線之控制器設計最後，本發明必須根據動態管線化方法所決定之動作先後順序的結果，以及資料路徑結果，設計一個控制器以掌控資料路徑單元的執行。上述動態管線化方法所決定之動作先後順序的結果，就是管線化外層行為狀態轉移圖 (PBSTG_o)和管線化內層行為狀態轉移圖(PBSTG_i)。此控制器由外控制器(outer controller，6)和內控制器(inner controller，3)兩部分所組成。外控制器(6)和內控制器(3) 分別由管線化外層行為狀態轉移圖(PBSTG_o)和管線化內層行為狀態轉移圖(PBSTG_i)推導而來。交談訊號如啟始 (start)及執行(done)被用來協調這兩個控制器的動作。啟始訊號是由外控制器(6)設定。當外控制器(6)在包含N₁的狀態的母狀態(parent state)時，啟始被設定為1以啟動管線化內層行為狀態轉移圖(PBSTG_i)的執行如下式(3)所示，以 θ代表此母狀態(parent state)：執行訊號(done)則是由內控制器(3)設定之。當管線化內層行為狀態轉移圖(PBSTG_i)在外層無運算狀態(Noop_o) 時，或者是在產生條件ci的狀態π且ci=0時，執行訊號 (done)被設定為1。也就是：資料路徑是由內控制器(3)、外控制器(6)共同控制，這兩個控制器可能同時發出不同的控制訊號到相同的硬體單元，例如算數邏輯單元(ALU)、暫存器、或者是多工器；進行各種暫存器配置(register allocation)以及運算單元配置(ALU allocation)。針對內層部份以及外層部份利用一般的方法處理即為資源配置(resource allocation)。另一方面，這種兩個控制器同時發出不同控制訊號到相同硬體單元的現象被稱為控制衝突(control conflicts)。對於一個遭遇控制衝突的硬體單元X，本發明解決此問題的方法是，使用一種控制訊號對多工器加以選擇，可選擇其中內控制器(3) 或外控制器(6)之一個，此多工器係使用run作為選擇訊號。詳細敘述如下，選擇訊號(run)係由外控制器所設定，當選擇訊號(run)呈現0表示控制訊號已經選擇外控制器；否則選擇內控制器。因此在排序電路的設計中，當外控制器在無運算狀態(Noop)時，資料路徑的控制權則在內控制器，此時選擇訊號(run)被設定為1。此外，當外控制器在某些協同狀態(concurrent state)Ω_i，而在這些狀態中單元X配置給管線化內層行為狀態轉移圖(PBSTG_i)的運算，則選擇訊號 (run)被設定為1。也就是解決單元X控制衝突的訊號run(X) 由以下的方程式設定：圖10是根據上述法則所設計之一種排序器電路控制器基本架構。然而控制電路的設計並不一定要分成內控制器(3) 以及外控制器(6)兩部份，亦可以先將管線化內層行為狀態轉移圖(PBSTG_i)與管線化外層行為狀態轉移圖(PBSTG_o) 結合成一個管線化(Pipelined)之行為狀態轉移圖(BSTG)，而將內控制器(3)及外控制器(6)結合成一個單一控制器，再配合原先的控制訊號啟始(start)、執行(done)、選擇(run) 組合而成一個單獨的控制電路。設計實例與實驗結果說明為了驗證動態管線化方法的效能，本發明分別設計了二元算數編碼電路、插入排序電路(insertion sorter)、以及模糊邏輯色彩修正電路等三個ASIC例子的傳統循序架構以及動態管線架構，並分析比較它們的時效如下。在二元算數編碼器方面，本發明使用三種不同類型的十二個檔案來做壓縮實驗。其結果報告如表1所示。表1 中的“C-ratio”表示資料壓縮率，“C-speed(S)”和 “C-speed(P)”則分別表示循序架構以及動態管線架構的壓縮速度。上述所謂的循序架構，乃是用一般傳統的循序架構電路設計法：先排定所設計動作的執行時序，安排分配硬體元件，導出其資料路徑(Data path)，推出狀態圖表，再進行相對應組合電路與序向電路之化簡與產生；其中並不使用管線式設計法。表1結果顯示可以獲得約2倍的時效提昇(Speedup)。至於在硬體成本方面，動態管線架構的輸出(layout)用了約65k個電晶體如圖11所示，循序架構使用S.R.Kuang等人於IEEE Transactions on Circuits ﹠ Systems Part I.所揭示之54k個電晶體，亦即使用0.8μm互補式金氧半電晶體製程(CMOS process)及CIC所提供之 cell library，動態管線架構約增加了20%的硬體成本，與時效提升相比，這是可接受的。至於在周期(cycle time)方面，雖然本發明會增加控制器之複雜度，表面上看似乎會拉長周期(cycle time)，但可藉由資料路徑(Data path)的管線化來縮短周期(cycle time)，就如同傳統管線化法設計之高速電路一般。所以在周期(cycle time)方面，本實驗所有例子其動態管線架構與循序架構皆是用相同的周期(cycle time)值。至於插入排序電路，本發明使用八組資料(Data 1~Data 8)進行實驗。資料1及資料5包含已經由小至大排好順序的資料，資料2及資料6包含由大至小的反相順序(inverse order)資料，資料3、資料4、資料7、及資料8包含沒有一定順序(random order)的資料；其實驗結果報告如表2 所示。表2中“資料大小(data size)”表示需要被排序的資料數目；而“sequential”及“dynamic pipelining”分別表示循序架構以及動態管線架構將資料排序所需要的時鐘周期 (clock cycle)數目。“speedup”則表示動態管線架構比循序架構所得的時效提昇倍數。結果顯示可以獲得約1.9倍的時效提昇。本實施例中僅做硬體架構設計與模擬，因此、在硬體成本方面，只就元件數目加以說明。動態管線架構只比循序架構多用了9個暫存器，在其他元件使用方面是完全一樣的。至於控制器的大小由循序架構的9個狀態 (states)增加至動態管線架構的16狀態(states)，但是其對應之狀態暫存器並沒有增加。就時效的提升而言，這些額外的硬體增加現象屬於可接受程度。至於在模糊邏輯色彩修正電路方面，本發明使用四種不同檔案大小的圖形來作實驗，其資驗結果報告如表3所示。在表3，I是代表平均的迴圈潛伏期(latency)，“循序架構(sequential)”及“動態管線架構(dynamic pipelining)”分別表示循序架構以及動態管線架構將資料排序所需要的時鐘周期(clock cycle)數目，”speedup”則表示動態管線架構比循序架構所得的時效提昇倍數。結果顯示亦可以獲得約2倍的時效提昇。本實施例僅做硬體架構設計與模擬，因此在硬體成本方面，只就元件數目加以說明。動態管線架構只比循序架構多用了3個暫存器，另外動態管線架構多用了一個除法器與一個乘法器，而循序架構因動作較單純，將此二元件合併成一個乘除法器，其他元件使用情形是完全一樣的。至於控制器的大小由循序架構的13個狀態 (states)增加至動態管線架構的22狀態，但其對應狀態暫存器只增加1個。就時效的提升而言，這些額外的硬體增加現象屬於可接受程度。由以上設計實例之結果顯示，本動態管線化硬體設計法確實能夠有效提昇時效，且本新方法其與傳統管線法所造成的(overhead)是相當的；會增加暫存器之個數，可能增加某些元件之數目，控制線路會變複雜；這些都是與傳統循序架構(sequential)方式設計之電路比較的。但其所獲得時效之提升也往往是循序架構方式電路的2倍或2倍以上，比用平行(parallel)方式設計來的划算，是以本新方法所付出的硬體代價是可以接受的。這也是現今所有高速電路(如CPU 等)皆用管線方式設計的原因。特點及功效本發明所提出的動態管線化硬體設計方法之特點，在於它使用一個由兩個相互交談的有限狀態機所組成的特殊控制器，以達成使用可變潛伏期方式，進而管線化執行時間可變的迴圈之執行並達到高時效的目標。此外，相對於所獲得的時效提昇，它所需要付出的是額外的面積，然而相較於一般的管線化處理方式，面積的增加是必然的現像，而且以其所獲得的效能遠比其增加的面積所造成的損失來的大，因此，它非常適合用於提昇具有執行時間可變的迴圈之特殊用途積體電路的時效。本發明可以應用在“用於無線互動式電視以灰色理論和模糊推論為基礎的可攜式媒體需求壓縮系統”計畫中的資料無損壓縮晶片之管線化設計，以進一步提昇資料編碼、解碼的時效。 [圖式簡單說明] 圖1、簡單管線 (a)固定值(Latency)=4 (b)有順序之固定值3,4,3,4... (c)不定，隨情況而變1,3,2,3,4,1... 圖2、插入排序電路的硬體行為描述圖3、插入排序電路的初始行為狀態轉移圖(BSTG) 圖4、圖3的行為狀態轉移圖(BSTG)分割結果 (a)行為狀態轉移圖(BSTG)以及 (b)內層行為狀態轉移圖(BSTG_i) 圖5、(a)原來的管線化內層行為狀態轉移圖(PBSTG_i)以及 (b)新的管線化內層行為狀態轉移圖(PBSTG_i) 圖6、圖5(a)的前置體(prelude)和後置體(postlude)的狀態移入後，獲得的外層新行為狀態轉移圖(BSTG_o) 圖7、圖6的外層行為狀態轉移圖(BSTG_o)漸次展開4次的結果圖8、插入排序電路最後的管線化外層行為狀態轉移圖(PBSTG_o) 圖9、插入排序電路最後的管線化外層行為狀態轉移圖(PBSTG_i) 圖10、動態管線化架構控制器的基本架構圖11、動態管線架構之二元算術編碼電路layout圖

十、申請專利範圍：
	1.一種可運用於可變執行時間的迴圈動態管線化方法，包括： (a)行為狀態轉移圖(BSTG)分割，將要設計之電路的行為，利用行為狀態轉移圖建立其所對應的模型，並且將此行為狀態轉移圖分為兩部份：一部份為固定執行時間的外層部份(BSTG_o)；一部份為可變執行時間的內層部份(BSTG_i)； (b)內層迴圈之管線設計，將內層的行為狀態轉移圖(BSTG_i)做管線化之設計與處理，進而得到管線化後的行為狀態轉移圖，以管線化內層行為狀態轉移圖(PBSTG_i)表示之； (c)-外層迴圈之管線設計，將外層行為狀態轉移圖(BSTG_o)做管線化之設計與處理，而得到管線化後的行為狀態轉移圖，以管線化外層行為狀態轉移圖(PBSTG_o)表示之； (d)-資料路徑之設計，把內外層部份分別管線化處理後，便針對管線化內層行為狀態轉移圖(PBSTG_i)及管線化外層行為狀態轉移圖(PBSTG_o)做資源配置(resource allocation)，以建構動態管線的資料路徑(data path)； (e)-動態管線之控制器設計，接下來利用管線化內層行為狀態轉移圖(PBSTG_i)產生內層部份的控制器，再由管線化外層行為狀態轉移圖(PBSTG_o)產生外層部份的控制器，藉由此兩個控制器或先整合此二控制器為一個控制器，再加上啟始(start)、執行(done)、選擇(run)等控制訊號組合而成動態管線化的控制電路。　　2.如申請專利範圍第1項所述之動態管線化方法，其中行為狀態轉移圖(BSTG)為一個有向循環圖，其頂點代表狀態，它的邊代表狀態轉移，而邊上的標籤則代表引發狀態轉移的條件。　　3.如申請專利範圍第1項所述之動態管線化方法，將迴圈動作中執行時間固定的部份與執行時間不固定的部份分割開來，執行時間固定的部份分割成外層行為狀態轉移圖(BSTG_o)，而執行時間不固定的部份，分割成內層行為狀態轉移圖(BSTG_i)。　　4.如申請專利範圍第1項所述之動態管線化方法，其中管線化內層行為狀態轉移圖(PBSTG_i)是利用一般的管線化方法將內層行為狀態轉移圖(BSTG_i)做管線化的處理，在此所謂一般的管線化方法，也就是將電路中迴圈的每次循環重疊執行之並藉此找到內層迴圈重疊執行的部分。　　5.如申請專利範圍第1項所述之動態管線化方法，其中管線化外層行為狀態轉移圖(PBSTG_o)是利用一般的管線化方法將外層行為狀態轉移圖(BSTG_o)做管線化的處理，但是外層部分每次循環的啟動時間受到內層迴圈執行次數多寡的影響，故在外層行為狀態轉移圖(BSTG_o)中插入Nα個運算代表執行內層迴圈所需用掉的狀態數(states)，其中α代表內層部份與外層部份可以同時執行的最大個數；再利用一般的管線化方法將插入Nα的外層行為狀態轉移圖(BSTG_o)管線化外層成管線化行為狀態轉移圖(PBSTG_o)，以及找出外層迴圈重複執行的部分。　　6.如申請專利範圍第1項所述之動態管線化方法，其中資源配置(resource allocation)是針對內層部份以及外層部份利用一般的方法來做暫存器配置(reG_ister allocation)以及運算單元配置(ALU allocation)。　　7.如申請專利範圍第1項所述的動態管線資料路徑(data path)設計方法即是利用管線化內層行為狀態轉移圖(PBSTG_i)及管線化外層行為狀態轉移圖(PBSTG_o)配合資源配置(resource allocation)所產生動態管線化的電路架構。　　8.一種執行動態管線化控制之電路設計架構，如下圖所示，其係包括一個內控制器、一個外控制及產生控制訊號啟始(start)、執行(done)、選擇(run)的電路，而其中外控制器即由管線化外層行為狀態轉移圖(PBSTG_o)所推導而來，內控制器由管線化內層行為狀態轉移圖(PBSTG_i)推衍而出，啟始(start)及執行(done)分別由內控制器及外控制器所產生，而選擇(run)訊號用來解決控制衝突，也就是避免內控制器及外控制器同時對相同的硬體發出一樣的控制訊號。　　9.如申請專利範圍第8項所述之電路設計架構，控制電路中的內控制器以及外控制器亦可結合成一個控制器，在設計控制電路時將管線化內層行為狀態轉移圖(PBSTG_i)以及管線化外層行為狀態轉移圖(PBSTG_o)同時的考慮，而以一個狀態圖表示之，形成結合兩個控制器功能之一個控制器。


十一、圖式：

瀏覽數:

分享

登入成功