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

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

前言1423-1424

摘要：计算系统的能耗问题是影响计算系统本身发展、使用以及人类生存环境的重大问题，受到学术界、工业界等各方面的高度关注。本刊定于今年出版“绿色计算”专题，为计算机系统的研究、开发、使用和管理等工作者提供一个展示计算系统节能创新技术的平台。本专题征文发出后，获得计算机领域专家学者的广泛支持，收到大量投稿；稿件经过数十位专家的评审，遴选出9篇论文刊登于本专题。本专题刊登的文章涵盖了面向高能效的体系结构设计、重要应用的高能效实现以及高能效的系统资源管理和调度等方面的内容。

基于可重构微服务器的高能效指纹比对方法1425-1437

摘要：大规模指纹应用需要强大的后端指纹比对计算能力作为支撑．基于可重构微服务器（reconfigurable micro server ，RMS）技术，提出一种软硬协同的高效指纹比对方法，该方法充分发挥可重构混合核心计算架构的优势，采用优化定制的硬件加速部件对指纹比对算法中的计算密集部分进行加速．复杂控制流和离散访存较多的算法部分则以软件形式在通用计算核心上高效执行．在单个RM S计算节点上完成了算法原型的实现并进行了详细测试．测试结果表明：单个RM S节点上的指纹比对性能约为105万次/秒，功耗仅为5 W ．与相关工作相比，该性能是单个X86集群节点的15．5倍；能效是X86集群节点的583倍，是基于Tesla C2075的GPU 服务器的5．4倍．与单纯的FPGA平台相比，基于RM S技术的实现方法更具灵活性和可扩展性，是未来构建大规模指纹比对系统的一种高效的技术解决方案．

DS P芯片中的高能效FFT加速器1438-1446

摘要：快速傅里叶变换（fast Fourier transform ，FFT ）是数字信号处理（digital signal processing ， DSP）领域中最耗时的核心算法，该算法的计算性能和计算效率将影响整个应用的执行效率。因此，在DSP芯片上设计实现了一个基于矩阵转置操作的高能效可变长度 FFT 加速器，采用多种并行策略开发批量小规模FFT 算法与大规模Cooley‐Tukey FFT 算法中指令级和任务级并行。设计“乒乓”多体数据存储器，重叠数据搬移和FFT 计算之间的开销，提高FFT加速器计算效率。并基于此存储器，提出基于基本块的快速矩阵转置算法，从而避免对数据矩阵的列访问；提出混合旋转因子产生策略，结合查表和基于CORDIC算法在线计算方式，最大限度降低旋转因子产生的硬件开销。实验结果表明：FFT加速器原型的峰值能效为146 GFLOPs/W ，相比Intel Xeon CPU 上的多线程FFTW实现，取得2个数量级的能效提升。

基于SMART技术的片上网络低功耗策略 P-SMART1447-1453

摘要：片上网络（network‐on‐chip ，NoC）消耗的功耗在整个芯片中所占比例不断增大，并且随着芯片工艺精度的提升和工作电压的不断降低，静态功耗占片上网络总功耗的比例也越来越大．当前芯片设计者致力于将未被使用的核设置为休眠状态来降低功耗．然而，即便是最前沿的芯片设计，当核休眠时与它连接的路由器都是保持在正常状态来进行报文传输．而与休眠核相连的片上网络路由器由于没有注入和吸收的报文，负载相对较低．在SMART （single‐cycle multi‐hop asynchronous repeated traversal）片上网络中，报文能够单周期从源路由器到目标路由器．基于单周期多跳旁路（SM ART ）技术，提出一种关闭低负载路由器虚通道的策略P‐SM ART ，以在不影响网络性能的情况下节省片上网络功耗．实验结果表明：相对于SMART 技术，P‐SMART的性能损失不超过2％，而功耗节省13．4％．

PLUFS：一种开销敏感的周期任务在线多处理器节能实时调度算法1454-1466

摘要：现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果，但仍不能保证最优可调度性。针对嵌入式实时系统中不可忽视的状态切换开销，提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合，在每个TL面的初始时刻、任务结束执行时刻实现节能调度，在不违反周期任务集最优可调度性的前提下，达到实时约束与能耗节余的合理折中。经过理论证明和模拟实验，结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性，而且节能效果整体优于现有算法，能耗节余比现有算法提高约10％-20％。

