异构计算

概念：

　　在异构计算系统上进行的并行计算通常称为异构计算。人们已从不同角度对异构计算进行定义，综合起来我们给出如下定义：异构计算是一种特殊形式的并行和分布式计算，它或是用能同时支持simd方式和mimd方式的单个独立计算机，或是用由高速网络互连的一组独立计算机来完成计算任务。它能协调地使用性能、结构各异地机器以满足不同的计算需求，并使代码（或代码段）能以获取最大总体性能方式来执行。

　　概括来说，理想的异构计算具有如下的一些要素：

　　（1）它所使用的计算资源具有多种类型的计算能力，如simd、mimd、向量、标量、专用等；（2）它需要识别计算任务中各子任务的并行性需求类型；（3）它需要使具有不同计算类型的计算资源能相互协调运行；（4）它既要开发应用问题中的并行性，更要开发应用问题中的异构性，即追求计算资源所具有的计算类型与它所执行的任务（或子任务）类型之间的匹配性；（5）它追求的最终目标是使计算任务的执行具有最短时间。

　　可见，异构计算技术是一种使计算任务的并行性类型（代码类型）与机器能有效支持的计算类型（即机器能力）最相匹配、最能充分利用各种计算资源的并行和分布计算技术。

原理：

　　1、异构计算系统。

　　它主要由以下三部分组成：（1）一组异构机器。（2）将各异构机器连接起来的高速网络。它可以是商品化网络，也可以是用户专门设计的。（3）相应的异构计算支撑软件。

　　2、异构计算的基本工作原理。

　　异构计算需求在析取计算任务并行性类型基础上，将具有相同类型的代码段划分到同一子任务中，然后根据不同并行性类型将各子任务分配到最适合执行它的计算资源上加以执行，达到使计算任务总的执行时间为最小。下面通过一个简单例子来说明异构计算的基本工作原理。

　　假设在某一基准串行计算机上执行某一给定计算任务的时间为ts，其中向量、mimd、simd以及sisd各类子任务所占执行时间的百分比分别为30%、36%、24%和10%。假设某向量机执行上述各类子任务相对于基准串行机的加速比分别为30、2、8和1.25，则在该向量机上执行此任务所需的总时间为

　　tv=30%ts/30+36%ts/2+24%ts/8+10%ts/1.25=0.30ts，

　　故相应的加速比为sv=ts/tv=ts/0.3ts=3.33

　　若上述向量机与其他的mimd机、simd机以及一台高性能工作站（sisd型）构成一个异构计算系统，并假设mimd机、simd机以及工作站执行相匹配子任务的加速比分别为36、24和10，则在该异构计算系统上执行同样任务所需时间就变为

　　thet=30%ts/30+36%ts/36+24%ts/24+10%ts/10+tc

　　其中tc为机器间交互开销时间，假设需2%ts时间，则thet=0.06ts，从而相应的加速比为shet=ts/0.06ts=16.67。

　　由上例可见，异构计算系统可比同构计算系统获取高得多的加速比。这主要是因为同构计算系统中的加速比只是靠并行性开发获取的，而异构计算系统中的加速比除了并行性之外，更主要的是靠开发异构性获得的（即不同类型子任务与相应类型的计算资源相匹配），尽管此时会有相应的交互开销。交互开销越小，异构计算的优越性就越加明显。

分类：

　　异构计算按以何种形式来提供计算类型多样性，可分为系统异构计算（shc-system heterogeneous computing）和网络异构计算（nhc-network heterogeneous computing）两大类。shc以单机多处理器形式提供多种计算类型，而nhc则以网络连接的多计算机形式提供多种计算类型。

　　根据异构性实现方式不同，即是空间异构性还是时间异构性，shc和nhc各自又可进一步分为两类。shc分为单机多计算方式和单机混合计算方式两大类，前者在同一时刻允许以多种计算方式执行任务，后者在同一时刻只允许以一种计算方式执行任务，但在不同时刻计算可从一种方式自动切换到另一种方式，如simd和mimd方式间的切换。前者的实例有美国hughes研究实验室和mit共同研制的图像理解系统结构（iua），它是多层异构系统结构，按图像理解层次要求设计每一层，低层是simd位串网络（4096），用来处理像素级操作（如图像增强），中层是由64个数字信号处理（dsp）芯片构成的，以spmd或mimd（中粒度）方式执行模式分类等操作，顶层是一个通用mimd（粗粒度）机器，完成场景和动作分析等知识处理操作。后者的实例为美国普渡大学研制的pasm系统原型，由16个pe（处理单元）组成的系统，它们可动态地加以划分以形成各种大小的独立的混合方式子机器，执行方式可按需要在simd和mimd之间自动切换。

