Nabil Hallou的二进制文件优化：通过向量化转换的研究

通过向量化变换对二进制文件进行优化Nabil Hallou引用此版本：Nabil Hallou通过向量化转换对二进制文件进行优化。计算机算术雷恩大学1，2017年。英语NNT：2017REN1S120。电话：01795489v2HAL Id：tel-01795489https://theses.hal.science/tel-01795489v22018年5月18日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire安娜2017THYLSE/ 雷恩第一大学布列塔尼卢瓦尔大学校园为了等级雷恩大学博士提及：Informatique数学博士学校par presentéeNabil Hallou为INRIA研究所编写的文件雷恩第一大学通过向量化变换这是雷恩最好的选择陪审团组成后：杜·尤里总统Rennes 1大学校长M DENIS BARTHOUBordeaux INP顾问/M Felix WOLFDarmstadt技术大学的讲师特别报告员Mme ISABELLE PUAUTProfesseur à l’Université de Rennes 1Mme ALEXANEJIMBOREAN乌普萨拉大学会议主持人考试M ERVEN ROHOUDirecteur de recherche INRIA，Equipe PACAP，àRennes/Directeur de thèseM·P·希利普· C·劳斯Strasbourg/Co-directeur de thèse确认这项研究是献给我亲爱的母亲，妹妹，和我的家人。我想向Erven Rohou博士表示衷心的感谢和感激， 感谢菲利普·克劳斯博士给我机会在他们的监督下学习和工作。在我的研究过程中，他们不断的指导、帮助、支持和善意是一种推动力，没有他们，我就无法提出这一卑微的贡献。内容目录1简历50.1Optimization dynamique decodebinaire 50.2Brève introduction àlavectorisation 60.3La re-vectorisation ducodebinaire 70.3.1将指令转换为等同指令SSEAVX 80.3.2Lacontrainte...................................................................................................0.3.3L’ajustement0.3.4L’ajustement du nombre0.3.4.1Nombre totalpilation 90.3.4.2Le nombre total0.4自动矢量0.4.1McSema 100.4.2Lavectorisation et la compilation lavolée 110.4.2.1Le problème desvariablesglobals 110.4.2.2Le marquage desvariablesglobals 110.5结果120.5.1重新矢量化120.5.1.1结果120.5.2自动矢量0.5.2.1结果130.6结论141一、导言151.1语境151.2问题定义171.3解决方案171.4出版物一览表2动态二进制优化212.1基于软件的配置文件212.1.1准时制（JIT）方法2212.1.2探测方法232.1.3间接费用232.2基于硬件的配置文件242.2.1硬件性能计数器概览242.2.2硬件性能计数器的有用功能252.2.3开销与准确性252.3Padrone基础设施2.3.1Profiling 262.3.2分析272.3.3代码缓存282.4结论293二进制代码的动态再向量化3.1背景313.1.1矢量化概览313.2二进制代码的再矢量化323.2.1SSE到AVX转换的原理3.2.2将指令从SSE转换为AVX 333.2.3注册活性343.2.4诱导变量353.2.5循环边界353.2.5.1编译时已知的循环边界3.2.5.2循环边界仅在运行时已知363.2.6别名和数据重复383.2.6.1别名概述3.2.6.2翻译具有数据依赖关系的循环的问题3.2.6.3静态间隔重叠测试383.2.6.4动态区间重叠测试393.2.7对齐限制393.2.8减少413.2.8.1翻译减少额3.2.8.2翻译器支持的归约子类3.3结论454二进制码47的动态矢量化4.1多面体模型的原理4.1.1静态控制部分（SCoP）484.1.2完全和不完全环套484.1.3迭代域494.1.4访问功能504.1.5指令51之间的执行顺序4.1.6数据依赖524.1.7循环变换564.1.7.1单模与多面体变换564.1.7.2多面体变换574.2二进制代码的矢量化4.2.1标量转化为矢量优化的原理624.2.2使用McSema 63将二进制转换为中间表示4.2.2.1McSema 634.2.2.2Padrone与McSema 644.2.2.3调整McSema以产生合适的LLVM-IR 654.2.3使用Polly 66实现LLVM-IR中循环的矢量化4.2.3.1Canonicalization规范化674.2.3.2范围检测684.2.3.3Scop提取694.2.3.4依赖性分析4.2.3.5日程安排694.2.3.6矢量化704.2.4LLVMJITtuning 724.2.4.1处理全局变量724.2.4.2标记IR操作数734.3结论735实验结果755.1再矢量化实验结果755.1.1硬件/软件755.1.2基准. 755.1.3业绩765.1.4间接费用805.2矢量化实验结果815.2.1硬件/软件815.2.2基准815.2.3业绩表现815.2.4间接费用825.3结论826相关工作836.1Compilers’6.2线程级推测系统876.3二进制到二进制自动向量化和自动并行化886.4在虚拟机级别或使用动态二进制进行优化翻译工具906.5结论. 917结论. 937.1前景94索引95Bibliography参考书目104图105.1摘要108简历从1982年开始使用Intel80286处理器开始，处理器制造商的趋势是尊重优先兼容性的约束。在短时间内，她permet aux programmes compilés pour un ancien processeurde因此，在新版本中使用旧版本中存在的处理功能是不方便的。这种资源的低利用率与一种不佳的性能相关。Cela se produit à cause de la non-disponibilité du code source.Pour donner quelques quelples concrets ， pour certain raisons l'industrie continued'utiliser des logiciels patrimoniaux ou hérités sur des nouvelles machines，而密集计算方案是为了在不了解材料的情况下在小组中巡回执行Pour respondre à ce problème de sous-utilisation des resources，notre rechercheporte sur l'optimization du code binaire pendant l'éxécution.我们希望各地区利用一种非常先进的生产方法。当最后一步被检测到时，它们是自动优化的，新的二进制代码被注入到程序代码中。这些电话是新版本的优化版本。我们采用了两种优化：第一种，重新矢量化是一种优化二进制-二进制，它可以用于处理旧版本（SSE）和优化版本转换（AVX），以最大限度地利用资源。其次，矢量化是对标量块矢量化的体系结构的独立优化。我们致力于集成自由逻辑：（1）将x86动态二进制转换为LLVM编译器的中间表示，（2）将多模型中的嵌入块抽象和向量化，（3）将编译器转换为LLVM编译器的实时编译器。在第1节中，我们介绍了Padrone，一种用于优化程序的方法，以及用于分析和注入代码的功能。Les sections 2 et 3 presentent la re-vectorisation et la vectorisation desboucles.第四节提出了实验结果。0.1二进制代码动态优化L’optimisation dynamique de code binaire vise à appliquer des transformations d’opti-misation56简历au code source ou à toute form de représentation intermediaire.在此研究中，我们使用了Padrone[RRC+14]板，这是一种多项技术，用于分析和操作通用和专用于建筑的二进制文件Les services de Padrone peuvent être divisés en trois grandes catégories：1）profilage，2）analyze，et 3）optimization，qui sont décrits brièvement dans lesparagraphes qui suivent.Le composantprofilage利用les appels système Linuxperf_event a finn d' accéderaux compensation de performance matériels. La technique该组件分析了过程中的文本段，分解并分析了代码二进制化，以生成一个图形Flotde GFC（GFC），并在可能的功能中定位代码块。 重新矢量化产生了GFC。最后一个是自动矢量化的中间表示。Padrone a les mêmes limitations que les autres décodeursdu jeu d'instructions x86.特别是，二进制代码的分解并不现实。这些原因包括saudsindirects，le code obscurci，或a présence dLe composantoptimization fournit des fonctionalitées de manipulation de code bi-naire，ainsi qu'un mécanisme d'injection de code-cache.在这一研究中，这是一个利用原理来重新生成代码的方法，该代码部分用于表示变换后的一个矢量块内部。Cecomposant s'occope du calcul des adresses en memories après le repositionnement ducode optimisé dans le tas. Padrone fonctionne comme un processessus distinct，quiinteragit avec le programmes cible grâce ànalitésLinux telles que le système defichiers/proc. 乐 观 主义者有能力-在执行过程中没有提出申请，因此不必在开始时重新开始执行方案。Il surveillel'exécution du programme，decte les points chauds，sélectionne la boucle vectoriséeSSE ou scalaire et fournit全 球 金 融 危 机 通 讯 员 。 Padrone est responsable del'injection d'une version optimisée et de la réorientation de l'exécution.0.2Brève introduction à la vectorisationUn opérande vectoriel est capable de stocker un tableau d'éléments de données in-dependants du même type.技术基础上的载体种类繁多。例如，一个操作SEE（Intel）测量128位，这意味着可以将五个简单精度（32位）或两个双精度（64位）的名称组合在一起。Une instruction vectorielle est une instruction can- pableLa Figure 1 illustre le pseudo-code des versions séquentielles et vectorisées7二进制码的再矢量化版本标量I n t A[ ]， B[ ]， C [ ];. . .f or（i =0; i n; i ++）{ a= A[ i];int [ i ];c = a+b ;C[ i] = c;}Versionvectoriséei n t A[ ]， B[ ]，C[ ];. . .联系我们 布克莱 v e c t o r i sé e i =0;i n; i+=f v）{va = A[ i . . i+fv[;Vb = B[ i . . i+fv[;vc = padd（va，vb）;C[ i. . i+fv [=v c;}联系我们 é p i l o g u e/01 - 02 - 2013（ ; i n; i ++）{Les i t é r a t i o n s r e s t a n t e s马格德堡丹L eCAS奥什 n 没乌斯怀恩 穆勒蒂普勒德菲弗联系我们}图1：矢量化矩阵的加法C= A+ B。变量va，vb，vc设计矢量，padd设计一个附加矢量。并行处理的名称是在图1中，元素为由于迭代次数增加，迭代次数按四次划分0.3二进制码的再矢量化Notre objectif est de Transformer les boucles vectorisées en SSE en versions AVX.重要的是，二进制文件是矢量化的，我们不关心SSE到AVX的指令转换，以及保证转换合法性的验证。我们集中注意力在体内的血管上，有连续的记忆。 相应地，可以进入SSE与AVX双重操作的données的名称因此，在parfait scénario中，一个块AVX执行一个块SSE的所有迭代的名称La Figure 2 montre les versions vectorielles SSE et AVX du pseudo-code de la bouclede la Figure 1.在SSE的原始版本中，第一个指令（ligne 2）在xmm0中列出了表A的4个要素。第二指令（第3级）与xmm0中所含B值的4个平行要素以及第三指令（第3级8简历1234567图2：Example de conversion des instructions du SSE vers4)把结果记录在画面C中。Le registrerax represente la variable d'induction. 最后一个增加了16个八位组：向量SSE的大部分（第5行）。球头的转换相对简单。但为了确保转型的合法性，必须有一个明确的可操作性。0.3.1将指令转换为等同于AVX的Pour simplifier l'implémentation du processessus de la conversion ， nous avonscalculit une table qui mappe une instruction SSE à une ou plusieurs instructionséquivalentes en AVX.它必须使AVX指令能够进行双重工作在SSE的指导下也是一样的。另一方面，移动是一个指令的运动de données SSE qui déplace 16 octets dedonnées de/vers la memoire et qui sont quiées sur des limites de 16 octets。在指令转换过程中，所有的données都被替换为32个八位字节，一个指令被替换为32个八位字节的向量。假设图2.a中的表C是32个八位字节， SSE版本中的ligne 4在AVX结果中转换为vmovaps（ligne 5）。因此，128位的xmm寄存器将转换为258位的xmm寄存器0.3.2La contrainte一个指令SSE可以在AVX上提供多种选择 同样地，所有的替换都是16个八位字节，两个指令都不能替换。指令vmovapsnécriitequelesdonnéessoientquiéessur16octetsetetnedéplacequelamoitié infériéndel'opérandevectoriel. L’instruction 我们认为画面A在图2.a中有16因此，SSE版本中的Ligne 2说明与AVX版本中的Lignes 2和3说明相同. L2：movapsA（rax），xmm0addpsB（rax），xmm0movapsxmm0，C（rax）addq$16，raxcmpq $4096，raxjne。L2. L2：vmovapsA（rax），xmm 0vinsertf1281，A（ rax，1 6），ymm0vaddpsB （ rax ） ，ymm0vmovapsymm0 ， C （ rax ）addq$32，raxcmpq4096美元，雷克斯9二进制码的再矢量化0.3.3L’ajustement du在 某 些 情 况 下 ， 变 量 d'induction sert à déterminer l'accès à la memoire à chaqueitération。 类似地，在图2.a中，在第2、3节中的记录et 4，est utilisé commeindice par rapport aux adresses de base des tableaux A，B etC à partir desquels leslectures et les écritures doivent être e e executuées. 唐内 如果指令中包含16个八位字节的操作，则寄存器中的16个八位字节将增加到5号线（图2.a）。Lorsque le code esttraduit en AVX，la taille de l'opérande devient 32 octets.相应地，索引增加的响应指令适应于AVX版本0.3.4L’ajustement du nombre totalUne itération AVX doit correspondre à deux itérations SSE.因此，总迭代次数的数值将增加一倍。转换过程涉及两个场景，总迭代次数与汇编或0.3.4.1编译时连接的总迭代次数有指令SSE的迭代和循环的名称可能是成对或不成对的Lorsquen=2×m，此外，所有迭代名称都不完整，n = 2 × m + 1，代码转换由两个基本块组成：首先，执行AVX指令的块接着SSE指令执行SSE最后迭代。0.3.4.2Le nombre total假设qu：n=m×fv+r，其中m是向量化迭代次数，r是剩余迭代次数< 在这种情况下，编辑生成一个向量块，它是fois的，和一个序列，它是fois的。在控制器不提供一个或两 个 执 行 时 刻 的 数 值 之 前 ， m 和 r 的 数 值 必 须 计 算 Nous modi Fions le coderesponsable de determiner la valeur dem etr au moment de10简历图3：自动矢量化过程0.4自动矢量化这些应用程序包含无法通过编译器进行矢量化的标量块，即使它们也是矢量化的。有一个理由le code source a été compilé pour une architecture whi ne prend pas encharge les instructions SIMD. Une autre raison est que certains compilateurs ne sontpas capables de vectoriser certains types de codes [15] ， car ils n'intégrent pasd'analyze avancéedes dependances de données et de capacités de transformation deboucles，comme le modèle polyédrique [12].在此部分中，我们将自动向量化标量块的优化部分放大我们利用McSema [16]的自由逻辑，通过LLVM的中间表示（RI）来实现代码二进制化，从而确定优化是否有效。 De la RI，il est possible de déléguer lefardeau de la vectorisation à un autre outil ， Polly [13] ， mettant en Üuvre destechniques du modèle polyédrique pour vectoriser les boucles.最后，我们使用编译LLVM（JIT LLVM）的volée二进制方式编译RI向量。La Figure 3 réquelle process devectorisation automatique.0.4.1麦克塞马McSema est un logiciel de décompilation dont la fonctionnalité est de traduire le codebinaire vers la représentation intermediaire de LLVM. McSema se compose de deuxoutils ， comme on le voit sur la Figure 4 ： Le bin_depth prend comme argumentsd'entrée l'executable et le nom de la fonecumble，il consider un CFG de la fonecumble然后，将数据结构转换为磁盘上的可存储格式，并将最后的数据记录在备忘录中。L'outil cfg_to_bc点燃了磁盘的données，重新安装了CFG，并将指令转换为LLVM的中间件。我们将修改下料口，以便将Padrone的fontium fréquemment exécutée fournie的地址计算在内，以代替其名称在外面，我们在外面11自动矢量化图4：此 外 ， 还 对 McSema进 行 了 修 改 ， 以便 将 CFG产 品 从 bin_downward直 接 传 输 到cfg_to_bc，以代替记录和记忆。图4是0.4.2矢量化和编辑Polly [13] est une infrastructure d'optimisation de boucle statique pour le compilateurLLVM ，capable d'esterier les opportunités de parallelisme pour les nids de bouclesconformes au modèle polyédrique：les bornes de la boucle et les accès à la memoiredoivent être a bouches.目标主要是矢量化安全代码。然而，册封的通行证是执行的，这是为了波利把RI变成一个合适的形式第二，波莉用一个静态控制器来检测这些曲线。第三，这些地区在多边形中是抽象的。最后，我们使用一种方法，通过分析依赖性来验证是否与boucle est parallèle相似我们需要一种算法，该算法可以在访问données sont consécutifs时进行验证。Ensuite，nous transformons les instructions eninstructions vectorielles et compilons à la volée à0.4.2.1全球变量问题La décompilation du binaire en représentation intermedédiaire consiste à générer lesinstructions et les adresses memoire sur lesquelles opérent.当然，麦克塞玛会根据指示来修改画面此外，还编制了关于在最佳治疗空间中的指示和分配表的一般中间代表。相应地，在地址的反向移动过程中注入该代码0.4.2.2全球变量侯爵所采用的解决方案包括：在汇编之前，通过McSema与其他人的合作，12简历21.81.61.41.210.80.60.40.20图5：Les re-vectorisation的结果在 通 用 二 进 制 指 令 中 处 理 检 索 到 的 代 码 。 La compi- lation de la représentationintermediaire passe par plusieurs étape.但是，0.5雷苏尔塔0.5.1再向量化Nos experiences ont été menées sur une station Linux Fedora 19 à 64 bits avec unprocesseur Intel i7-4770 Haswell cadencé à 3，4 GHz.我们有两种基准。Le premiertype consiste en quelques boucles vectorisables fabriquées à la main.Le deuxième typeest un sous-ensemble de la suite TSVC [MGG+ 11].0.5.1.1雷苏尔塔我们通过与SSE初始化块执行的vitesse的关系来测量AVX获得的再矢量化加速。Ensuite，nous les comparons au accélérations na- tives obtenues à partir des vitesses d'écutiondes codes AVX et SSE générées unique- ment par deux versions de GCC：GCC-4.7.2 etGCC-4.8.2.在我们重新矢量化的情况下，我们的报告将其与原生AVX编译器进行比较。这些数据在图5中表示。 三分之一滴水，la première ligne（dscal）montre que lecode AVX produit par GCC est supérieur de 1，4 ×à la version SSE. Le code produit parnotre re-vectoriseur原生GCC-4.8.2 AVXRe-vectorizer（4.8.2）原生GCC-4.7.2 AVX Re-vectorizer（4.7.2）相对于SSE的13雷苏尔塔rapidement que la version SSE，soit une amélioration de 19% par rapport à la versionAVX native.使用GCC-4.8.2，我们的re-vectoriseur能够改善boucles的性能，仅为67%。因此，我们将继续超越GCC以获得AVX，在Vecadd案例中仅为66%。AVX ciblage的理由之一是，GCC-4.8.2编写了一个平行环的序言，以确保进入画面。Malheureusement，laboucle ne profete pas de l'embryement et s'appuie sur des accès de memoire nonembryés.在上证所的舞台上，它没有开场白，也没有在16个八重奏的回忆录上休息。事实上，代码 AVX généré par GCC-4.7.2 est plus simple，sans prologue，et similaireà notre propre génération de code ， et les performances correspondantes sontégalement corrélées.在GCC-4.7.2中，我们通过与代码SSE的关系重新评估了整体性能。我们观察到，cela se produit lorsque le même registre（ymm0）est utilisé à plusieurs reprises danslecorpsdelabouclepourmanipulationdif-férentstableaux.Celaaugmenteconsidérablement le nombre塞西在s125的案件中尤为突出。在这些结果中，我们对执行职能的最佳做法是，我们认为有可能根据《原产地法》收回，因为这限制了向法院提出申诉的可能性。 矛盾在GCC-4.8.2中，双转换器的性能是由AVX原生系统提供的。 Cela is prévu car le compilateur a souvent la capacité de forcer l'encourement 这些画面是32个八位元组。 最乐观的人不应该 代码在SSE中编译我们不保证16个八位字节的安全。在这种情况下，AVX转换的名称与访问指令相同 在SSE原始文件中的备忘录（就像块一样），但算术指令的名称是moitié。请注意，我们的朋友在许多情况下使用SSE代码，我们也有能力返回原始代码。0.5.2自动矢量化Les expériences ont été réalisées à此外，这些基准测试使用GCC 4.8.4与选项-O3-fno-tree-vectorize编译，该选项可减少矢量化并维护剩余的优化。0.5.2.1雷苏尔塔Nous evaluons les performances de la vectorisation en mesurant les accélérations desboucles optimisées pour SSE et AVX contre les boucles non vectorisées.结果如图6所示。我们观察到自动矢量化提高了矢量因子的性能。在s1351的例子中，SSE版本超过了1.95 ×的一致性标量。在这个问题上，AVX版本执行速度超过3.70倍。两个萨克斯管我们也一样14简历图6：Les résultats de la vectorisation automatique一个超直线加速：2.10倍加速度。我们将此值与GCC 4.8.4的加速度进行比较，其值为2.04 ×。这一小块代码是根据GCC 4.8.4的通用指令编写的，而编译器JIT LLVM不具有相似性。0.6结论实际上，这种趋势是多个核心和矢量单元在处理过程中的整合的进展。Cela nous aorienté à choisir les transformation liées à la vectorisation. Ces optimisations ont lacapacité d'accélérer l'exécution du programme a finer les fais de la transformationpendant l'exécutionand d'obtenir une performance性能significant显著.这些优化方法包括重新矢量化的块矢量化和自动矢量化的块标量。D'une part ， une table de transduction consient des instructions SSE avec leurscorrespondances en AVX utilisée pour re-vectoriser les boucles tout en guarantissant lalégalité de la transformation.在外面，动态信息不是用来改善性能的。另一方面，在执行时，所有的画面地址都是不确定的，因此，可以使用这些地址来选择所执行的指令，而不是使用不确定的指令。这些实验表明，在AVX原生编译器中，代码的数量很小，而且加速也不一致另一方面，这些标量散点不是自动矢量化的。La methode décompile le binairevers sa représentation intermediaire.由于niveau掩盖了机器的细节，因此我们可以利用 polyédrique 模 型 对 boucles 进 行 优 化 。 最 终 ， elles sont compilées à l'aide ducompilateur LLVM et injectées dans le processus cible.结果显示，在接近目标的过程中取得的进步和进步是非常重要的第1介绍计算市场的扩张与为研究和工业目的开发的复杂应用密切相关;例如，天气预报、地震和分子分析等各个领域的建模和仿真算法，以及克服摩擦的飞机设计等。市场的需求推动计算机体系结构和编译界朝着提高性能和更好地利用计算机资源的方向发展本章由三部分组成。首先，它介绍了CPU设计的趋势，朝着在单芯片上集成多核和向量处理单元的方向发展。其次，它通过发现CPU功能的充分利用失败来定义论文问题陈述。 这个问题主要源于原则CPU行业采用的向后兼容性，这使得程序在较新的CPU中执行的可伸缩性变得不容易;尽管他们之前的编译针对的是同一家族的旧CPU。第三，它提出了一个基于运行时优化的解决方案，减轻向量处理利用率不足。选择面向并行计算机子类的优化的决定是：第一，目前广泛和持续发展的各种处理器供应商的这些类型的架构。第二，投资回报率，确保加速运行程序，以支付二进制运行时微调的费用，并提供关于非优化版本的显着加速。1.1上下文自20世纪70年代以来，设计师们已经用尽了几个领域的研究来提高CPU的性能。例如，指令流水线将指令周期分成多个阶段，使它们同时操作，从而导致更高的吞吐量。此外，由于从有序到无序执行的过渡，指令级并行性（ILP）继续得到改进，这允许以不同的顺序执行指令，同时保留数据依赖性。因此，它通过给予无依赖性的指令更高的执行优先级，而不管它们在函数中的顺序，来1516介绍源源不断的此外，片上高速缓存将第一级（有时是第二级）高速缓存集成到处理器中，弥补了处理器和主存之间不平衡的增长速度之间的差距。不可否认的是，数据缓存允许低延迟访问内存操作数相比，数百个周期的延迟为主要的存储器。此外，在20世纪90年代和21世纪初，CPU设计师关注的是提高处理器时钟速度。以前的CPU设计领域的持续改进面临着死胡同。对ILP改进的热情转向了多核设计。虽然并行计算在2000年代之前已经是一个研究领域，但越来越多的人关注这些类型的架构的工业化，这些架构允许线程级并行（TLP）编程范例，成为将ILP性能推向其边缘的替代方案。这背后有两个主要原因：（1）一项研究成果[HP 02]在寻找最佳管道深度时证实，管道深度的增