XOS：面向用户体验质量的高能效异构多核调度算法1467-1477

摘要：智能移动设备的重要作用日益凸显，然而，对于性能的追求与有限电池容量的矛盾制约了产业的发展．异构多核处理器架构以其平衡性能与能耗的优势，成为一种新型的解决方案．用户体验优化是智能移动设备的重要设计目标．借助一个分段式的用户体验模型，提出了面向异构多核设备的XOS （experience oriented scheduler ）调度算法．XOS 能够跨层获取任务信息，识别与用户直接交互的任务组，保证这些任务的计算资源分配以保障用户体验，同时限制非交互性任务的计算资源以降低能耗．通过建立一套仿真系统验证了算法的有效性并进行了调整优化，然后在Odroid‐XU3开发板Android系统中进行了原型实现和验证．实验结果表明：XOS算法对于不同类型的任务仅产生了2．7％-7．3％的用户体验下降，但节省了8％-48％的能量．

实时系统温度功耗管理的优化方法研究1478-1492

摘要：实时系统的能量受限特性、峰值温度约束以及实时任务的时间约束使其能耗问题备受学术界和工业界的关注，目前已有很多相关功耗管理研究．不考虑温度因素的传统功耗管理大多仅通过动态电压调节技术（dynamic voltage scaling ，DVS）方法调度处理器的状态实现，然而随着芯片尺寸的不断缩减，处理器的功耗密度越来越大，温度与功耗之间的相互影响已不容忽视，由此在传统管理研究的基础上又衍生出了很多温度感知的新方法．1）对实时系统温度功耗管理依托的3个模型（任务模型、热模型和功耗模型）进行总结整理；2）根据是否考虑温度因素将现有研究分为温度无关的和温度感知的2类进行综述，后者又按面向单任务/面向多任务进行分类；3）从具体机制、优化目标、优化效果以及调度时间等方面进行比较，分析现有研究的优缺点；4）指出未来研究方向．

分布式集装箱数据中心的绿色层次化管理1493-1502

摘要：近几年，模块化数据中心（集装箱数据中心）因其高能效可拓展的特点而成为极具前景的IT 基础设施解决方案。预定制的集装箱数据中心不仅可以被部署在传统仓库级数据中心设施中以支持容量扩展，还能够被部署在城市/郊外以支持物联网数据的本地处理。把传统集中建设和管理的数据中心与地理上分布的模块化数据中心结合起来，能够更加方便地利用本地绿色能源发电以及减少数据传输成本。针对目前涌现的地理上分布的集装箱式数据中心模块提出了一种新型分层化管理模式，该技术将分布式集装箱数据中心逻辑上划分成多个性质和功能不同的层级。一个中央调配系统被用来监控每个层级的集装箱数据中心并施加动态休眠机制以进一步提升数据中心的整体效能。小规模测试实验结果显示分层化管理机制能够提升12％-32％的数据中心整体能效，并且保持较高的服务性能。

时间约束的异构分布式系统工作流能耗优化算法1503-1516

摘要：针对现有异构分布式可变电压/频率（dynamic voltage/frequency scaling ，DVFS）计算系统下具有时间约束的工作流能耗优化算法易陷入局部最优的问题，提出了一种新的全局能耗优化算法：反向蛙跳全局能耗感知算法，该算法利用工作流下界完成时间和约束时间之间存在的盈余，逐步从约束时间开始，以不同的跃度值向下界完成时间反向蛙跳，在此过程中基于局部最优解的判断不断调整跃度值直至蛙跳终点，同时保留该过程中工作流满足时间约束且任务运行能耗最小的调度序列。在此基础上利用处理器松弛时间回收技术，在保持任务间依赖关系和满足工作流时间约束的前提下，调整处理器运行电压/频率至更低的合适级别上，从而进一步降低工作流运行能耗。实验表明：该算法能显著降低工作流整体能耗，节能优势明显。

