当期目录

• 2015年, 第05期　刊出日期：2015-05-25 上一期    下一期
  本期栏目： 论文

论文

细粒度任务并行GPU通用矩阵乘

张帅，李涛，王艺峰，焦晓帆，杨愚鲁

2015, 37(05): 847-856. doi:

摘要 ( 183 )   PDF (963KB) ( 293 )   　　

稠密线性代数运算对模式识别和生物信息等许多实际应用至关重要，而通用矩阵乘（GEMM）处于稠密线性代数运算的基础地位。在cuBLAS与MAGMA中，GEMM被实现为若干kernel函数，对大型GEMM计算能够达到很高的性能。然而，现有实现对批量的小型GEMM计算性能发挥则较为有限。而且，现有实现也不能在多个具有不同性能的GPU之间自动扩展并达到负载均衡。提出任务并行式GEMM（TPGEMM），用细粒度任务并行的方式实现批量矩阵乘和多GPU矩阵乘。一个或多个GEMM的计算能够被拆分为多个任务，动态地调度到一个或多个GPU上。TPGEMM避免了为批量矩阵乘启动多个kernel函数的开销，对批量矩阵乘能够取得显著高于cuBLAS与MAGMA的性能。在低开销细粒度任务调度的基础上，TPGEMM支持单个GEMM计算在多个GPU间的自动并行，在一台具有四个不同性能GPU的工作站上取得了接近100%的扩展效率。

实时微处理器体系结构综述

石伟，张明，郭御风，龚锐

2015, 37(05): 857-864. doi:

摘要 ( 155 )   PDF (605KB) ( 282 )   　　

实时应用已经成为嵌入式应用中一类快速崛起的典型应用。作为实时系统的核心部件，实时微处理器体系结构是微处理器领域的一个重要研究方向。与通用处理器追求最大吞吐量不同，实时处理器要求具有紧凑且可计算的最坏执行时间。传统的实时处理器往往采用较为简单的处理器结构，避免复杂结构引入执行时间的不确定性。随着实时应用对处理器性能需求越来越高，实时处理器正逐渐向多线程与多核结构发展。在多线程与多核处理器中，共享资源竞争导致实时系统的确定性变差，对实时处理器体系结构带来了更大挑战。对实时微处理器体系结构进行综述，首先从指令集、微体系结构、存储、I/O、任务调度等多个方面对传统实时处理器进行分析；然后分别对采用多线程与多核结构的高性能实时处理器展开分析；最后对几种商用实时处理器结构进行比较，总结实时处理器发展现状与未来发展趋势。

一种基于资源预分配的虚拟机软实时调度方法

丁晓波1,2，马中1,3，戴新发3，黄伟华3

2015, 37(05): 865-872. doi:

摘要 ( 137 )   PDF (1046KB) ( 216 )   　　

虚拟机技术作为云计算的重要技术之一，近年来得到广泛关注，但是由于虚拟机管理层的存在，导致语义鸿沟，使得实时应用程序、并发程序等在虚拟机上的运行性能受到影响。分析和研究了Xen虚拟机管理器的Credit调度算法，针对其在并发调度和软实时调度方面存在的不足，提出了改进调度算法,实现了算法的调度器原型。新的调度算法对软实时虚拟机进行Credit比例预分配，采用动态调度时间片机制，以nonworkconserving方式实现软实时任务周期调度，保障调度周期满足运行周期要求。通过区分并发和非并发软实时虚拟机，采取不同的调度策略，在满足资源利用率的基础上，确保实时任务的顺利运行。测试结果表明，该调度算法在对并发和非并发软实时任务调度上，具有良好的表现，较好满足了软实时应用调度需求。

基于TAM的企业云应用服务采纳模型及关键因素

石双元1,吴颖敏2,张泽中1，徐凯3

2015, 37(05): 873-881. doi:

摘要 ( 154 )   PDF (696KB) ( 259 )   　　

