文摘
硬格问题被认为是最有前途的一个问题生成密码机制,在量子计算是安全的。最短向量问题(高级)是最著名的点阵的问题之一。在本文中,我们提出三种改进了基于gpu的并行算法求解高级使用经典的枚举和修剪枚举。有两种改进预处理:我们使用高斯随机化和启发式期待一个更好的基础,导致迅速最短向量,我们预计的水平优化CPU和GPU之间交换数据。第三改善,我们改进了基于GPU实现通过生成一些点在GPU而不是CPU。我们使用NVIDIA GeForce gpu GTX 1060 6 g型。我们取得了显著改善何曼思的改进。改进加快修剪枚举近2.5倍使用单一GPU。此外,我们提供了一个实现multi-GPUs通过使用两个gpu。枚举的结果表明我们的算法是可伸缩的自加速实现使用两个gpu几乎比何曼思几乎5倍的改善。 The improvements also provided a high speedup for the classical enumeration. The speedup achieved using our improvements and two GPUs on a challenge of dimension 60 is almost faster by factor 2 than Correia’s parallel implementation using a dual-socket machine with 16 physical cores and simultaneous multithreading technology.
1。介绍
一个格子所有整数的集合的组合吗线性无关的向量 在 。这些向量被称为晶格的基础。最著名的计算问题涉及晶格的最短向量问题(高级副总裁)和壁橱向量问题(CVP)。具体地说,高级副总裁,给定一个基础 ,一个是要求输出最短的非零矢量在晶格,在CVP,给定一个基础 和目标 ,一个是要求输出一个晶格向量最接近 。高级副总裁和CVP np难问题在最坏的情况下1,2]。
由于高级的硬度和CVP,被广泛应用于密码学和其他数学应用程序。更确切地说,它们是用于创建公钥密码体制,被称为lattice-based密码。Lattice-based密码有优势在密码系统的速度和硬度,早些时候在Lattice-based密码可以实现更多的速度比RSA和ECC密码体制在同等安全级别(3,4]。此外,点阵问题是已知postquantum问题[5]。最知道lattice-based密码是热交换器(6],NTRU [7),最近LWE-based密码(8,9]。此外,晶格理论有更多的调查等密码学之外创建新密码的打破等公钥密码体制RSA和ECC。
目前已知的高级算法和CVP可以分为两类:(1)近似算法返回一个近似解决方案高级或本量利:第一个多项式时间近似算法高级庆祝Lenstra, Lenstra, Lovasz (iii)的基础上减少算法(10),达到一个近似的因素指数的维度 。然后,减少块出现的想法和几块晶格减少算法(11- - - - - -14提出了先后。目前,最常用的近似算法对高级块Korkine-Zolotarev (BKZ)由斯诺和Euchner [14]。微光和BKZ主要是用来减少基础以提高质量的基础。在近似算法,它们通常使用以及修剪枚举(15]。修剪枚举是基于删除子树,不太可能导致一个解决方案。(2)精确算法返回一个确切的解决方案高级或本量利:他们是基于穷举搜索。因此,他们是昂贵的运行时间而言,这至少是一个指数维度的晶格。精确算法包括古典枚举(16),也称为枚举;也泰森多边形法细胞(17)高级副总裁和CVP和筛分18)高级副总裁。没有筛选算法解决CVP实例。
两个类别实际上结合很重要。首先,减少晶格近似算法不能输出最短向量在高维晶格。他们是用来发现向量足够短,以确保一个枚举过程有效地工作。第二,枚举算法的运行时间取决于输入的质量基础。所以,预处理输入栅格基础使用减少晶格近似算法是一个重要的组成部分,枚举算法。
在本文中,我们集中我们的工作并行晶格枚举算法求解图形处理单元(GPU)的高级副总裁。经典的算法[Kannan晶格枚举被首次提出16]和芬克以及Pohst [19]。因此,枚举有时被称为KFP算法。这些算法的特点是,他们需要一个polynomial-space复杂性。此外,他们有良好的渐近运行时,最好的理论算法(由于Kannan [16]),并进一步分析了(20.),实现最坏时间复杂度,格的维数。提出的基于枚举算法[Kannan16]和芬克以及Pohst [19],斯诺和Euchner [14)提出另一种流行的polynomial-space枚举算法搜索最短向量的晶格,在指数运行时间,不超过成本在晶格尺寸 。尽管Schnorr-Euchner枚举的复杂性似乎高于Kannan的;它实际上是一个广泛使用的实用方法。例如,它是一个基本的工具在大众数学库NTL [21]和fpLLL [22]。
枚举算法求解高级可以被视为一种深度优先搜索树结构,将所有向量指定搜索区域的确定性。通常,减少基础如BKZ执行首先改善基础可能产生短向量通过枚举。枚举树(由古典枚举算法)为解决高级的增长很大程度上是由于大量的子树,这使得研究人员寻找另一种方法来加快枚举。斯诺和Euchner14称为]提出了一种新的策略修剪枚举。修剪的枚举的主要思想是修剪搜索树的子树中找到一个精确解的概率太小了(23]。通过使用修剪枚举,穷举搜索被限制为只有一个子集的所有可能的解决方案。虽然,这可能会导致一些丢失的概率精确解,但它提供了显著改善的执行时间。在[23),伽马等人提出了极端的修剪方法来解决高级副总裁和高级近似和显示,可以加快枚举指数随机化算法。
1.1。以前的作品
处理高级使用并行计算架构并不是一个新趋势。有太多的工作等近似算法的微光和BKZ或枚举等精确算法(16和筛选18]。回来和吉姆24]介绍了第一个微光在多核计算机体系结构的并行实现。他们表现出一种提高约3.2倍,在传统的非平行算法。之后,同样的修改(作者介绍了数字25],在[增加算法的加速241.25)倍。枚举的最短向量被认为是在26),实现其改善利用现场可编程门阵列(fpga)。Dagdelen和施奈德27)实现了一种新的并行算法基于KFP枚举算法的修改版本的斯诺和Euchner发明的新算法14]。Dagdelen使用多核CPU和施奈德的并行算法取得了显著加速达到14个因素相比,目前最好的公共实现顺序(fpLLL实现(22])。何曼思et al。28]介绍了GPU实现使用Nvidia GeForce 280 GTX GPU的枚举。值得注意的是,作者用这种廉价和简单规范的GPU相比,当前可用的GPU可以实现一个实现五倍的速度,在一个核心的英特尔酷睿2极端QX9650 3 GHz。枚举算法,嵌入的极端修剪的方法是利用云计算服务提供商(29日]。云计算服务提供商允许作者测试高维度的最短向量,例如,114年和120年的维度,为他们提供许多高性能的NVIDIA gpu。随后,专题等。30.)表明,基于枚举的搜索树CVP包含许多对称分支。他们提出了避免冗余计算的探索只有一个对称分支,这减少了计算数量的分支。此外,他们提出了另一种策略,在多核线程之间的工作负载平衡。这些策略实现多核改善的实现(27)由35%到60%的一个因素。
1.2。我们的贡献
在本文中,我们提出一种改进的并行版本的修剪的枚举算法(近似算法)14)发现一个最短,晶格非零向量。此外,我们表明,该改进是有效的古典枚举(具体算法)。我们使用NVIDIA的CUDA框架实现算法在GPU上。结果表明,我们的策略提高何曼思的实现(28)基于修剪枚举几乎5倍使用两个gpu。对于古典枚举,我们比较我们的实现专题的实现(30.]。实验结果通过求解一个挑战维度60表明我们的策略基于两个专题gpu是超过两倍的实现基于16个物理核心和同步多线程技术。
GPU被认为是最有前途的技术之一,在并行计算领域由于其密集的计算能力。它加快了性能等许多问题(31日,32]。一个GPU包含成千上万的核心。此外,GPU开发与速度远远超过了cpu的速度发展。GPU硬件的观点是归类为异构模型,和它的工作原理以及CPU;输入数据必须首先通过CPU,然后复制到GPU。该操作被认为是主要的因素,减少了GPU的并行计算的性能。频繁的CPU和GPU之间的数据传输可能会影响我们的并行计算的性能。为了避免我们只能复制不能轻易在GPU上生成的数据。换句话说,GPU强大的计算,生成数据计算可能成本不到复制它们。然而,在某些情况下,生成数据的操作导致缓慢的执行时间。 The trade-off between the cost of copying data and generating data must be treated carefully as one of the important factors for improving the parallel computing in GPU.
为了加快解决高级的计算使用枚举,我们可以利用GPU,把高级的搜索树的成千上万的子树,可以独立运行。搜索树分为两部分:第一部分运行在CPU和GPU上运行。第二部分这两个部分由一个水平子树的生成和发送到GPU来运行。每个子树分配给一个线程在GPU。实际上,现在有成千上万的子树,不能马上送到GPU,所以我们需要很多趟GPU为了覆盖所有子树生成水平 。
技术核心的贡献是提出了三种策略加快古典枚举和修剪枚举的运行时间。第一个策略是基于随机化的基础。我们执行随机化的基础上,例如,100个基点。然后,我们测量的质量基础,估计每个枚举树的节点的基础。在Hanrot及Stehle [20.),一个枚举树的节点可以使用高斯估计启发式。导致更少的节点选为基础最好的基础。第二种策略是基于期望最好的水平的CPU和GPU之间传输数据的成本非常低,而第三个策略是基于获得基于GPU的改进,可以由产生一些树在GPU而不是CPU。第三个策略的主要思想是类似于一个用于改善BDD枚举(33]。
1.3。我们的研究结果
我们的工作表明,我们可以提高何曼思等的实现(28]修剪枚举和专题等的实现(30.)等经典枚举通过应用一些改进开始一个更好的基础和选择一个好的级别GPU和CPU之间的数据交换。此外,我们建议生成一些具有特定属性的子树在GPU而不是CPU。
1.4。路线图
剩下的纸是组织如下。节2格的基础上,我们引入一个背景。节3,我们将展示经典的枚举算法求解高级副总裁。节4,我们描述了修剪枚举算法求解高级副总裁。部分5致力于给我们的贡献为提高当前解决高级使用GPU的并行算法。节6,我们展示了实验结果。最后,结论和未来的工作部分所示7。
2。预赛
在本节中,我们首先定义晶格紧随其后简要回顾所需的背景和晶格的基础上减少。
让是欧几里得 - - - - - -维空间, 是一组线性无关的向量 。产生的晶格是一组 所有的线性组合的积分 。一组被称为晶格的基础 。的整数和被称为晶格的尺寸和等级,分别。如果 ,然后被称为满秩晶格。一个格子据说积分如果它是包含在吗 ,也就是说,任何依据只包含整数向量。在本文中,我们假定基向量 的晶格整数的条目,这是通常情况下在lattice-based密码学。
通常,为了简单起见,基础 由 组成的列向量的矩阵,晶格的基础l。我们定义行列式或晶格的体积 ,用 ,作为 。因为我们寻找最短向量,我们必须意识到晶格的基础不是唯一的。任意两个不同的基础矩阵和 ,我们说 当且仅当和由单位模的相关矩阵,即 ,在哪里是一个 与整数矩阵的条目和行列式 。
这种变换的幺模的矩阵使我们能够生成一个新的基础,比原来的基础。因此,出现的问题是当一个基础比另一个“更好的”或更方便。我们可以说,依据一个晶格”尽可能接近正交是“是方便的34];因此,我们可以说,进一步依据正交更好。所以,第一步获得更短的向量为基础晶格是生成一个正交基;然后,基于正交基以及什么是所谓的晶格减少,我们可以创造一个更好的基础。减少晶格基础是发现的过程与短和近正交向量的基础。一个著名的方法生成一个正交基晶格是gram - schmidt正交化方法。
gram - schmidt正交化方法适用于任何一组向量转换为另一组向量两两正交,他们除了跨度相同的空间。
对于一个给定的晶格 ,我们定义相应的gram - schmidt正交化 如下: 在哪里表示内心的生产表示欧几里得范数。
gram - schmidt正交基向量 似乎是最好的减少基向量,但这是不对的,因为他们并不一定的晶格。如果基础 包括整数向量,然后gram - schmidt正交基向量 和系数是理性的(14]。然而,gram - schmidt正交基底晶格还原过程是有益的;减少晶格可以很容易地计算如果依据正交或足够接近正交基(34]。1982年,Lenstra et al。10)提出了一个概念叫大典时减少和降低多项式时间算法,计算一个LLL-reduced基础来自任意基础相同的格子。微光算法是基于gram - schmidt正交,它旨在生成一个新的基础上尽可能的晶格gram - schmidt正交基。如今,该算法用于减少晶格实践是BKZ算法。在本文中,我们使用BKZ实现NTL Shoup博士(图书馆21执行BKZ减少)。
3所示。经典的枚举算法
为了解决高级副总裁,枚举算法通常使用,因为它们是最有效的算法目前现实的维度。标准的枚举算法通常归因于(16]和芬克以及Pohst [19]。在[14],斯诺和Euchner列举晶格向量的曲折的策略,使算法有更好的性能。这个算法(伪代码可以发现算法1)可以描述如下:根据输入的基础 ,gram - schmidt系数 ,二次规范gram - schmidt正交化 , , , 的 ,和一个初始 ,和它的目标是找到一个系数向量 满足的方程
|
原始枚举算法的搜索空间是所有系数向量的集合 满足 。这些线性组合被组织在一个树结构。树的树叶包含完整的线性组合,而内部节点包含部分向量。寻找树叶决定最短非零向量以深度优先搜索的顺序执行(16]。最重要的部分枚举树的切断部分,即。,the strategy in which the subtrees are explored and subtrees that do not lead to a shorter vector are eliminated. This strategy is based on the computation of an intermediate squared norm ,在哪里是一个级别的树。下面的引理显示了它是如何计算的。
引理1。(见[34])。让 晶格是一个依据 , 是gram - schmidt和正交的基础gram - schmidt系数 。让 是欧几里得范数的一个上界的晶格 。让 这样 ;然后,对于 , 让 和 。因此,可以减少不平等以下公式:
4所示。修剪枚举算法
为了减少斯诺和Euchner算法的执行时间,斯诺和霍纳在1995年提出了一个修改枚举15),称为修剪。修剪枚举是基于删除子树,不太可能导致一个解决方案。修剪的枚举的主要思想是修剪搜索树的子树中找到一个精确解的概率太小了(23]。通过使用修剪枚举,穷举搜索被限制为只有一个子集的所有可能的解决方案。虽然,这可能会导致一些丢失的概率精确解,但它提供了显著改善的执行时间。2010年,伽马等人提出了枚举与极端的修剪23),李子更高的枚举树的节点数,从而大大减少了算法的执行时间。虽然极端修剪显著加速搜索树,错过了解决方案的概率是非常高的。找到一个解决方案的概率仅为0.1%。然而,根据伽马et al .,可以增加的概率达到90%以上,如果我们执行枚举在不同的基地近1000倍。在本文中,我们集中在修剪枚举并提出一种有效的方法来加速搜索使用修剪枚举。
修剪枚举是基于使用绑定每一个层次的而不是使用绑定对于所有的水平。数学,在修剪枚举,我们更换的不平等 ,每一层通过 ,在哪里绑定在层次吗 。绑定在层次从绑定吗使用一个名为边界函数的函数。一个精心挑选的边界函数有助于迅速大幅列举树,同时会导致一个解决方案。实际上,有许多边界函数;著名的一个是线性边界函数提出的帆船和Euchner14),这是 。修剪枚举算法类似于算法1除了我们计算在步骤3和替换通过在步骤6的算法1。
5。提出了基于gpu的修剪枚举
在本节中,我们提出一个基于gpu的修剪枚举算法(算法4),搜索最短向量在晶格。该算法是一种改进的版本的GPU的算法描述何曼思et al。28),进而提出基于枚举算法ENUM斯诺和Euchner14]。基于gpu的修剪枚举算法可以很容易地适应是一个基于gpu的古典枚举算法通过减少修剪条件。的改进是通过引入三种策略加快修剪枚举算法的运行时间2。第一个策略,提出了部分5.1。1,用于改善晶格的质量基础上,找到一个更好的基础,加速了枚举。第二种策略是基于期望最好的水平α在CPU和GPU之间传输数据的成本很低,提出了部分5.1。2。第三个策略,提出了部分5.2,基于改进的基于GPU的,可由产生一些树在GPU而不是CPU。
|
提出了基于gpu的修剪枚举算法的伪代码所示算法4。它由三个不同的阶段:预处理(步骤3和步骤4),顺序(步骤6日至14日和步骤- 34),一部分和并行部分(步骤15 - 29)。在步骤3中,我们称之为算法2应用策略选择更好的基础。在步骤4中,我们使用第二种策略选择一个良好的水平GPU和CPU之间的数据交换。连续的部分是CPU上执行。它的工作原理如下:首先,我们生成GPU-points CPU使用的算法3;然后,生成的GPU点被发送到GPU上运行。一旦GPU终止,GPU的执行点算法3再次生成另一个GPU点用于下一个推出的GPU。运行在GPU并行部分。这部分流程相同的方式并行的部分并行算法(28),除了子树枚举时终止(步骤16),其相邻的子树对应于一个邻居点生成在GPU上运行相同的线程。如果当前邻居点切断一样(21)步,生成子树枚举取消,一个新的起点是分配给当前线程(26)步。GPU点集完成他们的子树枚举在GPU的线程。相同的方式在28),一个子树枚举在流泻的GPU执行和深度优先搜索顺序,从水平朝着叶水平(0级)。
|
5.1。预处理策略
在本节中,我们提出两种预处理策略选择一个更好的基础,一个更好的水平在算法4。我们使用随机化和高斯启发式的部分5.1。1期待一个更好的基础,导致迅速最短向量;另外,在节5.1。2,我们预计的水平优化CPU和GPU之间交换数据。在[23],伽马等人利用随机增加成功的概率找到一个短向量通过生成许多不同晶格的基础 ,在我们的战略部分5.1。1旨在减少搜索树的分支的数量通过寻找一个基础,是对应于一个较小的搜索树,即。搜索树,少了一个分支。
高斯启发式提供一个估计的数量在晶格点不错集。更具体地说,它说,对于一个给定的晶格l和一组年代点的数量 大约是 。在[20.),Hanrot Stehle发现(和验证23]),节点的深度可以从高斯估计启发式如下: 在哪里表示的体积k维球的半径 。
回忆的体积k维球可以被计算 在哪里表示γ函数(35]。
从方程(7)和单位球的体积在维度 ,我们可以在深度一些绑定的节点数量在Schnorr-Euchner算法2通过设置一个初始边界一个的晶格如下:
5.1.1。战略选择更好的晶格
基础更好如果它导致更快的解决方案,即:,如果the number of nodes of the search tree corresponding to a basis is smaller; we propose to find a better basis by generating many basis using a randomization strategy which is carried out by multiplying the original basis by a random small unimodular matrix as shown in [6]。然后,我们为每个基础计算相应的节点使用高斯启发式在方程(6)。算法2描述了这一策略,变量指的是生成的基础。
5.1.2中。确定战略层面
选择水平可以被认为是一个具有挑战性的任务实现枚举算法有效的GPU,因为水平这是非常接近根增加GPU的计算负荷。然而,它减少了可能的点。相反,水平非常远离根GPU上减轻了计算负载,但它增加大量的数量可能点发送到GPU,这意味着GPU和CPU之间通信的数量将大幅增加。因此,主要的挑战是如何平衡计算负载GPU和CPU和GPU之间的通信。换句话说,面临的挑战是如何确定水平的最佳选择相结合的两个目标减少计算负荷,同时CPU和GPU之间的通信。在本节中,我们提出这一挑战的策略。我们使用的策略是基于使用高斯启发式计算预期节点候选的水平。然后通过近似在GPU上运行一个节点所花费的时间,我们可以预期执行时间实现枚举每个级别的所有节点的节点数量乘以近似的时间在GPU上运行一个节点。最后,我们选择的最佳选择这是对应于最小的预期执行时间。例如,假设我们有一个晶格100和10个候选人水平的维度 来 。首先,我们计算出预期的节点数量在每一层使用方程(6)。然后,我们运行每个候选人的GPU的内核级别在短时间内,并通过使用CUDA效用nvprof,我们可以执行所花费的平均时间GPU的内核。然后,这段时间除以每个GPU的节点数量的内核,我们得到一个近似为一个节点执行时间。假设一个节点的执行时间 ,…, ,相应的水平 ,…, ,分别。现在,我们可以期望水平的执行时间通过近似执行节点所花费的时间乘以这个级别的节点数量。更准确地说,让 表示所有节点的预期执行时间的水平 ,…, ,分别。然后, 计算如下: ,…, 。相对应的级别之间的最小值 ,…,被选中作为生成GPU点最好的水平。
5.2。为提高利用GPU的策略
CPU和GPU之间传输数据的开销可以减轻通过减少数量的GPU点送到GPU。为了实现我们提出GPU点分成两个类型进行分类,这样转移操作只需要第一类型,而对于第二种类型,生成的GPU点在GPU而不是CPU。让我们首先调用类型的GPU点开始点和第二类型的GPU点你的邻居点(图1)。开始点代表GPU点不能根据其生成邻点不动后来在树上。而邻居点GPU点很容易预期基于相邻点的值,而无需在树上。例如,假设我们有5分 , , , ,和水平 。让 , , , ,和的相应值 , , , ,和 ,分别。这一点发送到GPU如果不平等吗 持有,否则被切断,如图1,因为 ,然后下一个值可以很容易地计算(步骤20算法1)。随后,作为算法的步骤211的因素计算,因此我们可以说点生成一个邻居点,因为它是通过使用整数吗和相邻的点 。同样的,我们可以生成你的邻居 。现在,我们在点 ,由于 ,然后枚举算法移动,所以因素的点将使用第9步计算的算法1,这取决于的值为 。因此,点不能没有透露这些值的生成 。换句话说,从点 ,我们必须在树上,直到我们达到这一点然后将显示这些值。因此,我们可以说点是一个起点。
5.2.1。生成GPU-Point算法
的改善策略5.2主要应用在步骤7 - 18的算法3和步骤16的算法4。我们显示了算法的工作流程4。现在,我们将展示如何算法3是如何实现的。算法3实现在CPU一样(28]。首先初始化的值在根级别 (步骤2)。在根级别(顶层),唯一的显示值 ;其他值 将显示在流泻,深度优先搜索遍历树秩序向水平 。当枚举到达的水平 ,搜索顺序改变是只要一个广度优先搜索顺序 。我们的算法之间的差异3和生成GPU的算法分28)是我们只生成一开始点。事实上,对于每个GPU点在层次 ,我们有两种情况:(1) (步骤7):在这种情况下,GPU的观点接受并添加到集合吗(GPU的集合点随后发送到GPU);然后,广度优先搜索的树枚举显示下一个点。然而,在这种情况下,第二点是你的邻居点,所以没有需要添加 ,之后,它可以轻松地生成算法在GPU中使用16—18步4。为每一个GPU点 ,我们储存的值 和 ,这些值是用于初始化数据的GPU GPU。(2) ,在这种情况下,相对应的子树被切断和枚举上升到父点使用流泻(步骤20-26算法3)。因此,枚举算法仍以深度优先的搜索顺序上下移动,直到它返回到水平与一个新值 。然后,相应的点作为一个新的GPU点,我们使用相同的程序(1)。
6。实验结果
在本节中,我们目前获得的结果通过实施该策略。此外,进行了一些分析显示高GPU的性能通过使用改进的部分5.1。2和5.2。我们的实现修剪枚举和古典枚举比较何曼思的修剪枚举(28和专题的枚举30.),分别。这部分组织如下。节6。1,我们现在平台规范和数据集的实现。节6。2,我们详细描述了实现结果显示执行时间通过使用修剪枚举每个提议的策略,我们也比较我们的实现结果何曼思的实现结果。节6。3,我们展示实现结果古典枚举使用该策略。然后,我们比较GPU执行时间多核CPU执行时间专题的实现。
6.1。平台规范和数据集
为了检验算法的改进,我们使用两个Nvidia GeForce 1060 GTX GPU与CPU并行执行2.83 GHz的英特尔酷睿2四核等顺序执行,每个GPU沿着分离核心的CPU。9.1软件使用CUDA平台上安装Ubuntu Linux 16.10。对数据集的实现,我们区分两种类型的数据集:修剪枚举的数据集的数据集古典枚举。修剪枚举生成的数据集使用NTL包,这被认为是一个著名的数学软件包晶格。NTL包的使用让我们产生更多的样品每个维度,并进行更多的检查我们的改进。我们为每个维度生成5个样本,样本是一个矩阵的基础上的列;每一行的每个元素的一些大小设置为64位。古典枚举的数据集是一个示例提供从SVP-Challenge (http://www.latticechallenge.org/svp-challenge/60)维度。维度晶格的将不同修剪枚举在80年和110年之间,当它被设置为60的古典枚举。水平我们创建GPU点设置根据第二个策略。一般来说,范围从来修剪枚举,它被设置为经典的枚举。将GPU点从CPU、GPU为每个GPU的内核在393216年发射GPU点。入住率的GPU被认为是获得充分利用GPU的主要因素,所以我们必须仔细设置线程的数量/块中扮演一个重要的角色在促进GPU的植入过程。我们的实现测试表明,该线程块大小128可能是一个不错的选择对于我们的Nvidia卡,收益率高计算性能。
传统的过程改善晶格的质量基础是使用还原法实现枚举算法之前,例如,微光或BKZ减少。实际上,我们使用BKZ减少我们的实现。修剪枚举,我们BKZ块大小设置为30岁,35岁,35岁和45尺寸80年,90年,100年和110年,分别在古典枚举的同时,我们将BKZ块大小设置为20尺寸60。有两个库可用于减少晶格:NTL图书馆Shoup博士(21和fpLLL Albrecht图书馆等。22]。fpLLL库没有提供BKZ。因此,对于我们的实验中,我们使用NTL库。
6.2。实现删除枚举
在本节中,我们目前的详细实现过程和结果通过实现每个提出了修剪枚举策略。我们比较我们的修剪枚举实现结果何曼思的修剪枚举。对于每一个尺寸,我们运行代码,何曼思的代码相同的五个样品:(1)战略的实现基于GPU生成GPU点(部分5.2):用于检查这一战略,我们比较了基于gpu的并行实现对何曼思的基于gpu的并行实现28),平台规范和使用的数据集两种实现都是相同的。根据实验结果表1使用这种策略,改善了是1.3左右。(2)基于优化的实现策略的选择 :对于每一个样本的维度 ,我们计算预期的节点在每个水平基于方程(6),然后通过计算近似GPU执行时间节点见的内核部分5.1。2,我们计算预期的执行时间。最后,我们选择最好的候选人之间的水平。例如,对于一个样本的维度n= 100,如表2,我们可以看到这一水平34有望优化执行时间。而在表3,预计32级优化的执行时间n= 90。(3)战略的实现基于基础提高质量使用随机化(部分5.1。1):为每个维度 ,我们随机原始基础100次;在每一次,我们进行BKZ减少和使用高斯启发式为每个随机获得预期的节点。相对应的结果是更少的节点的基础。这种策略加速执行时间的近1.5倍,如表所示1。
结果表1和图2表明三种策略的组合提高了执行时间何曼思的修剪枚举的近2.5倍。
最后,我们将展示我们的可伸缩性的实现策略通过使用两个gpu。结果表4表明,使用两个GPU实现改进几乎是两倍的速度比一个GPU的改进。更准确地说,两个gpu加速的执行时间何曼思的修剪枚举几乎5倍(图2)。
6.3。实现古典枚举
在本节中,我们将实施我们的战略在古典枚举的结果。我们比较我们的实现结果专题的实施结果(30.]。维60,我们使用一个样本获得高级的挑战。我们有专题的实现的执行时间(30.]。
图中所示的结果3表明,该策略也为古典枚举有效。挑战维度60可以解决在45秒,24秒使用一个GPU和两个GPU,分别。而配置的机器与16个物理核心和同步多线程技术(30.)解决相同的维度在47秒60的挑战。因此,我们与两个gpu是两倍的速度比改进同步多线程技术提供的16个物理核心维度60的挑战。
6.4。GPU性能分析
改进利用GPU的一些特性已经被应用在何曼思et al。28)如使用寄存器和共享内存(36]。尽管他们通过减少延迟,提高了执行时间他们影响入住率36)由于寄存器和共享内存的大小是非常有限的。一般来说,使用的寄存器和共享内存实现GPU性能的改进。我们也改善了访问全局内存效率通过合并访问的全局内存36]。
在本节中,我们分析我们的策略使用GPU的性能因素。已知的GPU的性能评价因素是(36入住率,散度,全球负载效率,和全球存储效率。最后两个因素测量的效率使用全局内存:读写效率。我们表明,我们的策略基于GPU喜欢“选择更好的水平”和“生成GPU点GPU”显著提高GPU的性能。是在表5”,选择的水平“改善GPU的性能起着关键作用。大幅减少的数量共进午餐GPU的内核。然而,它影响GPU性能的一些因素,例如,全球存储效率和分支效率。是在表5,全球存储效率降低的水平因为当水平移动行动起来,更多的变量需要存储在寄存器中。自注册是非常有限的,额外的数据被划分到一个自由空间的全局内存。因此,全球存储效率的影响。
表6显示“GPU生成GPU点”的策略降低消耗的时间推出GPU的内核和CPU和GPU之间传输数据。然而,这种策略,我们可能失去合并获得一些数据,这是全球存储效率降低的原因。此外,为了生成GPU点GPU,我们需要添加一些分支机构来实现。因此,分支机构效率的影响。
7所示。结论和未来的工作
在本文中,我们提出了提高三种策略解决高级的修剪枚举。战略基于GPU生成GPU点,一个策略基于提高基础的质量通过使用一个随机化的方法,并基于期望最好的策略水平我们生成GPU点。我们表明,显著加快能获得通过使用这些策略。实验结果表明,近2.5倍的加速和5是通过使用一个单一的GPU和两个GPU,分别。此外,我们表明,两个gpu的两倍速度比16个物理核心提供了同步多线程技术。对于未来的工作,我们计划与多核使用multi-GPUs实现这些策略。
数据可用性
使用的数据来支持这项研究的发现可以从第一作者。
的利益冲突
作者宣称没有利益冲突。