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

计算机学报 2018年第10期杂志 文档列表

基于线程池的GPU任务并行计算模式研究2175-2192

摘要：GPU已经成为具有高并发高内存带宽的通用协处理器，但是GPU与CPU在体系结构和编程模型上存在很大差异，导致CPU-GPU异构计算系统的编程复杂度提高，即使采用统一计算设备架构(CUDA)提供的kernel并发技术和多流技术也较难充分控制和利用GPU上的计算资源，难以有效地处理不规则的并行应用问题.为从体系结构角度探索GPU硬件支持的页锁定内存和统一虚拟地址空间等特征，该文提出了CPU辅助任务调度管理下的基于线程池技术的GPU任务并行计算模型CAGTP，实现了CPU-GPU异构计算系统上的共享内存式程序设计.提出并设计了CPU端的任务队列、计算线程块级任务调度器、任务槽和GPU端的任务复用kernel函数等机制，实现了CPU与GPU间的高效细粒度任务交互，避免了原生CUDA程序中多次启停kernel函数的开销，有效地支持了GPU上的细粒度不规则并行任务计算，而且利用模型API接口函数能够降低CPU-GPU异构计算系统的编程难度.实验结果表明，CAGTP模型中任务调度的开销是kernel函数调用的5%，有效提升了通用矩阵乘、乔列斯基分解和K均值、T近邻等典型线性代数和机器学习算法的计算性能；CAGTP模型易于扩展使用多块GPU，且在性能差异较大的多个GPU之间达到负载均衡，能够高效求解混合任务和具有不规则并行性的应用问题.

流数据处理中负载突发感知的弹性资源分配2193-2208

摘要：在分布式并行数据流处理中，面向实时变化且具有突发性的流数据负载，固定的资源分配将造成资源浪费或服务质量降低，因此，可伸缩的弹性资源分配是一个亟待解决的关键问题.然而，由于资源分配延迟和负载预测模型存在误差，已有的弹性资源分配策略无法准确地提供与突发负载相匹配的资源，且存在不必要的资源调整反复，增加了系统开销.该文主要解决弹性资源分配的调整延迟和调整颠簸问题.针对上述问题，主要的挑战在于突发负载的准确预测和节点间的协作.为此，该文提出了一个上、下游节点协同的弹性资源分配策略，最优化数据质量和资源使用率，兼顾考虑调整代价.在该策略中，基于数据负载关联模型和双向的控制机制，下游节点能够实时感知和预测上游节点产生的突发负载和负载的变化趋势，预先调整资源并避免调整颠簸；同时，上游节点能够基于反馈机制，动态调节数据处理速率以抑制下游节点的负载波动，降低其资源调整的可能性.实验结果表明，当负载变化较大时，该策略平均减少数据丢失达85%，并显著降低了系统资源调整开销，同时，提高了资源使用率.

“神威·太湖之光”计算机系统大规模应用特征分析与E级可扩展性研究2209-2220

摘要：复杂应用系统面临着全系统、全物理过程、自然尺度的计算模拟，对计算机能力提出更高要求.该文介绍了“神威·太湖之光”系统半机以上超大规模并行应用的算法特点、体系结构适应性、计算复杂度、访存复杂度和通信复杂度的大规模实验分析结果，基于大规模应用计算和数据移动特征以及异构众核体系结构特点提出新的性能模型，得出影响大规模应用性能的关键因素，提出E级复杂应用对未来E级计算机系统的设计需求.

基于申威众核处理器的海冰模式并行加速方法2221-2235

