计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2019年第04期杂志 文档列表

计算机研究与发展杂志体系结构

基于动态权衡的新型非易失存储器件体系结构研究综述677-691

摘要：作为现有存储器的潜在替代技术,新型非易失存储器受到了来自学术界和工业界越来越多的关注.目前,制约新型非易失存储器广泛应用的主要问题包括写延迟长、写操作动态功耗高、写寿命有限等.针对这些问题,传统的解决方法是利用计算机体系结构的方法,通过增加层或者调度的方式加以避免或隐藏.但是,这类解决方案往往存在软硬件开销大、无法同时针对不同问题进行优化等问题.近年来,随着对新型非易失存储材料研究的深入,一系列器件自身所包含的动态权衡特性被陆续发现,这也为体系结构研究提供了新的机遇.基于这些器件自身的动态权衡特性,研究人员提出了一系列新的动态非易失存储器优化方案.与传统的优化方案相比,这类新型方案具有额外硬件开销小、可同时针对多个目标进行优化等优点.首先对非易失存储器存在的问题及传统的优化方案进行了概括;然后对非易失存储器件中3个重要的动态权衡关系进行了介绍;在此基础上,对近年来出现的一系列基于非易失存储器动态权衡特性的体系结构优化方案进行梳理;最后,对此类研究的特点进行了总结,并对未来的发展方向进行了展望.

类Paxos共识算法研究进展692-707

摘要：随着互联网数据量和业务量的快速增长,集群规模越来越大,由于机器和网络等故障使得业务中断的可能性越来越高.如何实现一个容错的分布式系统十分重要.多机达成共识是分布式容错系统中一个最基础,最核心的问题.Paxos等一系列共识算法的出现有效地解决了这个问题.近年来,越来越多的系统使用共识相关技术,关于分布式共识算法的研究也层出不穷.这些共识算法可以被划分成2个大类:强领导者共识算法和弱领导者共识算法.随着远程直接内存访问(remote direct memory access,RDMA)等网络技术和现场可编程门阵列(field-programmable gate array,FPGA)等硬件技术的发展,又出现了一些结合新型网络和硬件技术的共识算法研究,用来提升分布式系统的性能.将从分布式共识算法发展历程的角度,介绍Paxos系列算法,阐述算法演进过程中的关键研究,讨论相关算法在不同场景下的优劣势,并展望该类算法的未来发展方向与前景.

二进制翻译中动静结合的寄存器分配优化方法708-718

摘要：针对二进制翻译器QEMU(quick emulator)在寄存器映射时未考虑基本块之间以及循环体之间对寄存器需求的差异,造成不必要的寄存器溢出而导致的冗余访存开销问题,引入全局寄存器静态映射和局部寄存器动态分配思想,提出高效的基于优先级的动静结合寄存器映射优化算法.该算法首先基于源平台不同寄存器使用的统计特征和各变量的生命周期,静态进行全局寄存器映射;然后依据中间表示与源平台寄存器之间的映射关系,获取基本块中间指令需求寄存器次数并排序确定寄存器分配的优先级;之后依据优先级顺序动态进行寄存器分配,从而减少寄存器溢出次数,降低生成的本地代码的膨胀率以及访存次数,提高目标程序性能.对NBENCH、典型的递归程序和SPEC2006的测试表明:该算法有效地减少了本地代码的访存次数,提高了程序性能,平均比优化前性能分别提升了8.67%,8.25%,8.10%.

一种基于自更新的简单高效Cache一致性协议719-729

