演算法之本質資料傳輸率量化方法Quantifying method for intrinsic data transfer rate of algorithms

專利類型

發明

專利國別 (專利申請國家)

美國

專利申請案號

13/700,336

專利證號

US 9,092,384 B2

專利獲證名稱

演算法之本質資料傳輸率量化方法Quantifying method for intrinsic data transfer rate of algorithms

專利所屬機關 (申請機關)

國立成功大學

獲證日期

2015/07/28

技術說明

此發明提出演算法複雜度中本質資料傳輸量的度量量化方法。這個資料傳輸量度量方法可以幫助演算法暨架構共同設計以同時探索演算法與架構，進而最佳化整體系統設計。演算法的複雜度分析與資料流模型，在同時最佳化演算法與架構時，扮演了十分重要的腳色。對於日益複雜的演算法而言，資料傳輸量毫無疑問地是最重要的複雜度參數之一。藉由演算法資料流模型並將相關的資料流圖型映射至線性方程式系統，進而分析相依矩陣以及拉普拉司矩陣，此發明可以有系統地量化演算法的本質資料傳輸量。更進一步地，此發明所萃取出之本質平行度可以有效地幫助複雜演算法在一般性的平台上做設計空間探索，因為這個複雜度標準具有平台獨立性而且可以在設計早期就把架構中重要的資訊給萃取出來。 The present invention discloses algorithmic complexity measuring methods on intrinsic data transfer rate for the Algorithm/Architecture Co-exploration design methodology capable and hence optimize systems. Algorithmic complexity analysis and dataflow modeling play significant roles in the concurrent optimization. The intrinsic data transfer rate is undoubtedly one of the most important complexity metrics. Based on dataflow modeling of algorithms and mapping the dataflow graphs onto linear equations with dependency and Laplacian matrices, the present invention is capable of systematically quantifying data transfer rates of algorithms based on the concept of edge cut in graph theory. Furthermore, the extracted intrinsic data transfer rate can effectively facilitate the design space exploration of generic platforms at various data granularities, since this complexity metric is platform-independent and capable of revealing essential architectural information at early design stages.

備註

連絡單位 (專責單位/部門名稱)

企業關係與技轉中心

連絡電話

06-2360524

網址