云计算将主导企业应用的未来已成为业界的共识，转向云计算是企业应用模式的颠覆性变化。企业用户需要采纳适合企业自身需求的云计算方案，具备评估采纳云应用服务风险的能力；而服务提供商则应提供满足不同企业需求的云应用服务。采用技术接受模型(TAM)的相关理论建立云应用服务技术接受模型，并运用模糊决策实验与实验评估法（DEMATEL）对所设计模型及实例数据进行分析，检验所设计的云应用服务技术接受模型及关键因素。研究结果表明，感知有用性、应用服务质量、社交影响对企业用户采纳产生关键影响。

分布式系统下的DAG任务调度研究综述

田国忠1,2,肖创柏1

2015, 37(05): 882-894. doi:

摘要 ( 531 )   PDF (889KB) ( 30842 )   　　

近年来随着网格、云计算工作流等分布式计算技术的发展，关于DAG（有向无环图）模型任务在分布式系统环境下的调度问题逐渐成为备受关注的研究热点。根据最新研究进展，对分布式系统下的DAG任务调度问题和有关技术进行了研究与讨论，主要包括四个方面：系统地描述了分布式系统和异构分布式系统的有关概念，异构分布式系统下的DAG任务调度问题、调度模型及其典型应用；对现有分布式系统下DAG任务调度的研究按照不同的方式进行了分类；探讨了多DAG共享异构分布式资源调度的研究现状；讨论了目前多DAG共享异构分布式资源调度研究存在的问题和未来可能的研究方向。

利用海量知识库实现实体标注的一种方法

汤效琴1 ，刘立波1 ，周涛2

2015, 37(05): 895-900. doi:

摘要 ( 141 )   PDF (601KB) ( 248 )   　　

互联网上聚集了大量的文本、图像等非结构化信息，RDF作为W3C提出的互联网上的资源描述框架，非常适合于描述网络上的非结构化信息，因此形成了大量的RDF知识库，如Freebase、Yago、DBPedia等。RDF知识库中包含丰富的语义信息，可以对来自网页的名字实体进行标注，实现语义扩充。将网页上的名字实体映射到知识库中对应实体上称作实体标注。实体标注包括两个主要部分：实体间的映射和标注去歧义。利用海量RDF知识库的特性，提出了一种有效的实体标注方法。该方法采用简单的图加权及计算解决实体标注的去歧义问题。该方法已在云平台上实现，并通过实验验证了其准确度和可扩展性。

一种改进的GPU虚拟化实施方法

陈志佳，朱元昌，邸彦强，冯少冲

2015, 37(05): 901-906. doi:

摘要 ( 223 )   PDF (748KB) ( 228 )   　　

当前虚拟桌面实施方法中，终端用户对3D图形处理能力越来越高的要求与虚拟机GPU处理能力之间的矛盾逐渐凸显。为解决上述问题，对GPU虚拟化的典型实施方法进行了研究。在对上述虚拟化技术进行分析的基础上，介绍了一种改进的基于设备独占法和API remoting法的虚拟化方案。利用Hypervisor创建两种模式的虚拟机，分别为一台父虚拟机(GVM)和多台子虚拟机(DVM)。GVM完全独占物理GPU，而DVM与物理GPU无直接交互关系。两种模式虚拟机共享GPU内存以及指令通道，DVM中的GPU调用指令传递至GVM，通过GVM对物理GPU进行快速调用，将调用结果返回到共享内存空间，进而呈现给用户。最后对改进的GPU虚拟化方法与典型虚拟化方法进行了对比与分析，总结了其中的优缺点，梳理了将来的研究重点。

基于Xeon Phi平台的波动方程叠前深度偏移

杨祥森1，金君2，王鹏1，马召贵1，亢永敢1

2015, 37(05): 907-913. doi:

摘要 ( 136 )   PDF (917KB) ( 208 )   　　

