《演算法本质平行度的分析方法》由会员分享，可在线阅读，更多相关《演算法本质平行度的分析方法（2页珍藏版）》请在金锄头文库上搜索。
1、演算法本质平行度的分析方法专利名称：演算法本质平行度的分析方法演算法本质平行度的分析方法 技术领域本发明关于一种分析与量化演算法的本质平行度(intrinsic parallelism)的方法。背景技术：阿姆达尔定律(G.M. Amdahl，以单处理器来达到大规模运算能力的可行性， AFIPS会议期刊，第483-485页，1967年)提出了一种软体程式的平行化的理论最大加速。 由于循序部份基于高资料相依性而不能被平行化，此理论最大加速是依程式中的循序部份 的比例来决定。阿姆达尔定律为特征化平行度提供了一个简单且初步的高阶想法。然而， 由此技术所量测的平行度取决于目标平台，而非演算法本身。所以，
2、这种平行度的量测对演 算法是非本质的，且会因目标平台而偏移。以相似的方式，以图为基础的技术(V. Escuder, R. Duran、R. Rico,以图论量化指 令层平行度，第二次效能评估方法与工具国际会议期刊，2007年)基于图论将程式的指令 层平行度(instruction level parallelism, ILP)量化。此技术一开始以资料相依性矩阵 D表示一指令序列。接着，程式的关键路径长度由D的矩阵乘法决定。此技术对于处理器导 向的平台更特定。因此，指令层平行度的量化并非演算法本质的，而是取决于目标平台与所 使用的编译器。Prihozhy等人基于运算复杂度与演算法的关键路径长度的
3、比例所定义的平行化 位准(parallelization potential)也能够估计平行度(A. Prihozhy、M. Mattavelli 与 D. Mlynek,为了有效率的实现多媒体的平行化位准的评估演算法关键路径的动态评估， IEEE影像技术电路与系统期刊，第593-608页，第15卷，第5号，2005年5月)。他们使用 运算的总数量来量测复杂度。然后，关键路径长度被定义为必须循序进行的运算的最大数 量。与阿姆达尔定律及指令层平行度方法比较，基于运算数量的平行化位准显现了更多的 本质平行度量测，但当然是在资料粒度较低的情况下。然而，由于运算的数量与关键路径长 度是基于以C/C+程
4、式所产生的资料流执行图来计算，可因程式风格与资料结构偏移，此 方法不能呈现演算法本质上最高平行度。另一方面，由演算法的资料流模型所产生的因果行迹图(causation trace graph)可呈现更多演算法本质的相依性与运算平行度。一般而言，因果行迹图相对窄与 线性的部份是由更多的循序运算所构成，而较宽的部份则包括较高的平行度。在论文中 (J.W. Janneck、D. Miller 与 D. B. Parlour，“剖析数据流程式”，IEEE ICME 2008 年期刊，第 1065-1068页，2008年6月)，运算的可平行度可以显现相同时间内的平均完成工作量来量 测。然而，此方法不能确
5、切地量化平行度。发明内容有鉴于此，本发明的一目的为提供一种演算法本质平行度的分析方法。基于本质演算法复杂度萃取与分析同时开发演算法与架构的演算法/架构共同开发(Algorithm/architecture co-exploration, AAC)方法，在新兴的电子系统层级 (electronic system Ievel7ESL)设计的时代已成为一种设计典范。演算法的本质运算平 行度是最重要的复杂度量测机制之一，其可促进新兴平台的开发，包括应用特殊应用导向 积体电路(application specific integrated circuits,ASIC)、可重构电路、大量平行处 理单元(p
6、rocessing element,PE)、以及多核心嵌入CPU等,用于现代与未来的讯号与资讯 处理应用中所采用的越来越复杂的演算法。因此，演算法所内蕴的平行度的利用对于同时 最佳化演算法与架构变成是必要且必须的。本发明的目的是基于线性代数理论提供一种系 统化的方法，以量化内蕴在演算法中的本质平行度上限，以促进讯号与资讯处理系统在新 兴平台上的开发。换言之，被萃取的平行度对于演算法本身是本质性的，不会被硬体或软体 影响，从而能够协助讯号与资讯处理系统的演算法/架构共同开发。为达上述目的，依本发明的演算法的本质平行度的分析方法包含由演算法产生 一资料流图，其由代表计算的节点与表示资料相依性与流动
7、的有向边构成；建立一代表资 料流图的矩阵；以及基于代表资料流图的矩阵的秩与维度量化本质平行度。如上所述，本发明揭露了一种演算法复杂度在本质平行度上的量测方法，其用于 新的演算法/架构共同设计方法，能够同时开发演算法与架构进而最佳化系统。演算复杂 度分析与资料流模型化在同时最佳化演算法与架构中扮演重要的角色。为了前瞻与未来 的讯号与资讯处理，本质平行度无疑地是最重要的复杂度量测机制之一。基于演算法的资 料流模型化与以例如相依性与/或拉普拉斯矩阵映射资料流图到线性方程式，藉由显现线 性方程式系统的自由度，本发明可以有系统地量化演算法内蕴的本质平行度。此外，本发 明中，秩理论被使用以加速量化演算法本
8、质平行度。再者，萃取的本质平行度可有效地促 进新兴平台之上，包括应用特定积体电路(application specific integrated circuits, ASIC)、可重构电路、大量平行处理单元(processing element, PE)、以及多核心嵌入CPU 等，用于更复杂的讯号与资讯处理应用的平台的设计空间的开发。与先前技术相比，本发明的方法具有几个优点。首先，其提供一种理论上可靠的方 法以量化演算法的平行度，而因果行迹(由(J. W. Janneck、D. Miller与D. B. Parlour所说 明)只提供相对的可平行程度比较资讯。此外，受益于资料流模型化，本发明的
9、方法也适用 于以不规则的资料相依度来特征化演算法。另外，相对于藉由高阶程式模型与ILP量化的 分析比较，本发明的平行度机制为本质性的，因此不会受限于特定处理器导向的平台，且可 映射演算法到通用平台，甚至是分散式系统上。以下将参照附图及相关说明使本发明更容易理解，但其仅为说明而非为限制本发 明图1为一流程图，显示依本发明较佳实施例的演算法平行度的分析方法；图2为一示意图，显示演算法平行度的分析方法的一种状况；以及图3为一实施例的资料流图的示意图。具体实施方式本发明经由以下的详细说明并参照附图将更清楚，附图中相同的标号关联到相同的元件。演算法中所蕴含的通用平行度的其中之一可以被显现为彼此独立的独立
10、运算集， 从而可以不同步而平行地被执行。然而，独立运算集系由相依的运算所构成，其必须循序地进行。因此，严格而言，演算法所内蕴的平行度等于全部独立运算集的数量。本发明的方法的主要目标是经由分析基于资料流模型与线性代数所产生的资料流图来萃取本质平行度。 演算法的输入会被分析，且输出包括本质平行度的上限以及相关联的以及不需同步就可以平行地被执行的独立运算集。图1为一流程图，显示依本发明较佳实施例的演算法平行度的分析方法，且图2为一示意图，显示分析演算法平行度的一种状况。如图1和图2所示，步骤SOl系从演算法产生一资料流图，其由代表运算的节点vl到v7,以及表示资料的相依性与流动的有向边el到 e4所
11、构成。图2所示的演算法系作为一简单的例子以便清楚地说明，其目的并非作为限制。 在实施例中，资料流图是由一表示演算法的资料流模型所产生。资料流模型不只能描述演算法的行为或功能，也显现其架构上的特性。节点vl到v7代表运算,且有向边el到e4表示资料的相依性与流动。例如,节点 vl表示变数Al和BI的计算,且从vl到v4的边el代表节点vl与v4的资料的相依性与流动，其余的可以依此类推。步骤S02建立一代表资料流图的矩阵例子。矩阵可为，例如，拉普拉斯矩阵或相依性矩阵。拉普拉斯矩阵的形式如下权利要求1.一种演算法的本质平行度的分析方法，包含 由该演算法产生一资料流图，其由代表计算的节节点与表示资料相
12、依性程度与流动的有向边构成； 建立一代表该资料流图的矩阵；以及 基于代表该资料流图的该矩阵的秩与维度量化该本质平行度。2.如权利要求1所述的演算法的本质平行度的分析方法，其中该资料流图是由代表该演算法的-资料流模型产生。3.如权利要求1所述的演算法的本质平行度的分析方法，其中该矩阵是从多个该资料流图映射于其上的线性方程式所建立。4.如权利要求1所述的演算法的本质平行度的分析方法，其中该矩阵为一相依性矩阵，其具有以下的形式5.如权利要求1所述的演算法的本质平行度的分析方法，其中该矩阵为一拉普拉斯矩阵，其具有以下的形式；6.如权利要求1所述的演算法的本质平行度的分析方法，其中该本质平行度等于该节点的数量减去该矩阵的秩。7.如权利要求1所述的演算法的本质平行度的分析方法，更包含 基于演算法所产生的该资料流图的该矩阵之基底来扩充零空间，进而指出各独立运算集。8.如权利要求1所述的演算法的本质平行度的分析方法，其中若该节点的数量未小于该边的数量，该矩阵为一相依性矩阵，否则该矩阵为一拉普拉斯矩阵。全文摘要一种演算法的本质平行度的分析方法，包括由演算法产生一资料流图，其由代表计算的节点与表示资料相依性与流动的有向边构成；建立一代表资料流图的矩阵；以及基于代表资料流图的矩阵的秩与维度量化本质平行度。
