基于匹配矩阵的异构重构计算的性能分析方法

摘要

本发明涉及一种基于匹配矩阵的异构重构计算的性能分析方法，包括以下步骤：1)建立异构重构计算系统模型HRCS；2)建立异构重构任务图模型HR-DAG；3)生成异构匹配矩阵Ma；4)生成重构耦合矩阵Co；5)通过调度算法来计算应用任务的执行完成时间，从来进行性能分析。与现有技术相比，本发明具有通过增加应用任务异构特征和通信重构特征的描述，更加丰富和准确地表达了应用任务对计算和通信的需求等优点。

说明书

技术领域

本发明涉及一种异构重构计算的性能分析方法，尤其是涉及一种基于匹配矩 阵的异构重构计算的性能分析方法。

背景技术

传统的以同构计算(Homogeneous Computing)为主要计算模式的高性能计算已 经开始向异构计算(Heterogeneous Computing，HC)的方向转变，例如“Roadrunner” 和我国国防科技大学研制的“天河一号”。另一方面，可重构计算(Reconfigurable  Computing，RC)也已经被引入到高性能计算中。可重构部件以其可配置特性提高 了计算的灵活性和处理部件的利用率，以其空间并行执行的特点增强了计算的高效 性，同时又降低了功耗。由此可见，包含有各种异构加速部件和可重构部件的异构 重构计算(Heterogeneous & Reconfigurable Computing，HRC)是高性能计算发展的 新趋势。HRC具有HC和RC的所有优点如：高效性、灵活性、高性价比、低功耗、 稳定性、高容错性和短开发周期等。但是HRC系统是否真的能够实现应用的高效 执行则需要进行性能评价。

传统上，高性能计算的性能分析方法有：理论分析，模拟仿真，测试测量等[6-8]。 理论分析方法是指对并行系统进行形式化建模，这些方法可以分为两类，确定性和 概率性形式。在确定性模型中，所有的量都是固定的。在概率性模型中，存在着不 确定性和随机变量。模拟是性能分析领域的一个被广泛使用的技术。它提供了一个 有效的方法来预测还没有被生产出来的计算机系统的性能。也可以被用来验证理论 分析方法的正确性。模拟技术包括：仿真技术，Monte Carlo模拟，追踪驱动模拟， 执行驱动模拟和离散时间模拟。性能测量技术包含两种技术：第一个技术是 profiling，在程序运行时跟踪基本的性能信息。程序的性能信息通常是在程序执行 结束后就立即展示给用户，可以显示程序的执行时间在不同程序代码之间的分布。 第二个技术是跟踪(tracing)。跟踪技术维护了一个记录程序所有活动细节的日志文 件。跟踪通常会产生大量的跟踪数据，特别是运行时间较长的程序。但是，跟踪技 术可以用来重建应用程序在运行时的行为。也可被用来评价由Profiling技术提供 的性能信息。因此，跟踪被认为是一个更通用的性能测量技术。这些现有的并行计 算性能分析方法不再适用于HRC，主要存在以下问题：

当给定一个应用时，选择怎样体系结构的并行计算机？应用在某种体系结构下 运行的性能如何？什么样的性能指标来衡量性能？怎样得到性能数据？这些问题 都是性能分析的目标和研究内容。

对于具有计算形式灵活、应用与资源的高效匹配、可编程性、可移植性、稳定 性、可扩展性和低功耗等多重分析标准的高效能计算，性能分析所涉及的内容也得 到了扩展，同时也产生一系列问题。

对HRC计算系统性能分析存在的问题：

(1)由于目前异构重构计算刚刚起步，还没有一个现成的异构重构计算系统 及其计算模型。

(2)没有现成的性能分析技术可以对异构重构计算系统的性能进行分析和预 测。现有的分析工具还不足以对异构重构计算系统进行分析。

(3)选择怎么样的性能指标来说明分析系统的性能。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种基于匹配矩 阵的异构重构计算的性能分析方法。

本发明的目的可以通过以下技术方案来实现：

一种基于匹配矩阵的异构重构计算的性能分析方法，其特征在于，包括以下步 骤：

1)建立异构重构计算系统模型HRCS；

2)建立异构重构任务图模型HR-DAG；

3)生成异构匹配矩阵M_a；

4)生成重构耦合矩阵C_o；

5)通过调度算法来计算应用任务的执行完成时间，从来进行性能分析。