摘要：海冰模式是地球模式的重要组成部分，其使用不同的网格和时间梯度来模拟海冰区域随时间的变化.海冰模式具有计算密集的特性，随着海冰模式计算精度的提升，传统的硬件已难以满足其计算需求.申威太湖之光超级计算机是第一台峰值性能超过100 Pflops的超级计算机，其为高精度的海冰模式过程模拟提供了新的硬件平台，但在该平台上实现算法高效并行化仍面临着诸多问题.一些应用程序已经在众核平台上实现移植和并行化，但是相比其他领域，气候软件在众核平台移植和并行化的过程相对缓慢.有关气候模式在众核平台的并行化研究大多基于GPU实现.早期的研究多基于单个气候运算过程，该过程通常为计算密集型程序，通信过程相对较少，基于GPU的实现可以取得较好的并行效果.与单一的运算过程不同，海冰模式程序需要与多个气候模式进行交互，如何减少通信过程开销以及如何充分利用申威处理器所提供的并行性能是我们遇到的主要问题.为解决这一问题，该文基于申威众核处理器，设计了一种针对海冰模式算法移植和并行化的方法.每个申威众核处理器包含有4个核组，每个核组包含有一个管理核心和64个计算核心.为充分发掘申威众核处理器的并行特性，该方法分别对海冰模式数据分割方式，数据传输过程以及计算方式进行了改进和优化.该文利用该方法对海冰模式的两个算法进行了移植和并行化，并使用CICE测试数据集和COREv2数据集对该方法的性能进行测试.实验表明，并行优化后的两个算法相较其只在管理核心上运行分别可获得11.6倍和9.8倍的性能提升，且与基本并行化方法相比，该方法最高可获得40%的性能提升.

面向神威·太湖之光的国产异构众核处理器OpenCL编译系统2236-2250

摘要：近年来硬件设计呈现出异构化的趋势，如何有效开发并行程序成为制约异构系统发展的瓶颈之一已成为业界共识.我国自主研制的“神威·太湖之光”超级计算机，采用了国产片上异构众核处理器SW26010，为了降低程序员的编程难度,同时提高软件的移植效率，作者设计并实现了支持国产SW26010众核处理器的OpenCL编译系统.该编译系统实现了OpenCL平台模型、内存模型和执行模型到SW26010众核处理器的映射与优化机制，同时生成性能良好的可执行文件.最后通过实验验证了该编译系统的正确性和有效性，典型OpenCL应用经该编译系统编译后，在中小输入规模下，性能显著优于Intel Xeon Phi，与NVIDIA GPU可比；在较大输入规模下，受限于局存SPM的容量限制，性能略低于NVIDIA GPU.

面向多核向量处理器的矩阵乘法向量化方法2251-2264

摘要：稠密矩阵乘法是大规模科学计算中许多算法的核心计算之一，文中提出一种高效的面向多核向量处理器的矩阵乘法向量化方法.提出一种按行计算的矩阵乘法向量化方法，该向量化方法的基本思想是每次同时计算C矩阵的一行元素，C矩阵第i行元素的值由k次向量乘累加完成，每次计算都是先将A矩阵第i行的第j个元素扩展为值相同的向量，再与B矩阵的第j行向量进行乘累加计算，每一次的向量乘累加计算是在各个VPE上并行进行，计算的源数据和结果数据均保存在VPE的本地寄存器上，每个计算结果涉及的乘累加计算均在同一个VPE上完成，并且A、B、C三个矩阵的数据均是按行顺序读取，访存效率高，在k循环结束时，同时完成C矩阵第i行元素值的计算.该方法能充分开发向量处理器的标量、向量协同数据加载能力，有效减少对DDR的存储带宽需求，能够避免低效的对乘数矩阵列向量数据的访问和各个VPE间的浮点归约求和计算，取得最优的内核计算性能；将处理器的一级数据缓存和阵列存储配置为SRAM访问模式，能够避免由于Cache数据不命中而导致的存储访问延迟，提高核心计算访问一级数据缓存和阵列存储的效率，采用组播DMA传输矩阵数据，能够显著提高从DDR读取矩阵数据的效率；提出依据向量处理单元VPE数量、VPE的FMAC运算单元数量、向量存储器的容量和矩阵元素的数据类型等向量处理器体系结构特点设计最优的核心子块矩阵分块参数设计方法，能够充分开发向量处理器的多核间数据并行、核内的多VPE间的向量SIMD并行、VPE内的多个FMAC单元并行、VPE内的标、向量指令级并行等多级并1106.88 GFLOPS，效率为96.08%，核心计算的效率达到99.39%.

