一种基于推迟提交的GPU虚拟化优化方法

摘要

本发明公开了一种基于推迟提交的GPU虚拟化优化方法。本方法为：1）客户机上的GPU虚拟化框架前端读入一待执行CUDA应用程序的二进制文件，查找并标记可推迟提交的循环；2）前端执行到可推迟提交的循环部分时，直到该循环结束之前，缓存所有的CUDA函数调用信息及其依赖关系，跳过该函数调用的执行，然后在该循环结束之后将该缓存信息一次发送到宿主机上的GPU虚拟化框架后端；3）后端根据该缓存信息重新构建函数调用并执行，然后将所有任务执行结果打包一次发送回前端；可推迟提交的循环指不去执行循环中的CUDA函数调用，循环依然可以正确执行。本发明减少了前后端通信的次数，从而对GPU虚拟化的性能进行优化。

说明书

技术领域

本发明属于虚拟化技术，涉及一种GPU虚拟化优化方法，尤其涉及一种基于推迟提交 的GPU虚拟化优化方法。

背景技术

GPU具有处理能力强、高存储器带宽、低成本等特点，不仅能很好地进行图形处理，在 高性能计算方面也具有很强优势。GPU因为其强大的并行计算能力，近年来被广泛应用到科 学计算、生物信息、气候预报、工程模拟等领域，发挥了巨大的作用。

虚拟化技术具有资源共享、在线迁移、进程隔离等优点，在集群、云计算方面起到了很 大作用。它不仅节约了计算资源，也提高了系统的稳定性和可靠性。由于虚拟化技术具有很 多优势，近年来被广泛应用到各个领域，如资源整合、改善软件生命周期、数据中心、云计 算等。

由于虚拟化技术和GPU各自的优势，越来越多的研究者在虚拟化环境中利用GPU来进 行高性能计算。虚拟化技术使得程序和软件运行在一个虚拟出来的计算环境中，而非真实的 计算环境。在这种环境中GPU不便被虚拟机直接访问。再加上GPU厂商对于GPU硬件规范 保密，因此虚拟化环境中GPU的使用和管理面临很大挑战。

目前有研究者通过远程API的方法开发出一些GPU虚拟化框架（如图1），使得在虚拟 机中可以访问GPU，这里选择CUDA应用程序作为应用的例子。远程API方法的GPU虚拟 化框架分为前端和后端两个部分。前端以动态库的形式被客户机中的CUDA程序加载，这样 在前端可以截获客户机中的所有对于CUDA API的调用。后端则是运行在宿主机中的一个桩 模块，负责接收前端截获的调用信息。在这种机制下，首先由前端将虚拟机中的CUDA函数 重写，将调用时的函数名称和相应参数传递给后端。后端为前端每个CUDA应用程序创建一 个进程，在该进程中转换来自前端重写后的CUDA函数，获得函数的名称和参数。最后通过 设备驱动，使用宿主机上真实的GPU硬件设备执行相应的函数调用。最后将函数的执行结果 返回给前端，这样前端的CUDA程序就可以获得正确的执行结果。很明显可以看到，这种方 法需要进行大量虚拟机与宿主机之间的数据传输，所有计算所需要的数据信息都需要传输到 后端才能进行计算，导致GPU虚拟化的性能严重下降。在CUDA程序规模较小时，这些GPU 虚拟化框架的性能下降并不太明显。但在进行实际应用中的高性能计算时性能下降非常明显。 某些CUDA程序在虚拟机中的运行时间几乎是在宿主机中运行时间的17倍左右，无法达到 实际应用的性能要求。

发明内容

本发明主要针对基于远程API的GPU虚拟化框架中数据传输量大而且频繁的问题，目的 是要在现有的GPU虚拟化框架环境的基础上，提出一种基于推迟提交策略的优化方法，尽可 能多的减少重复或冗余的数据传输。该方法检测客户机中的CUDA应用程序，从中找到可以 推迟提交的部分，从而使得程序在执行时避免频繁，重复的传输大量数据，以减少数据传输 带来的开销，从而提高GPU虚拟化的性能。此项发明可以保证映射之后程序可以准确无误的 执行，保持和未修改之前一样的行为。同时还能保证效率高于原有框架。

本发明的技术方案为：

一种基于推迟提交的GPU虚拟化优化方法，其步骤为：

1）客户机上的GPU虚拟化框架前端调用二进制分析模块读入一待执行CUDA应用程序 的二进制文件，在该二进制文件中查找并标记可推迟提交的循环；