基于统计量的存储系统磁盘功耗建模方法研究1517-1531

摘要：大数据的迅猛发展导致数据中心的存储规模急剧扩张，由此引发的高能耗已经成为数据中心普遍面临的一个突出问题，磁盘类存储介质在数据中心耗能中所占的比例也在逐年增加，能耗建模在目前学者们的研究中越来越受到关注。精确的磁盘能耗模型不仅可以解决数据中心中的电力配套问题，而且为当前数据中心各种能耗管理技术体现更为精确的节能效果。提出了一种基于统计量的磁盘能耗预测模型，该模型弥补了传统细粒度模型产生的额外负载影响，同时获取了比传统粗粒度模型更佳的预测准确率。在实际应用中，该模型不需要分析记录复杂的磁盘内部活动细节，也不需要繁杂的参数采集，仅需要存储系统中宏观的统计量作为参数，且预测精度与细粒度模型近似。通过实验验证，该模型在能耗预测上的平均误差为3％，并且针对同步IO及异步IO都有较好的预测效果。此外，该模型还可以应用于各种在线系统的能耗预测。

无线传感器网络中高能效的Bezier曲线路由算法1532-1543

摘要：无线传感器网络在面向事件监测中蕴藏着巨大的应用价值，但由于传感器节点电源能量耗尽导致经常失效或废弃，因此研究无线传感器网络节能的算法具有重要意义。多路径路由沿多条路径分配能量负载，提高了网络的寿命和质量。需要强调的是均匀地调节更多节点参与到网络的路由任务能够保护某节点由于负载过重从而能量迅速流失直至节点失效。反之，所有的流量沿最短路径路由，路由不仅拥塞，而且沿源节点和汇聚节点对之间的最佳路由周围的节点由于过载最终缩短了网络寿命。从2个方面展开：1）提出了一种高能效的基于Bezier曲线的多路径路由算法（multipath routing algorithm based on Bezier curve ，M PRB），并通过与传统的路由算法比较，实验数据验证了该算法能够获得更好的节能效果；2）基于查询区域划分设计的路由树个数与能耗关系比较了2种高能效的时空查询算法，并通过理论分析与实验仿真研究了查询区域划分方法、划分个数对能耗的影响，结果表明基于角度的查询区域划分方法是一种低能耗、面向绿色计算的方法。

ICIC_Target：目标节点的局部因果关系网络的发现算法1544-1560

摘要：因果关系的研究在于揭示自然规律的和人类社会发展本质及其规律，对人类长久以来的生产生活和科学研究有着非常重要的作用。目前，因果关系的研究受到前所未有的广泛关注，但仍存在诸多困难和挑战。致力于建立一个因果激励/抑制模型以抽象地表示和解释因果的作用机制，并在此基础上提出用于目标节点的局部因果关系网络的自动发现方法框架ICIC和算法ICIC_Target.该方法不预先设定因果结构（如设定为无圈、隐含结构），并根据对因果关系本质的认识，利用初始变量（exogenous variables）和初始团树（IClique）的概念，在判定边和方向之前对变量进行粗略地排序，从而提高了因果关系网络发现的性能。在4个不同类型的数据集上实现了与多种经典方法，如 HITON ，IC ，PC ，PCMB 等的对比实验，实验结果表明ICIC_Target方法适用范围广，有较好的鲁棒性，同时，从理论上分析证实了ICIC_Target方法具有较好的稳定性和较低的复杂度。

《信息安全研究》期刊简介1560-1560

摘要：指出“没有网络安全就没有国家安全,没有信息化就没有现代化）数字时代信息安全工具的大众化是不可阻挡的历史潮流，大众化的信息安全已经直接影响到我们每个人的利益，信息安全已成为国家、地方区域经济结构优化提升和转型发展的新机遇。

一种基于簇类进化的电力经济负荷分配优化算法1561-1575