基于事件驱动的MapReduce类流量产生方法与网络评测2265-2281

摘要：大规模网络结构设计是构建大规模分布式系统和E级高性能计算集群的核心技术之一，底层网络设计者需要结合顶层应用通信流量特征，进行网络结构选型与优化.不当的应用通信模型会引起网络结构设计与实际需求的背离，进而导致系统通信和整体性能的下降.传统基于“黑盒”数据分析的流量建模方法存在业务建模粒度粗和应用数据规模扩展性差等缺陷.该研究引入模拟业务内部逻辑的“事件驱动”思想，提出一种针对主流计算模式MapReduce进行流量建模与流量产生方法.与真实应用流量的对比评测显示，该方法能够准确体现MapReduce计算业务所产生网络流量的特征.基于正确的流量模型，该文对四种主流数据中心网络进行了性能模拟分析.结果表明：相较负载随机均匀分布流量，同一种网络在负载MapReduce特性流量时性能将下降超过30%，因此特性流量能更加明显地展现网络拥塞与瓶颈问题.仿真实验所得到的有关网络性能瓶颈、拓扑可扩展性以及网络性价比的结论，为大规模数据中心网络选型和性能优化提供了新的依据.

一种考虑屏蔽效应的电路输入向量敏感性计算方法2282-2294

摘要：输入向量敏感性的计算在电路的高可靠设计过程中有着重要的实际意义，尤其是针对有着特定应用场景的电路产品.该文以概率转移矩阵模型为主要技术手段，首先简要分析了输入向量对电路故障的“驱赶”作用，接着基于屏蔽机理构建了针对电路基本构件的三种屏蔽效应的量化模型，然后利用混合编码并通过虚拟法构建的电路基本构件输出端的可观察敏感性输入向量实现了输入向量敏感性的迭代传播，再结合范数理论计算了电路输入向量的敏感性.理论分析与实验结果表明，该文所提方法的计算精度与同类型方法相似，但计算速度要快2~6倍，内存开销稍小，计算过程则更为灵巧与简便，是一种可操作性强的有效计算模型，其时空复杂性与电路中的基本构件数目成线性增长的关系.此外，实验发现输入向量的敏感性随电路基本构件故障概率的增大而增大，且电屏蔽效应与锁存窗屏蔽效应对输入向量敏感性的影响也随电路基本构件故障概率的增大而呈现出增强的趋势，电屏蔽效应尤甚.

PCRAM损耗均衡研究综述2295-2317

摘要：随着半导体工艺的高速发展，计算机系统中处理器与主存之间性能差距的不断增大，传统存储器件的集成度已接近极限，能耗问题也日益突出，当前传统的主存技术面临挑战.相变随机存储器(PCRAM)具有集成度高、功耗低、非易失、字节级编址等优良特性，是最有发展潜力的、最有可能完全取代DRAM主存的非易失性存储器之一.首先介绍了PCRAM的发展与应用现状，指出T型结构是当前学术界和产业界广泛采用的器件结构，目前已经有PCRAM产品逐步开始量产并投入商业应用.然后，介绍了PCRAM当前面临的挑战，指出PCRAM面临的写耐久性局限是限制期发展与应用的主要障碍之一，分布不均匀的写操作会使PCRAM快速失效.接着，从硬件辅助和软件辅助两个角度分别介绍了当前研究人员所提出的一些具有代表性的PCRAM损耗均衡技术，在分析和归纳当前研究现状的基础上，指出了现有方案的优点和亟待完善之处.最后，展望了未来PCRAM损耗均衡技术的研究方向，为该领域今后的发展提供参考.

基于寄存器簇恢复的追踪信号选择方法2318-2329

