【摘 要】
：
平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,
【机 构】
：
绍兴文理学院计算机科学与工程系,浙江绍兴312000
论文部分内容阅读
平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,32个子区,相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法),割边率减少1.7％～30.2％,说明了该算法的优越性.同时该算法具有良好的可扩展性,划分的子区数量及图的规模对划分时间具有较低的影响.
其他文献
本文提出了一种高线性度的全双工光载射频系统.该系统克服了下行链路三阶交调失真与周期性功率衰落的影响,同时对上行链路进行波长重用,简化了基站的成本和复杂度,实现了高线性度的全双工光载射频系统.实验结果表明,与基于单个马增调制器的常规系统相比,本系统下行链路中三阶交调失真得到明显抑制,克服了光纤色散引起的功率衰落,系统无杂散动态范围提高17dB,宽带信号的星座图和误差矢量幅度改善明显,另外,上行链路可以实现稳定的波长重用及宽带信号传输.
针对带内全双工(In-band Full Duplex,IBFD)电子系统的收发机自干扰问题,提出了一种基于相位调制器的光子射频自干扰消除系统.利用两个相位调制器在萨格纳克(Sagnac)环中分别实现接收信号和本地参考干扰信号的调制,通过偏振控制最终可在光域中消除自干扰信号.实验结果表明,所提方案最终可以实现超过45dB的单频干扰消除和超过25dB的宽带干扰消除,系统的动态范围可达99.4dB·Hz2/3.
携带轨道角动量的涡旋光束在自由空间光通信信道中传输时,信道中的湍流介质会改变涡旋光束的传播特性,破坏波前螺旋结构,最终直接影响通信的稳定性和可靠性.针对现有实验研究在普适性方面的不足,本文选取基于相干光束合成技术的高功率涡旋光束阵列为研究光源,从理论角度出发,建立一套完备的体系架构,用以分析大气湍流引起的幅度和相位起伏对基于轨道角动量的自由空间光通信系统性能的影响.应用光学外差检测,对湍流条件下信噪比的随机分布进行详细的研究,并基于此得到多进制相移键控调制下符号错误概率的解析表达式,评估不同湍流信道参数、
由于在性能和复杂度之间的良好折中,软信息辅助硬判决译码近年来受到了光通信领域的高度关注,其中包括了软信息辅助比特标记(Soft-Aided Bit-Marking,SABM)算法.为了易于硬件实现,本文基于阶梯码(Staircase Code,SCC)提出了一种改进型SABM算法(improved SABM,iSABM),称为iSABM-SCC.iSABM-SCC利用信道软信息,通过两个可信度阈值将硬判决输出比特标记为三种可信度等级,用以辅助硬判决译码识别译码错误和扩展纠错能力,达到提升阶梯码性能的目的.
甲骨文是中国最早的系统文字,是目前能见到的最早的成熟汉字.甲骨文的研究对历史探究和文化传承具有重要的意义.但是要实现字符级别的甲骨字符图像标注,在现有技术环境下,只能通过资深甲骨学专家进行人工标注,不仅耗费人力资源,而且效率低下.针对这一问题,在前期工作中的甲骨字符图像识别模型的基础上,本文提出了一种甲骨字符图像自动标注算法.该算法通过先分列后切割的思想,先将甲骨拓片上的每一个字符图像归结到某一个
大气湍流引起的光束闪烁和抖动,将使光通信接收机焦平面上点扩散函数(Point Spread Function,PSF)随机起伏和漂移,导致光电探测器无法有效覆盖信号光场.针对自由空间光通信(Free Space Optical Communications,FSO)系统在多模高斯背景光噪声场和接收光信号能量效率的限定下最小化系统误码率的问题,提出了一种适用于强度调制/直接检测(Intensity Modulation/Direct Detection,IM/DD)的自适应光电阵列信号处理算法.该方法采用合
当前基于深度学习的有监督前景分割方法得益于大量待分割场景的标注信息,其性能大幅超越传统的无监督方法 .然而,获取高精度的像素级标注需要耗费大量的人力和时间成本,这严重限制了有监督算法在无标注场景的部署应用.为解决对场景监督信息依赖的问题,设计了一种与传统的帧间差分法相融合的跨场景深度学习架构,即帧间高级特征差分算法.该算法重点围绕时域变化等跨场景共性知识的迁移,在不依赖待分割场景监督信息的前提下实
目前,电力企业对电力负荷的预测,主要集中在对地市级别以上的区域预测,对于单个变电站和用电大客户的负荷预测尚未得到足够重视.重点介绍了回归分析法在变电站与大客户短期负荷预测的应用,并以柳州供电局74个变电站、35个大客户为例进行实践分析.
论文基于涡旋光束传输特性及光散射理论,研究了叠加态涡旋光束经旋转随机粗糙表面的场分布及干涉特性.对拓扑荷值大小相同、符号相反的两束涡旋光进行了叠加生成仿真及实验,利用角谱衍射理论,分析了旋转随机粗糙表面均方根粗糙度对光束传输的影响,数值计算了不同拓扑荷值的叠加态涡旋光束经旋转随机粗糙表面后,与参考光进行干涉得到不同转速下归一化强度值随时间变化的曲线,并通过光强-时间函数间接求得频移量,再反演得到旋转目标的转速.结果表明:通过仿真曲线的周期反演频率,当转速Ω分别为2π/3 rad/s,2πrad/s,10π