2）GPU虚拟化框架前端执行该CUDA应用程序，当执行到可推迟提交的循环部分时， 直到该循环结束之前，缓存所有的CUDA函数调用信息及其依赖关系，跳过该函数调 用的执行，然后在该循环结束之后将该缓存信息一次发送到宿主机上的GPU虚拟化 框架后端；

3）宿主机上的GPU虚拟化框架后端根据该缓存信息重新构建函数调用并执行，然后将 所有任务执行结果打包一次发送回客户机上的GPU虚拟化框架前端；

其中，所述可推迟提交的循环是指循环中包含若干CUDA函数调用，但在该循环中不 去执行这些CUDA函数调用，该循环依然可以正确执行的循环。

进一步的，查找所述可推迟提交的循环的方法为：

1）二进制分析模块对该二进制文件进行反汇编，然后为其中的每一用户级函数建立一控 制流图；

2）在每一控制流图中找到所有的循环；

3）在每一自然循环中找到所有的函数调用点，识别出所有包含CUDA函数调用的循环；

4）对每一CUDA函数调用的循环做寄存器级别的变量活性分析和数据相关性分析，根据 每一CUDA函数调用信息及其依赖关系确定出所述可推迟提交的循环。

进一步的，所述可推迟提交的循环包括三类；其中，第一类循环为：CUDA函数调用的 参数不依赖于循环变量，且该参数不依赖循环中的其他变量，调用的结果不影响循环中其他 语句的正常执行；第二类循环为：CUDA函数调用的参数依赖于循环变量，但该参数不依赖 循环中的其他变量，调用的结果不影响循环中其他语句的正常执行；第三类循环为：CUDA 函数调用的参数仅依赖于之前的CUDA函数调用产生的结果。

进一步的，所述二进制分析模块静态或动态的在CUDA程序的二进制文件中插入变量来 标记所述可推迟提交的循环的类别。

进一步的，对于第一类循环，所述缓存的信息包括循环初值，步长和次数，CUDA函数 调用的参数、函数名，参数信息及数据依赖关系；对于第二类循环，所述缓存的信息包括循 环初值，步长和次数，CUDA函数调用的参数、函数名、循环变量以及依赖于循环变量的参 数；对于所述第三类循环，所述缓存的信息包括循环初值，步长和次数，相互依赖的函数、 依赖其他变量或参数的参数之间的依赖关系。

进一步的，对于第一类循环，GPU虚拟化框架后端根据该缓存信息重新构建函数调用的 方法为：首先根据GPU虚拟化框架前端发送来的循环初值，步长和次数，建立一个循环；然 后根据发送过来的函数名在CUDA库中找到对应函数；然后根据发送过来的参数和数据重新 构建函数调用。

进一步的，对于第二类循环，GPU虚拟化框架后端根据该缓存信息重新构建函数调用的 方法为：首先根据GPU虚拟化框架前端发送来的循环初值，步长和次数，建立一个循环；然 后根据发送过来的函数名在CUDA库中找到对应函数，将循环变量替换为GPU虚拟化框架 后端的循环变量；然后根据发送过来的参数和数据重新构建函数调用。

进一步的，对于第三类循环，GPU虚拟化框架后端根据该缓存信息重新构建函数调用的 方法为：首先根据GPU虚拟化框架前端发送来的循环初值，步长和次数，建立一个循环；然 后根据发送过来的函数名在CUDA库中找到对应函数，根据参数的依赖关系重新计算参数的 表达式，还原函数调用；然后根据发送过来的参数和数据重新构建函数调用。

进一步的，利用dyninst工具读取该二进制文件，然后反汇编，最后静态或动态的为每一 个函数建立一控制流图。

进一步的，所述GPU虚拟化框架后端设立一缓冲队列，将每一次发送的缓存信息作为一 组任务缓存到所述缓冲队列。

本发明整体方案分为以下几个部分：

（1）二进制文件分析模块，主要用来分析客户机中的二进制文件，找到可推迟提交的代 码部分，并进行位置信息记录等处理。

（2）修改基于远程API调用的GPU虚拟化框架的前端，利用二进制文件分析的结果， 对数据的传输重新调度，减少重复的数据传输。

（3）修改基于远程API调用的GPU虚拟化框架的后端，通过前端发送来的一组调用信 息进行处理，并将结果返回前端

推迟提交策略原理