　　nhc可进一步分为同类异型多机方式和异类混合多机方式两类。同类异型多机方式中所使用的多机，它们的结构属同一类，即支持同一种并行性类型（如simd、mimd、向量等类型之一），但型号可能不同，因此性能可以各有差异。通常的now或cow为同类同型多机方式，因此可看成是同类异型多机方式中的特例。异类混合多机方式中所使用的多机，它们的结构则属不同类型。

层次结构：

　　网络异构计算系统主要由一组异构计算机、一个连接所有机器的高速网络和一个并行编程环境所组成。逻辑上这种系统可分为三个层次：网络层、通信层和处理层。如图1所示。

　　网络层主要用来连接在不同地点的计算机，如图1中的计算站a和计算站b，并考虑其中消息传递的路由选择、网络流优化和网络排队理论等问题，这与传统的计算机网络设计类似。

　　通信层工作于网络层之上，主要为系统中各种不同的计算机提供能够相互通信的机制。通信工具软件应提供使众多异构计算机集合可视为是一个单一的系统映像、单个虚拟异构并行机的机制。这将方便用户编程。这种通信工具通常提供一组原语来提供各种通信。典型流行的通信工具是pvm（并行虚拟机）和mpi（消息传递标准接口）。

　　处理层主要用来管理异构机器组并保证任务的高效执行。它所提供的主要服务包括编程环境和语言支持、应用任务的类型分析和任务划分、任务的映射与调度以及负载平衡等。

主要问题：

　　异构计算处理过程本质上可分为三个阶段：并行性检测阶段、并行性特征（类型）析取阶段以及任务的映射和调度阶段。并行性检测不是异构计算特有的，同构计算也需要经历这一阶段。可用并行和分布计算中的常规方法加以处理。并行性特征析取阶段是异构计算特有的，这一阶段的主要工作是估计应用中每个任务的计算类型参数，包括映射及对任务间通信代价的考虑。任务映射和调度阶段（也称为资源分配阶段）主要确定每个任务（或子任务）应映射哪台机器上执行以及何时开始执行。

　　从用户来看，上述的异步计算处理过程可用两种方法来实现。第一种是用户指导法，即由用户用显式的编译器命令指导编译器完成对应用代码类型分析及有关任务的分解等工作，这是一种显式开发异构性和并行性方法，较易于实现，但对用户有一定要求，需将异构计算思想融入用户程序中。另一种是编译器指导法，需将异构思想融入编译器中，然后由具有“异构智力”的编译器自动完成应用代码类型分析、任务分解、任务映射及调度等工作，即实现自动异构计算。这是一种隐式开发异构性和并行性方法，是异构计算追求的终极目标，但难度很大，对编译器要求很高。

　　自动异构计算的概念性模型如图2所示。首先对两个对象进行分析，一是异构计算系统中的机器集，二是求解的应用程序。为了获取最好的执行效果，对它们不但进行定性分析，还需进行相应的定量分析。

　　整个异构计算处理过程可分为以下四个阶段：第一阶段主要是对各台机器进行计算特征的分类，得出异构计算系统所能完成的计算类型；按代码块统计应用对计算特征的需求并加以分类；用基准程序测试各机器的性能参数，包括速度参数及机器间通信性能参数，生成对应的两个机器速度性能矩阵和通信带宽矩阵。将程序按计算类型分类划分；估算各子任务的计算量和子任务间通信量，生成相应的任务dag图。dag图中结点上的数值表示子任务计算量，弧上的数值表示两结点间通信量。

　　第二阶段主要是根据dag和速度性能矩阵计算出每个子任务在各台机器上的执行时间，生成时间性能矩阵；根据通信性能矩阵和子任务的通信量计算各子任务间的通信时间，生成通信时间矩阵。

　　第三阶段根据前两个阶段结果，给出各子任务到各机器的映射和符合任务dag图偏序关系的调度。映射和调度可以是静态或动态的，动态调度需根据机器负载和网络状态信息进行。

　　第四阶段为执行。

应用与研究：

　　异构计算的应用范围很广，几乎所有涉及巨大挑战性问题的求解都可用异构计算进行经济有效的求解。典型的应用包括图像理解、质点示踪、声束形成、气候建模、湍流对流混合模拟以及多媒体查询等。这些应用中通常都含有多种不同的计算类型的需求，因此很适合于用异构计算来进行求解。

　　1、未来应重点开展异构混合多机方式的网络异构计算的研究，它代表着发展趋向，且较经济有效；2、自动异构计算是长期追求目标，在现阶段宜采用用户指导方法来进行研究和开发；3、应尽量利用现有成熟工具如pvm和mpi来开展异构计算的研究和开发；4、应注意开展异构计算的理论分析和建模、性能估计模型、有关软件工具以及异构计算中任务映射和调度算法等方面的研究；5、应研究如何使异构计算系统具有良好的单一系统映像。