高階合成中使用臆測編碼轉換技術之排程等效驗證

Equivalence Checking of Scheduling with Speculative Code Transformations in High-Level Synthesis

李季慧

指導教授 ： 周景揚

國立交通大學/電機學院/電機學院IC設計產業專班/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00085

摘要

高階合成是一個將演算法層次的描述轉換成暫存器轉移層次設計的程序，它可以提昇生產力。然而這轉換程序容易錯誤。排程，高階合成的子工作，是驗證高階合成中最大的挑戰，因為排程會改變原來的執行順序。這篇論文的研究主題是排程驗證。我們提出一個正規方法可用來驗證排程前後的描述是否相等。排程前後的描述由包含資料路徑的有限狀態機所表示。它們一開始先被分解成有限條路徑；接著，在這些路徑中找到相等的路徑。兩個包含資料路徑的有限狀態機的相等和兩條路徑的相等在這篇論文中被定義。提出的方法不只適合驗證保留控制架構的排程，也適合驗證會改變控制架構的排程。排程改變控制架構藉由合併連續的路徑或將某些程式碼在不同的基本塊中移動。由驗證高階合成的測試程式的實驗結果顯示我們演算法可以有效地驗證排程。

關鍵字

高階合成 ； 排程 ； 等效驗證 ； 臆測 ； 公共子表達式刪除 ； 代碼移動

並列摘要

無資料

並列關鍵字

High-Level Synthesis ； Scheduling ； Equivalence Checking ； Speculation ； Commmon Subexpression Elimination ； Code Motion

參考文獻

[4] C. Y. Hitchcock and D.E. Thomas, “A Method of Automatic Data Path Synthesis,” Design Automation Conference, page 484-489, Jun. 1983.

[5] B. M. Pangrle and D.D. Gajski, “Slicer: A State Synthesizer for Intelligent Silicon Compilation,” IEEE International Conference Computer Design: VLSI in Computers & Processors, Oct. 1986.

[8] G. Lakshminarayana, A. Raghunathan, and N.K. Jha, “Incorporating Speculative Execution into Scheduling of Control-flow Intensive Behavioral Descriptions,” Design Automation Conference, page 108-113, Jun. 1998.

[9] L.C.V. dos Santos and J.A.G. Jess, “A Reordering Technique for Efficient Code Motion,” Design Automation Conference, page 296-299, Jun. 1999.

[10] M. Rim, Y. Fann, and R. Jain, “Global Scheduling with Code-motions for High-level Synthesis Applications,” IEEE Transactions on VLSI Systems, vol. 3, page 379-392, Sept. 1995.