我们使用480个AMD RX 480 GPU的计算集群解决数学问题的经验。 作为一个问题，我们从A. Chudnov教授的一篇文章中得到了定理的证明。 “
分离有向图和具有保证收益的游戏的循环类的集合的循环分解 。” 任务是在Nim型联盟游戏中找到一个联盟的最少参与者人数，以确保其中一方获胜。
CPU开发
第一个真正实现大规模销售的处理器是1978年开发的Intel 8086。 8086的时钟速度仅为8 MHz。 几年后，出现了第一个处理器，其中有2、4甚至8个内核。 每个内核都允许其代码独立于其他内核执行。 为了进行比较，现代的Intel Core i9-7980XE处理器以2.6 GHz的频率运行，并包含18个内核。 如您所见，进步不会停滞不前！
GPU开发
在开发中央处理器的同时，还开发了视频卡。 基本上，它们的特征对于计算机游戏非常重要，在计算机游戏中，新技术尤其丰富多彩，而3D图像的渲染正逐渐接近摄影质量。 在计算机游戏开发的开始阶段，图像的计算是在CPU上进行的，但是很快就达到了3D图形开发人员的创造性，他们甚至设法优化了明显的东西（
InvSqrt（）是一个很好的例子）。 因此，带有用于执行3D计算的特殊指令集的协处理器开始出现在视频卡中。 随着时间的流逝，此类团队的数量不断增加，这一方面使图像处理更加灵活有效，另一方面使开发过程复杂化。
自1996年以来，开始生产图形加速器S3 ViRGE，3dfx Voodoo，Diamond Monster等。 1999年，nVidia发布了GeForce 256处理器，引入了术语GPU-图形处理器。 它已经是通用的，它可以处理几何计算，坐标转换，照明点的放置以及使用多边形。 GPU与其他图形芯片之间的区别在于，除了专用命令外，内部还有一组标准命令，您可以使用这些命令来实现自己的渲染算法。 这带来了显着的优势，因为它可以添加任何特殊效果，而不仅是已经编程到视频卡中的效果。 从GeForce 8000/9000开始，流处理器出现在GPU中-已经是成熟的计算机。 根据型号的不同，它们的数量从16到128不等，在现代术语中，它们称为统一着色器单元，或简称为着色器单元。 今天生产的AMD Vega 64 GPU包含4096个着色器单元，时钟频率可以达到1536 MHz！
GPU包含什么？
GPU体系结构与CPU的不同之处在于，它们具有大量的内核和一组主要针对矢量计算的简约指令。 在体系结构级别，已经解决了多个内核并行运行以及同时访问内存的问题。 现代GPU包含2到4000个着色器单元，这些着色器单元组合成计算单元（计算单元）。 在并行计算中，同时访问内存的问题尤其严重。 如果每个流处理器都试图写入存储单元，那么这些命令将最终在锁中，并且需要排队，这将大大降低性能。 因此，流处理器以小组的形式执行指令：一组执行计算时，另一组加载寄存器，依此类推。 您也可以将内核合并到具有共享内存和内部同步机制的工作组中。
GPU的另一个重要特征是向量寄存器和向量ALU的存在，它们可以同时执行向量的多个组件的操作。 这是3D图形的主要必要条件，但是由于我们的世界是三维的，因此没有什么可以阻止我们将其用于许多物理计算。 在存在自由矢量ALU的情况下，它们也可以用于计算标量。
它们是如此不同，CPU和GPU
对于计算系统的完整运行，两种类型的设备都很重要。 例如，我们正在执行分步程序，某种顺序算法。 无法执行算法的第五步，因此在第四步中将计算其数据。 在这种情况下，使用具有大缓存和高时钟速度的CPU会更有效率。 但是，有一整类任务很适合并行化。 在这种情况下，GPU的有效性显而易见。 最常见的示例是计算渲染图像的像素。 每个像素的过程几乎相同，有关3D对象和纹理的数据位于视频卡的RAM中，并且每个流处理器都可以独立计算自己的图像部分。
这是现代任务的一个示例-训练神经网络。 需要训练大量相同的神经元，即改变每个神经元的权重系数。 进行此类更改后，有必要使测试序列通过神经网络进行训练，并获得误差向量。 这样的计算非常适合GPU。 每个流处理器都可以像神经元一样工作，并且在计算过程中不必按顺序构建解决方案，我们所有的计算将同时进行。 另一个例子是空气动力学流量的计算。 有必要找出设计桥梁在风的作用下的可能行为，以模拟其空气动力学稳定性，找到整流罩的最佳安装位置，以调节气流或计算抗风共振能力。 还记得伏尔加格勒著名的“舞蹈之桥”吗？ 我认为当时没人愿意在桥上...
可以通过相同的数学方程式描述每个点处的气流行为，并在大量铁芯上并行求解这些方程式。
GPU掌握在程序员手中
为了在GPU上执行计算，使用了一种特殊的语言和编译器。 有几种用于执行常规GPU计算的框架：OpenCL，CUDA，C ++ AMP，OpenACC。 前两个被广泛使用，但是CUDA的使用仅受nVidia的GPU限制。
OpenCL由Apple在2009年发布。 后来，英特尔，IBM，AMD，Google和nVidia加入了Khronos集团，并宣布支持该通用标准。 从那时起，该标准的新版本每隔一年半到两年出现一次，每一次带来越来越严重的改进。
迄今为止，OpenCL C ++版本2.2语言符合C ++ 14标准，支持在设备内同时执行多个程序，它们之间通过内部队列和管道进行交互，并允许灵活地管理缓冲区和虚拟内存。
实际任务
我们参与其中的博弈论中一个有趣的问题是A. Chudnov教授的一篇文章的定理证明。 “
分离有向图和具有保证收益的游戏的循环类的集合的循环分解 。” 任务是在Nim型联盟游戏中找到一个联盟的最少参与者人数，以确保其中一方获胜。
从数学的角度来看，这是对支持循环序列的搜索。 如果以零和一的列表的形式表示序列，则可以通过逻辑按位运算来实现对支持的检查。 从编程的角度来看，这样的序列是一个长寄存器，例如256位。 解决此问题的最可靠方法是对所有选项进行排序，但由于显而易见的原因，不可能的选项除外。
解决问题的目标是有效的信号处理（检测，同步，坐标测量，编码等）问题。
解决此问题的复杂性是通过大量选项进行分类。 例如，如果我们正在寻找n = 25的解决方案，那么这是25位，如果n = 100，则已经是100位。 如果我们取所有可能组合的数量，则对于n = 25，它是2 ^ 25 = 33554432，而对于n = 100，它已经是2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 376个组合。 复杂性的增加简直是巨大的！
此任务可以很好地并行化，这意味着它非常适合我们的GPU集群。
程序员与数学
最初，数学家们在Excel的Visual Basic中解决了这个问题，因此他们设法获得了主要的解决方案，但是脚本语言的低性能使我们无法前进。 n = 80的决定花了一个半月的时间。我们在这些耐心的人面前低头。
第一阶段，我们用C语言实现了任务算法，并在CPU上启动了它。 在此过程中，事实证明，使用位序列时可以进行很多优化。
接下来，我们优化了搜索区域并消除了重复。 同样，对由编译器生成的汇编器代码进行分析并针对编译器功能对代码进行优化也可得出良好的结果。 所有这些使得有可能显着提高计算速度。
优化的下一个阶段是分析。 对代码各部分执行时间的测量表明，在算法的某些分支中，内存上的负载显着增加，并且发现了程序的过多分支。 由于此“小”缺陷，几乎没有使用三分之一的CPU能力。
解决此类问题的一个非常重要的方面是编写代码的准确性。 没有人知道这个问题的正确答案，因此，没有测试向量。 数学家发现的解决方案范围只有第一部分。 新解决方案的可靠性只能通过编写代码的准确性来保证。
因此，在GPU上为解决方案准备程序的阶段已经到来，并且代码已修改为可以在多个线程中工作。 现在，控制程序正在执行线程之间的调度任务。 在多线程环境中，计算速度提高了5倍！ 这是由于4个线程的同时操作和功能组合而实现的。
在此阶段，该决策在10分钟内进行了高达n = 80的正确计算，而在Excel中，这些计算花了一个半月！ 小胜利！
GPU和OpenCL
决定使用OpenCL 1.2版，以确保不同平台之间的最大兼容性。 最初的调试是在Intel的CPU上进行的，然后在Intel的GPU上进行的。 然后他们从AMD切换到GPU。
OpenCL 1.2标准支持64位整数变量。 AMD有限地支持128位尺寸，但可以编译为两个64位数字。 出于兼容性原因和优化性能，决定将256位数字显示为一组32位数字，并在内部ALU GPU上尽快对其进行逻辑按位运算。
OpenCL程序包含一个内核-该功能是程序的入口点。 用于处理的数据从CPU下载到视频卡的RAM，并以缓冲区（指向输入和输出数据数组的指针）的形式传输到内核。 为什么要数组？ 我们执行高性能计算，我们需要许多同时执行的任务。 内核在多个实例中在设备上运行。 每个内核都知道其标识符，并从共享缓冲区获取自己的输入。 最简单的解决方案最有效的情况。 OpenCL不仅是一种语言，而且还是一个全面的框架，可以在其中全面考虑科学和游戏计算的所有细节。 这使开发人员的生活更加轻松。 例如，您可以启动许多线程，任务管理器会将它们放置在设备本身上。 那些没有立即开始执行的任务将在计算单元空闲时排队等待并启动。 每个内核实例在输出缓冲区中都有自己的空间，在工作完成时将响应放置在其中。
OpenCL管理器的主要任务是确保多个内核实例的并行执行。 数十年来积累的科学和实践经验在这里得到了应用。 当某些内核将数据加载到寄存器中时，这时的另一部分将与内存一起工作或执行计算-结果，GPU内核始终处于完全加载状态。
OpenCL编译器在优化方面做得很好，但是对开发人员来说，影响性能更容易。 GPU优化有两个方向-加快代码执行速度和并行化的可能性。 编译器对代码的并行化程度取决于几件事：暂存寄存器的数量（位于最慢的GPU内存中-全局），已编译代码的大小（必须适合32 kb的缓存），使用的向量寄存器和标量寄存器的数量。
ComBox A-480 GPU或一百万个内核
当我们从Excel切换到由480个AMD RX 480显卡组成的计算集群时，这是项目中最有趣的部分，体积大，速度快，效率高。 完全准备完成任务并获得世界从未见过的结果。
我想指出，在改进和优化代码的所有阶段，我们从一开始就开始寻找解决方案，并将新版本的答案与以前的答案进行了比较。 这使我们可以确保代码优化和改进不会在解决方案中引入错误。 在这里，您需要了解，教科书结尾处没有正确的答案，世界上没有人知道。
集群上的发射证实了我们对解题速度的假设：对n> 100的序列进行搜索大约需要一个小时。 几分钟之内就能看到ComBox A-480集群上的新解决方案是多么令人惊奇，而在CPU上却花了很多小时。
在短短两个小时的计算集群中，我们得到了所有的解决方案，总计n = 127。 对解决方案的检查表明，所获得的答案是可靠的，并且与文章中所述的A. Chudnov教授的定理相对应。
速度进化
如果您在解决问题的过程中看到性能提高，则结果大致如下：
- 在Excel中，一个半月到n = 80；
- 在Core i5上使用优化的C ++程序，一个小时达到n = 80；
- 使用多线程在Core i5上10分钟达到n = 80；
- 在一个AMD RX 480 GPU上10分钟到n = 100;
- 在ComBox A-480上120分钟到n = 127。
前景与未来
为了使我们的生活更美好，科学与实践相交的许多任务正在等待中。 计算能力租赁市场刚刚兴起，并且对并行计算的需求持续增长。
并行计算的可能应用：
- 车辆和无人机的自动控制任务；
- 空气动力学和流体动力学特性的计算；
- 语音识别和视觉图像；
- 神经网络训练；
- 天文学和航天学的任务；
- 数据的统计和相关分析；
- 折叠蛋白质-蛋白质化合物；
- 使用AI早期诊断疾病。
一个单独的方向是在GPU上进行云计算。 例如，亚马逊，IBM和Google等巨头将其计算能力出租给了GPU。 今天，我们可以充满信心地说，高性能并行计算的未来将属于GPU集群。