该策略主要应用于CUDA应用程序中含有CUDA函数调用的循环部分。在远程API调用 的GPU虚拟化框架下，每次调用CUDA函数前后端都会进行一次通信。该策略通过分析含 有CUDA调用的循环，判断该循环是否满足可以被推迟提交的条件。如果通过分析发现该 循环可以被推迟提交，那么我们就可以在前端将可被推迟提交的CUDA调用的函数名，参数 信息及数据依赖关系等信息缓存起来。在循环结束时，一次性的将这些信息发送到后端，这 样后端就可以根据发送来的信息重构函数调用，从而相当于前后端只进行了一次通信，大大 减少了通信问题所带来的开销（如图2）。

这里所谓的可以被推迟提交的循环，指的是循环中有一部分CUDA函数调用，如果我们 在循环中不去执行这一部分CUDA函数调用，循环依然可以正确的执行。也就是说，我们只 需要在循环的最后，告诉后端我们需要执行多少次调用即可，而不用在循环中每遇到一次调 用就将请求发送到后端。

根据循环中CUDA函数调用所需的参数与循环中其他变量的数据依赖等关系，我们将推 迟提交分为以下三种情况：

第一类推迟提交

特点为：CUDA函数调用的参数与循环变量不相关，也不存在与其他变量的数据依赖关 系。如下面代码就是一个简单的例子。

我们可以看到，该CUDA函数调用的参数不依赖于循环变量y，也并不依赖其他的变量 （循环中只有一个函数调用，无其他变量）。此时在整个虚拟化框架的前端（前端位于客户机 中），我们会将循环中的CUDA调用的函数名，参数以及函数调用所需的数据（指针指向的 地址空间中的数据），循环所需次数，初值和步长缓存起来，缓存在前端处理进程动态开辟出 来的内存空间中（自己定义的信息缓冲池）。

由于第一类推迟提交的特点就是调用的参数不依赖于循环变量，参数不依赖循环中的其 他变量（没有数据相关），调用的结果不影响循环中其他语句的正常执行，因此我们在整个循 环结束时，在原程序中静态或动态的插入处理函数，该处理函数会将之前缓存下来的调用信 息，以及一个标识符（标识这是第一类推迟提交），利用GPU虚拟框架（gvirtus）的通信信 道发送到后端，同时等待后端返回结果。后端常驻进程监听到前端发送来的任务之后，判断 该次推迟提交是第一类推迟提交。然后利用函数调用信息重构函数调用，并且循环执行。循 环次数和步长也已经由前端发送过来。最后如果正确执行，通知前端执行完成。前端接收到 完成的结果后，继续执行剩下的程序。

常见的通信方式有比如基于TCP/IP协议的套接字，或者基于内存共享技术的数据传输方 式，下面不再赘述。

第二类推迟提交

特点为：CUDA函数调用的参数依赖于循环变量，但是参数与其他变量无数据依赖。如 下面代码就是一个例子。

与第一类推迟提交的情况类似，只是除了第一类推迟提交所需要缓存的信息之外，由于 参数中用到了循环变量，因此我们还需要在缓存的信息中特别地指出哪些参数用到了该循环 变量。后端的处理过程也与第一类类似，首先还原函数调用，然后根据循环次数和步长及初 值构造循环，将调用放到该循环去执行。只是特别的，我们要把参数中标记为循环变量相关 的变量换做后端这个循环的循环变量，也就是做一个变量替换。这样每次执行的时候循环变 量的变化就与原循环中的一致了。

第三类推迟提交

第三类推迟提交的情况比较复杂。特点为：循环中的CUDA函数调用参数依赖于之前的 CUDA函数调用产生的结果，但是不依赖于其他的变量或函数。同时其他的变量或函数也不 依赖于这些CUDA调用的结果。也就是说参数只是与其他的CUDA调用存在依赖关系。比 如第二次循环的参数需要第一次循环计算过后产生的结果，并且只依赖于上一次计算的结果， 代码如下。

对于这种情况，我们依然可以推迟提交，因为延后这些函数调用的提交，由于与循环中 其他的变量或函数调用没有数据依赖关系，所以不会对程序的行为造成影响。该类推迟提交 最大的特点就是，函数执行所需的参数，依赖于该循环中其他的CUDA调用或者该函数本身。 比如这里的histo_main_kernel函数，当循环第二次执行到该函数时我们发现，第一个参数就 依赖于上一次循环该函数的计算结果。如果第一次不执行，那么我们无法知道结果，也就无 法知道参数是什么。因此我们需要将这些相互依赖的函数作为一个整体一并处理。也就是说 这里我们会发送一组函数调用，他们必须同时在循环中出现才能正确执行。同时我们还需要 把这些依赖其他变量或参数的参数进行特别标注，记下他们的依赖关系。比如这里我们就要 记录dim3的第一个参数，等于ranges_h数组的第二个值减去第一个值再加上1，就不能简单 的只是把当时的参数值缓存下来。