波动方程叠前深度偏移适用于强横向变速介质，是一种高精度成像方法，但其巨大的计算量阻碍了该技术的应用。Xeon Phi是一种全新的高性能计算设备，为波动方程叠前深度偏移方法的推广应用提供了新的技术支持。以裂步傅里叶算子为例，介绍了面向Xeon Phi平台的偏移算法移植和优化方法，即采用offload模式将计算核函数加载到Xeon Phi设备上，在Xeon Phi 协处理器上采用多线程方式，并且调整程序结构，充分利用SIMD矢量引擎提高向量化处理效率。扩展负载动态均衡的并行框架，形成了一套适用于大规模异构系统、基于Xeon Phi平台的波动方程叠前深度偏移软件。实际数据测试表明Xeon Phi平台可以极大地提高地震偏移处理效率，具有良好的可扩展性。

TMP-TIE：基于流量迁移预测的域间出口选择算法

赵丹1，阳贵刚1，胡晓峰2

2015, 37(05): 914-919. doi:

摘要 ( 129 )   PDF (1239KB) ( 190 )   　　

出口选择算法是域间路由策略的直接体现，并具备流量工程能力。针对可调域间路由出口选择算法引起的大幅流量迁移问题，以控制与转发分离的网络架构为背景，提出了基于流量迁移预测的出口选择算法TMP-TIE。该算法在TIE算法的基础上加入对流量迁移的预测和判定，避免出口变化引起的大幅流量迁移，降低对域间流量传输的影响。通过模拟实验比较了热土豆、TIE和TMP-TIE的性能，实验结果说明，TMP-TIE具有最小的路由敏感性和流量敏感性，能降低故障条件下的网络代价和网络拥塞的概率，有利于实现域间流量工程。

可分负载WSN的能耗最小负载调度研究

徐卫,刘端阳,暴占兵

2015, 37(05): 920-924. doi:

摘要 ( 113 )   PDF (573KB) ( 195 )   　　

减少无线传感器网络的能耗、延长网络生存周期已成为研究的热点之一。针对星型可分负载无线传感器网络的能耗最小问题，以典型可分负载调度为基础，提出了朴素的顺序调度算法（SSSA）及能耗与时间权衡调度算法（ETTS）。从理论与仿真角度分别证明了SSSA算法是在最短时间要求下的能耗最小负载调度算法，并通过仿真实验验证了两种算法对减少网络能耗、延长网络生存周期的有效性。实验表明：当网络拓扑对存活节点个数依赖较高时，应采用SSSA调度算法；当网络关心初始几轮负载处理能耗时，应采用ETTS算法。此外，随给定时间的增加，ETTS算法的能耗进一步减少。

基于跨层设计的认知无线Mesh网络拥塞反馈研究

陈燕燕

2015, 37(05): 925-929. doi:

摘要 ( 117 )   PDF (610KB) ( 236 )   　　

在认知无线Mesh网络中，由于信道状态变化导致的链路负载差异，网络拥塞成为影响认知无线Mesh网络系统性能的重要因素。针对这一问题，提出了基于最大最小公平策略的拥塞反馈算法。该算法通过综合分析基于随机搜索遗传算法的多速率编解码调制、多重数据流的信道分配机制，以及优化的路由选择三种机制的网络资源分配约束条件，来构建跨层模型，计算网络拥塞。同时，通过拥塞值反馈，实现对物理层、链路层和网络层的联合跨层优化，最大程度避免网络拥塞。仿真结果表明，该算法在网络发生拥塞时收敛更快，能够有效避免拥塞，均衡负载，并能提升网络吞吐量。

基于集成混合采样的软件缺陷预测研究

戴翔1，毛宇光1,2

2015, 37(05): 930-936. doi:

摘要 ( 137 )   PDF (697KB) ( 168 )   　　

对软件缺陷预测的不平衡问题进行了研究，提出了一种处理不平衡数据的采样方法，用来解决分类器因为样本集中的样本类别不平衡而造成分类器性能下降的问题。为了避免随机采样的盲目性，利用启发性的混合采样方法来平衡数据，针对少数类采用SMOTE过采样，对多数类采用KMeans聚类降采样，然后综合利用多个单分类器来进行投票集成预测分类。实验结果表明，混合采样与集成学习相结合的软件缺陷预测方法具有较好的分类效果，在获得较高的查全率的同时还能显著降低误报率。

基于图文法的程序流程图与源代码自动转换

朱云，曾晓勤，朱宁，刘禹锋

