计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2016年第09期杂志 文档列表

超级计算系统互连网络带内管理的实现与评测1717-1732

摘要：互连网络是超级计算系统的关键部件,其易管理性将直接影响整个系统的RAS特性（可靠性、可用性和服务性）.“天河二号”超级计算系统采用了定制的高速互连网络,该网络由大约5856块网络交换芯片NRC和18 304块网络接口芯片NIC构成,其互连规模极其巨大.为了实现对系统内众多网络芯片及其端口的高效率配置和监控等管理操作,该互连网络采用了基于带内的网络管理技术.该文描述了带内网络管理的设计与实现,具体包括网络管理功能、网络管理总体结构、带内管理描述符格式与报文处理流程、管理软件的总体框架等.基于部署在国家超级计算广州中心的实际系统,该文对“天河二号”互连网络带内的管理进行了测试,测试结果证明了带内管理的高效性.

通用图形处理器线程调度优化方法研究综述1733-1749

摘要：随着通用图形处理器（GPGPU）并行计算能力的日益增强,其应用范围越来越广.然而由于不规则计算任务使得通用图形处理器资源难以得到充分利用,其性能并未达到最大化.在论述GPGPU微体系结构的基础上,该文重点讨论了多种针对GPGPU性能提升的线程调度优化方法,主要从针对优化分支转移提升线程级并行度、针对访存效率的提升和针对标量指令执行以提升资源利用率三方面的线程调度优化方法进行了分析和比较.另外,由于功耗问题已成为制约GPGPU发展的主要因素之一,该文还分析了影响GPGPU功耗效率的主要原因及目前提高GPGPU功耗效率的主要低功耗技术,并对目前针对GPGPU功耗优化的典型线程调度优化方法进行了分析比较.最后,该文指出了未来线程调度优化方法需要进一步探讨的一些问题.

数据中心网络高效数据汇聚传输算法1750-1762

摘要：在数据中心中,类MapReduce的分布式计算系统在数据的混洗阶段产生巨大流量,令数据中心的东西向网络资源成为瓶颈.将这些高度相关的数据流在接收端进行聚合是分布式计算的通用处理方式,为了降低网络通信量并有效利用带宽,文中采用网内关联性流量的汇聚传输策略,将混洗和汇聚并行化,达到进一步降低东西向网络资源消耗、缩短混洗阶段延迟的目的.目前提出的IRS-based算法在适用场景上有一定局限性,为了解决这一问题,文中首先在以服务器为中心的代表结构BCube上建立incast最小树模型,分别提出MIB-based算法和MC-based算法,仅根据已知拓扑结构和发送节点编号即可快速生成一棵近似的最小代价incast树.MIB-based算法针对发送节点强关联的情况,使高层发送节点尽可能汇聚到已有的低层发送节点构建incast树;MC-based算法针对发送节点松散关联的情况,将节点进行最大程度上的聚合,通过增加最少的汇聚点完成incast树的构建.随后将上述两种算法结合起来进一步提出适用于各种场景的M2-based算法,通过推算时间复杂度证明该算法能够满足在线构建incast树的需求.最后,详细分析了M2-based算法对其他数据中心网络结构的适应性以及网内汇聚传输能够减少作业完成时间的原理.小规模实验结果表明,在不同网络规模下,M2-based比IRS-based节省了网络中约3%的数据量,整个作业在混洗和Reduce阶段的等待时间比不采用网内汇聚缩短约2/3;在不同传输节点规模下,M2-based比IRS-based节省了网络中约19%的数据量,整个作业在混洗和Reduce阶段的等待时间比不采用网内汇聚缩短约3/4.

面向三维多核片上系统的热感知硅后能耗优化方法1763-1774

摘要：高能效（Energy efficiency）已成为目前嵌入式多核片上系统（System-on-Chips,SoCs）设计中的首要优化目标.基于电压/频率岛设计的三维多核片上系统能够为构建高能效系统提供一种有力的解决方案.然而,不断增加的工艺偏差导致制造后芯片中电压/频率岛的性能参数偏离其额定值.在较大偏差的影响下,可能无法满足任务的截止时间约束.另外,已有的研究工作大多针对二维平台,无法很好地解决因三维集成而不断恶化的发热问题.面向采用电压/频率岛设计的三维多核SoC,文中提出一个硅后优化框架,在最小化系统能耗的同时,能够满足任务截止时间和系统热约束.除了能效感知的任务调度和电压/频率分派方法,提出的优化框架还采用任务迁移平衡核栈的功耗以实现热优化.实验结果表明,与已有的热平衡方法比较,文中提出的方法能减少平均18.6%的能耗.同时,与经典的能耗优化方法比较,文中提出的方法能降低平均5.6℃的峰值温度.

