使用分支設限技巧來解決高階合成中的時序問題

Abstract

在本論文中，對高階合成中的時序問題提出一個以分支設限技巧來解決的 快速方法。我們為提升速度，而推薦一些順序法則來當作設限程序。我們 造出 MPT其指示每個控制步(contorl step)中可能包函的運算元最大數目 。我們的演算法還支援了許多日常上不同形態如：多循環運算 (multicycle operations)，鏈運算(chaining operations)，管狀資料 道(pipelined data-paths)和互斥運算(mutually exclusive)。我們利用 一個簡單方法預先將臨界路線上的運算元排好以增進演算法速度。我們演 算法的複雜度為O(S*S*N*N)，其中S表控制步數目，N表臨界路線上的運算 元數目。由實驗結果顯示我們所提出的方法相當有效，且得到令人興奮的 結果。 This paper describes a fast method for the scheduling problem in high-level synthesis. The concept of Branch-and-Bound is the basis for this scheme. To reduce the computation time, we propose a series of priority rules to serve as bound functions. We create MPT graphs instead of distribution graphs, which have been used in most previous systems. MPT graphs indicate the maximum concurrency of similar operations in each control step. The algorithm supports a set of real-world constraint types, such as multi-cycle operations, chained operations, pipelined data-paths, and mutually exclusive operations. We pre-schedule the nodes on the critical path using a simple method that removes a subset of the total number of nodes from the computationally more expensive parts of the algorithm. The complexity of this algorithm in the worst case is O(N*N*S*S), where S is the number of C-steps and N is the total number of non-critical-path operations. The implementation of this scheduling method is presented using examples from the literature.