除此三类之外的情况（比如循环中的CUDA函数产生的结果会对循环中后续程序行为产 生影响），我们都不能推迟CUDA函数调用的提交，否则程序将不能正确执行。

前端二进制分析模块

该模块位于GPU虚拟化框架的前端，主要的功能和工作步骤如下：

1）静态或动态的读入一个CUDA应用程序的二进制文件，在汇编级别上为所有函数建 立控制流图（CFG）。可以利用dyninst工具（一组二进制文件分析工具），读取二进制 文件，然后反汇编，最后静态或动态的为每一个用户级函数（user level函数）建立一 控制流图。

2）在控制流图中找到所有的循环。

3）在自然循环中，找到所有的函数调用点，并判断该函数是否为CUDA函数调用（可 以根据编译时的调试信息等方式获取函数名，并与CUDA库函数中的所有函数名进行 对比。同时判断该函数是否是CUDA库函数。满足以上两点的就是CUDA函数调用）。 从而找到所有包含CUDA调用的循环。

4）在循环中做变量活性分析和数据相关性分析（具体可以参考《编译原理》等书或资料）， 从而找到每一个CUDA函数入口处的参数与其他变量（包括循环变量等）的依赖关系。 根据之前原理部分的分析，找到可以推迟提交的循环部分。

5）将可以推迟提交的部分进行记录。

这样我们就可以完成可推迟提交代码的识别。

前端框架修改

根据二进制分析模块的结果，当CUDA应用程序执行到可推迟提交的循环部分时，直到 循环结束之前，缓存所有的CUDA调用信息及其依赖关系（参数，函数名，计算所需数据， 参数表达式等等），并在循环结束之后将这些信息一次性发送到后端处理，同步等待后端执行 结果。具体缓存哪些信息，已经在前面三类提交的分析中说明了。同时在二进制分析模块中 我们已经找到了所有可以推迟提交的循环部分，并且做了标注（静态或动态的在CUDA程序 的二进制文件中插入变量来标记这是第几类推迟提交），因此在执行时我们就知道该缓存哪些 信息以及如何缓存和发送及处理了。

后端框架修改

后端设立缓冲队列，接收前端发送来的一组任务。根据调用信息和依赖关系重新构建函 数调用，并在真实的硬件设备上（即GPU，位于后端）进行计算。最后一次性将所有任务执 行结果打包发送回前端。

具体的重构过称为：

1）对于第一类推迟提交，首先根据前端发送来的循环初值，步长和次数，建立一个循环。 循环中执行的函数名可以由前端发送来的名字知道。这样就可以在CUDA库中找到该函数。 参数也已经由前端发送而来。由于第一类推迟提交的特点，这里的参数都是一些常量或指针。 常量可以直接使用，如果是指针，需要在后端动态开辟内存空间，同时将前端发送来的数据 放入该内存空间，并将指针替换为新开辟的内存空间的位置。这样程序才能正确的读取数据。

2）对于第二类推迟提交，首先根据前端发送来的循环初值，步长和次数，建立一个循环。 循环中执行的函数名可以由前端发送来的名字知道。这样就可以在CUDA库中找到该函数。 参数也已经由前端发送而来。如果参数是常数或指针，可以与上面第一种情况进行相同的处 理。如果发现某变量是循环变量，需要将这里的变量替换为后端这个循环的循环变量。

3）对于第三类推迟提交，首先根据前端发送来的循环初值，步长和次数，建立一个循环。 循环中执行的函数名可以由前端发送来的名字知道。这样就可以在CUDA库中找到该函数。 如果参数是常数或指针或循环变量，处理情况类似于第二种情况。如果参数依赖于其他的同 组的CUDA调用的参数或调用结果，需要根据参数的依赖关系，重新计算参数的表达式（依 赖关系其实就是根据其他的几个变量，怎样通过运算得到该变量本身），这样就还原了一个函 数调用。依次为该组缓存信息中的其他的CUDA调用进行处理。

与现有技术相比，本发明的积极效果为：

1.在线性。根据实验，由于推迟提交机制的加入，在部分应用场景下性能的提升效果 明显，可以满足程序实时运行。对于函数调用频繁的应用，甚至可以使得其性能接近native 下的效果。

2.通用性。我们提出的基于推迟提交的GPU虚拟化优化方法，与平台无关，不依赖特 定的操作系统，所用的虚拟化框架及优化方法可以应用于各类GPU。

