Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2016年 第53卷 第7期    出版日期:2016-07-01
综述
2016年绿色计算专题前言
刘志勇, 窦勇
2016, 53(7):  1423-1424. 
摘要 ( 819 )   HTML ( 0)   PDF (389KB) ( 653 )  
相关文章 | 计量指标
计算系统的能耗问题是影响计算系统本身发展、使用以及人类生存环境的重大问题,受到学术界、工业界等各方面的高度关注。本刊定于今年出版“绿色计算”专辑,为计算机系统的研究、开发、使用和管理等工作者提供一个展示计算系统节能创新技术的平台。本专辑征文发出后,获得计算机领域专家学者的广泛支持,收到大量投稿;稿件经过数十位专家的评审,遴选出9篇论文刊登于本专辑。本专辑刊登的文章涵盖了面向高能效的体系结构设计、重要应用的高能效实现以及高能效的系统资源管理和调度等方面的内容。
系统结构
基于可重构微服务器的高能效指纹比对方法
钱磊,赵锦明,彭达佳,李祥,吴东,谢向辉
2016, 53(7):  1425-1437.  doi:10.7544/issn1000-1239.2016.20160076
摘要 ( 965 )   HTML ( 0)   PDF (4765KB) ( 777 )  
相关文章 | 计量指标
大规模指纹应用需要强大的后端指纹比对计算能力作为支撑.基于可重构微服务器(reconfigurable micro server, RMS)技术,提出一种软硬协同的高效指纹比对方法,该方法充分发挥可重构混合核心计算架构的优势,采用优化定制的硬件加速部件对指纹比对算法中的计算密集部分进行加速.复杂控制流和离散访存较多的算法部分则以软件形式在通用计算核心上高效执行.在单个RMS计算节点上完成了算法原型的实现并进行了详细测试.测试结果表明:单个RMS节点上的指纹比对性能约为105万次秒,功耗仅为5 W.与相关工作相比,该性能是单个X86集群节点的15.5倍;能效是X86集群节点的583倍,是基于Tesla C2075的GPU服务器的5.4倍.与单纯的FPGA平台相比,基于RMS技术的实现方法更具灵活性和可扩展性,是未来构建大规模指纹比对系统的一种高效的技术解决方案.
DSP芯片中的高能效FFT加速器
雷元武,陈小文,彭元喜
2016, 53(7):  1438-1446.  doi:10.7544/issn1000-1239.2016.20160123
摘要 ( 1504 )   HTML ( 7)   PDF (3876KB) ( 841 )  
相关文章 | 计量指标
快速傅里叶变换(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-SMART
李彬,董德尊,吴际,夏军
2016, 53(7):  1447-1453.  doi:10.7544/issn1000-1239.2016.20160150
摘要 ( 761 )   HTML ( 1)   PDF (3553KB) ( 530 )  
相关文章 | 计量指标
片上网络(network-on-chip, NoC)消耗的功耗在整个芯片中所占比例不断增大,并且随着芯片工艺精度的提升和工作电压的不断降低,静态功耗占片上网络总功耗的比例也越来越大.当前芯片设计者致力于将未被使用的核设置为休眠状态来降低功耗.然而,即便是最前沿的芯片设计,当核休眠时与它连接的路由器都是保持在正常状态来进行报文传输.而与休眠核相连的片上网络路由器由于没有注入和吸收的报文,负载相对较低.在SMART(single-cycle multi-hop asynchronous repeated traversal)片上网络中,报文能够单周期从源路由器到目标路由器.基于单周期多跳旁路(SMART)技术,提出一种关闭低负载路由器虚通道的策略P-SMART,以在不影响网络性能的情况下节省片上网络功耗.实验结果表明:相对于SMART技术,P-SMART的性能损失不超过2%,而功耗节省13.4%.
PLUFS: 一种开销敏感的周期任务在线多处理器节能实时调度算法
张冬松,王珏,赵志峰,吴飞
2016, 53(7):  1454-1466.  doi:10.7544/issn1000-1239.2016.20160163
摘要 ( 707 )   HTML ( 0)   PDF (4387KB) ( 543 )  
相关文章 | 计量指标
现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果,但仍不能保证最优可调度性.针对嵌入式实时系统中不可忽视的状态切换开销,提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合,在每个TL面的初始时刻、任务结束执行时刻实现节能调度,在不违反周期任务集最优可调度性的前提下,达到实时约束与能耗节余的合理折中.经过理论证明和模拟实验,结果表明:PLUFS算法不仅保证了周期任务集的最优可调度性,而且节能效果整体优于现有算法,能耗节余比现有算法提高约10%~20%.
XOS:面向用户体验质量的高能效异构多核调度算法
宫晓利,于海洋,孙承君,李涛,张金,马捷
2016, 53(7):  1467-1477.  doi:10.7544/issn1000-1239.2016.20160113
摘要 ( 1362 )   HTML ( 0)   PDF (2548KB) ( 544 )  
相关文章 | 计量指标
智能移动设备的重要作用日益凸显,然而,对于性能的追求与有限电池容量的矛盾制约了产业的发展.异构多核处理器架构以其平衡性能与能耗的优势,成为一种新型的解决方案.用户体验优化是智能移动设备的重要设计目标.借助一个分段式的用户体验模型,提出了面向异构多核设备的XOS(experience oriented scheduler)调度算法.XOS能够跨层获取任务信息,识别与用户直接交互的任务组,保证这些任务的计算资源分配以保障用户体验,同时限制非交互性任务的计算资源以降低能耗.通过建立一套仿真系统验证了算法的有效性并进行了调整优化,然后在Odroid-XU3开发板Android系统中进行了原型实现和验证.实验结果表明:XOS算法对于不同类型的任务仅产生了2.7%~7.3%的用户体验下降,但节省了8%~48%的能量.
实时系统温度功耗管理的优化方法研究
李甜甜,于戈,宋杰
2016, 53(7):  1478-1492.  doi:10.7544/issn1000-1239.2016.20160134
摘要 ( 795 )   HTML ( 1)   PDF (2463KB) ( 502 )  
相关文章 | 计量指标
实时系统的能量受限特性、峰值温度约束以及实时任务的时间约束使其能耗问题备受学术界和工业界的关注,目前已有很多相关功耗管理研究.不考虑温度因素的传统功耗管理大多仅通过动态电压调节技术(dynamic voltage scaling, DVS)方法调度处理器的状态实现,然而随着芯片尺寸的不断缩减,处理器的功耗密度越来越大,温度与功耗之间的相互影响已不容忽视,由此在传统管理研究的基础上又衍生出了很多温度感知的新方法.1)对实时系统温度功耗管理依托的3个模型(任务模型、热模型和功耗模型)进行总结整理;2)根据是否考虑温度因素将现有研究分为温度无关的和温度感知的2类进行综述,后者又按面向单任务面向多任务进行分类;3)从具体机制、优化目标、优化效果以及调度时间等方面进行比较,分析现有研究的优缺点;4)指出未来研究方向.
分布式集装箱数据中心的绿色层次化管理
侯小凤,宋朋涛,唐伟超,李超,梁晓峣
2016, 53(7):  1493-1502.  doi:10.7544/issn1000-1239.2016.20160119
摘要 ( 1010 )   HTML ( 2)   PDF (2645KB) ( 493 )  
相关文章 | 计量指标
近几年,模块化数据中心(集装箱数据中心)因其高能效可拓展的特点而成为极具前景的IT基础设施解决方案.预定制的集装箱数据中心不仅可以被部署在传统仓库级数据中心设施中以支持容量扩展,还能够被部署在城市/郊外以支持物联网数据的本地处理.把传统集中建设和管理的数据中心与地理上分布的模块化数据中心结合起来,能够更加方便地利用本地绿色能源发电以及减少数据传输成本.针对目前涌现的地理上分布的集装箱式数据中心模块提出了一种新型分层化管理模式,该技术将分布式集装箱数据中心逻辑上划分成多个性质和功能不同的层级.一个中央调配系统被用来监控每个层级的集装箱数据中心并施加动态休眠机制以进一步提升数据中心的整体效能.小规模测试实验结果显示分层化管理机制能够提升12%~32%的数据中心整体能效,并且保持较高的服务性能.
时间约束的异构分布式系统工作流能耗优化算法
蒋军强,林亚平,谢国琪,张世文
2016, 53(7):  1503-1516.  doi:10.7544/issn1000-1239.2016.20160137
摘要 ( 940 )   HTML ( 3)   PDF (3863KB) ( 590 )  
相关文章 | 计量指标
针对现有异构分布式可变电压/频率(dynamic voltage/frequency scaling, DVFS)计算系统下具有时间约束的工作流能耗优化算法易陷入局部最优的问题,提出了一种新的全局能耗优化算法:反向蛙跳全局能耗感知算法,该算法利用工作流下界完成时间和约束时间之间存在的盈余,逐步从约束时间开始,以不同的跃度值向下界完成时间反向蛙跳,在此过程中基于局部最优解的判断不断调整跃度值直至蛙跳终点,同时保留该过程中工作流满足时间约束且任务运行能耗最小的调度序列.在此基础上利用处理器松弛时间回收技术,在保持任务间依赖关系和满足工作流时间约束的前提下,调整处理器运行电压/频率至更低的合适级别上,从而进一步降低工作流运行能耗.实验表明:该算法能显著降低工作流整体能耗,节能优势明显.
基于统计量的存储系统磁盘功耗建模方法研究
孙鉴,李战怀,张晓,王惠峰,赵晓南
2016, 53(7):  1517-1531.  doi:10.7544/issn1000-1239.2016.20160133
摘要 ( 780 )   HTML ( 1)   PDF (8104KB) ( 344 )  
相关文章 | 计量指标
大数据的迅猛发展导致数据中心的存储规模急剧扩张,由此引发的高能耗已经成为数据中心普遍面临的一个突出问题,磁盘类存储介质在数据中心耗能中所占的比例也在逐年增加,能耗建模在目前学者们的研究中越来越受到关注.精确的磁盘能耗模型不仅可以解决数据中心中的电力配套问题,而且为当前数据中心各种能耗管理技术体现更为精确的节能效果.提出了一种基于统计量的磁盘能耗预测模型,该模型弥补了传统细粒度模型产生的额外负载影响,同时获取了比传统粗粒度模型更佳的预测准确率.在实际应用中,该模型不需要分析记录复杂的磁盘内部活动细节,也不需要繁杂的参数采集,仅需要存储系统中宏观的统计量作为参数,且预测精度与细粒度模型近似.通过实验验证,该模型在能耗预测上的平均误差为3%,并且针对同步IO及异步IO都有较好的预测效果.此外,该模型还可以应用于各种在线系统的能耗预测.
网络技术
无线传感器网络中高能效的Bezier曲线路由算法
万少华,张引,
2016, 53(7):  1532-1543.  doi:10.7544/issn1000-1239.2016.20150172
摘要 ( 901 )   HTML ( 5)   PDF (4348KB) ( 663 )  
相关文章 | 计量指标
无线传感器网络在面向事件监测中蕴藏着巨大的应用价值,但由于传感器节点电源能量耗尽导致经常失效或废弃,因此研究无线传感器网络节能的算法具有重要意义.多路径路由沿多条路径分配能量负载,提高了网络的寿命和质量.需要强调的是均匀地调节更多节点参与到网络的路由任务能够保护某节点由于负载过重从而能量迅速流失直至节点失效.反之,所有的流量沿最短路径路由,路由不仅拥塞,而且沿源节点和汇聚节点对之间的最佳路由周围的节点由于过载最终缩短了网络寿命.从2个方面展开:1)提出了一种高能效的基于Bezier曲线的多路径路由算法(multipath routing algorithm based on Bezier curve, MPRB),并通过与传统的路由算法比较,实验数据验证了该算法能够获得更好的节能效果;2)基于查询区域划分设计的路由树个数与能耗关系比较了2种高能效的时空查询算法,并通过理论分析与实验仿真研究了查询区域划分方法、划分个数对能耗的影响,结果表明基于角度的查询区域划分方法是一种低能耗、面向绿色计算的方法.
人工智能
ICIC_Target:目标节点的局部因果关系网络的发现算法
李岩,王挺,刘万伟,张晓艳
2016, 53(7):  1544-1560.  doi:10.7544/issn1000-1239.2016.20148251
摘要 ( 707 )   HTML ( 0)   PDF (3119KB) ( 467 )  
相关文章 | 计量指标
因果关系的研究在于揭示自然规律的和人类社会发展本质及其规律,对人类长久以来的生产生活和科学研究有着非常重要的作用.目前,因果关系的研究受到前所未有的广泛关注,但仍存在诸多困难和挑战.致力于建立一个因果激励抑制模型以抽象地表示和解释因果的作用机制,并在此基础上提出用于目标节点的局部因果关系网络的自动发现方法框架ICIC和算法ICIC_Target.该方法不预先设定因果结构(如设定为无圈、隐含结构),并根据对因果关系本质的认识,利用初始变量(exogenous variables)和初始团树(IClique)的概念,在判定边和方向之前对变量进行粗略地排序,从而提高了因果关系网络发现的性能.在4个不同类型的数据集上实现了与多种经典方法,如HITON,IC,PC,PCMB等的对比实验,实验结果表明ICIC_Target方法适用范围广,有较好的鲁棒性,同时,从理论上分析证实了ICIC_Target方法具有较好的稳定性和较低的复杂度.
一种基于簇类进化的电力经济负荷分配优化算法
陈皓,潘晓英,张洁
2016, 53(7):  1561-1575.  doi:10.7544/issn1000-1239.2016.20150378
摘要 ( 757 )   HTML ( 5)   PDF (3748KB) ( 481 )  
相关文章 | 计量指标
电力经济负荷分配不仅能保证电力系统安全稳定地运行、延长机组使用寿命,还能节省能源,最大化电力企业的经济效益.此类问题可归为一种具有高维、不可微目标函数及多个非线性约束的数值优化问题.提出了一种新型的全局优化算法——簇类进化算法(cluster evolutionary algorithm, CEA),并将其应用于求解ELD问题.CEA利用聚类过程在进化个体间构建一定结构的连接关系,并利用这种虚拟的簇类化组织来协调和控制系统的优化计算过程,提高群体的问题空间搜索效率以及抗早熟能力.在仿真实验中13个典型测试函数和3个IEEE系统被用于对CEA的性能进行检验.实验数据显示CEA对13个约束数值优化问题可用较小的计算代价获得较高质量的解,而对3个测试系统的计算结果则要好于目前已报道的最佳解.实验数据的统计分析显示CEA是一种高效的数值优化算法,可作为一种有效的ELD问题求解方法.
支持向量机多项式光滑函数的误差理论研究
何文斌,刘群锋,熊金志
2016, 53(7):  1576-1585.  doi:10.7544/issn1000-1239.2016.20148462
摘要 ( 749 )   HTML ( 0)   PDF (1152KB) ( 434 )  
相关文章 | 计量指标
光滑函数在光滑支持向量机的理论中起着重要作用.1996年Chen等人提出一个支持向量机的光滑函数——Sigmoid函数的积分函数,并解决了该光滑函数的误差问题.2005~2009年,袁玉波、熊金志和刘叶青等人相继提出支持向量机的无穷多个多项式光滑函数和多项式光滑的支持向量机模型,但都未解决这类多项式光滑函数的误差函数问题.为此,用 Newton-Hermite 插值方法研究该问题.研究结果表明:1)用 Newton-Hermite 插值方法可计算这类光滑函数的误差函数,并给出了具体算法;2)这类误差函数有无穷多个,可用一个一般形式表示,并得到了这个一般形式;3)这类误差函数具有许多重要性质,并给出了严格证明.解决了支持向量机无穷多个多项式光滑函数的误差函数及其性质问题,建立了这类多项式光滑函数的误差理论,为研究支持向量机的光滑理论提供了基本的理论支持.
求解约束可满足问题的eSTR算法优化
王瑞伟,李占山,李宏博
2016, 53(7):  1586-1595.  doi:10.7544/issn1000-1239.2016.20150284
摘要 ( 784 )   HTML ( 1)   PDF (1385KB) ( 593 )  
相关文章 | 计量指标
表约束方法是1种外延式知识表示方法,每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组,直观易于理解,在约束程序中得到了深入的研究,这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中.但随着约束的增多及其元组集增大,占有的空间与相容性检测效率成了关键问题.eSTR是1个将STR扩展到高阶相容的算法,通过深入分析eSTR算法后发现有2种优化方式:PW\+{sup}数据结构和极小约束范围,同时证明了在极小约束范围上,约束网络仍然能够维持PWC+GAC,其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗,而PW\+{sup}数据结构能够通过避免不必要的PW支持检测来减少eSTR2的CPU运行时间,实验结果表明:2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU运行时间,在许多类实例上明显优于eSTR2和eSTR2w.
结合互补度的基于扩展规则#SAT问题求解方法
欧阳丹彤,贾凤雨,刘思光,张立明
2016, 53(7):  1596-1604.  doi:10.7544/issn1000-1239.2016.20150032
摘要 ( 649 )   HTML ( 0)   PDF (1344KB) ( 448 )  
相关文章 | 计量指标
#SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一,在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法CER(counting models using extension rules)深入研究的基础上,提出一种结合互补度的#SAT问题求解方法.在计算给定子句集的模型个数时,利用SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成需要计算的子句集合,并在SE-Tree中添加终止结点,避免大部分含互补文字子句集合的生成,且不会因剪枝而导致求解不完备.提出互补度的概念,在扩展SE-Tree结点时按照互补度由大到小的顺序扩展,较早地生成含互补文字且长度较小的子句集合,有效减少枚举树生成的结点个数,进而减少对子句集合判断是否含互补文字的计算次数.实验结果表明:与CER方法相比该方法效率较好,且进一步改进了CER方法在互补因子较低时求解效率低下的不足.
基于分布式低秩表示的子空间聚类算法
许凯,吴小俊,尹贺峰
2016, 53(7):  1605-1611.  doi:10.7544/issn1000-1239.2016.20148362
摘要 ( 1066 )   HTML ( 1)   PDF (1536KB) ( 610 )  
相关文章 | 计量指标
针对基于低秩表示的子空间分割算法运算时间较长、聚类的准确率也不够高,提出一种基于分布式低秩表示的稀疏子空间聚类算法(distributed low rank representation-based sparse subspace clustering algorithm, DLRRS),该算法采用分布式并行计算来得到低秩表示的系数矩阵,然后保留系数矩阵每列的前k个绝对值最大系数,其他系数置为0,用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵,接着用谱聚类得到聚类结果.但是其不具备增量学习功能,为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法(scalable distributed low rank representation based sparse subspace clustering algorithm, SDLRRS),如果有新增样本,可以利用前面的聚类结果对新增样本进行分类得到最后的结果.实验结果表明:所提2种子空间聚类算法不仅有效减少算法的运算时间,还提高了聚类的准确率,从而验证算法是有效可行的.
软件技术
面向软件非功能需求的软件过程建模方法
张璇,李彤,王旭,代飞,谢仲文,于倩
2016, 53(7):  1612-1630.  doi:10.7544/issn1000-1239.2016.20150112
摘要 ( 918 )   HTML ( 9)   PDF (4290KB) ( 608 )  
相关文章 | 计量指标
软件非功能需求决定了软件的质量,而软件质量需求的满足很大程度上依赖于软件开发或演化时所使用的过程.从软件过程的角度出发,总结凝练满足软件非功能需求的过程策略,使用面向方面方法,提出面向软件非功能需求的软件过程建模方法,从软件过程的方法和技术角度保证软件的质量需求贯穿软件生命周期全过程得以实现.首先,基于对软件非功能需求的分析,总结满足非功能需求的过程策略,构建过程策略知识库,在此基础上,使用面向方面方法将过程策略定义的活动封装为方面,并通过方面合成机制织入基本软件过程模型,既实现了基本模型与面向非功能需求活动间的分离,又实现了软件生命周期全过程注入有助于软件质量提升的活动,其中,重点解决了方面织入基本模型的冲突控制及检测问题;另外,通过开发面向非功能需求的软件过程建模辅助工具NPAT(non-functional requirements-oriented processes aided tool),为过程建模及冲突控制提供了技术支持;最后,通过在案例中使用所提出的理论、方法和技术,说明所提出的理论和方法是可行的,开发的辅助工具是有效的,可以通过非功能需求定制的软件生命周期过程达到提升软件质量的目标.
系统结构
基于顶点加权的介度中心近似算法研究
王敏,王蕾,冯晓兵,曹宝香
2016, 53(7):  1631-1640.  doi:10.7544/issn1000-1239.2016.20148355
摘要 ( 751 )   HTML ( 4)   PDF (2554KB) ( 554 )  
相关文章 | 计量指标
介度中心(betweenness centrality, BC)是衡量网络节点重要程度的一个广泛使用的指标,最快的介度中心算法需要计算n次单源最短路径,时间复杂度是O(V×E).介度中心算法的瓶颈就在于计算量太大,导致运行时间太长,无法在实际中应用,因此需要从近似算法的角度降低介度中心算法的计算量.目前介度中心近似算法在计算自然图时对计算量的降低并不显著.为了进一步降低介度中心算法的计算量,提出了一种基于顶点加权的介度中心近似算法,该算法采用顶点加权的方式将多次重复计算过程累加到一次计算过程上,结合选择高影响力源点的方法可以大大降低介度中心算法的计算量,加速比平均达到了25倍,并且最大误差百分比小于0.01%.
截止时限为关键参数的混合关键级实时任务调度研究
黄丽达,李仁发
2016, 53(7):  1641-1647.  doi:10.7544/issn1000-1239.2016.20150331
摘要 ( 869 )   HTML ( 1)   PDF (1377KB) ( 525 )  
相关文章 | 计量指标
混合关键级系统 (mixed criticality system)的研究源于在单一平台上执行多个重要级不同的功能,当前混合关键级调度研究,一般考虑高关键级任务在不同关键级运行模式表现为或周期或计算时间不同,即以任务释放时间间隔和最差情况执行时间为关键参数.但截至时限(dendline)也是实时任务的重要时间参数,尤其是对硬实时任务,以截止时限作为关键参数进行相应混合关键级调度的研究尚是空白.针对此问题,以截止时限作为关键参数,以响应时间分析为基础,对单处理器平台中的混和关键级任务的可调度性进行分析,并提出了一种预提升关键级的调度算法RCLA(raising critical-level in advance),在低关键级运行模式下,高关键级低优先级任务有限度地提前抢占低关键级高优先级任务的执行,既确保了满足高关键级任务在不同关键级运行模式下的截止时限,也让尽可能多的任务可以被调度执行,使得计算资源得以充分利用.仿真结果验证了RCLA算法的有效性.