所述的异构重构计算系统模型HRCS为：

HRCS＝(V_P，E_P)；其中，点集V_P＝{p₁，p₂，…，p_M}表示系统中处理部件的集合； 边集E_P＝{e₁，e₂，…，e_L}表示处理部件间链路的集合。

所述的异构重构任务图模型HR-DAG为：

HR-DAG＝(V_T，E_T，w，D，H，R)；其中，点集V_T＝{t₁，t₂，…，t_N}表示子任 务的集合；边集E_T＝{e₁，e₂，…，e_K}是子任务间的偏序关系集合；W表示子任务的计 算量集合；D表示子任务间的通信量集合；H表示子任务执行的异构特征集合；R 表示子任务间通信的重构特征集合。

所述的异构匹配矩阵M_a＝(v_ij)_N×M，其中v_ij代表应用任务t_i在处理部件p_j上的 执行速度，1≤i≤N，1≤j≤M。

所述的重构耦合矩阵C_o＝(c_ij)_K×L，其中c_ij表示任务间重构特征r_i与拓扑结构t_j之间的耦合度，且0≤c_ij≤1，1≤i≤K，1≤j≤L，K为异构重构任务图中边的个数，L 为拓扑结构类型的个数。

所述的通过调度算法来计算应用任务的执行完成时间具体为：

利用异构匹配矩阵M_a将应用任务优化映射匹配到处理部件上，根据公式1： T_comp(t_i)＝w_i/v_ij求出应用任务的执行时间，其中w_i为任务t_i的计算量；利用重构耦合 矩阵C_o来指导系统拓扑结构的动态重构，并根据公式2：T_comm(t_a，t_b)＝d_ab/(B*c_ij)求 出任务间的通信时间，其中d_ab为任务t_a和t_b之间的通信量，B为系统的通信带宽； 循环直至所有的任务执行完毕，最后可计算出整个应用任务的完成时间。

与现有技术相比，本发明具有以下优点：

(1)给出了异构计算，重构计算、异构重构计算的定义，以及异构、重构、高 性能计算三者之间的相互关系；

(2)建立了异构重构计算体系结构模型和异构重构应用任务HR-DAG图模型， 后者是对传统DAG的扩展，通过增加应用任务异构特征和通信重构特征的描述， 更加丰富和准确地表达了应用任务对计算和通信的需求；

(4)定义了异构匹配矩阵M_a，描述不同类型应用任务在各种处理部件上执行效 果的匹配程度；

(5)定义了重构耦合矩阵C_o，刻画了处理部件间的通信链路满足子任务对通信 模式或拓扑结构需求的程度。

附图说明

图1为本发明的流程图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。

实施例

异构重构计算系统HRCS是可能包含通用处理器CPU、专用加速部件(如GPU) 和可重构部件(如FPGA)的新型高性能计算机系统，系统中的所有处理部件通过一 个可编程的互连网络进行连接，使得互连网络的拓扑结构能够适合应用任务的通信 需求。为了开展对HRCS的性能分析，需要建立HRCS的系统模型，基于该模型 可以进行任务执行时间、加速比、可扩展性、性能价格比等其它性能指标的分析。

具体实施方案如下：

(1)把应用程序生成异构重构任务图，并根据经验数据得到任务图中每个子任 务的计算量和子任务之间的通信量，计算每个计算任务适合的计算部件和每条通信 任务适合的互连网络类型。任务图中的节点表示为三元组(t_i/w_i/h_i)，其中t_i表示第i 个任务，w_i表示任务t_i的计算量，h_i表示任务t_i的异构特征；边同样表示为三元组 (e_j/d_j/r_j)，其中e_j表示第j条通信边，d_j表示通信边e_j上的通信量，r_j表示通信边e_j连接的两个任务之间的通信特征。

(2)根据异构匹配矩阵生成任务图中每个计算任务在不同处理部件上的计算时 间，为每个计算任务选择适合的处理部件。

(3)根据重构耦合矩阵生成任务图中的每个通信任务在不同互连网络上的通信 时间，为每个通信任务选择适合的互联网络类型。

(4)根据提出的基于度量矩阵的任务执行时间分析算法把任务图中的计算任务 和通信任务进行调度，安排每个任务所适合的处理部件，并根据通信任务的时机对 可重构的互连网络进行重构，以适合通信任务的通信，最后可得出整个异构重构任 务图的执行时间。