3.透明性。我们的推迟提交优化对于普通用户来说完全是透明的，也就是说普通用户无 需知道任何关于推迟提交机制的细节。客户机启动以后，整个推迟提交策略换会自动的进行， 无需任何用户干预。

4.有效性。通过实验，在部分开源项目和基准程序中，确实能够提高程序的执行效率。

我们使用的测试环境如表1：

表1、测试环境

我们采用Parboil基准程序来进行评测。Parboil基准程序由John A.Stratton等人研发，涵 盖了不同科学和商业领域，包括图像处理、生物分子模拟、流体动力学、天文学等。每个基 准程序包括多种实现方法，有的还对算法进行了优化。Parboil基准程序和CUDA SDK相比， 数据规模更大，运行时间更长，更能代表实际情况中用于高性能计算的CUDA程序。

这里我们主要采用了推迟提交优化策略对基准程序histo（包含于Parboil基准程序）进行 了优化，并在不同的通信方式以及不同的优化环境下进行了实验对比。

纵坐标为归一化之后的运行时间（相对于非虚拟化环境的运行时间），横坐标为不同的优 化方法下该基准程序的执行时间。

从图3我们可以看出，在三种不同的通信方式下，基准程序histo在原始GPU虚拟化框 架下的执行时间是非虚拟化情况下的数倍，虚拟化性能不高。利用地址映射机制优化的运行 环境下执行时间虽然有提高，但虚拟化性能依然不是很高。最后利用推迟提交进行优化之后 的运行时间，几乎与非虚拟化环境下的运行时间相同。由于例子过多这里不再赘述。

附图说明

图1为基于远程API调用的GPU虚拟化框架架构。

图2为推迟提交优化前后对比。

图3为评测实验结果。

图4为优化后的GPU虚拟化框架架构。

具体实施方式

我们基于开源的全虚拟化虚拟机管理器KVM，以及Linux客户操作系统，加上开源GPU 虚拟化框架Gvirtus，实现了一个新的优化过的GPU虚拟化框架（图4）。下面结合本图进行 进一步说明。其中虚线部分为该技术添加或修改过的部分，应用实例以CUDA应用程序和 CUDA函数库为例子（CUDA是显卡厂商Nvidia公司推出的运算平台，这里的CUDA程序 泛指利用该运算平台编程后形成的应用程序）。

Gvirtus开源虚拟化框架分为前端和后端两个部分：前端在客户机中，负责重写CUDA库， 截获客户机中程序对CUDA函数的调用，将调用信息发送到后端进行处理；后端在宿主机中， 负责接收前端截获的函数调用信息，并在在真实的硬件环境上进行计算，最后将结果返回前 端，完成一次调用。

这里给出一个优化过后的框架的执行流程以及实现细节：

·客户机中的CUDA程序在运行时预先调用二进制分析模块，找到程序中可以被推迟提 交的代码部分。二进制分析模块采用Dyninst（一个开源的二进制分析工具）提供的库函数和 接口进行编写，并在此基础上实现循环识别，函数调用，活性分析等功能。

·Gvirtus前端通过二进制分析模块返回的可以推迟提交的代码部分，动态的检测当前截 获的CUDA函数调用是否在可以被推迟提交的部分之内。如果是则将该调用所需的信息缓存 起来，跳过该CUDA函数的执行（相当于该调用直接返回执行成功，实际没有执行）。当循环 结束时（即前端检测到代码离开可推迟提交的代码区间时）一次性将缓存的函数调用信息发 送到后端的调度模块中。

·Gvirtus后端接收前端发送来的一组任务，为每一个任务，根据发送来的信息（如参数， 函数名，计算所需数据，参数依赖关系及表达式等等）重组函数调用，并将调用发送给后端 的桩模块进行执行。

·Gvirtus后端调用CUDA的库函数，在真实的硬件环境下执行该函数调用，并等待执行 结果，最后一次性打包发送给前端。

·Gvirtus前端接收后端发送来的结果，完成函数的调用。至此完成一次推迟提交任务的 执行。

本发明所提出的基于推迟提交的GPU虚拟化优化方法，其主要技术特征是利用二进制代 码分析技术，找到可以推迟提交的代码部分，去除冗余和重复的数据通信，减少前后端通信 的次数，减少了前后端数据传输所带来的开销，从而对GPU虚拟化的性能进行优化。因此凡 是利用推迟提交策略的GPU虚拟化技术都在本专利的保护范围之内。