2017年论文/雷恩第一大学布列塔尼卢瓦尔大学印章下为的等级雷恩第一大学博士提及：计算机科学马蒂斯博士学院阿里·哈桑·穆萨维在联合研究单位6074 - IRISA编制计算机科学与随机系统研究所UFR电子计算用于浮点-点到定点转换目标- ting嵌入式专业版的论文于2016年12月16日在陪审团由以下人员组成：大卫·德福MFC-佩皮尼昂大学/报告员莱昂内尔·拉卡萨涅PR-皮埃尔和玛丽·居里大学/报告员卡琳·海伊德·伊曼WCF-皮埃尔和玛丽·居里大学/考试丹尼尔·梅纳尔PR-INSA Rennes/检查员友文由纪CR-INRIA布列塔尼大西洋/审查员史蒂文·德尔PR-雷恩大学1/论文主任知识引导、引导、拯救;无知使人迷误、迷惑、毁灭。谢谢你史蒂文总是在那里给我建议和激励，我想无限感谢他为我的论文工作的成功所做的一切我也要感谢他的建议对这项工作产生了重大影响我还要感谢Patrice Quinton对审查/更正本手稿的贡献。我感谢所有评审团成员，他们同意评判我的作品，特别是莱昂内尔·拉卡萨涅和大卫·德福尔，他们担任了报告员的我感谢Inria/Irisa的所有工作人员，特别是CAIRN团队的成员，感谢他们对我的热烈欢迎。 我要特别感谢负责所有行政程序的Nadia Derouault，感谢Nicolas Simon和Antoine Morvan在开发工具方面提供的帮助，以及Gaël Deest、Simon Rokicki、Baptiste Roux和所有其他人。最后但并非最不重要的是，我想感谢我的家人这些年来的支持内容表法文摘要v图XI列表表列表xv词汇表171引言11.1背景和动机21.2ALMA项目41.3时间线61.4贡献和组织82 浮动点到定点转换112.1引言122.2浮点表示122.3定点表示142.4浮点与浮点 定点...................................................................................................................162.5浮点到定点转换方法192.5.1整数单词长度确定192.5.2单词长度优化212.5.3定点代码第22代2.6自动转换工具232.6.1MaTL aB定点转换器232.6.2以色列国防军九号. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...242.7结论273 背景：单指令多数据293.1导言303.2指令集313.2.1传统向量处理器313.2.2多媒体扩展32我ii内容表3.3使用多媒体扩展363.3.1手册简化373.3.2自动简化方法383.4结论424 超级词级并行性454.1导言464.2相关工作474.2.1OriginalSLP48...............................................................................................................4.2.2OriginalSLP扩展和增强.................................................................................................4.3HolisticSLP50...........................................................................................................................4.3.1概述514.3.2短缺594.4Prop osedHolisticSLP算法增强功能64......................................................................................4.4.1流程和冲突图包（PFCG）654.4.2小组选择程序664.4.3算法复杂性724.4.4伪代码744.5实验设置和结果784.5.1执行情况784.5.2目标处理器794.5.3基准测试814.5.4测试设置814.5.5结果824.6结论885 SLP感知的单词长度优化915.1导言925.2动机和相关工作945.3联合WLO和SLP提取965.3.1概述和直觉975.3.2处理器型号985.3.3SLP感知WLO算法1015.3.4准确感知SLP提取算法1065.3.5SLP感知缩放优化1095.4源代码到源代码编译流程1125.4.1流程概述1125.4.2整数单词长度确定1145.4.3准确性评估1155.4.4选择和排序SLP115的基本块5.4.5定点/PID代码生成1155.5实验评价和结果116内容表5.5.1实验设置1165.5.2WLO-then-SLP源到so或rceFLow117...............................................................................5.5.3基准测试1185.5.4目标处理器1195.5.5结果1195.5.6浮点与浮点固定点.................................................................................................1215.5.7WLO+SLP与WLO-then-SLP............................................................................ 1215.6结论1236 结论125A 目标处理器型号129A.1XENTIUM129A.2ST240129A.3 KAHRISMA130A.4 VEX130出版物133参考书目135iv内容表Ff我S法文摘要嵌入式处理器在成本、功耗和性能方面受到严格的限制。 为了限制它们的成本和/或功耗，一些处理器不具有对浮点运算的硬件支持。另一方面，为了简单起见，在诸如信号处理和电信的几个领域中的应用通常使用浮点运算来指定。然后根据目标体系结构调整/优化该原型实现。在没有硬件支持浮点运算的嵌入式处理器上移植此类应用程序需要软件仿真，这可能会严重降低应用程序的性能。为了避免这种情况，浮点和定点这两种表示方式如图所示。1. 从浮点到定点的转换是一个复杂的过程IW1 E MSEM逗号（隐式）LSRExposantMantisLSR整数部分分数部分所示数字：sif * 2-F（-1）s*mantisse*2指数图1性能和计算精度之间的微妙权衡除其他外，它允许以降低计算精度为代价来减小数据大小。这是因为使用定点运算，同时保持结果的完全准确性，需要显著增加数据的字大小例如，两个大小为w的数之间乘法的精确结果字大小的增加可能超过目标处理器支持的最大大小，需要更大运算符的软件仿真，这也可能降低应用程序的性能。 为了避免这种情况，通过应用量化来减小数据（和操作的结果）的大小，这对应于消除低有效位。这些量化操作引入了计算误差，称为Vvi法文摘要压实...压实+解压缩C1C2...cNA1A2aNb1 b2...BN量化误差，其在系统中传播并可能导致输出中的大误差，从而降低结果的精度通常，量化越大（即数据大小越小），精度越低，但性能越好因此，在计算精度和性能之间存在折衷此外，大多数嵌入式处理器提供对单指令多数据（SID）矢量计算的支持，以提高性能。这是因为它允许同时对多个数据执行然而，通常需要转换这种矢量化变换对数据大小很敏感;数据大小越小，矢量化速率就越高。因此，在矢量化和数据大小之间出现了另一种折衷另一方面，矢量化仍然不会导致性能的提高，它甚至会降低性能! 实际上，为了应用向量运算，必须首先聚合或压缩每个操作数的数据以形成向量，该向量通常对应于PID寄存器。类似地，数据必须被解压缩以便单独使用，如图所示2. 这些（去）压缩操作可能导致在记忆中矢量化压实在SIMD注册表中C1C2... cN图2在数据在存储器中组织不良的情况下，这是显著的开销因此，为了有效地提高性能，矢量化变换必须考虑到这种额外浮点到定点转换和矢量化是两个需要非常长的开发时间的棘手变换为了解决这一问题并缩短应用程序的上市时间，大量的工作都集中在A1 B1 A2 B2++...C1C2aNbN+cNA1A2... aN...viiWord长度simm群组SLPWLO（全部或部分）这些转换。在现有技术中这些方法通常包括三个主要部分：— 确定整个零件的尺寸 通过基于模拟或使用诸如区间算术和仿射算术之类的分析方法。— 单词大小的确定 这通常是通过利用精度和性能之间的折衷来优化的，称为"字长优化"或WLO。为了实现这一点，需要能够估计定点实现的计算精度和性能的方法已经提出了几种方法— 定点代码生成[50]。另一方面，也有允许利用PID计算单元的方法，其中包括在基本块级别上提取并行性的技术，称为"超级字级别并行性"或SLP（超级字级别并行性），由Larsen和Amarasinghe在2000年引入。 这些方法的目的是在基本块中找到可以用SID操作替换的操作组。这样的组称为PID组，必须包含相同类型的独立运算（加法、乘法、运算）。... ... ）并处理相同大小的数据SLP提取算法[69，125，78]的目标是找到"最佳"聚类解决方案，该解决方案通过考虑与（去）压缩操作相关的额外成本来提高性能。然而，在现有技术中，这两种变换被独立地考虑，然而它们是高度相关的。实际上，WLO确定直接影响SLP的搜索空间的数据大小，从而确定找到的解决方案的性能。如果WLO因此，它将无法有效地为了更好地利用这种折衷，WLO必须考虑SLP，而SLP在不了解数据大小的情况下无法继续 该相位调度问题如图所示。3.图3viii法文摘要定点规格(IWLs仅）基础块WLSLP-AwareWLO准确性感知SLP萃取组定点规格（完整）simm群组准确性约束处理器模型准确度评价服务SLP-Aware缩放优化在此背景下，首先提出了一种用于SLP提取的改进算法。它基于LIU等人在2012年提出的最先进的算法，对其进行了仔细分析，以确定其弱点，然后提出了改进建议。L’algorithme proposée est ensuite implémenté dansune plateforme de compilation source-à- source, 在一组针对多个嵌入式处理器的九个测试应用中提取的实验结果显示，我们的算法提供了明显的改进。然后，提出了一种新的技术，允许与最先进的方法不同，这种新技术可以更好地利用计算精度和应用性能之间的折衷，目标是具有SID指令集的嵌入式处理器，而不支持浮点运算的硬件该方法包括将意识到计算精度的SLP提取算法与意识到SLP聚类机会性和相关开销的WLO算法相结合为了解决前面提出的阶段排序问题，调整了所提出的SLP提取算法，以释放与数据大小相关的约束。 以这种方式，现在可以开始提取SLP，而不必等待WLO的结果。 这避免了选择在不违反精度约束的情况下不可行的PID组。然后，所选择的PID组被用于"指导"WLO算法的字大小选择该图4说明了这种方法。我们在Genec os中以流的形式实现了这种方法。图4完全自动化的源代码到源代码编译为了证明我们的有效性ix我们将这种方法与传统方法进行比较，传统方法首先独立应用浮点到定点的转换，然后提取SLP，这也是在Gene c o s中实现的我们在几个嵌入式处理器上测试了这两个流 结果证实了我们的方法在利用性能和精度之间的折衷方面的有效性。x法文摘要图列表1浮点表示（右）和定点表示（左）的比较。V2替换N个标量运算的矢量化变换的示例通过单个PID操作加上（解）压缩操作。......................................................................................六3WLO和SLP之间的相位调度问题4所提议方法的说明。................................................................................................................................八1.1CPU在过去40年中的趋势由K. Rupp atwww.karlrupp.net/2015/06/40-微处理器趋势数据........................................................................................................................................... 2年1.2ALMA工具链流程图。.................................................................................................................... 51.3大纲。................................................................................................................................................92.1IEEE 754标准中浮点数的二进制表示。..............................................................................................122.2有符号定点数的二进制表示。................................................................................................................. 142.3IEEE单精度浮点数精度与范围。............................................................................................................172.4范围传播示例。..........................................................................................................................................202.5IDF IX流程图。................................................................................................................... 253.1与标量加法操作相反的单指令多数据（SID）加法操作的插图。..................................................303.2能够执行32位标量加法（当传播为1时）或2x16位SID加法（当传播为0时）的次w阶并行运算符（SWP）的插图。.................................................................................................................343.3一些软SID操作的示例。...............................................................................................................353.4矢量化示例。..................................................................................................................................393.5在不支持未对齐访问且矢量大小为2的多媒体扩展的情况下，来自未对齐步长-1参考（中间）与未对齐步长-1（左）和未对齐步长-2（右）的矢量内存负载的插图。............................... 403.6说明循环矢量化和SuperwordLevel Parallelism（SLP）之间差异的示例。 [min：max]表示从偏移量min到偏移量max（包括偏移量max）开始的对连续数组元素的向量内存访问。a<，b>表示打包/拆包操作。.......................................................................................................42十一xii图列表示例C代码片段（左）及其语句依赖关系图（右）。 ... ...47 4.2.....................................回忆图中的示例4.1. ......................................................................................................................................514.3HolisticSLP算法fl ow图。 .................................................................................................... 五十二4.4V变量包冲突图（VPCG）和统计分组图（SGG）图中的例子4.1. ...............................................................................................................................534.5AG（{S4，S5}）在图的示例的第一次选择迭代处。4.1. ....................................................564.6选择{S4，S5}更新的VPCG（左）和SGG图的示例4.1. ...................................................................................................................................574.7示例说明整体SLP算法。 这表明VPCG和SGG并不代表周期性依赖冲突。 分组解为{c1，c2，c3}由于c1、c2和c3之间的循环依赖性而不合法的4.8示例显示虚假依赖关系如何影响整体SLPVP重用估计。614.9示例说明整体SLP候选人福利估计。.................................................................................. 634.10 SLP提取框架概述。...................................................................................................................... 654.11 图中示例的数据流图（DFG）和Pack流和冲突图（PFCG）。4.1. PFCG中的矩形节点表示分组节点，其中椭圆形节点表示候选节点。非定向边表示候选项之间的冲突，定向边表示V可变包（VP）流。突出显示的节点（橙色）表示重用。..............................................................................................674.12 通过应用十次整体SLP获得的各种基准的连续版本的执行时间改进。......................................694.13 在各种基准测试的连续版本中改进执行时间在应用所提议的SLP提取十次之后。...............................................................................................704.14 回忆一下图的例子4.9. ...................................................................................................................714.15 图中示例的PFCG。 4.14在使用prop-2的第一次迭代中................................................. 714.16 与原始（顺序）代码相比，通过应用我们提出的SLP提取方法获得的PID代码的执行时间改进，对于构建距离-N邻居所考虑的N个不同值P FCG中的候选人（子PFCG）。目标处理器是KAHRISMA。734.17 SLP提取框架在GEcos79中的实施4.18 测试程序图。..............................................................................................................................................824.19 通过prop获得的PID代码的执行时间改进 hslp，overori g. 测试是重新进食10次f或ea chbe nchmark。 条形表示平均值，线段表示最小值和最大值执行时间的改进。......................................................................................................................................844.20 通过prop获得的PID代码的执行时间改进 hslp，overori g. 测试是重新进食10次f或ea chbe nchmark。 条形表示平均值，线段表示最小值和最大值执行时间的改进。......................................................................................................................................854.21 使用87号提案4.22 在KAHRISMA上运行的jacobi2d基准测试中，执行时间改进和简化时间变化，并考虑到批处理大小。..........................................................................................................................................87
我的内容管理
展开