摘要：在集成电路开发中，原型芯片硅后可观测性差，使得硅后调试变得异常困难，延长了芯片的开发周期.基于追踪的可调试性设计通过在芯片中添加追踪缓存以存储关键的追踪信号，可提高芯片的可观测性.但由于调试硬件开销有限，如何选择有限的追踪信号以提高芯片可观测性成为硅后调试的研究热点.该文提出了一种基于寄存器簇恢复的追踪信号选择方法，其可分为两步：寄存器簇生成、寄存器簇融合和选择，其中寄存器簇生成根据寄存器的反馈环信息构建初始寄存器簇，而寄存器簇融合和选择可以通过簇合并优化初始寄存器簇，并选择对状态恢复率提升最大的寄存器簇作为追踪寄存器簇.当追踪寄存器簇确定后，簇输入即为追踪信号，簇内寄存器即为需获取的快照信号.在基准电路ISCAS89上的实验结果表明，相对于现有的追踪信号选择方法，该方法可获得更高的状态恢复率，比现有最好的选择结果平均可提高7%，最高可提高57%，同时算法运行时间更短，比现有最快的选择方法平均也有54倍的加速，而仅需增加不到2%的存储开销和不到1%的逻辑开销.

CPS资源服务模型和资源调度研究2330-2343

摘要：信息物理融合系统(Cyber-Physical Systems，CPS)融合了信息世界与物理世界，作为工业互联网与智能制造等重要领域的关键技术引起了越来越多的关注.与WEB服务相比，CPS系统中资源种类繁多、数量庞大、资源之间的异构性强，并且具有大量重复的物理实体，不同物理实体所处的物理环境不同且具有不同的执行性能(QoS)，导致在对具体任务进行资源调用时存在多种调度方案，该文针对该问题展开研究.首先，鉴于CPS系统结构复杂的特点，该文综合分析现有的CPS建模研究成果，采用面向服务的体系架构(Service-Oriented Architecture，SOA)的思想研究CPS的体系结构，在此基础上研究了CPS与WEB服务之间的异同点，确定了面向服务CPS资源服务模型研究的可行性，提出了CPS系统中资源、物理实体、虚拟物理实体、虚拟资源的划分.同时，基于此划分提出了一种OWL(Web Ontology Language)和XML(Extensible Markup Language)混合式的CPS资源服务模型，该模型采用OWL分别对虚拟物理实体、物理实体提供的服务、CPS上层任务进行描述，并采用XML对真实物理实体的QoS参数进行描述.其次，在CPS资源服务模型的基础上，提出了基于智能规划的CPS任务-虚拟资源调度机制，该机制主要确定满足任务需要的多个候选资源集，该候选资源集组成资源的初始调度序列.然后，该文根据资源的QoS要求建立了多目标线性规划的资源选择数学模型并对多目标遗传算法的关键步骤进行创新，提出了以基于多目标遗传算法的资源选择算法求解该模型的方法，所得最优解即为资源候选集中满足整体QoS最优的资源调度序列.最后，以智能电网为例，验证了该文提出的基于智能规划的CPS任务-虚拟资源调度机制和基于多目标遗传算法的CPS资源选择方法的有效性.

基于证据链生成的Android勒索软件检测方法2344-2358

摘要：近年来，基于Android平台的勒索软件呈现爆发式增长趋势，同时恶意行为也正在不断的进化.Android勒索软件专门以用户智能设备和隐私文件为攻击目标，给受害者带来了严重的精神和财产损失.该文提出了一种轻量化的勒索软件检测方法，能够在应用安装到手机之前发现潜在的勒索风险.通过广泛收集2721个勒索软件样本，并对这些样本进行深入分析，该文在勒索软件锁屏、加密、权限、威胁文本、支付方式和网络通信等方面提取特征，利用模块化规则归纳学习算法实时检测风险.另外，基于自然语言生成技术提出了一种证据链生成方法，将待检测应用的信息和匹配的分类规则以普通用户能够理解的方式展现，帮助非专业用户做出合理的决策.最终实验表明，所实现系统能够达到95%的检测准确率，90%的普通用户表示能够正常理解证据链描述，性能分析结果证明系统能够满足智能手机实时检测的需求.