摘要：随着片上多处理器系统核数的增加,当前一致性协议上存在的许多问题使共享存储系统复杂而低效.目前一些一致性协议极其复杂,例如MESI(modified exclusive shared or invalid)协议,存在众多的中间状态和竞争.并且这些协议还会导致额外失效通信,以及大量记录共享信息的目录存储开销(目录协议)或广播消息的网络开销(监听协议).对数据无竞争的程序实现了一种简单高效一致性协议VISU(valid/invalid states based on self-updating),这种协议基于自更新操作(self-updating)、只包含2个稳定状态(valid/invalid).所设计的两状态VISU协议消除了目录和间接事务.首先基于并行编程的数据无竞争(dataracefree,DRF)模型,采用在同步点进行自更新共享数据来保证正确性.其次利用动态识别私有和共享数据的技术,提出了对私有数据进行写回、对共享数据进行写直达的方案.对于私有数据,简单的写回策略能够简化不必要的片上通信.在L1cache中,对于共享数据的写直达方式能确保LLC(last level cache)中数据最新从而消除了几乎所有的一致性状态.实现的VISU协议开销低、不需要目录、没有间接传输和众多的一致性状态,且更加容易验证,同时获得了与MESI目录协议几乎相当甚至更优的性能.

基于QEMU的动态二进制插桩技术730-741

摘要：软件插桩是程序优化、软件调试、软件测试、故障定位等软件动态分析的基础技术.而其中,动态二进制插桩技术,因其无侵入性,即既不需要对源代码进行修改编译,又不需要重新组装二进制程序,不会引起目标码膨胀,而广泛应用于软件动态分析,特别是在资源受限、功耗低、实时性高的嵌入式软件领域,动态二进制插桩技术十分关键.然而,现有的二进制插桩工具仅能应用于用户态软件分析,在嵌入式全系统软件领域,还没有相应的二进制插桩工具.针对上述问题,在基于动态二进制翻译的开源指令集仿真器QEMU(quick emulator)基础上,研究突破基本块运行时间统计收集,并消除中断对嵌入式系统软件控制流分析的不良影响,实现了在中间码上对嵌入式全系统软件的动态二进制插桩,完成嵌入式全系统软件运行控制流跟踪,并开发日志处理工具.实验表明,该方法能完成目标码的调用图、函数剖面、覆盖率、控制流等分析,可以解决了嵌入式全系统软件动态二进制分析问题.

一种高效解决间接转移的反馈式静态二进制翻译方法742-754

摘要：为了在追求程序执行效率的同时解决静态二进制翻译中的间接转移问题,针对现有间接转移问题处理方法中线性遍历翻译方式代码优化较少、冗余代码较多的缺陷,提出了基于基本块翻译的反馈式静态二进制翻译方法,并结合二级地址映射表实现了间接转移目标地址的快速映射.首先,在目标可执行程序运行过程中添加监控反馈机制解决代码发现问题,对未确定的间接转移地址进行反馈,以便对源程序重新划分基本块并重新翻译执行;然后构造二级地址映射表,借助二级地址映射快速解决代码定位问题.在开源二进制翻译平台QEMU(quick emulator)上实现了反馈式静态二进制翻译框架FD-SQEMU(feedback static QEMU),并基于SPEC2006和NBENCH测试集进行测试,与QEMU相比,FD-SQEMU平均加速比分别达到3.97倍和6.94倍;与课题组之前提出的保存源程序指令全地址的静态SQEMU翻译器相比,FD-SQEMU的平均加速比达到1.18倍,最高加速比达到了1.36倍,验证了提出的框架和方法的有效性.

基于工作负载感知的固态硬盘阵列系统的架构设计与研究755-766

摘要：在RAID-0阵列中设计了一种基于冷热数据分离存储的固态硬盘阵列系统架构HA-RAID,并结合滑动窗口技术进行优化.其主要思想是,利用固定长度的滑动窗口将阵列系统中的盘划分为普通盘和热点盘,热点盘专门存放热数据,普通盘存放普通数据,且阵列中各盘的角色随着滑动窗口的移动而不断变化.在8块商用固态硬盘组成的RAID-0阵列系统上对HA-RAID予以实验分析.实验结果表明,相比于未引入冷热数据分离机制的原始RAID-0做法,HA-RAID可以将热数据相对均匀地存储到各个盘上,很好地实现了阵列系统级的负载和磨损均衡,从而将阵列中热点盘出现的比例降低到几乎为0.在真实的企业级工作负载下,相比原始RAID-0,HA-RAID减少12.01%~41.06%的平均响应时间,很好地实现了阵列系统级的I/O性能提升.