基于OpenCL的Viola-Jones人脸检测算法性能优化研究1775-1789

摘要：Viola-Jones人脸检测算法是最为成功的可实用的人脸检测算法之一.然而,随着该算法所在领域数据处理规模的不断扩大,现有算法的性能已经越来越无法满足日益增长的交互性与实时性要求.使用GPU计算平台提升该算法性能,以满足日益增长的实时性要求已经成为研究热点.然而,该算法在对GPU的实现和优化中,存在线程间负载不均衡的非规则特性,如果仅使用传统的优化方法,则难以在GPU计算平台上达到较高性能.针对此种情况,该文构建了针对此类算法的并行优化框架,通过Uberkernel、粗粒度并行、Persistent Thread、线程与数据的动态映射、全局及本地队列等优化方法的应用,突破了负载不均衡非规则特性导致的性能瓶颈,大幅提高了人脸检测算法在GPU计算平台上的性能.同时,该文通过对不同GPU计算平台关键性能参数的定义、抽取和传递,实现了该算法在不同GPU计算平台间的性能移植.实验结果表明,与OpenCV2.4中经过高度优化的CPU版本在Intel Xeon X5550CPU上的性能相比,优化后的算法在AMD HD7970和NVIDIA GTX680两个不同GPU计算平台上分别达到了11.24-20.27和9.24-17.62倍的加速比,不仅实现了高性能,而且实现了在不同GPU计算平台间的性能移植.

软错误率变动对检查点机制的影响1790-1800

摘要：随着集成电路工艺进入纳米时代,芯片正面临着软错误的威胁.除了软错误在数量上的威胁外,处理器还面临着由于工艺变动性和电压、温度、位置等工作环境变动而导致的错误率变动性的威胁,即系统的错误率不会一直稳定而是随着时间发生变化.检查点是系统容错的主要机制,它的开销和检查点的间隔密切相关,目前检查点间隔的确定大多是基于恒定错误率的.但是在软错误变动的情况下,自适应检查点的方法比固定方法更能够显著降低检查点开销,它通过预测系统的错误率来确保系统的检查点间隔始终与最优状态接近.但是自适应检查点所能获得的性能改善与错误率变动的具体程度相关.因此本文研究软错误率变动的形式和幅度如何影响检查点的开销.该文开展了如下研究：基于温度、电压、位置等因素对软错误影响的原理,建立了一个包含变动幅度、持续时间等参数的错误率变动的模型;基于错误率变动模型,模拟了在理想情况下自适应检查点机制能够获得的性能改善;提出了一种基于错误历史预测错误率的方法,从而验证了在实际情况下自适应检查点能够达到的效果.实验结果表明,变动的幅度在3倍以上且持续时间在12.5%以上时,该文方法就能获得实际上的性能改善.

求解Boltzmann模型方程高性能并行算法在航天跨流域空气动力学应用研究1801-1811

摘要：对Boltzmann方程碰撞积分物理分析与可计算建模,得到适于描述航天再入从外层空间到近地面各流域统一Boltzmann模型方程,提出求解Boltzmann模型方程统一算法高性能并行计算数学模型.发展离散速度空间区域分解大规模并行计算技术,分析统一算法变量依赖关系,建立可扩展并行计算方案;研究数据并行分布与并行执行特征,开展大规模并行化程序设计,并在小、中、大规模256-512、4096-20 625CPU及异构计算机500-45 000、3125-112 500进程并行算法测试,建立稳定运行于国产千万亿次超级计算机高性能可扩展大规模并行算法与航天器再入跨流域复杂气动力/热绕流问题并行化软件应用平台.通过对稀薄流到连续流再入飞行不同高度可回收返回式卫星飞行器、近空间大尺度机动飞行器跨流域绕流环境不同粒度高性能计算与验证,揭示大尺度复杂结构飞行器跨流区飞行稀薄过渡流区热流系数比连续、近连续流区热流系数随物面变化剧烈得多、大得多,发现该类飞行器后端面热流最大值发生在水平舵外侧拐角处,达驻点热流六分之一量级,提供了一个可靠求解航天器再入各流域高超声速绕流问题统一算法高性能并行计算应用研究方向.

三维片上网络体系结构研究综述1812-1828

摘要：伴随着三维集成电路的迅速发展,三维片上网络受到国内外研究者的广泛关注.三维片上网络主要用于实现三维堆叠芯片的互连通信,为三维集成电路提供超低的延迟和竖直方向上超高的带宽,从而解决系统集成度增加导致的通信瓶颈问题,有利于克服存储墙问题并提高三维堆叠芯片的性能.文章介绍了三维集成电路研究现状及其结构优势,分析三维片上网络体系结构的特点和存在的问题,包括竖直方向的单跳传播问题、路由器交叉开关的复杂度控制问题以及热效应的控制问题,从系统层、微结构层和电路层对三维片上网络体系结构的研究热点及其实例进行了深入分析,最后对三维片上网络所面临的挑战和设计方法进行了总结和展望.

