考慮可退化複合型功能單元之延遲最佳化高階合成技術

Abstract

複合型功能單元(compound functional units)，例如：乘加器(MAC)，與基本功能單元(basic function units)相比，通常能夠設計成具有較少延遲與較小面積的優點，使用他們來做系統設計(system design)是很常見的方法。在這篇論文中，我們提出一個以整數線性規劃(ILP)為基礎的方法，稱為增強版考慮複合型功能單元的整數線性規劃演算法(eCILP)，以及一個啟發式(heuristic)的方法，稱為考慮複合型功能單元的列表式排程演算法(LSC)，來解決考慮可退化複合型功能單元(degenerable compound functional units)之延遲最佳化(delay optimization)高階合成(high-level synthesis)問題。由於其整數線性規劃的特色，eCILP保證能夠獲得最佳解，但在面對大型設計時可能無法在符合實際需求的時間內得到答案，而LSC能夠在非常短的時間內得到近似最佳解。藉由推導出複合型功能單元的所有可能退化型式與考慮功能單元數量使用限制下(resource constraints)之元件最佳利用，我們提出的兩個方法都是藉由從元件庫推導出來的樣式模板(patterns)來映對欲做高階合成的設計。eCILP的實驗結果顯示使用可退化複合型功能單元能夠使延遲改善最多達到百分之二十；而LSC除了實驗結果幾乎能夠和eCILP一樣好(差距只有在百分之二到百分之四之間)之外，在處理大型設計時也能夠在一秒鐘之內完成。

Utilizing compound functional units, e.g., multiplier-accumulator (MAC), designed with shorter delay and smaller area than cascaded basic functional units, is a well-known technique in system design. In this thesis, we present an ILP-based approach, named Enhanced Integer Linear Programming considering Compounds (eCILP), and a heuristic approach, named List Scheduling considering Compounds (LSC), to solve the delay optimization problem for high-level synthesis with degenerable compound functional units. Due to the ILP-based characteristic, eCILP guarantees the optimal solution but may fail to solve large-scale designs in practical runtime, whereas LSC obtains the near-optimal solution in a short period of time. By deriving all possible degenerative forms of compounds and maximizing the utilization of resources, both of the approaches exploit patterns derived from the given resource library to cover the target designs and achieve the synthesis result of a design under resource constraints. The experimental results of eCILP show that employing degenerable compounds can improve the delay up to 20%; moreover, LSC not only performs almost as well as eCILP does (the difference is only 2% to 4%), but also completes large-scale designs within 1 second.