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

当期目录

2016年 第53卷 第6期    出版日期:2016-06-01
系统结构
基于2阶段同步的GPGPU线程块压缩调度方法
张军,何炎祥,沈凡凡,江南,李清安
2016, 53(6):  1173-1185.  doi:10.7544/issn1000-1239.2016.20150114
摘要 ( 1008 )   HTML ( 0)   PDF (4900KB) ( 659 )  
相关文章 | 计量指标
通用图形处理器(general purpose graphics processing unit, GPGPU)在面向高性能计算、高吞吐量的通用计算领域的应用日益广泛,它采用的SIMD(single instruction multiple data)执行模式使其能获得强大的并行计算能力.目前主流的通用图形处理器均通过大量高度并行的线程完成计算任务的高效执行.但是在处理条件分支转移的控制流中,由于通用图形处理器采用串行的方式顺序处理不同的分支路径,使得其并行计算能力受到影响.在分析讨论前人针对分支转移处理低效的线程块压缩重组调度方法的基础上,提出了2阶段同步的线程块压缩重组调度方法TSTBC(two-stage synchronization based thread block compaction scheduling),通过线程块压缩重组适合性判断逻辑部件,分2个阶段对线程块进行压缩重组有效性分析,进一步减少了无效的线程块压缩重组次数.模拟实验结果表明:该方法较好地提高了线程块的压缩重组有效性,相对于其他同类方法降低了对线程组内部数据局部性的破坏,并使得片上一级数据cache的访问失效率得到有效降低;相对于基准体系结构,系统性能提升了19.27%.
异构系统双关键级分布式功能的动态调度
刘樑骄,谢国琪,李仁发,杨柳,刘彦
2016, 53(6):  1186-1201.  doi:10.7544/issn1000-1239.2016.20150175
摘要 ( 839 )   HTML ( 0)   PDF (5939KB) ( 618 )  
相关文章 | 计量指标
异构分布式嵌入式系统是由多种不同关键级功能组成的混合关键级系统,且每个功能又是由多个具有优先级约束的任务组成的分布式功能.异构分布式嵌入式系统的混合关键级调度在性能与时间约束上面临严重的冲突.如何提高系统总体性能,并仍然确保高关键级功能的实时性,在性能与实时性上取得合理的权衡则成为研究的主要优化问题.提出公平策略的动态双关键级任务调度算法F_DDHEFT(fairness on dynamic dual-criticality heterogeneous earliest finish time)以提高系统的整体性能;提出关键级策略的动态双关键级任务调度算法C_DDHEFT(criticality on dynamic dual-criticality heterogeneous earliest finish time) 以满足高关键级功能的实时性;提出时限时距策略的动态双关键级任务调度算法D_DDHEFT(deadline-span on dynamic dual-criticality heterogeneous earliest finish time),在满足高关键级功能实时性的基础上,提高系统的整体性能,最终在性能与时间约束上取得合理的权衡.实例分析和实验结果验证了D_DDHEFT算法的优越性.
DLPF:基于异构体系结构的并行深度学习编程框架
王岳青,窦勇,吕启,李宝峰,李腾
2016, 53(6):  1202-1210.  doi:10.7544/issn1000-1239.2016.20150147
摘要 ( 1196 )   HTML ( 7)   PDF (4335KB) ( 1120 )  
相关文章 | 计量指标
深度学习在机器学习领域扮演着十分重要的角色,已被广泛应用于各种领域,具有十分巨大的研究和应用前景.然而,深度学习也面临3方面的挑战:1)现有深度学习工具使用便捷性不高,尽管深度学习领域工具越来越多,然而大多使用过程过于繁杂,不便使用;2)深度学习模型灵活性不高,限制了深度学习模型发展的多样性;3)深度学习训练时间较长,超参数搜索空间大,从而导致超参数寻优比较困难.针对这些挑战,设计了一种基于深度学习的并行编程框架,该框架设计了统一的模块库,能可视化地进行深度学习模型构建,提高了编程便捷性;同时在异构平台对算法模块进行加速优化,较大程度减少训练时间,进而提高超参数寻优效率.实验结果表明,该编程框架可以灵活构建多种模型,并且对多种应用取得了较高的分类精度.通过超参数寻优实验,可以便捷地获得最优超参数组合,从而推断各种超参数与不同应用的联系.
众核处理器片上网络的层次化全局自适应路由机制
张洋,王达,叶笑春,朱亚涛,范东睿,李宏亮,谢向辉
2016, 53(6):  1211-1220.  doi:10.7544/issn1000-1239.2016.20150149
摘要 ( 971 )   HTML ( 1)   PDF (3494KB) ( 572 )  
相关文章 | 计量指标
Mesh和环拓扑结构以其实现简单、易于扩展的特点成为众核处理器片上网络应用最为广泛的拓扑结构.应用于Mesh结构中的健忘型路由算法在网络流量较大时影响片上网络的负载均衡,表现在降低吞吐量和增大数据包延迟.自适应算法中的本地自适应算法和区域自适应算法均存在不同程度的短视现象,不适合大规模的Mesh结构,而目前全局自适应算法又由于路由计算量大而速度缓慢.提出一种新的层次化全局自适应路由机制,包括一个全局拥塞信息传播网络Roof-Mesh和一个层次化全局自适应路由算法(global hierarchical adaptive routing algorithm, GHARA).通过全局拥塞信息传播网络得到拥塞信息,GHARA采用全网分区逐级计算路由的方式,减少了全局路由的计算步骤,从而减少了平均数据包延迟、提升了饱和带宽.实验结果表明GHARA表现优于其他区域和全局自适应路由算法.在人工注入通信模式下,8×8 Mesh平均饱和带宽比全局自适应算法GCA提高10.7%,16×16 Mesh平均饱和带宽比全局自适应算法GCA提高14.7%.在运行真实测试程序集SPLASH-2模式下,数据包延迟最高比GCA提高40%,平均提升14%.
一种缓存数据流信息的处理器前端设计
刘炳涛,王达,叶笑春,张浩,范东睿,张志敏
2016, 53(6):  1221-1237.  doi:10.7544/issn1000-1239.2016.20150317
摘要 ( 816 )   HTML ( 3)   PDF (5802KB) ( 801 )  
相关文章 | 计量指标
为了能够同时发掘程序的线程级并行性和指令级并行性,动态多核技术通过将数个小核重构为一个较强的虚拟核来适应程序多样的需求.通常这种虚拟核性能弱于占有等量芯片资源的原生核,一个重要的原因就是取指、译码和重命名等流水线的前端各阶段具有串行处理的特征较难经重构后协同工作.为解决此问题,提出了新的前端结构——数据流缓存,并给出与之配合的向量重命名机制.数据流缓存利用程序的数据流局部性,存储并重用指令基本块内的数据依赖等信息.处理器核利用数据流缓存能更好地发掘程序的指令级并行性并降低分支预测错误的惩罚,而动态多核技术中的虚拟核通过使用数据流缓存旁路传统的流水线前端各阶段,其前端难协同工作的问题得以解决.对SPEC CPU2006中程序的实验证明了数据流缓存能够以有限代价覆盖大部分程序超过90%的动态指令,然后分析了添加数据流缓存对流水线性能的影响.实验证明,在前端宽度为4条指令、指令窗口容量为512的配置下,采用数据流缓存的虚拟核性能平均提升9.4%,某些程序性能提升高达28%.
面向监听一致性协议的并发内存竞争记录算法
朱素霞,陈德运,季振洲,孙广路,张浩
2016, 53(6):  1238-1248.  doi:10.7544/issn1000-1239.2016.20150100
摘要 ( 888 )   HTML ( 1)   PDF (2922KB) ( 503 )  
相关文章 | 计量指标
内存竞争记录是解决多核程序执行不确定性的关键技术,然而现有点到点的内存竞争记录机制带来的硬件开销大,难以应用到实际的片上多核处理器系统中.以降低点到点内存竞争记录方式的硬件开销为出发点,为采用监听一致性协议的片上多核处理器(chip multiprocessor, CMP)系统设计了基于并发记录策略的点到点内存竞争记录算法.该记录算法将两两线程间点到点的内存竞争关系扩展到所有线程,采用分布式记录方法为每个线程记录一个由内存竞争关系的一方构成的内存竞争日志;重演时采用简化的生产者消费者模型,确保了确定性重演的实现,有效降低了硬件消耗和带宽开销.在8核处理器系统中的仿真结果表明,该并发式点到点内存竞争记录算法为每个处理器核添加硬件资源约171B,每千条内存操作指令记录日志大小约2.3B,记录和重演阶段均添加不到1.5%的带宽开销.
软件技术
基于CUPTI接口的典型GPU程序负载特征分析
郑祯,翟季冬,李焱,陈文光
2016, 53(6):  1249-1262.  doi:10.7544/issn1000-1239.2016.20148354
摘要 ( 1081 )   HTML ( 3)   PDF (6942KB) ( 716 )  
相关文章 | 计量指标
基于图形处理器(graphics processing unit, GPU)加速设备的高性能计算机已经成为目前高性能计算领域的一个重要发展趋势.然而,在当前的GPU设备上开发高效的并行程序仍然是一件非常复杂的事情.针对这一问题,1)总结了影响GPU程序性能的5类关键性能指标;2)采用NVIDIA公司提供的CUPTI底层接口,设计并实现了一套GPU程序性能分析工具集,该工具集可以有效地分析GPU程序的性能行为;3)采用该工具集对著名的GPU评测程序集Rodinia中的17个程序和一个真实应用程序进行了负载特征分析.总结出常见性能瓶颈的典型原因,并给出一些开发高效GPU程序的建议.
基于YARN集群的计算加速部件扩展支持
李钦,朱延超,刘轶,钱德沛
2016, 53(6):  1263-1270.  doi:10.7544/issn1000-1239.2016.20148351
摘要 ( 970 )   HTML ( 3)   PDF (2880KB) ( 608 )  
相关文章 | 计量指标
以GPU和Intel MIC为代表的计算加速部件已在科学计算、图形图像处理等领域得到了广泛的应用,其在基于云平台的高性能计算及大数据处理等方向也具有广泛的应用前景.YARN是新一代Hadoop分布式计算框架,其对计算资源的分配调度主要针对CPU,缺少对计算加速部件的支持.在YARN中添加计算加速部件需要解决多个难点,分别是计算加速部件资源如何调度以及异构节点间如何共享问题、多个任务同时调用计算加速部件而引起的资源争用问题和集群中对计算加速部件的状态监控与管理问题.为了解决这些问题,提出了动态节点捆绑策略、流水线式的计算加速部件任务调度等,实现了YARN对计算加速部件的支持,并通过实验验证了其有效性.
基于排队理论的动态任务调度模型及容错
何王全,魏迪,权建校,吴伟,漆锋滨
2016, 53(6):  1271-1280.  doi:10.7544/issn1000-1239.2016.20148445
摘要 ( 1186 )   HTML ( 9)   PDF (2600KB) ( 1307 )  
相关文章 | 计量指标
高效的动态任务调度和容错机制是高性能计算面临的挑战之一,已有的方法难以高效扩展到大规模环境.针对该问题,提出了基于N层排队理论的高可扩展动态任务调度模型,为程序员提供简洁的并行编程框架,有效降低了编程负担;使用泊松过程相关理论分析了任务申请的平均等待时间,通过给定的阈值进行决策分层;结合局部感知的轻量级降级模型,可有效降低大规模并行课题的容错开销,提高系统的可用性.Micro Benchmark在神威蓝光32768核环境下测试表明,对于平均执行时间为3.4s的短任务,基于N层排队理论的动态任务调度模型可扩展性很好,调度开销是传统模型的7.2%;药物软件DOCK在16384核环境下的整体性能比该软件原有的任务调度提升34.3%;局部感知的轻量级降级模型具有故障后损失小的特点,DOCK的测试表明比传统容错方法执行时间减少3.75%~5.13%.
网络技术
命名数据网络中一种基于节点分类的数据存储策略
黄胜,滕明埝,吴震,许江华,季瑞军
2016, 53(6):  1281-1291.  doi:10.7544/issn1000-1239.2016.20148097
摘要 ( 851 )   HTML ( 0)   PDF (3490KB) ( 611 )  
相关文章 | 计量指标
缓存是命名数据网络(named data networking, NDN)有别于传统网络最突出的特性之一,NDN中默认所有节点都具有缓存所有经过数据的功能.这种“处处缓存”策略导致网内大量冗余数据的产生,使网内缓存被严重浪费.针对上述问题,首次提出了一种基于节点分类(based on node classification, BNC)的数据存储策略.基于节点位置的不同,将数据返回客户端所经过的节点分为“边缘”类节点与“核心”类节点.当数据经过“核心”类节点时,通过权衡该类节点的位置与数据在不同节点的流行度分布,将数据存储在对其他节点最有利的节点中;当数据经过“边缘”类节点时,通过该数据流行度来选择最有利于客户端的位置.仿真结果表明,提出的策略将有效提高数据命中率,减少数据请求时延和距离.
基于控制中心的新型SAN架构的设计与实现
陆一飞,张震伟,陶军,唐玲
2016, 53(6):  1292-1305.  doi:10.7544/issn1000-1239.2016.20150025
摘要 ( 764 )   HTML ( 2)   PDF (4393KB) ( 546 )  
相关文章 | 计量指标
随着互联网技术的快速发展,数据的爆炸式增长,存储系统的软硬件紧耦合设计严重地限制了存储技术的发展,也越来越无法满足移动互联网和大数据时代下对存储系统快速、多变的需求.软件定义网络(storage defined network, SDN)作为一种新的网络架构,更适合下一代数据中心的发展.在SDN思想基础上,提出了一种基于控制中心的新型SAN架构(controller-based SAN, CSN),该架构分离FC交换机的协议控制面和数据面,将FC协议的控制功能和分布式服务功能部署在控制器中,随后详细阐述了该架构的控制器设计、通信机制和整体机制的设计与实现.在CSN基础上,又提出了按需可用带宽优先路由协议.最后,通过实际开发环境验证该架构的可行性.通过实验测试,得出CSN下服务器能够更快地与存储服务器建立连接,并且存储网络具有更高的吞吐量、更快的收敛性、更好的可靠性和可扩展性,此外,还对中心控制器的CPU、内存和带宽进行压力测试.
基于合作博弈的数据中心骨干网带宽分配策略
孟飞,兰巨龙,胡宇翔
2016, 53(6):  1306-1313.  doi:10.7544/issn1000-1239.2016.20148400
摘要 ( 750 )   HTML ( 0)   PDF (2041KB) ( 626 )  
相关文章 | 计量指标
数据中心(data center, DC)之间通过部署流量工程来提高连接各个数据中心骨干网的利用率,虽然效率提升显著,但对不同类型汇聚流的带宽分配的公平性没有考虑.将多个汇聚流对带宽分配的竞争行为建模为一个合作博弈,通过寻求此博弈的纳什谈判解(Nash bargaining solution, NBS)来确定优化的带宽分配策略CGBA(cooperation game based bandwidth allocation),权衡各汇聚流的最小带宽保证与带宽分配的公平性.在Mininet平台上进行实验仿真并和典型的带宽分配策略对比,结果表明CGBA不但可保证各汇聚流的最小带宽需求,还确保了各类流对带宽资源竞争的公平性.
基于种群动力学的P2P IPTV系统内容污染扩散模型
王海舟,陈兴蜀,杜敏,王文贤
2016, 53(6):  1314-1324.  doi:10.7544/issn1000-1239.2016.20150066
摘要 ( 969 )   HTML ( 0)   PDF (3003KB) ( 437 )  
相关文章 | 计量指标
近年来,随着P2P(peer-to-peer)技术的日益成熟,基于P2P技术的IPTV(Internet protocol television)系统逐渐流行并取得了巨大成功,吸引了来自全球产业界和学术界的密切关注.但是,由于P2P IPTV系统自身特有的分布性、匿名性、快速传播性、用户规模大等特点使得其更容易成为攻击的目标.在对P2P IPTV内容污染攻击过程和节点在内容污染攻击中的行为特征进行详细分析的基础上,建立了一个具有种群动力学特征的P2P IPTV系统内容污染扩散模型,该模型充分考虑了在真实世界的P2P IPTV系统内容污染攻击中用户的持续观看行为、用户的加入和离开行为对频道用户规模动态演变的影响.实验结果表明,提出的P2P IPTV内容污染扩散模型可以有效和准确地刻画真实内容污染攻击场景中污染攻击对频道的在线节点规模动态演变和节点离开行为的影响情况.
稠密RFID标签环境下捕获感知贝叶斯标签估计
王阳,吴海锋,曾玉
2016, 53(6):  1325-1331.  doi:10.7544/issn1000-1239.2016.20148405
摘要 ( 621 )   HTML ( 0)   PDF (1168KB) ( 573 )  
相关文章 | 计量指标
动态帧时隙Aloha算法是一种常用的被动式射频识别(radio frequency identification, RFID)标签防冲突算法.在该算法中,帧长需要动态设置以保证较高的识别效率.通常,帧长的设置与标签数和捕获效应的发生概率相关.传统的估计算法虽然可以估计出标签数和捕获效应的发生概率,但是在稠密RFID标签环境下,标签数可能远大于初始帧长,其估计误差会显著增加.为了解决传统算法无法应用于稠密RFID标签环境的问题,提出了捕获感知贝叶斯标签估计,并且给出了非等长时隙下最优帧长的设置方法.从实验结果来看,提出算法的估计误差在稠密RFID标签环境下显著低于传统算法,而且根据估计结果设置帧长所得到的识别效率也高于传统算法.
软件技术
基于云架构的交通感知数据集成处理平台
赵卓峰,丁维龙,韩燕波
2016, 53(6):  1332-1341.  doi:10.7544/issn1000-1239.2016.20150458
摘要 ( 940 )   HTML ( 2)   PDF (2084KB) ( 575 )  
相关文章 | 计量指标
海量、多源、不间断的交通感知数据环境下,如何提供集成化的交通感知数据处理支持是多样化交通应用实施中的难点.现有的通用计算框架及平台由于缺少对具有时空相关等特征的交通感知数据和应用间交通感知数据共享的支持,使得交通感知数据处理应用的开发存在较高的复杂性并且易于造成大量重复的数据跨节点传输而影响应用性能.针对此问题,通过分析交通感知数据及其处理需求特征,提出一种基于可跨应用共享的时空数据对象的交通感知数据处理模型,通过引入时空数据对象这一新的概念抽象并提供易并行划分的时空数据对象组织及共享支持,实现分布计算中对时空型交通感知数据的优化管理.在此基础上,设计并实现了交通感知数据集成处理平台.通过实际应用和基于真实交通数据的实验测试表明:该平台相对于传统的交通感知数据处理方法及系统在性能及扩展性等方面均具有一定的优势.
基于非完全信息博弈的云资源分配模型
苑迎,王翠荣,王聪,任婷婷,刘冰玉
2016, 53(6):  1342-1351.  doi:10.7544/issn1000-1239.2016.20150062
摘要 ( 822 )   HTML ( 0)   PDF (2945KB) ( 626 )  
相关文章 | 计量指标
针对云环境下相互竞争的多租赁市场运营模式,以提高资源供求双方利益及资源能效为目标,提出了一种基于非完全信息博弈的云资源分配模型.首先利用隐Markov理论根据服务提供商(service provider, SP)的历史资源需求情况预测其当前出价,以预测值为基础构建动态博弈定价模型,激励服务提供商选择符合整体利益的最优购买出价策略,从而实现利益最大化;然后设计了支持多服务提供商、多种资源同时分配,以分类资源单位价格进行分配的资源分配模型,保证了基础设施提供商(infrastructure provider, INP)的收益最优.仿真实验表明:在博弈定价模型中,预测价格与实际交易价格相近且交易价格低于实际估值,能够保障服务提供商的利益;基于不同种类资源单价的分配模型能够增加基础设施提供商的收益.
信息处理
增量的动态社会网络匿名化技术
郭彩华,王斌,朱怀杰,杨晓春
2016, 53(6):  1352-1364.  doi:10.7544/issn1000-1239.2016.20140695
摘要 ( 867 )   HTML ( 0)   PDF (3816KB) ( 526 )  
相关文章 | 计量指标
随着社会网络的快速发展和普及,如何保护社会网络中的敏感信息已成为当前数据隐私保护研究领域的热点问题.对此,近年来出现了多种社会网络匿名化技术. 现有的匿名技术大多把社会网络抽象成简单图,然而实际生活中存在大量增量变化的社会网络,例如email通信网络,简单图并不能很好地刻画这种增量变化,因此,将社会网络抽象成增量序列具有现实意义.同时,在实际生活中大部分网络是带有权重信息的,即很多社会网络以加权图的形式出现,加权图与简单图相比携带了更多社会网络中的信息,也会带来更多的隐私泄露. 将增量的动态社会网络抽象成一个加权图的增量序列. 为了匿名加权图增量序列,提出了加权图增量序列k-匿名隐私保护模型,并设计了基于权重链表的baseline匿名算法WLKA和基于超图的匿名算法HVKA来防止基于结点标签和权重链表的攻击. 最后,通过在真实数据集上的大量测试,证明了WLKA算法能够保证加权图增量序列隐私保护的有效性,HVKA算法则在WLKA的基础上更好地保留了原图的结构性质并提高了权重信息的可用性,同时还降低了匿名过程的时间代价.
基于兴趣匹配的机会社会网络消息分发机制
张淯舒,王慧强,冯光升,吕宏武
2016, 53(6):  1365-1375.  doi:10.7544/issn1000-1239.2016.20148412
摘要 ( 832 )   HTML ( 4)   PDF (3084KB) ( 649 )  
相关文章 | 计量指标
机会社会网络(opportunistic social networks)能够利用节点移动创造的相遇机会,在缺乏持续端到端连接的网络中,为用户提供稳定的消息分发途径,但在消息分发效率以及用户体验方面存在不足.为提高消息分发系统的性能、改善网络用户体验,提出一种基于节点兴趣匹配的机会社会网络分发机制.通过引入混合结构的机会社会网络分发系统解决网络拓扑信息获取不全与节点计算能力不足的问题;从节点行为规律与兴趣爱好2方面对网络进行分析,并提出一种用于复杂关系数据分析的联合聚类方法;针对用户需求,设计消息属性与节点兴趣匹配优先的消息分发策略.仿真结果表明,该机制能够在投递率、投递时延、缓存占用率等方面提升网络性能,且具有较高的分发效率、覆盖率与兴趣匹配度.
一种半监督的局部扩展式重叠社区发现方法
陈俊宇,周刚,南煜,曾琦
2016, 53(6):  1376-1388.  doi:10.7544/issn1000-1239.2016.20148339
摘要 ( 990 )   HTML ( 1)   PDF (3221KB) ( 804 )  
相关文章 | 计量指标
重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想,不仅利用网络的拓扑结构信息,还充分地利用网络节点的属性信息.首先将网络节点的属性信息转化为成对约束,并根据成对约束修正网络的拓扑结构,使网络中的社区结构更加明显;然后基于网络节点的度中心性选取种子节点,得到分散的、局部节点度大的种子作为初始社区;再采用贪心策略将初始社区向邻居节点扩展,得到局部连接紧密的社区;最后检测并合并冗余社区,得到高覆盖率的社区发现结果.在模拟网络数据和真实网络数据上与当前有代表性的基于局部扩展的重叠社区发现算法进行了对比实验,结果表明SLEM方法在稀疏程度不同的网络上均能发现较高质量的重叠社区结构.
一种基于多元社交信任的协同过滤推荐算法
王瑞琴,蒋云良,李一啸,楼俊钢
2016, 53(6):  1389-1399.  doi:10.7544/issn1000-1239.2016.20150307
摘要 ( 1188 )   HTML ( 3)   PDF (2115KB) ( 873 )  
相关文章 | 计量指标
协同过滤推荐是当前最成功的个性化推荐技术之一,但是传统的协同过滤推荐算法普遍存在推荐性能低和抗攻击能力弱的问题.针对以上问题,提出了一种基于多元化社交信任的协同过滤推荐算法CF-CRIS (collaborative filtering based on credibility, reliability, intimacy and self-orientation).1)借鉴社会心理学中的信任产生原理,提出基于多个信任要素(可信度、可靠度、亲密度、自我意识导向)的信任度计算方法;2)深入研究社交网络环境中各信任要素的识别、提取和量化方法;3)基于用户间的综合信任度选取可信邻居,完成对目标用户的个性化推荐.基于通用测试数据集的实验研究结果表明:该算法不但可以极大地提高推荐系统的精确度和召回率,而且表现出良好的抗攻击能力.
人工智能
EDDPC:一种高效的分布式密度中心聚类算法
巩树凤,张岩峰
2016, 53(6):  1400-1409.  doi:10.7544/issn1000-1239.2016.20150616
摘要 ( 1219 )   HTML ( 3)   PDF (2497KB) ( 715 )  
相关文章 | 计量指标
聚类分析是数据挖掘中经常用到的一种分析数据之间关系的方法.它把数据对象集合划分成多个不同的组或簇,每个簇内的数据对象之间的相似性要高于与其他簇内的对象的相似性.密度中心聚类算法是一个最近发表在《Science》上的新型聚类算法,它通过评估每个数据对象的2个属性值(密度值ρ和斥群值δ)来进行聚类.相对于其他传统聚类算法,它的优越性体现在交互性、无迭代性、无数据分布依赖性等方面.但是密度中心聚类算法在计算每个数据对象的密度值和斥群值时,需要O(N\+2)复杂度的距离计算,当处理海量高维数据时,该算法的效率会受到很大的影响.为了提高该算法的效率和扩展性,提出一种高效的分布式密度中心聚类算法EDDPC (efficient distributed density peaks clustering),它利用Voronoi分割与合理的数据复制及过滤,避免了大量无用的距离计算开销和数据传输开销.实验结果显示:与简单的MapReduce分布式实现比较,EDDPC可以达到40倍左右的性能提升.
基于泛化反向学习的多目标约束差分进化算法
魏文红,王甲海,陶铭,袁华强
2016, 53(6):  1410-1421.  doi:10.7544/issn1000-1239.2016.20150806
摘要 ( 1115 )   HTML ( 10)   PDF (2991KB) ( 735 )  
相关文章 | 计量指标
差分进化算法是一种简单有效的进化算法,基于泛化反向学习的机制在进化算法中经常可以引导种群的进化.针对多目标的约束优化问题,提出了一种基于泛化反向学习的多目标约束差分进化算法.该算法采用基于泛化反向学习的机制(generalized opposition-based learning, GOBL)产生变换种群,然后在种群初始化和代跳跃阶段,利用非支配排序、拥挤距离和约束处理技术从原始种群和其变换种群中选择更优的种群个体作为新的种群继续迭代进化;该算法通过采用基于泛化反向学习的机制,可以引导种群个体慢慢向最优的Pareto前沿逼近,以求得最优解集.最后采用多目标Benchmark问题对该算法进行了实验评估,实验结果表明:与NSGA-Ⅱ,MOEA/D及其他的多目标进化算法相比,提出的算法具有更好的收敛性,并且产生的解能够逼近最优的Pareto前沿.