特殊應用處理器的高階合成流程與演算法

Methodologies and Algorithms for High-Level Synthesis of Application Specific Processors

余承叡(Cheng-Juei Yu)

指導教授 ： 王勝德

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2011年)

https://doi.org/10.6342/NTU.2011.01457

摘要

近年來，由於電子系統複雜度的提升，使得設計層級與設計抽象度需隨之提高，例如使用行為層的描述。高階合成是處理行為層描述的主要工作，其包含三項子工作以產生資料路徑、控制邏輯與記憶元件：資源配置、連接與排程。其中資源排程被認為是高階合成處理中，最重要的一項工作。本論文的主題之一為研究資源限制下的排程問題，並提出兩種效能比已有技術更好的搜尋演算法來求此問題的最佳解。我們提出的演算法能夠有效率得切除不必要的搜尋空間，並經由理論上的分析得出該演算法進行搜尋運算時，在時間與空間上的優勢。
除了我們能夠處理資料路徑的排程之外，本論文並提出一連串的方法，用以處理由Ｃ程式語言所描述的應用程式，並將之轉成特殊應用的處理器硬體電路。在應用程式中，函數呼叫時的動態信息傳遞與其所代表的控制路徑的轉換與處理也在我們的考量範圍中。基於階層式有限狀態機的觀念並進一步延伸，我們提出一些階層式狀態機的樣板作為硬體電路設計的基本模組。應用程式經由建議的改寫方式，可編譯成為能以階層式狀態機描述的較低階的設計，並繼續轉成可合成的硬體描述語言，最後得到一個與應用程式功能相同的特殊應用處理器。在過程中，階層式狀態機可看作一種介於Ｃ語言與硬體描述語言間的中間描述，並可做功能性的模擬，提供週期精確或週期近似兩種不同程度的模擬方式。最後，經由實驗數據，本論文的最後展示我們提出的方法的使用效能，並與已有的工具與方法做詳盡的比較。

關鍵字

高階合成 ； 搜尋演算法 ； 自動化設計 ； 排程演算法 ； 階層式有限狀態機

並列摘要

Growing design complexity has led designers to generate designs at higher levels of abstraction, such as, the behavior description level. The core task for synthesizing the behavior description is the high-level synthesis (HLS), which contains three main steps to create a hardware architecture of datapath elements, control logic and memory elements: resource allocation, binding and scheduling. Among these tasks, resource scheduling is considered the most important in a HLS process. A part of this thesis is devoted to the study of the problem of resource-constrained scheduling (RCS) and proposes two search algorithms to exactly solve the problem in an effective, systematic way. The proposed algorithms are capable of reducing the computational effort required to obtain the best schedules on a pre-defined datapath by effectively pruning the non-promising search space. The effectiveness of the algorithms against existing approaches over time and space is demonstrated by theorems and related analysis. Furthermore, this thesis also presents methodologies that help convert a given application specified in C programming language into a hardware implementation of a custom processor.
Besides datapaths representing standalone functional blocks the proposed RCS algorithms can schedule effectively, control paths representing calls of functions are also considered. Based on and extended from the concept of hierarchical finite-state machines (HFSMs), a number of built-in HFSM templates are proposed and used as the elementary components of a hardware design. Guidelines on the refinement of a C program are introduced; the refined C functions are compiled into HFSMs that in turn generate synthesizable hardware description language (HDL) code as the final design. A set of HFSMs is viewed as an intermediate representation between C and HDL and can be functionally simulated. Two modeling levels, i.e. cycle-accurate and cycle-approximated, are supported. In the end of this thesis, experimental results on a series of several well known algorithmic benchmarks demonstrate the effectiveness of the proposed algorithms and approaches against existing ones.

並列關鍵字

High-Level Synthesis ； Search Algorithms ； Design Automation ； Resource-Constrained Scheduling ； Hierarchical Finite State Machines

參考文獻

[3] P. Coussy, et al., "An Introduction to High-Level Synthesis," Design & Test of Computers, IEEE, vol. 26, pp. 8-17, 2009.

[4] S. A. Edwards, "The Challenges of Synthesizing Hardware from C-Like Languages," Design & Test of Computers, IEEE, vol. 23, pp. 375-386, 2006.

[5] C. E. Stroud, et al., "Behavioral model synthesis with Cones," Design & Test of Computers, IEEE, vol. 5, pp. 22-30, 1988.

[6] D. Ku and G. DeMicheli, "HardwareC -- A Language for Hardware Design (Version 2.0)," Stanford University1990.

[7] D. Galloway, "The Transmogrifier C hardware description language and compiler for FPGAs," in FPGAs for Custom Computing Machines, 1995. Proceedings. IEEE Symposium on, 1995, pp. 136-144.