当前位置 >>

研究成果

2016年度实验室代表性研究工作进展

撰稿：摄影：发布时间：2016年12月29日

1. 超并行高效能计算机体系结构与设计方法研究
（1）高效能计算机体系结构以及设计方法
为把握“人机物”三元融合的发展趋势和机遇，从2012年启动“海云计算系统”研究工作，其目标是针对万物互联所产生的并发度提升10倍、能效提升100倍需求，研究创新的处理器芯片与服务器系统。相比通用处理器，面向智能应用的可重塑处理器能效比提高两个数量级，突破了智能计算芯片体系结构设计的“功耗墙”问题，成为目前智能芯片设计主流架构之一，多次获得国际顶级学术会议最佳论文，开辟了计算机体系架构可编程定制硬件的新方向。通过数据通路软硬件全栈优化处理技术，海云服务器在运行家电物联网服务时，平均单节点支持的并发度相比传统商用服务器提升10倍，实现了服务器整机层次上效能比的大幅提升，高效支撑百亿级海量终端并发服务的快速响应。

对树状结构数据的存储和查询处理进行了深入的研究，研发了一个树状结构数据管理系统Steed (System for tree structured data)。针对简单路径进行了优化，考虑了外存存储、内存数据结构、列组装算法的优化。与现有的类似系统PostgreSQL/JSON, MongoDB, Hive+Parquet相对比，Steed对于数据分析类操作普遍有10—1000倍的性能提升。成果被CCF A类会议SIGMOD 2017录用。对Density Peaks (DP)算法进行并行化的研究，提出并实现了一种基于MapReduce平台的LSH-DDP算法。在EC2云平台上的实验验证了LSH-DDP比基础的并行化方法快1.7-70倍，比前期最佳方案EDDPC提高2倍性能。与K-means聚类相比，LSH-DDP具有相似的性能，从而使DP算法的计算代价问题得到了很好的解决。成果发表在CCF A类期刊IEEE TKDE 2016上。

针对大数据的并行处理系统进行了深入的分析与综述。从数据存储和数据处理两个角度对已有的大量大数据系统进行梳理和分类，对经典的MapReduce和数据库系统进行了对比分析，总结了目前主流的大数据测试集，最后提出了未来的主流研究方向。论文发表在Proceedings of the IEEE上。提出了一种基于空间填充曲线的MPI_Alltoall集合通信算法。该算法具有缓存无关特性。相关工作已被PPoPP’17录用为Poster。面向众核架构提出了一种SpMV解决方案。通过为SpMV定制片段归约或片段Scan算法，来隐藏SpMV的计算时间，从而实现一个高效的SpMV算法。在计算精度方面，同时支持单精度及双精度。相关工作已发表在CCF B类期刊TACO上。

（2）高并行度、低能耗的众核处理器体系结构
本年度，本创新群体项目研究的多个方面都取得了重大突破，包括：机器学习加速器指令集、处理器性能评估和建模、片上网络等方向。我们提出了深度学习处理器指令集Cambricon（参见会议论文“Cambricon: An Instruction Set Architecture for Neural Networks”）被计算机体系结构领域顶级国际会议ISCA2016所接收，其评分排名所有近300篇投稿的第一名。在国际上提出了首个深度学习处理器指令集。Cambricon指令直接面对大规模神经元和突触的处理，一条指令即可完成一组神经元的处理，并对神经元和突触数据在芯片上的传输提供了一系列专门的支持。指令集是计算机软硬件生态体系的核心。Intel和ARM正是通过其指令集控制了PC和嵌入式生态体系。该研究在深度学习处理器指令集上的开创性进展，为我国占据智能产业生态的领导性地位提供了技术支撑。此外，在国际权威杂志Communications of the ACM和IEEE MICRO发表了对深度学习处理器的全面综述，在分布式系统的IEEE TRANS 期刊中发表了关于并行处理器片上网络设计的创新结构。

针对大数据以及机器学习领域的典型算法进行了体系结构加速支持研究，主要研究进展包括：选取了大数据应用中的基本字符操作算法进行分析和热点评估，针对常用字符操作进行了加速方法及结构的设计，提出了一种基于cacheline的面向字符操作的加速方法—TCC（Text Cache Computing），该方法适应于具有地址连续性的基本操作。基于TCC方法我们还设计实现了两种加速部件，一是加速字符串操作的部件—TCSU（Text-Cache-based String Unit）。二是加速字符连续比较的部件TCCU—（Text-Cache-based Char Unit）。相关研究工作发表在第18届IEEE International Conference on High Performance Computing and Communications (HPCC)学术年会上，基于相关研究工作还申请了11项发明专利。