摘要：电力经济负荷分配不仅能保证电力系统安全稳定地运行、延长机组使用寿命，还能节省能源，最大化电力企业的经济效益．此类问题可归为一种具有高维、不可微目标函数及多个非线性约束的数值优化问题．提出了一种新型的全局优化算法———簇类进化算法（cluster evolutionary algorithm ，CEA ），并将其应用于求解ELD问题．CEA利用聚类过程在进化个体间构建一定结构的连接关系，并利用这种虚拟的簇类化组织来协调和控制系统的优化计算过程，提高群体的问题空间搜索效率以及抗早熟能力．在仿真实验中13个典型测试函数和3个IEEE系统被用于对CEA的性能进行检验．实验数据显示CEA对13个约束数值优化问题可用较小的计算代价获得较高质量的解，而对3个测试系统的计算结果则要好于目前已报道的最佳解．实验数据的统计分析显示CEA是一种高效的数值优化算法，可作为一种有效的ELD问题求解方法．

支持向量机多项式光滑函数的误差理论研究1576-1585

摘要：光滑函数在光滑支持向量机的理论中起着重要作用．1996年Chen等人提出一个支持向量机的光滑函数———Sigmoid函数的积分函数，并解决了该光滑函数的误差问题．2005-2009年，袁玉波、熊金志和刘叶青等人相继提出支持向量机的无穷多个多项式光滑函数和多项式光滑的支持向量机模型，但都未解决这类多项式光滑函数的误差函数问题．为此，用 Newton‐Hermite 插值方法研究该问题．研究结果表明：1）用 New ton‐Hermite插值方法可计算这类光滑函数的误差函数，并给出了具体算法；2）这类误差函数有无穷多个，可用一个一般形式表示，并得到了这个一般形式；3）这类误差函数具有许多重要性质，并给出了严格证明．解决了支持向量机无穷多个多项式光滑函数的误差函数及其性质问题，建立了这类多项式光滑函数的误差理论，为研究支持向量机的光滑理论提供了基本的理论支持．

求解约束可满足问题的eSTR算法优化1586-1595

摘要：表约束方法是1种外延式知识表示方法，每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组，直观易于理解，在约束程序中得到了深入的研究，这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中．但随着约束的增多及其元组集增大，占有的空间与相容性检测效率成了关键问题．eSTR是1个将STR扩展到高阶相容的算法，通过深入分析eSTR算法后发现有2种优化方式：PWsup数据结构和极小约束范围，同时证明了在极小约束范围上，约束网络仍然能够维持PWC＋GAC ，其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗，而 PWsup数据结构能够通过避免不必要的PW 支持检测来减少eSTR2的CPU 运行时间，实验结果表明：2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU 运行时间，在许多类实例上明显优于eS T R2和eS T R2w ．

结合互补度的基于扩展规则＃SA T问题求解方法1596-1604

摘要：＃SA T 问题又称模型计数（model counting ）问题是人工智能领域的研究热点之一，在人工智能领域被广泛应用。在对基于扩展规则的＃SAT 问题求解方法CER（counting models using extension rules）深入研究的基础上，提出一种结合互补度的＃SA T 问题求解方法。在计算给定子句集的模型个数时，利用SE‐Tree（set enumeration tree）形式化地表达计算过程，逐步生成需要计算的子句集合，并在SE‐T ree中添加终止结点，避免大部分含互补文字子句集合的生成，且不会因剪枝而导致求解不完备。提出互补度的概念，在扩展SE‐T ree结点时按照互补度由大到小的顺序扩展，较早地生成含互补文字且长度较小的子句集合，有效减少枚举树生成的结点个数，进而减少对子句集合判断是否含互补文字的计算次数。实验结果表明：与CER方法相比该方法效率较好，且进一步改进了CER方法在互补因子较低时求解效率低下的不足。

基于分布式低秩表示的子空间聚类算法1605-1611

摘要：针对基于低秩表示的子空间分割算法运算时间较长、聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（distributed low rank representation‐based sparse subspace clustering algorithm ，DLRRS），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前k个绝对值最大系数，其他系数置为0，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果。但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（scalable distributed low rank representation based sparse subspace clustering algorithm ，SDLRRS），如果有新增样本，可以利用前面的聚类结果对新增样本进行分类得到最后的结果。实验结果表明：所提2种子空间聚类算法不仅有效减少算法的运算时间，还提高了聚类的准确率，从而验证算法是有效可行的。