动态内存分配器研究综述2359-2378

摘要：通用动态内存分配器自出现以来一直是系统软件的基本组件.伴随着近些年来多核处理器的发展和新型非易失存储器的出现，关于动态内存分配器的研究也随之聚焦于不同的优化方向，比如多线程环境下的性能优化和针对新型非易失内存介质特性的优化.该文在归纳整理近三十年动态内存分配器的发展和研究状况的同时，对推动内存分配器发展的历史原因进行了分析.此外，作者整理了现有动态内存分配器测试可采用的工作负载和标准测试集，并提出了一套全面、多维度评价内存分配器的指标体系.最后，作者指出了现有工作的优势和面临的缺陷，并探讨了未来内存分配器相关的研究方向，为该领域在今后的发展提供了一定的参考.

具有磨损均衡意识的混合固态硬盘FTL算法2379-2393

摘要：在采用SLC(Single-Level-Cell)和MLC(Multi-Level-Cell)闪存的混合固态硬盘设计中，SLC和MLC之间的写数据分配和磨损均衡是混合固态硬盘闪存转换层设计的关键问题之一.针对此问题，提出一种具有磨损均衡意识的混合固态硬盘闪存转换层算法——WLAFTL(Wear Leveling Aware Flash Translation Layer).首先，它提出了一种动态的基于磨损均衡思想和请求大小融合的数据分配机制，即根据SLC和MLC的磨损速率来动态调整热数据识别阈值的大小，然后将小的写请求分配到SLC、大的写请求分配到MLC.其次，它提出了一种基于磨损均衡思想与数据先进先出(FIFO)调度策略融合的SLC冷数据回收/迁移机制，减少由SLC向MLC迁移的数据量.实验结果显示，与ComboFTL和CFTL算法相比，在使用相同地址映射机制的条件下，WLAFTL算法的平均响应时间分别平均有13.6%和12.7%的改善，总的擦除次数分别平均减少9.2%和20.4%，同时能够更好地实现SLC和MLC之间的磨损均衡.

大规模复杂信息网络表示学习：概念、方法与挑战2394-2420

摘要：大数据时代的到来，使得当前的复杂信息网络研究领域面临着三个基础性问题，即网络的动态性、大规模性以及网络空间的高维性.传统复杂信息网络特征的表示通常以邻接矩阵、出入度、中心性等离散型方式表达，这种表达方式在现有的大规模动态信息网络的新环境下，其计算效率及准确率都受到了很大的挑战.随着机器学习算法的不断发展，复杂信息网络的特征表示学习同样也引起了越来越多的关注.与自然语言中的词向量学习的目标类似，目前较为前沿的大规模复杂网络特征表示学习方法的目标是将网络中任意顶点的结构特征映射到一个低维度的、连续的实值向量，在进行这种映射的过程中，尽量保留顶点之间的结构特征关系，使大规模网络特征学习能够有效地应用于各类网络应用中，如网络中的链接预测、顶点分类、个性化推荐、大规模社区发现等.通过对复杂信息网络特征的学习，不仅能够有效缓解网络数据稀疏性问题,而且把网络中不同类型的异质信息融合为整体，可以更好地解决某些特定问题.同时，还能够高效地实现语义相关性操作，从而显著提升在大规模，特别是超大规模的网络中进行相似性顶点匹配的计算效率等.该文主要对近些年来关于复杂信息网络表示学习的方法和研究现状进行了总结，并提出自己的想法和意见.首先概述了表示学习的发展历史，然后分别阐述了有关大规模复杂信息网络、网络表示学习等基本概念与理论基础；接着，根据学习模型的不同，对经典的、大规模的、基于内容的、基于融合的以及异构的网络表示学习模型进行了全面的分析与比较.另外，对当前的网络表示学习方法所采用的实验数据集、评测指标以及应用场景等也进行了总结概括.最后给出了大规模复杂信息网络表示学习的研究难题