（3）片上并行系统的测试与高可靠设计方法
在集成电路和容错计算方向，本年度共发表论文17篇，其中SCI期刊论文6篇，EI期刊和国际会议论文11篇，申请专利5项。取得的主要创新性成果包括：1）提出了一种面向深度学习的加速器芯片自动综合工具Deepburning，为应用自动生成支持任意参数的卷积神经网络硬件加速器电路，有效缓解了深度学习硬件加速器设计周期长、目标算法更新快带来的设计难题。2016年基于该工具参加IEEE Rebooting组织的DAC低功耗图像识别竞赛（LPIRC）获得全部两项冠军。2）提出了一种模型检验的状态覆盖率评估方法，一方面纠正了以往近似计算方法中的漏算（覆盖率低估），达到准确计算覆盖率，另一方面将以往方法仅能处理ACTL公式扩展到能够处理所有CTL公式，有效提高了状态覆盖率评估的处理能力。3）提出了一种面向近阈值计算处理器的任务映射与电压调制技术，利用在线的程序特性监测对现成的故障容忍能力进行排序，同时结合离线的软件测试方法得到不同处理器核的故障分布，然后通过程序与处理器核心的匹配映射，找到最可靠的线程映射方法，提升可靠性的同时最小化多核处理器运行功耗。4）提出了一种基于核性能等效的处理器性能优化方法CoreRank，通过一些典型的微指令流（snippet）来测试处理器核的“健康”状况，能够有效的隐藏处理器核的性能降级。5）提出了面向物理不可克隆函数(PUF)硬件安全模块的攻、防、检方法，包括基于复合启发式算法的PUF安全性评估方法，证实了若干新型PUF未达预期安全性；基于随机数发生器的外围防护电路设计，能有效提高PUF的安全等级；基于统计分析的PUF故障诊断方法，能精准定位故障。

（4）高性能计算机的并行编程和优化
在性能优化方面：首先，针对数据中心混合负载的场景，我们采用了回归分析的方法来预测多核芯片上的核间性能干扰模型。我们的方法不仅能够获得不超过1%的预测误差，而且能够在体系结构的特征层面解释应用程序在混合运行时所表现出的竞争性和敏感性。该研究成果为数据中心混合负载应用的性能优化解决了一个关键性问题。其次，针对图计算自身特征对性能及优化措施的显著影响，我们将编译优化思想用于图算法优化，提出一种冗余计算消除的介度中心算法，消除公共DAG子图带来的冗余，从而大幅度提高算法效率。实验结果显示，该算法比目前最快的介度中心算法快4.6倍。在软件正确性和安全性保障方面：为权衡缺陷定位的效率与精度，我们提出最小调试边界（简称MDFS）的概念，并以该概念为基础，设计了围绕符号替换的自动缺陷定位方法（简称MDFS方法）。实验表明，该方法相对于经典的基于状态替换以及基于变异的缺陷定位技术,能够更精确、高效地定位Linux应用程序（如：Grep）中的真实缺陷。在软件安全方面，我们提出了代码持续随机化技术，即通过持续地变换代码布局，阻止攻击者获取目标程序的有效代码。实验表明该系统不仅开销非常低（低于9%）而且还能够有效阻止Nginx内存泄露攻击。

2. 数据并行与线程并行合一的可伸缩处理器体系结构
本年度，旨在发展一种新型的微处理器体系结构，用同一套控制和运算部件来同时支持线程并行和数据并行，使其具有结构简单灵活、片上资源利用率高、性能价格比高、性能功耗比高等特点。我们通过研发基于数据流的多模式计算支持了数据并行性和线程并行合一的软硬件协同计算模式。主要工作内容体现在以下三点。

（1）多线程并行和数据并行上下文动态切换机制
本研究实现了一种数据流图的流水执行模式，将科学计算中的一次循环所执行的操作转换为一个数据流数据流图，并映射到执行阵列上。其中，在程序运行过程中，在本结构中首先运行的是多线程的执行状态。为了增加硬件资源的利用率，本结构中的单个PE（处理单元）可以映射多个线程执行。在数据流图流水执行模式中，每一个线程上下文的开始不需要等待上一个线程上下文的结束，多个上下文以流水的方式进入执行阵列，数据流图中的每一条指令在执行一次后会立刻接收到下一个上下文的操作数，使执行单元的利用率得到极大的提高。