基于路径约束求解的多目标状态激励生成方法1829-1842

摘要：该文提出了一种针对多个难达目标状态的激励生成方法,该方法基于抽象引导的半形式化方法框架.采用一个评估函数对候选状态进行评价,该评估函数综合考虑了从一个状态到不同目标状态的全局抽象距离信息,评价出从各个状态到达某个目标状态或者同时到达多个目标状态的潜能,并以此指导模拟过程直到最终搜索到一条能同时覆盖多个目标状态的状态序列.此外,该文采用了基于路径约束求解的激励生成方式,这种方式结合了具体模拟和符号模拟技术,符号模拟沿着具体执行路径提取分支条件构成路径约束,通过约束条件的翻转与求解能够有效地产生输入向量,以一种较均衡的模式遍历设计的状态空间,帮助验证快速覆盖到目标.实验结果表明,该文方法能够有效地同时验证设计中的多个目标状态.

支持通信资源全局共享的射频片上网络研究1843-1857

摘要：随着半导体集成电路的飞速发展,未来的片上芯片中将集成数百上千个处理核,以实现越来越复杂的功能.基于电气互连的片上网络在大规模片上系统中将很难满足未来高性能计算及多核处理器系统的通信需求.基于射频互连的片上网络能够以接近光的速度实现片内的低功耗远距离数据通信,是未来片上网络发展的重要趋势之一.现有的射频片上网络研究中,片上射频资源都为固定的射频通信节点独占,存在资源利用率不高,无法满足实时通信需求等问题.针对这些问题,该文首次提出基于共享射频互连的片上网络SRFNoC,并对其进行了清晰的刻画.在此基础上,提出基于集群共享的射频片上网络Club_SRFNoC,从网络拓扑结构设计、映射算法,共享信道的仲裁机制以及路由等方面进行了深入地研究.通过周期精准的实验仿真,Club_SRFNoC片上网络能够以43%（平均值）的片上射频资源,实现Club_ERFNoC片上网络相同的网络性能.

一种新型的虫孔气泡流控实现策略1858-1867

摘要：气泡流控是一种实现环内无死锁路由的高效方法.该方法在超级计算机Bluegene/L中得到了成功应用.然而气泡流控只适用于虚跨步（VCT）切换网络.目前,研究人员提出了一些方法把气泡流控策略应用到虫孔切换的片上网络中.然而这些虫孔气泡流控策略需要复杂的控制信息.文中提出了一种新型的设计方法实现高效、简洁的虫孔气泡流控.首先采用支持非原子缓冲分配的多请求缓冲结构（MRIBO）代替传统的FIFO缓冲结构存储报文.MRIBO支持Flit在不同报文间乱序存储,缓冲区中的每一个Flit能够独立路由.在MRIBO存储方式下,作者设计了一种类似VCT网络的气泡流控,适用于虫孔网络的新型气泡流控策略.证明了在MRIBO方式下,新型流控策略可以保证单向环内的Flit总是可以流动,不会出现死锁,在单向环内实现了无死锁路由.基于斯坦福大学开发的BookSim模拟平台,作者测试了新型虫孔气泡流控策略的性能.通过修改源代码,在BookSim中实现了基于新型虫孔气泡的维序路由算法（WBFC）和完全适应性路由算法（Adapt-BF）.作者分别比较了这两种算法和传统的基于子午线（Dateline）的维序路由算法（DOR）以及完全适应性路由算法（Adapt-DL）在不同维度的Torus网络中的报文平均延迟.模拟结果显示：这种新型虫孔气泡流控策略的性能大大优于传统的虫孔切换.其中,8-ary 2-cube Torus网络性能测试中,在uniform通信模式下,Adapt-BF算法的报文延迟相对Adapt-DL算法有近18%的减少.文章通过新型的缓冲组织结构打破了虫孔交换中报文传输的原子性,保证了Flit独立路由,所以就可以在虫孔网络中像VCT网络中处理报文一样处理Flit.在这种情况下,VCT网络中基于局部信息的Bubble流控技术可以几乎不加修改地应用到虫孔网络中.因此,这种方法简化了虫孔气泡流控的实现.

基于AWGR的OCS/EPS数据中心光电混合网络1868-1882

