| 摘要: | 隨著行動裝置的低功率需求，衍生多重供應電壓(multiple supply voltages, MSV)的晶片設計模式， 對一顆系統晶片(SoC) 的實體設計平面規劃或佈局而言，則形成了時脈島網路(clock island network)， 其時脈延遲(clock latency)、邊界時序偏移(boundary clock skew)及功率消耗等，將決定此顆晶片的執行 效能與可靠度。 傳統的 MSV 設計方式是將原始電路分割成數個電壓島(voltage islands)，並將相同供應電壓的單 元區塊擺放在同一電壓島，而著重效能區塊的電壓島則施以較高的供應電壓；利用不同電壓島供應不 同電壓的設計模式，可降低晶片的整體功率消耗。動態式多重供應電壓(multiple dynamic supply voltage, MDSV)設計方式是讓各電壓島可動態地改變供應電壓而因應其功能運作情況，如此較符合晶片實際操 作與需求，當一電壓島處理大量計算工作時，則使用較高的供應電壓，相對地，處理非著重效能工作 時，可使用較低的供應電壓，藉此動態地節省能量。因此，能夠在數十個電壓島在動態電源供應模式 下而完成時脈樹的建置，降低晶片整體功率消耗，且能保持原本的晶片效能，此即為本研究計畫的目 的。 我們定義在 MDSV 設計下的時脈樹建置之問題，輸入為已知一組時脈端點與端點電容量、數十 個電壓島、每個電壓島至少工作兩種電壓、數種電源工作模式及邊界時序偏移限制值；輸出為在不會 違反邊界時序偏移限制值而合成出一個具有ADBs 的時脈樹建置。對於這個問題，我們提出在MDSV 設計環境下之時脈樹建置演算法流程，分為(1)建立一個具有插入緩衝器之時脈樹的主要步驟(main step for buffered clock tree construction)、(2)再具有插入ADBs 修正之緩衝器時脈樹建置的後端最佳化 步驟(post-optimization step for inserted-ADBs & buffered clock tree construction )及(3)進一步作整數線性 規劃最佳化步驟(ILP optimization step for inserted-ADBs & buffered clock tree construction)等三個部 份。主要步驟採用一負載平衡式的時脈樹合成器，首先以最小擴張樹(MST)的方式去估計連線的等效 電容，然後執行以圖形理論為基礎的叢集(clustering)方法；為了減少連接各電壓島之間的連線延遲與 時序偏移，將叢聚方法分為本地階層 (local-leveled)與全域階層(global-leveled)叢聚，並考量電容負載 平衡。叢聚完成之後，這些時脈端點所構成的數個電壓島已達到負載平衡的情況，再對時脈樹逐層插 入緩衝器。後端最佳化步驟包含了四個流程，在每一電源模式下，由上而下地插入具可調整延遲時間 式緩衝器(adjustable delay buffer, ADB)並指派延遲時間與由下而上地估計ADB 並擴展延遲時間等兩 者，逐步以ADBs 與指派延遲時間取代一些buffers 使時脈延遲與時序偏移盡量最小化，再以返回追 蹤，在不違反邊界時序偏移下而消除不必要取代的ADBs；進一步，另兩者在多種電源模式下的插入 ADBs 並指派延遲時間及延遲時間的改善等，整合電源模式導向設計之最佳化(power-mode-guided optimization)方法，在MDSV 下均不違反邊界時序偏移，進而控制每個時脈樹的節點會有0 個至電源 模式數相同多個的延遲時間被指派，且進一步將每個ADB 的延遲時間種類減至最少，使時脈樹能具 有最小的時序偏移。最後輸出結果為在MDSV 設計下而合成出一個具有插入ADBs 修正之緩衝器的 時脈樹建置，且不違反邊界時序偏移限制。為了驗證與評估所提出一個具有插入緩衝器之時脈樹建置 與再具有插入ADBs 修正之緩衝器時脈樹建置的後端最佳化等兩步驟之結果，將以此結果當已知，再 重新以整數線性規劃對插入ADBs 與緩衝器作指定時間延遲之最佳化，且將演算法與數學方法等兩者 獲得結果作一比較。 本研究計畫為兩年連續性的工作，第一年的工作正在進行中，依據所提出的 MDSV 設計環境下 之時脈樹建置演算法流程，建立一個具有插入緩衝器之時脈樹的主要步驟已初步完成與結果，而再具 有插入ADBs 修正之緩衝器時脈樹建置的後端最佳化步驟也已有初步的雛形；第二年計劃研究重點為 延續第一年獲得的經驗與累積成果，尤其是，再具有插入ADBs 修正之緩衝器時脈樹建置的後端最佳 化步驟，考量以[25]之可作片段延遲時間(如10ps)連續地調整延遲時間式緩衝器(continuously adjustable delay buffer, CADB)之擴充模型，及擴充電壓島的電壓模式如0.8v, 1.0v 和1.2v 等至少三種，使 MDSV 的操作環境下，各種組成電源模式更多元，對整體時脈樹之調整延遲時間與時序偏移的彈性更大。再 將以此結果當已知資訊，重新設計以數學規劃方法如MILP(mixed integer linear programming)，對此結 果作最佳化，即對CADB 插入總數量及所有CADB 數量之總延遲時間作最小化，此舉可將演算法與 數學方法等兩者獲得結果在延遲時間、時序偏移、CADB 數量與執行時間等作比較，可進一步解析所 提出的演算法與數學方法最佳化結果的真實差異。
As the low power requirements of mobile electronic devices, multiple supply voltages have applied to a chip or SoC (system-on a chip) design. Consequently, there is a voltage-island-based clock network in the floorplanning or placement of physical design for a SoC. The clock latency, boundary clock skew, and power consumption dominate the performance and reliability of the SoC. Traditional MSV designs that partition the original IC into several “voltage islands”. Modules or blocks are powered by same voltage and grouped into same voltage island. Higher voltage level is used in timing critical paths while lower one is used for blocks that are not critical performance. Multiple dynamic supply voltage (MDSV) techniques are proposed to provide dynamic energy saving. For non-performance critical jobs on voltage islands, lower supply voltages can be assigned for power saving. For computationally intensive jobs on voltage islands, higher supply voltages can be assigned for keeping high performance. Thus, by dynamically adjusting the supply voltages in each voltage island, MDSV designs can reduce power consumption while still keeping the performance. Solving the above of them is the purpose of our proposal. We define the problem of clock tree construction on MDSV design. Given a set of clock sinks with defined their loading capacitances, number of voltage islands and each voltage island works at least two supply voltages, number of dynamic power modes, and a boundary clock skew, the objective is to synthesize a adjustable delay buffered (ADB) clock tree without skew violation in the MDSV designs. We propose three steps of algorithmic flowchart to solve the above problem, which include: (1) main step for buffered clock tree construction, (2) post-optimization step for inserted-ADBs & buffered clock tree construction, and (3) ILP optimization step for inserted-ADBs & buffered clock tree construction. The main step propose a load-balanced clock tree synthesizer and adopts the minimum spanning tree (MST) metric to estimate the interconnect capacitance and execute the graph theoretic clustering. With local-leveled and global-leveled clustering methods and the consideration of loading capacitance balance, the clock latency and skew can be reduced. Then buffers can be inserted into the clock tree level by level. The post-optimization step includes four jobs. In each power mode, both top-down ADB insertion with delay value assignments and bottom-up ADB elimination with delay value extensions first replace some buffers by ADBs with delay values for minimizing latency and matching boundary skew and then backtrack the clock tree to eliminate those unnecessary ADBs. Another both ADB insertion and delay value assignments and ADB delay value reduction in multiple power modes integrate the power-mode-guided optimization by controlling the inserted ADB delay value in each node of the clock tree and the delay level of each ADB can be thus reduced but no violation for boundary skew. Finally, we can get the objective result using the above algorithm. The ILP step adopts the algorithm-based result as input to optimize the delay value assignments of inserted ADBs and buffers for obtaining optimal result. Comparing the differences of algorithm-based and ILP-based results, thus we can evaluate the proposed algorithm. This is a two-year project proposal. The first-year job is under working and the main step for buffered clock tree construction has been finished. The post-optimization step for inserted-ADBs & buffered clock tree construction has also implementing. The work of second year is to extend the first-year experimental results and to improve, especially for the post-optimization step, we adopt the continuously adjustable delay buffer (CADB) in [25] (e.g., 10ps per delay level) and extend each voltage island at least three kind of voltages (e.g., 0.8v, 1.0v, and 1.2v) for more multiple power modes. With the above expansion, we refine the post-optimization step of the algorithm flowchart to produce buffered clock tree with CADB insertion in MDSV designs. Then, we adopt the algorithm-based result as input and define their objective and constraints to optimize the delay value assignments of inserted ADBs and buffers. Then, the MILP (mixed integer linear programming) mathematical approach is applied for obtaining optimal result. Finally, we compare the differences of algorithm-based and ILP-based results in terms of clock latency, skew, and number of CADB and evaluate the proposed algorithm. |