图1 上下文切换模式示意图

（2）高通量低延迟的数据通路结构设计
在本研究处理器中，多个PE通常通过二维网络互连，所有PE同时执行同一个数据流图。本项目所研究处理器结构中的路由有如下特征：1.多目的地；2.高注入率；3.性能对传输延迟敏感。基于上述三个特征，本研究提出了一种面向本结构的高效片上网络路由。该路由支持多个目的地，从而实现一次传输多个带有同样数据的消息。同时，该路由采用输出缓冲来最大化网络的吞吐率，并且采用非分片（Non-Flit）方式最小化传输延迟。从输入端口进入的消息包被分发到输出队列中，对于每一个输入端口，有P-1个输出队列与其对应，P为输出端口数量，P-1表示不包含该输入端口方向。

（3）软件指令映射算法优化技术
本研究提出了面向流水执行数据流结构的LBC（Load Balance Centric）指令映射算法。LBC算法首先按照深度对所有指令进行排序，按照深度顺序依次映射每条指令（第一层FOR循环）。对于每条待映射指令，考虑执行单元阵列上的所有PE（第二层FOR循环），分别计算待映射指令映射到此PE上的映射代价。计算映射代价时，跳过无法放置更多指令的PE。最后，从所有PE中选出映射代价最小的PE作为最佳映射位置。LBC以执行单元负载为核心，同时考虑定点浮点和网络拥堵的影响因素，将所有指令按照一定规则映射到执行单元阵列上，提高了执行单元和网络的有效利用率，从而提高了流水执行模式的数据流结构的性能。

3. 集成电路安全隐患检测的理论与方法
在集成电路安全隐患检测的理论与方法研究中，分别从安全硬件模块、硬件木马检测、软硬件协同的安全性三个角度开展了探索与研究，取得了以下创新性研究成果：

（1）物理不可克隆函数的攻、防、检方法
物理不可克隆函数是一种新型安全模块，因其在制造前难以预测、制造中难以控制、制造后难以克隆的优势，在集成电路安全领域有着广阔的应用前景。为了实现安全无故障的物理不可克隆函数，在攻、防、检三个方面都提出了相应的关键技术。首先，针对物理不可克隆函数的攻击方法研究，对于揭示其安全程度、决策应用场景、改进电路设计具有重要意义。针对新型的基于非线性电气特性的物理不可克隆函数，提出了基于遗传算法、模拟退火算法与蚁群算法的复合启发式攻击算法，与国际上同类方法相比，将预测精度提高了约20%，揭示了两种新型物理不可克隆函数未达到预期的安全性。其次，为了防御先进的攻击方法、拓展物理不可克隆函数的应用场景，防护设计同样十分重要。针对物理不可克隆函数的激励响应对相关性高的核心难题，提出了基于复合物理不可克隆函数和真随机数发生器的外围防护电路，与国际上同类方法相比，将安全性提高了约25%。最后，在生产制造过程中，故障可能发生在物理不可克隆函数中，因此通过故障检测、发现失效物理不可克隆函数后通过诊断找到引起故障的主要原因从而指导加速量产学习具有重要意义。针对现有技术停留在发现故障而无法定位故障的现状，提出了面向物理不可克隆函数的诊断激励生成与故障诊断方法，实现了100%的诊断精度。

（2）基于统计学习算法的通用硬件木马检测框架
针对硅后硬件木马检测通常需要黄金模型、且易受工艺偏差影响的问题，提出了一种基于统计学习算法的通用硬件木马检测框架。首先，提出稀疏门级分析技术，将基于侧信道分析的硬件木马检测问题转换为求解欠定线性方程组问题。其次，在设计中嵌入工艺偏差测试电路，利用先验分布和少量实测，通过贝叶斯推理最大后验估计获得整个芯片的工艺偏差分布。最后，利用正交匹配追踪算法求得欠定方程组的唯一稀疏解，根据解的非零分量幅度判断是否存在硬件木马。实验结果表明，与国际上同类方法相比，该方法具有更高的效率和精度，在平均每逻辑门测量次数远小于1次的情况下，几乎到达100%的正确检测率。

（3）基于能耗侧信道的代码追踪方法
软件代码追踪是攻击嵌入式系统的关键技术手段，提出了一种基于能耗侧信道的代码追踪方法，从硬件入手，实现了一种非侵入式的攻击方法，也暴露了嵌入式系统的软硬件安全隐患。提出隐式马尔科夫模型来表征代码执行情况和其对应的侧信道的关系，并用它来恢复最有可能的指令执行序列。实验结果表明，所提方法能够高效、精确的识别出代码的执行流程，并且能够有效检测到代码异常执行的情况。