摘要：随着云计算和大数据应用技术的发展,数据中心的数量和规模迅速发展,为了满足服务器之间大规模数据流动的需求,数据中心网络的通信能力面临巨大的挑战.传统数据中心中,网络的路由交换设备一般仅采用电域交换技术,电域交换技术虽然可以快速地、灵活地切换数据包的传输路径,但其本身存在通信带宽低、交换容量有限、高能耗等缺点.为了提高数据中心网络的性能、降低网络的能耗,最近的研究提出了若干基于慢速路径切换光器件的光电混合网络结构.它们通常只能将小部分数据量非常大的网络流放在高带宽的光网络上传输,其他的网络流仍然需要电域网络传输.随着快速可调波长激光器以及光波长路由器件的成熟,使光电混合网络结构灵活应对动态、多样的流量模式成为可能.该文基于快速可调波长激光器TWC（Tunable Wavelength Converters）和光波长路由器AWGR（Arrayed-Waveguide Grating Router）,首次提出了一种OCS（Optical Circuit Switching）/EPS（Electrical Packet Switching）光电混合网络结构Ace-net.在文中详细描述了光电混合网络的结构以及带宽测量、仲裁控制、流量分配等机制,这些机制利用TWC器件快速波长变换的特性,能快速地应对网络流量的变化,使更多的网络流量在光域网络上传输;同时使用模拟器对此结构进行了评测,模拟结果表明此网络结构具有很好的网络性能.

多核共享缓存bank冲突分析及其延迟最小化1883-1899

摘要：在硬实时多核系统中,共享资源冲突的问题为硬实时任务的最差情况下执行时间（WCET）分析带来了新挑战.虽然现有的共享缓存冲突分析技术在storage冲突方面已取得研究进展,但对于bank冲突而言,现有研究仍局限于通过界定bank冲突延迟上限来分析和处理bank冲突.该文通过优化核-bank映射关系来使硬实时多核系统中的bank冲突延迟最小化,即在对bank冲突延迟进行分析的基础上,首先通过优化核-bank之间的映射关系来消除bank冲突;若无法消除,则需要寻找能使bank冲突延迟最小化的核-bank映射关系解,并为此设计了一种基于多核总线请求时间序列的bank冲突延迟求解算法.最后,文中设计了能够对总线访问延迟进行消重的多核硬实时任务WCET估算方法.实验结果表明：文中所提的优化方法可消除这类bank冲突或使其延迟最小化,文中所提的WCET估算方法与现有估算方法相比可获得更精确的最差情况下执行时间（WCET）.

基于预采样的模块级热分析方法1900-1911

摘要：对片上多核系统（MPSoC）进行高效结构级热分析是进行温敏布图规划与实时功耗温度管理研究的关键.由于需要预先使用HotSpot提取布图规划中功能模块之间的相关热阻参数,最新的结构级热分析算法BloTAM在温敏布图规划中的热分析效率并不理想.对于散热条件与内核尺寸确定的温敏布图规划,该文提出了一种预采样的结构级热分析算法PS-BloTAM,它先使用HotSpot为采样模块阵列建立相关热阻预采样矩阵S（即相关热阻库）,温敏布图规划产生一个方案后,PS-BloTAM可以根据方案中模块的大小与位置直接使用S计算出模块之间的相关热阻矩阵R,然后使用R计算出不同工作模式下的模块温度.采用传统的设计库思想,PS-BloTAM能够快速计算出不同布图规划方案所产生的热点温度.实验数据表明：（1）与HotSpot相比,PS-BloTAM的平均误差与最大误差分别小于1.65%和6.64%,可以获得43倍的加速效果;（2）与BloTAM相比,PS-BloTAM可以获得3.4倍的加速效果;（3）在温敏布图规划的应用中,PS-BloTAM以小于1.24%误差的代价、获得了比HotSpot快近10倍的加速效果.

TrustZone技术的分析与研究1912-1928

摘要：互联网时代的到来给嵌入式应用系统带来了前所未有的发展机遇,但是随之而来的网络应用安全问题也使得嵌入式应用系统面临着越来越严重的威胁,安全性已经成为嵌入式系统设计中一项极为重要的需求.为此,ARM公司提出了基于TrustZone技术的一套系统级安全解决方案,该技术是在尽量不影响系统的功耗、性能和面积的前提下通过硬件来实现安全环境与普通环境的隔离,而软件提供基本的安全服务和接口,由软硬件相结合而构建系统安全,也正因为这些特点而受到国内外研究者的广泛关注.文中重点分析了TrustZone技术提供的安全隔离系统基本架构、安全机制的实现方式及如何构建可信执行环境.在此基础上将该技术与其他提高嵌入式安全的技术作了分析对比,也进一步探讨了其优势与不足之处,并针对不足之处提出了可能的解决方案.最后,深入讨论了该技术在学术领域的相关研究工作和商业应用情况,同时结合当前嵌入式应用领域存在的安全问题展望了该技术的未来发展方向和应用需求.