2015, 37(05): 937-945. doi:

摘要 ( 199 )   PDF (1324KB) ( 264 )   　　

程序流程图在整个软件工程的生命周期中发挥着非常重要的作用。在软件设计中，设计人员通常需要先根据算法从结构上画出程序执行流程图，然后再依据流程图写出相应的源程序代码；在分析和维护软件时，如果能先将源程序代码逆向转换成流程图，则可以有效地帮助分析程序结构。显然，若能让计算机自动地实现流程图与源程序代码之间的相互转换，将大量节省软件开发的人力资源和时间耗费。讨论了如何利用基于边的图文法EGG来自动地实现这种转换，并用具体例子展示了应用EGG图文法的归约和推导操作分别实现流程图的语法分析和流程图的逆向生成，前者可以完成从流程图自动生成源程序代码，而后者则可以从源程序代码自动生成流程图。

一种基于熵理论和中介真值度量的综合评价法

唐莹，张育平，陈海燕

2015, 37(05): 946-950. doi:

摘要 ( 207 )   PDF (440KB) ( 200 )   　　

综合评判问题在生活中随处可见，综合评价方法也有数十种之多。其中，基于模糊数学的中介真值度量方法是评价多指标对象的方法之一，是一种能够有效处理模糊现象的方法，也是一种主观赋权法。为了使评价结果更加客观，提出了一种基于熵理论和中介真值度量相结合的综合评价方法，将熵理论应用到一级指标权重的获取，利用基于专家打分的层次分析法计算出二级指标权重，有效减小了中介真值度量方法中完全主观计算权值所造成的误差。最后，通过应用于某地住宅项目的质量评估，并分别与中介真值度量方法和熵权法的评估结果进行比较分析，验证所提方法的可行性及有效性。

广义可能性互模拟及其逻辑刻画

张兴兴,邓楠轶,马占有,李永明

2015, 37(05): 951-957. doi:

摘要 ( 126 )   PDF (633KB) ( 168 )   　　

首先，给出了基于广义可能性测度的计算树逻辑的扩展GPoCTL*、计算树逻辑的约简GPoCTL－以及带回报的计算树逻辑GPoRCTL的语构和语义。在经典互模拟和广义可能性测度的基础上讨论了广义可能性互模拟及其相关性质。最后证明了GPoCTL、GPoCTL*和GPoCTL－公式与互模拟状态之间的等价关系。

面向时移电视类业务的组合测试实践研究

王燕,聂长海,张少兵

2015, 37(05): 958-966. doi:

摘要 ( 142 )   PDF (637KB) ( 240 )   　　

时移电视是三网融合的典型多媒体业务之一，具有功能多、操作复杂等特点。由于已有的测试方法尚未充分考虑系统中各参数的相互作用，因而较难发现系统某些功能缺陷和故障。以自适应组合测试方法学为基础，将其应用于机顶盒时移业务的测试。通过建立实用的交互式电视业务组合测试模型，设计测试用例并进行测试，最后对发现的故障进行定位。该实践研究为已有的组合测试理论和方法提供实证的同时，也发现了机顶盒时移业务存在的问题。

基于单亲遗传算法混合动态规划的电动汽车充电调度优化策略

陆坚毅1，杨超1，肖来元2，郑锐1

2015, 37(05): 967-973. doi:

摘要 ( 180 )   PDF (544KB) ( 261 )   　　

充电调度是电动汽车运营的一个重要内容，合理有效的充电策略在帮助运营商降低成本的同时还能减轻电网高峰时段的供电负担。从充电站运营商的角度出发，在实时电价和每个充电任务时间必须连续的假设下，建立了一个电动汽车充电成本最小模型，给出一个单亲遗传算法混合动态规划的两阶段常规充电调度算法。与电桩一旦闲置即刻分配车辆进行充电的策略以及传统单亲遗传算法相比较，该充电调度策略在电桩负载均衡的情况下有效降低了电费成本,说明了算法的有效性。此外，实验结果表现出了充电任务在多数相同时段聚集从而避开高电价时段的特征，说明充电策略对减轻高峰时段的电网压力也有一定帮助。