4.差错容忍计算器件基础理论与方法
本项目旨在结合集成电路以及计算技术的发展和应用需求，针对CPU/GPU/多核处理器、神经网络加速器/视频编解码器、片上存储器/新型存储器等计算相关器件，开展差错容忍计算器件的基础理论与方法研究，在满足应用质量要求前提下、通过合理降低计算的精确性而换取芯片乃至计算机在能耗、性能、吞吐率、面积、存储密度、可靠性、成品率等方面的益处，显著降低设计成本，形成应用与系统、软件与硬件、高层与低层相结合的计算方法学，为集成电路及相关应用领域考虑差错容忍的计算提供创新方法和关键技术。

本项目2016年发表SCI期刊论文10篇（含IEEE/ACM Trans.论文7篇），发表EI论文25篇（含DAC 3篇，ITC、DATE、ICCAD、ICCD各1篇）。2016 年度取得的重要技术突破如下：
在性能/精度可控的设计自动化方面，针对深度神经网络加速芯片在图像识别、大数据分析等差错容忍计算应用领域的广泛应用，提出了一种深度学习加速器自动生成工具DeepBurning（如图1 所示）。包含两项关键技术：1）基于模板设计的深度学习模型自动解析技术，将神经网络软件模型映射到神经网络处理器硬件的结构化描述，同时根据硬件开销、计算精度需求确定好硬件各项参数，从预先搭建好的神经网络运算部件单元库中查找所需要的硬件部件。2）自动指令生成技术，使用软件编译器协同生成调度控制信号流，以指令的形式预先存放到文件中，该指令控制流将在加速器的工作过程当中，负责将目标网络模型，按照神经网络不同层之间的先后关系，分时映射到目标硬件当中；同时还要生成地址存取信号来同步层内运算划分之间的数据流走向，使整个神经网络层划分并行化且无缝的衔接起来。这两项技术大大降低面向深度学习加速硬件设计与定制的开发门槛，减少软件开发与硬件设计工作的协同开销，使得算法与应用开发人员可以直接参与深度学习加速处理器硬件设计。

图1 性能/精度可控的深度学习加速器自动生成工具DeepBurning

在精度损失可控的电路设计方面，针对处理器芯片的片上缓存，提出了一种面向深度学习与神经网络的精度损失可调的有损压缩电路。技术特点如下：1）根据计算精度需求，对深度神经网络前向传播中用到的权重参数进行自适应压缩，从而实现访存速度与计算精度的自动调节，提升计算效率。2）根据计算精度需求，选择不同编码的定点数据表示方法，结合离线Kmeans聚类算法，采用少量词条对静态权重数据进行编码，进一步提升压缩比例，从而大幅度提升芯片的访存效率与计算能效。

在多核处理器差错容忍设计方面：1）针对新型低功耗处理器的提出了一种近阈值电压片上存储器数据恢复技术，无需使用故障纠错码，利用处理器存储层次内的天然数据冗余，结合低开销的故障校验码，为近阈值电压条件下工作的低功耗片上SRAM提供针对多位差错的检错与纠错能力；2）针对高性能多核处理器中出现的粗粒度计算与存储器节点级失效现象，提出了一种基于多核节点利用率的地址重映射技术，该技术利用多核处理器片上网络的请求转发能力，有效屏蔽多核节点级硬件失效对上层应用的影响，同时最小化失效引起的性能开销，使得多核处理器即便在不稳定的工作状况下也能保持较高的工作性能。

5.面向气候和湍流模拟的百万量级异构众核可扩展并行算法与优化方法
基金重点项目“面向气候和湍流模拟的百万量级异构众核可扩展并行算法与优化方法”2016年根据课题年度计划安排,在大规模异构众核并行的建模理论与可扩展性方法、重点应用领域共性算法的可扩展并行算法设计和异构众核并行编程框架研究方面, 取得了一系列研究进展,相关成果在CCF A类论文3篇，CCF B类论文发表2篇，CCF C类论文发表2篇，SCI期刊发表4篇。

