《编译原理 教学课件 ppt 作者 王生原 董渊 杨萍 张素琴 2010-compiler-review》由会员分享，可在线阅读，更多相关《编译原理 教学课件 ppt 作者 王生原 董渊 杨萍 张素琴 2010-compiler-review（21页珍藏版）》请在金锄头文库上搜索。
1、董渊 等: 编译技术年度进展报告 1 编译技术年度进展报告 * 董渊 1+, 冯晓兵 2, 王生原 1, 陈文光 1 1(清华大学 计算机科学与技术系,北京 100084) 2(中国科学院计算技术研究所, 北京 100190) 摘要:编译技术是信息产业链中沟通处理器和应用程序之间最为关键的环节，对于整个产业的可持续发展具 有重要的战略意义。 任何高级语言程序都需要经过编译处理才能够运行， 而任何处理器性能的充分发挥都必须依 赖编译优化技术的支持， 因此处理器和编译器的发展相辅相成。 在未来十年整个计算机领域面临的两个巨大挑战： 多核/众核处理器编程和复杂软件系统安全性/可靠性中，编译技术研究都
2、将会起到至关重要的作用，因此具有五 十多年发展历史的编译方向依然是国际上极为活跃的重要研究领域。 同时， 编译技术也当前国家战略规划中急需 发展的方向高性能通用处理器和基础软件的关键支撑， 近年来我国在编译领域取得了长足进步， 本文从学术 研究、产业发展、软件平台和教育等几个方面给出这个领域的情况报告，并给出未来发展展望和建议。 编译技术和程序设计语言是信息时代软件系统的核心基石。截止 2010年，在有“计算机界诺贝尔奖”之称 的“图灵奖”43年历史中，约 1/3的获奖都在“编译技术和程序设计语言”这个领域，占据绝对领先地位1。本 领域顶极会议PLDI（ACM Programming Lang
3、uage Design and Implementation）2，在根据引用数量得到的 CiteSeer全部计算机学科会议和期刊影响力排行榜中高居第三3。 编译技术也是高性能通用处理器和基础软件等我国当前国家战略规划急需发展方向的关键支撑， 在“核心 电子器件、高端通用芯片及基础软件产品”等国家科技重大专项中均有部署。 近年来我国在编译领域取得了长 足进步， 2009年国内学者先后组织召开了“多核环境下的编译技术研讨会”和“编译课程教学研讨会”4等会议， 交流编译技术研究进展和教育问题，探讨进一步的发展方向，本文在这几次讨论的基础上整理成文，从学术 研究、产业发展、软件平台和教育等几个方面给出
4、这个领域近年来的进展情况报告，并初步探讨未来的发展 方向和建议采取的措施。 1 1编译技术面临的问题 计算机软件逐步渗透到日常生产和生活中的各个环节，高端服务器系统和移动嵌入设备构成云计算时代 的计算主体，高端服务器普遍采用多核、众核体系结构，同时应用程序日益复杂化、多样化。如何开发、验 证软件，保证程序正确、高效地执行，成为大家普遍关注和深入研究的热点。 编译技术面临着来自于三个方面的问题：如何高效开发应用程序？高效而准确地采用计算机语言来描述 现实世界的问题是软件开发人员对语言设计人员和编译器开发人员提出的要求，针对特定应用领域的编程模 型是解决这类问题的有效手段；如何提高程序运行效能？在
5、编译过程中采用各种优化方法，全面提升软件性 能几乎是编译器诞生以来一直不变的主题，而随着电池供电移动设备的普及，针对代码体积和功耗的优化也 逐步成为大家日益关注的问题，因此研究人员正在面临着综合考虑多目标优化以提高计算效能的难题；如何 保证程序值得信赖？应用程序的规模和复杂性不断增加，与此同时运行环境的复杂性也日益增加，多核系统 中程序并发执行带来一系列新的问题，如何解决这些问题成为大家关注的又一个问题，而检测工具和形式化 * 本文工作得到国家自然科学基金（项目号 90818019） ，国家高技术研究发展计划(863)（项目号 2008AA01Z102）和国家核 高基重大专项（项目号 2009
6、ZX01036-002）的资助。 董渊 等: 编译技术年度进展报告 2 验证成为解决这个问题的重要手段。 2 2编译技术前沿研究进展 2 2. .1 1面向多核架构的编程模型 随着工业水平的不断提高，多核处理器日益普遍。尤其是异构多核，由于它能够在特定领域中针对应用 的特点充分发挥不同处理器核的作用，成为当今处理器的主流架构。异构体系结构已成为未来大规模计算硬 件的基础，可能包含多核、 众核、 专用加速设备， 多层次的内部互连和结构并行，使得传统MPI5、 OpenMP 6、 OpenTM7、 UPC8等单一的消息或者共享的编程模型难以清晰描述各个计算部件的协同关系， 而CUDA 9、Open
7、CL10等编程模型又存在编程要求高、产能低、调试难、兼容性差等不足。结合应用和硬件架构的 新变化，以上述模型为基础开展众核并行编程模型及语言的研究是最近几年编译技术的一个重要方向。 2.1.1基于 MPI的并行编程模型 MPI并行编程模型方面， 针对多核平台呈现出多资源的共享竞争和明显的 NUMA特征，中科院计算所研 究人员完成了三个相关的工作。一是对MPI程序采用两阶段的度量和调度。度量代码插桩以获得带宽需求爆 发的代码段、调度代码插桩进行互斥的并行调度。度量开销低（10%以内） ，但是调度的收益不明显，说明调 度的粒度过大。二是实现了基于通信切片的MPI优化进程映射工具11。利用切片程序抽
8、象方法，大大降低 了通信模式收集的时间。针对MPI 应用中普遍使用的迭代算法，该课题组提出激进切片的方法，来保证较高 的裁剪度，实验表明激进切片能保持很高的通信拓扑相似度。三是在MPI 程序的检错方面，运行时方法是比 较实用的技术，但是对于死锁检测普遍存在集中式检测的扩展性问题。提出通信模式循环不变的概念，以及 与检测第一迭代相等价的充要条件，并给出了相关的编译分析和运行时验证技术，该技术在一个运行时检测 工具和模型检测工具上得到实现，得到几十倍的性能提升12。 2.1.2基于 OpenMP/OpenTM的并行编程模型。 面向 OpenMP和 OpenTM 应用的并行数据重用模型。数据重用模型
9、是局部性优化技术的基础，为缓解存 储墙问题起到了重要作用。经典的数据重用模型只面向串行程序，随着多核处理器技术的不断发展，并行程 序中的局部性优化技术变得越来越重要。吴俊杰等人将经典的数据重用模型扩充到并行领域，分别提出了面 向 OpenMP 和OpenTM应用的并行数据重用模型13-18。针对重用在线程、事务中的关系，系统地讨论了 并行应用中重用的分类、判定和求解方法。应用这一模型研究了 OpenTM 循环的优化技术，降低了事务回退 的风险。并行数据重用模型给出了并行程序中重用性的定量分析方法，对面向共享存储结构的并行程序分析 和编译优化技术的研究具有重要的指导意义。 尉红梅等人根据众核结构
10、特点和应用需求重点研究了加速编程模型，加速编程模型以加速编译指示为核 心， 该编译指示以OpenMP为基础， 增加了发挥众核特性的扩展19，用户在应用中插入合适的加速编译指示 以标识核心代码，由高层编译生成适合众核架构的高效代码。 随着并行应用复杂度和规模的扩大，非规则核外应用和数据重分解已经成为程序员生产率和应用性能提 高的主要瓶颈。充分利用 OpenMP易于编程、支持增量并行的特点，扩充其并行计算模型支持非规则核外和 数据重分解，并在分布式存储系统上进行并行编译通信优化研究具有重要意义。鉴于此，胡长军等人扩充 OpenMP 编程模型、执行模型和存储模型支持分布式存储系统上的数据重分解和非规
11、则核外应用2021。在 编程模型方面，扩充OpenMP规范定义了处理单元组、模板数组、数组重对齐与数组重分布、核外数组等指 导语句来描述数据重分解和非规则核外问题。 在执行模型方面，采用扩展的Fork-Join 模型支持分布式存储和 核外应用。在存储模型方面，提出“部分数组共享”存储模型的通信优化技术。在“部分数组共享”存储模型基 础上提出的共享数组识别算法，具有算法输入集小和识别信息更全面的特点。首次提出了基于该模型的一系 列针对底层MPI代码生成的优化，如将零散的MPI_Send/Receive 操作用MPI组通信进行替代，开发了非阻 塞的组通信来保障通信/计算重叠，利用周期性来为多维数组
12、打包/解包等。 该研究小组提出面向非规则核外应 用的通信与 I/O隐藏技术22。首次通过给出 INSPECTOR/EXECUTOR模型各个组件的相关性分析，将 INSPECTOR阶段进行分解并提出相应的流水化转换策略。该策略与传统的 INSPECTOR/EXECUTOR模型相 董渊 等: 编译技术年度进展报告 3 比， 不仅能够更有效地重叠通信、 I/O和计算， 而且没有增加任何附加的存储空间。 还提出面向非线性引用的 通信生成技术23，将整数格与代数方法相结合提出了编译时通信集和相应SPMD代码的生成策略。提出面 向数据重分解的通信调度优化24， 采用通信表和通信调度表来描述数据重分解的实际
13、通信状况。 首次将周期 性理论引入到数据重分解相关的通信调度优化，并给出相应的通信调度生成算法。该算法不仅减少了通信调 度的生成时间以便应用到编译时，而且还有效地避免了通信冲突和减少了实际通信时间。 大规模科学计算中非规则、 非结构化并行的日益普遍， OpenMP3.025的task结构的出现为有效地解决该 类问题提供了可能。 如何利用现有的OpenMP3.0编程模型降低Cell处理器26这一典型异构多核的编程难度， 提高非规则、非结构化并行应用的效率，成为学术界和工业界急需解决的一个问题。胡长军等人实现了一套 异构多核Cell处理器上支持OpenMP3.0 的运行时系统。考虑到异构多核本身的
14、优势，利用现有 OpenMP3.0 编程模型降低异构多核处理器的编程难度，提高编程效率。为了对非规则应用进行优化，构建了一个面向异 构多核 Cell处理器的软件cache模型， 还实现了一个面向非规则应用的软件cache的预取方案。 建立一套异构 多核Cell处理器上面向 OpenMP3.0的task的任务调度策略， 提出了一套集成了广度优先和工作优先的调度策 略，既减少了PPE与 SPE之间的通信，又进一步实现了负载均衡。 2.1.3基于 UPC的并行编程模型。 Berkeley 的UPC（Unified Parallel C）是一种全局地址空间语言，是当前国际上并行语言研究热点之一。 中科
15、院计算所的科研人员基于 UPC 源代码开发了面向国产曙光系列并行机的UPC编译系统，并进行层次并 行特征扩展，CUDA集群、Godson-T平台和曙光的实验结果均有良好表现。自 2006年起，该课题组开展了 分割的全局地址语言和相关编译技术的研究。其目标是针对基于多核处理器芯片的高性能计算机上，片内、 节点内和节点间的三级并行体系结构， 研究能统一多层次并行的并行程序设计模型。2007年到2008 年， 基于 Berkeley的 UPC 开源编译器，课题组为曙光 5000研制了 UPC 编译系统，提供了细粒度访存的多方面支持。 一是利用曙光机器节点内的硬件全局地址空间（GAS） ，将UPC程序
16、中的远程细粒度通信转换为远程 load /store指令， 显著地降低通信延迟； 第二， 针对远程 load/store指令流水的深度受限的问题， 实现了软件caching 的优化。实验表明，对于细粒度通信模式的应用程序，远程load/store指令支持和软件caching 优化能带来平 均 10%的性能加速。第三，针对细粒度的不规则应用，研究了结合了指针本地化、探测、通信计算重叠的运 行时通信调度方法，很好地隐藏了远程访问的延迟。 第四， 选择有代表性的带宽受限的应用 NPB-FT，实现了 细粒度通信重叠的优化，得到 48.75和 8034的性能加速。与MPI的对比表明，PGAS 中高效的单边通 信能更好地支持细粒度通信重叠27。 针对众核处理器上普遍存在的分布存储体、以及片上存储受限的情况，该课题组在 2009 年对 UPC 语言 扩展了层次并行的特征，目前该特征已经在 CUDA集群和 Godson-T（中科院计算所设计的 64 核处理器）两 个实验平台上得到了实现2829