基于改进聚类分析的神经网络集成方法应用研究

杨红波1,郑剑2

2015, 37(05): 974-978. doi:

摘要 ( 210 )   PDF (517KB) ( 48309 )   　　

随着工业生产规模扩大、生产过程日趋复杂，人们对过程模拟提出了更高的要求。提出一种基于改进聚类分析的神经网络集成方法。首先，根据数据密度分布，改进传统K均值聚类分析中初始中心点选取的不足，对样本进行分类，扩大样本间的差异性；第二，运用具有快速学习能力的广义回归神经网络算法对各类样本建立个体神经网络并进行训练；第三，对所有样本增加构造补偿神经网络，进行误差补偿，以消除由于选择错误造成的输出误差；最后，根据计算得到的聚类中心对输入样本进行数值分析，选择输出个体神经网络，并与构造的补偿网络输出进行比较，最终实现神经网络集成。通过人工数据Sinc验证模型，此方法有效提高了模型精度，对提高过程模拟准确性提供了新途径。

基于筛选进化模型的指标体系建立方法

张恒巍，韩继红，张健，王晋东，寇广

2015, 37(05): 979-985. doi:

摘要 ( 149 )   PDF (734KB) ( 217 )   　　

针对评估指标的优选和权重分配问题，借鉴生物进化思想，构建筛选进化模型SEM，在筛选中计算基于欧氏距离的数据可信度和基于评价信息熵的指标适应度，根据指标适应度选择优势指标进入指标初始集，对劣势指标执行交叉和变异操作形成新的备选指标集。经过多轮筛选后建立指标初始集，并依据指标适应度进行权重分配。实例分析表明了该方法的可行性和有效性。

复杂环境下的遗留物检测算法

叶立仁，何盛鸿，赵连超

2015, 37(05): 986-992. doi:

摘要 ( 186 )   PDF (1176KB) ( 400 )   　　

针对在复杂环境下检测遗留物体的问题，提出一种有效的算法。首先，采用局部更新的混合高斯模型与改进的三帧差分法分别得到前景，通过比较得到目标候选区域，并进一步采用阴影消除与连通域分析分割得到暂时静止物团块。其次对达到静止时间阈值的团块采用方向梯度直方图（HOG）行人检测，在排除驻留行人的可能后将其标记为遗留物。最后对检测出的遗留物进行加速分割检测特征（FAST）局部特征匹配，以克服行人遮挡、光线变化对结果的影响。实验结果表明，本算法具有较高的准确性和处理速度，能较好地克服复杂环境中存在的干扰影响。

H.264帧间模式选择快速算法

杨琪，李小曼，罗超宇

2015, 37(05): 993-1000. doi:

摘要 ( 113 )   PDF (480KB) ( 217 )   　　

为尽可能降低H.264标准中的帧间模式选择时间复杂度，降低码率，提出一种快速帧间模式选择算法。算法利用目标检测技术中的Surendra算法以及所提出的速度特性和方向特性检测算法提前判定最佳候选模式，降低了帧间模式选择算法时间复杂度。实验结果表明，在保证重建视频质量的前提下，算法不仅能有效降低时间复杂度，还能降低码率；算法总体性能优于H.264标准算法和目前常见的帧间模式选择快速算法；对于含有大量静止背景或只含少量低速运动的视频，算法性能更加优越。

ICIC_Prediction:基于因果关系全局动态特性的预测方法

李岩1，王挺1，张晓艳2

2015, 37(05): 1001-1008. doi:

摘要 ( 101 )   PDF (508KB) ( 203 )   　　

因果关系的预测是因果关系研究的重要内容和主要应用。现有的很多预测方法以寻找最优预测方程或最小特征变量集合为目的，以简化计算。提出一种新的可用于处理政策干预的因果关系预测方法ICIC_Prediction，不局限于利用马尔科夫毯等特征变量集合，而是从因果关系网络结构出发，利用因果关系系统及其采样数据的动态全局特性，预测目标变量在当前采样中的取值。通过在NIPS 2008 “因果与预测”的评测会议上发布的四个不同类型的数据集上的对比实验，分析并展示了ICIC_Prediction方法的优势和特点。