纠删码存储系统中基于网络计算的高效故障重建方法767-778

摘要：目前分布式存储系统的规模越来越大,不论存储设备是磁盘还是固态盘,系统都始终面临着数据丢失的风险.传统分布式存储系统大多采用基于三副本的高可靠性技术,但为了追求较低的存储开销,大量系统正在转向基于纠删码的可靠性方法.但是在纠删码方案下,重建故障数据需要读取多个存储设备,这将导致大量的网络传输和存储I/O操作,增大系统恢复开销.为了能够在不损失其他性能的同时降低恢复开销,利用软件定义网络(software defined networking,SDN)技术,提出一种基于网络计算的高效故障重建方案——网络流水线(in-network pipeline,INP),其中SDN控制器利用网络的全局拓扑信息构造重建树,系统依据重建树进行数据传输,并在交换机上完成部分计算,减少向后传输的网络流量,从而消除网络瓶颈,提升恢复性能.测试评估了不同网络带宽下INP的恢复效率.实验结果表明:与传统的纠删码系统相比,INP总是能大幅减少网络流量,并且在一定带宽条件下,能够接近正常读的时间开销.

基于历史数据的虚拟机资源分配方法779-789

摘要：云数据中心中广泛应用虚拟化技术以实现资源的按需分配,从而减小运营成本,提高数据中心的灵活性和可扩展性.然而,虚拟化技术的这些特性也带来了如何在保证虚拟机按需分配的同时,充分利用物理资源而又减小资源冲突率的问题.针对这个问题提出了2种基于历史负载数据的虚拟机资源分配方法,并结合常用的虚拟机放置策略,与现有的常用虚拟机资源分配方法进行对比分析.同时,针对现有的独立评价指标具有片面性的问题,提出1个综合有效性指标,能够结合虚拟机的分配所消耗的物理机数量、物理机的资源利用率以及资源冲突率3方面的指标来综合评价方案的有效性.最后通过实际的云计算负载测试,证明了提出的基于历史数据的虚拟机资源分配方法整体上优于常用的虚拟机资源分配方法,并且综合有效性指标能够合理地从整体上评估虚拟机分配方案的有效性.

地球科学大规模并行应用的重叠存储优化790-797

摘要：存储是地球科学类软件的重要组成部分,周期性输出中间态和检查点会带来大量的访存操作,不恰当的访存设计会严重影响软件在大规模计算时的性能表现.针对地球科学类软件的存储问题,从软件层面提出一个重叠存储优化方法,通过设置额外的I/O进程隐藏输出过程.该重叠存储优化主要有3个优势:1)将输出和计算操作重叠在一起,实现了输出的重叠化和隐藏化;2)抑制了收集通信的开销,突破了收集操作的通信带宽瓶颈和内存限制;3)能容易地使用各种高级并行输出库函数.利用重叠存储优化了天河二号上的WRF,ROMS_AGRIF,GRAPES,并完成了性能测试.结果表明:经过存储优化后,程序的峰值性能都获得了显著的提升.还讨论了在固定总进程数下,计算进程和I/O进程数的最佳比例是多少.优化后的程序与原版相比,模式专家只需要在配置文件额外设置2个新变量即可使用,十分易于学习.

一种基于斯格明子介质的高效存内计算框架798-809

摘要：存内计算(processing in memory,PIM)作为一种新兴的技术,支持数据在存储单元内就地处理,减少了数据的移动并增加了数据的并行处理,在一定程度上弥补了冯·诺依曼架构的缺陷.和传统易失随机存储介质相比,赛道型内存(racetrack memory,RM)具有密度大、非易失且静态功耗低等特点,支持高效的存内计算.为解决性能与功耗问题,提出了一种新型的基于斯格明子(Skyrmion)介质的非易失性存内计算框架.该框架采用斯格明子赛道内存(Skyrmion-based racetrack memory)作为存储单元,采用斯格明子逻辑门(Skyrmion-based logic gate)构成的加法乘法器组成计算单元,无须大量CMOS(complementary metal oxide semiconductor)电路辅助,设计复杂度大大降低.同时,通过在电路级优化存储单元读写端口数目与在系统级改进内存地址映射方式,大幅提高该框架的运行效率.实验结果表明:相比基于磁畴壁(domain-wall)的非易失性存内计算框架,提出的框架在运行时间上节省了48.1%,同时在能耗上节省了42.9%.