1.在几个重点应用领域的可扩展并行算法设计研究方面，研究了几种底层基本算法构件的优化方法，为上层大规模程序的优化奠定了基础。
1.1提出了一种基于空间填充曲线的MPI_Alltoall集合通信算法。当前超级计算机硬件的发展趋势是节点内具有大规模并行度，具有深度存储层次（包括L1/L2/L3以及DRAM），具有不同的内存布局，如UMA及NUMA。节点内通信本质上是cache line的传递。传统集合通信算法主要是为了降低网络延迟及带宽开销，如何在众核架构上最优化通信性能？我们的解决方案是通过内嵌Morton Order空间填充曲线，来指导数据拷贝顺序，提升数据局部性，cache缺失率从P2B/L + P2降为P2B/L。进一步将砑涮畛淝咂骄郑扛鼋谈涸鹌渲幸欢巍８盟惴ň哂谢捍嫖薰靥匦浴Ｎ颐窃贗ntel Xeon Phi众核架构上进行了性能测试，当消息长度小于16KB时，缓存无关算法相对于共享堆空间的简单实现性能提升40%左右，长消息上性能持平；在全部消息长度上，相对于最新MPICH3库性能提升200%-300%。相关工作已被PPoPP’17录用为Poster。

1.2面向众核架构提出了一种SpMV解决方案。稀疏矩阵向量乘的最大挑战在于SpMV的计算密度低以及稀疏矩阵的非规则性。由于稀疏矩阵的不规则，导致了访存不规则，负载不均衡等问题。针对计算密度低的问题，我们主要可以采用设计新的格式，来减少访存带宽消耗。针对访存不规则问题，首先按块索引，块内填充零元素，可以在一定程度上减少矩阵的非规则性。我们也可以通过设计有利于充分利用硬件cache稀疏矩阵存储格式来提高非规则内存访问的性能。针对负载不均衡的问题，目前主要是两种方法，第一种方法是通过填充零元素，使用冗余计算来均衡负载。第二种方法是使用负载均衡的算法，如片段归约，片段Scan等算法。由于SpMV本身计算密度非常低，我们可以通过为SpMV定制片段归约或片段Scan算法，来隐藏SpMV的计算时间，从而实现一个高效的SpMV算法。进一步的，我们对BCCOO格式进行扩展，支持多种众核架构：同时支持NVIDIA/AMD GPUs 以及Intel Xeon Phi两种众核架构。通过启发式算法对自动调优搜索空间进行剪枝，显著降低了自动调优开销。在计算精度方面，同时支持单精度及双精度。相关工作已发表在CCF B类期刊TACO上。

1.3基于AVX指令集提出了一种优化的GEMV向量化算法。为了充分利用AVX向量化指令，首先对算法进行访存优化，包括数据对齐已经数据预取等优化方法，其次进行SIMD优化，包括利用vhaddpd以及广播指令等，最后进行并行优化。与之前的SSE比较性能有较大提升，相比Intel MKL, GotoBLAS, ATLAS，我们实现的GEMV算法能提升5%到10%。相关工作发表在International Journal of Database and Theory and Application 2016上。

2.在两个重点应用领域的可扩展并行算法设计研究方面，进一步在国产平台上对选取的两类应用进行大规模测试，深入分析了大规模应用的特征和瓶颈，为后续优化设计工作奠定了基础。
2.1在全球气候模拟应用方面。首先，在上年度工作的基础上，在天河1上继续开展0.5°×0.5°分辨率的IAP AGCM4.1的AMIP积分试验，共完成了8年（1991-1998）的积分试验。

2.2大规模3维FFT及直接法湍流模拟应用方面，通过对Parray编程接口的数组类型进行扩充，引入国产处理器的线程类型；以及对Parray编程接口生成代码进行扩充，直接生成国产处理器的Parallel C语言代码，实现了高层并行编程接口Parray在国产处理器集群的初步移植和典型物理过程应用的初步实现。采用数组类型描述众核集群上的数据存储、进程/线程分布，把通讯、访存操作描述为数组类型间的拷贝或变换。在神威太湖之光系统上实现了最大规模为16384的直接数值法湍流模拟并测试了相关的性能。主要的测试性能数据如下,16384规模时能达到40.2Tflop/s。

2.3在大规模应用的支持方面，扩展了MPI通信敏感的调度策略并增加了对非阻塞通信的支持。从大气环球模式IAP AGCM4.1应用中提取了动力框架部分的热点tend_lin，并在多核平台进行了初步验证。在纯计算性能方面AceMesh是OpenMP的1.94X（16线程最快配置下），L3失效率平均降为OpenMP的1/7；在包含构图时间的情况下，AceMesh执行时间比OpenMP快22%。下一步我们将完整评估该应用的MPI多进程版本，并向大规模众核平台进行移植。

附件下载：