[發(fā)明專利]基于機動性的高層次綜合調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201610996769.2
• 申請日: 2016-11-11
• 公開（公告）號: CN106599366A
• 公開（公告）日: 2017-04-26
• 發(fā)明（設計）人: 李勇;賈寶東;彭元喜;雷元武;陳書明;萬江華;田甜;海月;王建之;舒雷志;張松松;宋明輝;朱保周;張榜
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 湖南兆弘專利事務所(普通合伙)43008
• 代理人: 周長清

技術領域

本發(fā)明主要涉及到集成電路設計領域，特指一種基于機動性的高層次綜合調(diào)度方法。

背景技術

隨著集成電路技術的快速發(fā)展，一方面促進了相應設計技術的發(fā)展，另一方面也對設計技術提出了更高的要求。如今的集成電路設計，面臨著功能強、性能好、規(guī)模大、成本低、設計周期短等一系列要求和挑戰(zhàn)，這些要求和挑戰(zhàn)引起了在集成電路設計方法上的全面革新。新一代的集成電路設計方法在系統(tǒng)描述、電路生成、功能驗證等諸多方面與傳統(tǒng)的設計方法有明顯的區(qū)別。高層次綜合技術就是其中一個重要的、有代表性的設計技術。

高層次綜合技術是一種將高級語言轉(zhuǎn)化為硬件描述語言的技術。算子調(diào)度是高層次綜合中至關重要的一步，算子調(diào)度是將編譯轉(zhuǎn)換生成的控制數(shù)據(jù)流圖中的每一個算子分配到各個控制步中，從而實現(xiàn)滿足約束條件下最優(yōu)或較優(yōu)的算子調(diào)度方案。

如圖1所示，高層次綜合主要分為三個步驟：1.分配，分配要確定可用的硬件資源的量，并管理其他硬件約束(例如速度，面積和功率)；2.調(diào)度，調(diào)度用來確定操作將發(fā)生在哪一周期，考慮控制、數(shù)據(jù)流和用戶指令；3.綁定，綁定用于確定每個操作所使用的庫單元，綁定考慮了元件的延遲，用戶的命令。其中，調(diào)度是很關鍵的一步，調(diào)度算法的好壞決定了最終的硬件電路面積、速度、以及功耗。

傳統(tǒng)的主要調(diào)度方法有ASAP(As Soon As Possible)和ALAP(As Late As Possible)調(diào)度、列表調(diào)度、以及力量引導調(diào)度。

ASAP和ALAP調(diào)度是兩種最基本的調(diào)度方法。ASAP通常被稱為“盡可能早”的調(diào)度算法，ALAP通常被稱為“盡可能遲”的調(diào)度算法。這兩種調(diào)度算法是最基本、最簡單的調(diào)度算法。ASAP調(diào)度算法不考慮任何資源的限制而試圖尋找時間特性最好的方案。“盡可能早”意味著盡量早地執(zhí)行每一個操作，就是將所有操作賦于最早可能調(diào)度到的控制步。ALAP調(diào)度算法也不考慮任何資源的限制而試圖尋找時間特性最優(yōu)的方案。與“盡可能早”的算法不同，“盡可能遲”意味著盡量晚地執(zhí)行每一個操作，只有當一個操作必須被調(diào)度，否則就會導致電路不能夠在約束步內(nèi)完成的時候才會被調(diào)度。

列表調(diào)度算法是一種構造型調(diào)度算法，該算法來源于微碼壓縮技術。列表調(diào)度算法的核心是為每一個算子確定一個優(yōu)先級數(shù)，按照優(yōu)先級數(shù)從大到小的順序確定算子被安排的順序。例如以算子出現(xiàn)的先后順序作為算子的優(yōu)先級函數(shù)，即先出現(xiàn)的算子優(yōu)先級高，先被安排，后出現(xiàn)的算子優(yōu)先級低，后被安排。

力量引導調(diào)度的目的是通過使同類型的算子盡可能均勻的分布在各個控制步中來最小化所需要的資源。在力量引導調(diào)度中，為了更清楚更形象地表述控制步中的算子與控制步的關系力量引導算法從物理學中引入了“力”的概念。把一個控制步想象成一個可以承載砝碼的彈簧，而這些砝碼就是可能放入該控制步的算子。每個控制步都承受來自算子施加的“壓力”。按照“各個控制步中同類算子的數(shù)量盡可能平均”的原則，要使得各個控制步上的“壓力”盡可能的平均。

由上可知，傳統(tǒng)調(diào)度方法中，ASAP和ALAP調(diào)度給出的調(diào)度方案并不是真正實用化的方案，因為盡可能地將操作執(zhí)行時間提前或推遲必然會使資源復用性變差。列表調(diào)度算法最大優(yōu)點就是比較簡單，易于實現(xiàn)，在大多數(shù)情況下都能得到較優(yōu)的算子調(diào)度方案。但是列表調(diào)度算法只關心算子安排次序問題，對整個優(yōu)化過程考慮不全面，所以并不能保證所得到的結果最優(yōu)。另外，確定一個有效的算子優(yōu)先級函數(shù)也比較困難。力量引導調(diào)度算法既指出應該選擇哪個算子進行安排，又指出這個算子應該安排在哪一個控制步中，雖然能夠得到最優(yōu)的調(diào)度結果，但是它比較復雜，不易于實現(xiàn)。

發(fā)明內(nèi)容

本發(fā)明要解決的技術問題就在于：針對現(xiàn)有技術存在的技術問題，本發(fā)明提供一種原理簡單、易于實現(xiàn)、能夠提高綜合后電路的資源利用率、最終減小硬件電路面積的基于機動性的高層次綜合調(diào)度方法。

為解決上述技術問題，本發(fā)明采用以下技術方案：

一種基于機動性的高層次綜合調(diào)度方法，其步驟為：

S1：確定算子的機動性；

S2：確定算子的調(diào)度順序：從機動性最小的算子開始調(diào)度；

S3：調(diào)度算子：在確定算子的調(diào)度順序之后，開始將算子安排到確定的控制步。

作為本發(fā)明的進一步改進：在步驟S1中，通過計算每個算子的ASAP和ALAP調(diào)度結果，來得到每個算子的機動性，確定每一算子的活動范圍。