面向关系数据库查询的能耗建模及计划评价810-824

摘要：传统关系数据库在选择查询计划时,其查询优化器仅以性能为目标,限制了数据库的节能潜力.因此,基于查询的资源消耗特征(CPU指令、磁盘数据块读取、内存数据块读取),提出一种查询计划的能耗模型和评价模型.模型不仅能够精确预测查询计划的能耗,为查询优化器选择节能的计划奠定基础.还使优化器能权衡功率与性能在计划总成本中所占的权重,并根据数据库的运行状态调整查询语句的优化目标(性能、功率、能耗)选择最优计划.实验结果表明:模型平均预测正确率为95.68%;当优化目标是功率时,功率节约范围为8.95%~29.25%;当优化目标是能耗时,能耗节约范围为3.62%~11.34%.

计算机研究与发展杂志学术活动

2019年《计算机研究与发展》专题(正刊)征文通知——密码学与智能安全研究729-729

摘要：依托于云计算、物联网、大数据技术的发展,自动驾驶、人脸识别、智能家居等人工智能技术快速进入了人们的视野,目前已经成为先进科技社会化应用的代表和社会热点.但是,安全问题却为这些技术的广泛应用提出了严峻挑战,没有强大的自主可控的安全技术的支撑,人工智能带来的也许不仅仅是便利,更可能是灾难.安全问题可以说是人工智能走向大规模应用的瓶颈和一个关键问题.而作为解决安全问题的核心技术——密码学,如何适应人工智能安全的需要是另一个关键问题.

计算机研究与发展杂志人工智能

基于Intel平台的Winograd快速卷积算法研究与优化825-835

摘要：随着深度学习的快速发展,其在语音处理、图像识别和自然语言理解等领域被广泛应用,为科研产业以及日常生活带去了巨大的变革.Intel紧跟深度学习的浪潮,推出了第2代Xeon Phi处理器KNL(knights landing),其后又了第3代Xeon Phi处理器KNM(knights mill),为深度学习的蓬勃发展带去了新的活力.通过在Intel平台上进行快速卷积算法Winograd的研究与优化,对比IntelMKL(math kernel library)DNN(deep neural network)中的卷积性能,推动Intel MKL DNN中深度神经网络接口的完善以及Intel平台上深度学习的发展.研究中结合Intel最新深度学习平台的AVX-512指令集、高速内存MCDRAM、多MemorySNC模式、二维网格状内核结构等特性,并通过对内存分配、数据调度等情况的分析,设计优化Winograd算法,一方面选取典型的卷积神经网络(convolutional neural network,CNN)网络模型VGG19,测试对比Intel MKL DNN的卷积实现,最终取得了2倍多的性能加速比;另一方面,通过测试常用卷积类型,对比Intel MKL DNN和NVIDIA cuDNN,验证了实现的Winograd对于常用卷积类型具有很好的适用性且具有实际使用价值.该研究工作期望为Intel平台在深度学习领域的发展提供重要的指导意义.

划分序乘积空间:基于划分的粒计算模型836-843

摘要：粒计算(granular computing)通过粒结构实现复杂问题求解.现有对粒结构中粒化方法的研究,主要是分别基于多层次的粒化方法和基于多视角的粒化方法,没有将多层次粒化方法和多视角粒化方法结合起来.基于多层次的粒化方法得到的粒结构由一个满足线性序关系的多个层构成,即单视角多层次.基于多视角的粒化方法得到的粒结构具有多个视角,但是每个视角仅有一个层.为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.首先,使用论域上的一个划分定义一个层.其次,使用一个嵌套的划分序定义一个多层次,表示为一个视角,层和层之间具有线性序关系.最后,给定多个视角,则定义了多个线性序关系,基于多个线性序关系的乘积,定义划分序乘积空间.划分序乘积空间给出了一种基于划分的粒计算模型.通过实例说明了划分序乘积空间在实际应用中的优越性.