基于信息增益的模糊K-prototypes聚类算法

欧阳浩1，王智文1，戴喜生2,刘智琦1

2015, 37(05): 1009-1014. doi:

摘要 ( 179 )   PDF (661KB) ( 217 )   　　

K-prototypes聚类算法结合了K-means算法和K-modes算法，可用于分析混合属性的数据对象。传统的K-prototypes聚类算法在计算数据对象的相异度时，未考虑各个属性对于最终聚类结果的影响程度，而现实世界中，各属性的重要程度是不同的。使用了信息论中信息增益的计算方法，来获得各个属性的权值。在计算各属性的差异度时，乘以这些权值，从而可以获得更为准确的聚类结果。为了增加算法处理模糊问题的能力，本算法引用了模糊理论，从而使其具有较好的抗干扰能力和处理不确定性问题的能力。通过对四个UCI数据集的聚类分析实验，表明了本算法的有效性。

广义可能性C均值聚类算法

文传军1，汪庆淼2

2015, 37(05): 1015-1018. doi:

摘要 ( 122 )   PDF (696KB) ( 196 )   　　

可能性C均值聚类算法（PCM）中模糊加权指标m要求大于1，通过对PCM算法的分析讨论，将PCM算法中模糊加权指标m设置为多个独立变量，且将其取值范围进行了扩展，称之为广义可能性C均值聚类（GPCM）。GPCM从理论上分析了加权指标m的扩展取值范围，并利用粒子群算法（PSO）对样本模糊隶属度进行估计。GPCM算法突破了PCM算法对参数m的约束。仿真实验验证了所提算法的有效性。

实时在线嵌入式系统复位设计

王迷迷，王斌，操凤萍，郑英

2015, 37(05): 1019-1023. doi:

摘要 ( 113 )   PDF (3177KB) ( 224 )   　　

实时在线嵌入式系统要求业务不间断、并便于在线诊断与维护。目前嵌入式设备的复位大多是通过看门狗全局复位，业务模块与管理模块复位耦合，无法实现在线诊断，可维护性差，不能满足实时在线系统的要求。针对这种情况，在分析实时在线嵌入式设备的电路特点和复位设计要求的基础上，提出了支持多源复位，具备临终遗言、复位原因监测、快速启动等功能，且业务处理与设备管理分离的新型复位方案。测试表明，该方案可保障业务持续或中断时间最短，并具备较好的可靠性和可维护性。关键词：

基于LabVIEW的孤堡输电杆塔基础偏移监测研究

陈新岗1,2，陈果1,李松1，倪志1,杨定坤1

2015, 37(05): 1024-1030. doi:

摘要 ( 84 )   PDF (1116KB) ( 262 )   　　

输电杆塔在输电网络中具有极其重要的地位，其稳定可靠性直接关系到电力网络的安全运行。为了准确掌握孤堡输电杆塔的运行状态，提出了以笛卡尔坐标系为基准的孤堡输电杆塔基础偏移算法。通过实际塔基结构构建模型进行实验分析和验证，结合实验数据设计了基于LabVIEW的孤堡输电杆塔基础位移监测系统。从得出的24组采样点与基础位移变化关系曲线可知，提出的算法对塔基支撑脚感应灵敏，系统对输电杆塔基础偏移具有较好的监测预警作用。

基于ARM的分布式多通道数据采集仪

陆建荣，单梁，汪静，李军，孙翌晨

2015, 37(05): 1031-1036. doi:

摘要 ( 106 )   PDF (906KB) ( 205 )   　　

设计以ARM9 S3C2451为核心处理器的分布式多通道数据采集仪。针对典型自动气象站的实际应用，设计并实现了外接设备驱动、ARM数据处理模块、ZigBee组网、数据通讯模块、A/D采样电路。阐明了数据采集仪嵌入式系统软件设计过程。经过测试，该数据采集仪在实际自动气象站应用中工作稳定，各项性能均能满足要求。