三元概念的一种构造方法844-853

摘要：三元概念分析是一种数据分析和信息处理的新方法.三元概念的构造是三元概念分析的重要问题之一.首先,研究一个三元概念的外延、内涵和方式中存在空集时该三元概念具有的性质,并给出这类三元概念的判定方法.其次,定义一类特殊的三元概念,称其为对象条件三元概念.在对象条件三元概念构成的集合上定义一种运算,并利用该运算提出一种基于对象条件三元概念生成三元概念的方法.该方法表明:如果一个三元概念的外延和方式均为非空集合,那么它可以由某些对象条件三元概念生成.此外,将一个三元背景按照每一个条件分解为一系列二元背景,研究该三元背景上的对象条件三元概念与分解后的二元背景上的对象二元概念之间的关系,并进一步给出了由对象条件三元概念生成三元概念的具体步骤.最后,通过实例阐明由对象条件三元概念构造三元概念的详细过程,并给出了三元图来清晰地描述所生成的所有三元概念.

基于带权词格的循环神经网络句子语义表示建模854-865

摘要：目前,循环神经网络(recurrent neural network,RNN)已经被广泛应用于自然语言处理的文本序列语义表示建模.对于没有词语分隔符的语言,例如中文,该网络以经过分词预处理的词序列作为标准输入.然而,非最优的分词粒度和分词错误会对句子语义表示建模产生负面作用,影响后续自然语言处理任务的进行.针对这些问题,提出基于带权词格的循环神经网络模型.该模型以带权词格作为输入,在每个时刻融合多个输入向量和对应的隐状态,融合生成新的隐状态.带权词格是一种包含指数级别分词结果的压缩数据结构,词格中的边权重在一定程度上体现了不同分词结果的一致性.特别地,利用词格权重作为融合函数中权重建模的监督信息,进一步提升了模型句子语义表示的学习效果.相比于传统循环神经网络,该模型不仅能够缓解分词错误对句子语义建模产生的负面影响,同时使得语义建模具有更强的灵活性.在情感分类和问句分类2个任务上的实验结果证明了该模型的有效性.

计算机研究与发展杂志软件技术

Uroad:一种高效的大规模多对多拼车匹配算法866-883

摘要：由于日益拥堵的交通环境和不断增加的私家车出行成本,越来越多的人关注并接受拼车的出行方式.虽然现在已经有很多针对拼车研究的算法,但是目前还没有从全局的角度出发考虑拼车匹配问题的算法.从全局的角度合理规划所有拼车匹配路线,使所有司机因为拼车而产生的绕路距离最小,这不但能减少空气污染还能缓解交通压力等.因此,提出了一种高效的大规模多对多拼车匹配算法Uroad来弥补这一不足.Uroad允许乘客在提出的拼车请求中包含出发时间段和最大拼车费用来表明自己要求的出发时间范围和对拼车服务最多愿意支付的费用;也允许司机提出出发时间和最晚达到时间约束来表明自己开始行程的时间点和最晚达到自身目的地的时间点.和其他拼车算法一样,Uroad根据乘客自身的行程距离和拼车后对司机造成的绕路距离来计算车费.根据乘客和司机的要求,Uroad支持多乘客与多司机全局最优匹配,并同时尽可能为每一名乘客匹配一名符合双方拼车条件的司机,最终使得所有司机产生的绕路距离总和最小.Uroad通过前期一系列的基于时间、欧氏距离、路网距离的3种空间剪枝策略来减少最短路径的计算量,从而提高算法的整体效率.实验结果显示,Uroad算法能在2min内,实现1000名乘客在100000名司机中找出最优的拼车匹配组合方案,与直接计算最短路径的基本方法相比,整体耗时缩短了40%.和现有算法中乘客随机选择司机的策略相比,加入了全局优化策略之后,Uroad算法中所有司机的绕路距离总和可减少60%左右.