虚拟专题文章

    先进计算

    默认 最新文章 浏览次数
    Please wait a minute...
    选择: 显示/隐藏图片
    1. 带状稀疏矩阵乘法及高效GPU实现
    刘丽, 陈长波
    《计算机应用》唯一官方网站    2023, 43 (12): 3856-3867.   DOI: 10.11772/j.issn.1001-9081.2022111720
    摘要212)   HTML3)    PDF (3222KB)(177)    收藏

    稀疏-稠密矩阵乘法(SpMM)广泛应用于科学计算和深度学习等领域,提高它的效率具有重要意义。针对具有带状特征的一类稀疏矩阵,提出一种新的存储格式BRCV(Banded Row Column Value)以及基于此格式的SpMM算法和高效图形处理单元(GPU)实现。由于每个稀疏带可以包含多个稀疏块,所提格式可看成块稀疏矩阵格式的推广。相较于常用的CSR(Compressed Sparse Row)格式,BRCV格式通过避免稀疏带中列下标的冗余存储显著降低存储复杂度;同时,基于BRCV格式的SpMM的GPU实现通过同时复用稀疏和稠密矩阵的行更高效地利用GPU的共享内存,提升SpMM算法的计算效率。在两种不同GPU平台上针对随机生成的带状稀疏矩阵的实验结果显示,BRCV的性能不仅优于cuBLAS(CUDA Basic Linear Algebra Subroutines),也优于基于CSR和块稀疏两种不同格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比分别为6.20和4.77。此外,将新的实现应用于图神经网络(GNN)中的SpMM算子的加速。在实际应用数据集上的测试结果表明,BRCV的性能优于cuBLAS和基于CSR格式的cuSPARSE,且在大多数情况下优于基于块稀疏格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比为4.47。以上结果表明BRCV可以有效提升SpMM的效率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    2. 基于新一代神威超算的量子计算模拟器加速和优化
    史新民, 刘勇, 陈垚键, 宋佳伟, 刘鑫
    《计算机应用》唯一官方网站    2023, 43 (8): 2486-2492.   DOI: 10.11772/j.issn.1001-9081.2022091456
    摘要424)   HTML59)    PDF (2000KB)(426)    收藏

    针对量子硬件规模逐步扩大、当下量子计算经典模拟速度不高的问题,提出了基于神威超算量子模拟器的两种优化方法。首先,通过改进张量转置策略和计算策略重新构建了张量收缩算子库SWTT,从而提高了部分张量收缩的计算内核效率并减少了冗余访存;其次,通过提高数据局部性的收缩路径调整方法实现了路径计算复杂度和计算效率之间的均衡。测试结果表明,该算子库改进方法可将“悬铃木”量子霸权电路模拟效率提升5.4%,单步张量收缩效率最高提升49.7倍;该路径调整方法可在路径计算复杂度膨胀2倍条件下提升约4倍的浮点效率。两种优化方法使神威超算整机模拟谷歌53量子比特20层量子芯片随机电路百万振幅采样的单精度和混合精度浮点运算效率分别从3.98%和1.69%提升至18.48%和7.42%,理论估计模拟时间从单精度的470 s降至226 s,混合精度的304 s降至134 s,证明两种方法大幅提高了量子计算模拟速度。

    图表 | 参考文献 | 相关文章 | 多维度评价
    3. 基于汉明距离的量子 K-Means算法
    钟静, 林晨, 盛志伟, 张仕斌
    《计算机应用》唯一官方网站    2023, 43 (8): 2493-2498.   DOI: 10.11772/j.issn.1001-9081.2022091469
    摘要307)   HTML32)    PDF (1623KB)(408)    收藏

    K-Means算法在处理大规模异构数据时,通常使用欧氏距离来衡量数据点之间的相似度,然而这样存在效率低下以及计算复杂性过高的问题。受到汉明距离在处理数据相似性计算上存在显著优势的启发,提出一种基于汉明距离的量子K-Means(QKMH)算法来计算相似度。首先,将数据制备成量子态,并使用量子汉明距离计算待聚类点和K个聚类中心之间的相似度;然后,改进了Grover最小值搜索算法查找距离待聚类点最近的聚类中心;最后,循环以上步骤,直到达到规定迭代次数或者聚类中心不再改变。基于量子模拟计算框架QisKit,将提出的算法在MNIST手写数字数据集上进行了验证并与传统和改进的多种方法进行了对比,实验结果表明,QKMH算法的F1值相较于基于曼哈顿距离的量子K-Means算法提高了10个百分点,相较于最新优化的基于欧氏距离的量子K-Means算法提高了4.6个百分点;同时经计算,QKMH算法时间复杂度比上述对比算法更低。

    图表 | 参考文献 | 相关文章 | 多维度评价
    4. 分布式工厂中微型制造单元多目标优化
    柳春锋, 李峥, 王居凤
    《计算机应用》唯一官方网站    2023, 43 (12): 3824-3832.   DOI: 10.11772/j.issn.1001-9081.2022111772
    摘要122)   HTML0)    PDF (1527KB)(79)    收藏

    由于各地区存在资源禀赋和产业政策差异,分布式生产对提升制造企业竞争力的作用非常重要,如何利用分布式生产增强大规模定制的柔性是提振消费信心需要解决的重要问题。结合微型制造单元的思想,在多市场多类型产品的分布式混流生产情景下,以最小化人工和转运等运营成本以及最大完工时间为目标,提出分布式工厂构建和生产调度集成模型,以求解微型单元构建、工人和机器配置和各批次产品的生产策略。所提模型能帮助企业实现产能快速释放和合理混流生产,从而实现满足多区域、多产品和差异化需求的分布式制造与销售,并在确保产量的同时降低制造过程中的运营成本。此外,设计多目标粒子群优化(MOPSO)算法求解模型,并将它与非支配排序遗传算法Ⅱ(NSGA?Ⅱ)和多目标模拟退火(MOSA)算法进行比较。大规模数值实验的结果表明,在相同的运行时间内,MOPSO算法在解集支配覆盖率(CM)、平均理想距离(MID)和最大分散度(MS)这3个指标上均优于NSGA?Ⅱ和MOSA算法。所提算法可以为微型化分布式生产系统提供高质量的生产运作决策方案。

    图表 | 参考文献 | 相关文章 | 多维度评价
    5. k元( n-1)方体子网络可靠性的近似评估方法
    冯凯, 李建德, 姬张建
    《计算机应用》唯一官方网站    2023, 43 (12): 3875-3881.   DOI: 10.11772/j.issn.1001-9081.2022111719
    摘要91)   HTML0)    PDF (2399KB)(51)    收藏

    多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。kn方体网络的子网络可靠性是以kn方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下kn方体中k元(n-1)方体子网络的可靠性,提出基于反向传播(BP)神经网络的k元(n-1)方体子网络可靠性的近似评估方法。首先,利用蒙特卡洛仿真方法和k元(n-1)方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法;其次,基于生成的训练数据集构造用于评估k元(n-1)方体子网络可靠性的BP神经网络模型;最后,对BP神经网络模型得出的k元(n-1)方体子网络可靠性的近似评估结果进行了分析,并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比,所提方法得出的结果更为精确;与基于蒙特卡洛的评估方法相比,所提方法的评估耗时平均减少了约59%。实验结果表明,所提方法在兼顾精度和效率方面具有一定优势。

    图表 | 参考文献 | 相关文章 | 多维度评价
    6. 基于深度强化学习的多数据中心一体化调度优化
    方和平, 刘曙光, 冉泳屹, 钟坤华
    《计算机应用》唯一官方网站    2023, 43 (6): 1884-1892.   DOI: 10.11772/j.issn.1001-9081.2022050722
    摘要239)   HTML11)    PDF (2415KB)(235)    收藏

    多数据中心任务调度策略的目的是把计算任务分配到各个数据中心的不同服务器上,以促进资源利用率和能效的提升,为此提出了基于深度强化学习的多数据中心一体化调度策略。所提策略分为数据中心选择和数据中心内部任务分配两个阶段。在多数据中心选择阶段,整合算力资源以提高总体资源利用率,首先采用具有优先经验回放的深度Q网络(PER-DQN)在以数据中心为节点的网络中获取到达各个数据中心的通信路径;然后计算资源使用成本和网络通信成本,并依据这两个成本之和最小的原则选择最优的数据中心。在数据中心内部任务分配阶段,首先在所选数据中心内部,划分计算任务并遵循先到先服务(FCFS)原则将任务添加到调度队列中;然后结合计算设备状态和环境温度,采用基于双深度Q网络(Double DQN)的任务分配算法获得最优分配策略,以选择服务器执行计算任务,避免热点的产生,并降低制冷设备的能耗。实验结果表明,基于PER-DQN的数据中心选择算法相较于计算资源优先(CRF)、最短路径优先(SPF)路径选择方法的平均总成本分别下降了3.6%、10.0%;基于Double DQN的任务部署算法相较于较轮询调度(RR)、贪心调度(Greedy)算法的平均电源使用效率(PUE)分别下降了2.5%、1.7%。可见,所提策略能够有效降低总成本和数据中心能耗,实现多数据中心的高效运行。

    图表 | 参考文献 | 相关文章 | 多维度评价
    7. 面向国产高性能众核处理器的编程模型
    陈虎, 周鹏灵
    《计算机应用》唯一官方网站    2023, 43 (11): 3517-3526.   DOI: 10.11772/j.issn.1001-9081.2022101548
    摘要220)   HTML3)    PDF (3529KB)(116)    收藏

    在国产高性能众核处理器上编程时,需要直接使用最底层的接口开发软件,这使编程和调试非常困难;并且各自平台的高性能软件编程模型较为基础,计算软件不能通用,造成了重复性开发。针对以上问题,实现了通用编程模型以及所对应的支撑库:一方面基于消息队列机制开发国产高性能众核处理器的线程级并行机制;另一方面基于单指令多数据流(SIMD)编程模型开发从核上的数据级并行性。首先,对国产高性能众核处理器体系结构进行抽象;其次,设计模型的消息队列机制,并为程序员提供一套异构并行编程接口,如系统参数接口、从核线程控制接口、消息队列接口、SIMD抽象接口;最后,在上述基础上形成全新的高性能计算软件开发模型和方法,方便用户开发基于国产高性能众核处理器的并行计算软件。性能传输测试结果表明,在国产众核处理器上,当启动核数较少时,所提模型的传输带宽普遍达到了峰值直接内存访问(DMA)带宽的90%;当启动的核数较多时,消息队列模型的传输带宽普遍达到了峰值DMA带宽的70%。在矩阵乘法实验中,与系统原语传输矩阵并计算的性能相比,所提模型的性能达到前者的90%;在口令猜测系统中,所提模型的代码性能与直接使用最底层的接口开发的代码性能基本持平。所提通用编程模型和支撑框架使高性能计算(HPC)软件开发更简易,并且具有更好的可移植性,可为促进国产自主HPC软件研发提供帮助。

    图表 | 参考文献 | 相关文章 | 多维度评价
    8. 流密码非线性布尔函数可重构运算单元设计方法RA-NLBF
    张宗仁, 戴紫彬, 刘燕江, 张晓磊
    《计算机应用》唯一官方网站    2023, 43 (11): 3527-3533.   DOI: 10.11772/j.issn.1001-9081.2022111690
    摘要114)   HTML0)    PDF (1594KB)(60)    收藏

    分组密码中的S盒(多输出)以及流密码中的反馈函数都需要特殊的布尔函数来保证密码算法的安全性。为解决现有流密码算法中非线性布尔函数(NLBF)可重构硬件运算单元资源占用过大、时钟频率低等问题,提出一种高效的基于与非锥(AIC)的NLBF可重构运算单元设计方法(RA-NLBF)。以密码学理论为基础,在着重分析多种流密码算法的NLBF特性,提取了涵盖与项次数、与项个数、输入端口数等NLBF函数特征的基础上,提出基于“混合极性Reed-Muller(MPRM)”和“传统布尔逻辑(TB)”双逻辑混合形式的NLBF化简方法,NLBF的与项数量减少29%,形成了适用于AIC的NLBF表达式;根据化简后的表达中与项个数、与项次数分布等特征,设计了可重构AIC单元和互联网络,形成可满足现有公开流密码算法中的NLBF运算的可重构单元。基于CMOS 180 nm工艺对提出的RA-NLBF进行逻辑综合验证,结果显示该方法的面积为12 949.67 μm2,时钟频率达到505 MHz,与现有相同功能的单元可重构序列密码逻辑单元(RSCLU)相比,面积减少了59.7%,时钟频率提高了37.3%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    9. 基于动态簇粒子群优化的无人机集群路径规划方法
    王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳
    《计算机应用》唯一官方网站    2023, 43 (12): 3816-3823.   DOI: 10.11772/j.issn.1001-9081.2022111763
    摘要172)   HTML7)    PDF (2693KB)(189)    收藏

    路径规划对于无人机(UAV)集群的任务执行十分重要,而且高维场景中的计算通常很复杂。群体智能为解决该问题提供了较好的解决思路。粒子群优化(PSO)算法具有参数少、收敛速度快、操作简单等优点,尤其适用于路径规划问题,但它在应用时存在全局搜索能力差、容易陷入局部最优的问题。为了解决上述问题以提升无人机集群路径规划的效果,提出了动态簇粒子群优化(DCPSO)算法。首先,利用人工势场法和滚动时域控制原理建模UAV集群路径规划问题的任务场景;其次,引入Tent混沌映射和动态簇机制进一步提升全局搜索能力和搜索精度;最后,使用DCPSO算法优化模型的目标函数,以获得UAV集群的每个轨迹点的选择。在单峰/多峰、低维/高维不同组合的10种基准测试函数下的仿真实验结果表明,与PSO、鸽子启发优化(PIO)、麻雀搜索算法(SSA)和混沌扰动鸽群优化(CDPIO)算法相比,DCPSO算法具有更好的计算最优值、均值和方差,搜索精度更佳,稳定性更强。此外,UAV集群路径规划应用实例仿真结果也验证了DCPSO算法的性能与效果。

    图表 | 参考文献 | 相关文章 | 多维度评价
    10. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度
    薛海蓉, 韩晓龙
    《计算机应用》唯一官方网站    2023, 43 (12): 3848-3855.   DOI: 10.11772/j.issn.1001-9081.2022121923
    摘要193)   HTML10)    PDF (3405KB)(60)    收藏

    针对自动引导车(AGV)在自动化集装箱码头(ACT)执行任务过程中的电量问题,提出基于改进的非支配排序遗传算法-Ⅱ(NSGA-Ⅱ)的考虑AGV充电策略的集成调度。首先,在岸桥、场桥和AGV集成调度模式下,考虑AGV在不同作业状态下的耗电量,并建立以最小化作业完工时间和总耗电量为目标的多目标混合规划模型;其次,为提高传统NSGA-Ⅱ的性能,设计自适应NSGA-Ⅱ,并将所提算法与CPLEX求解器、NSGA-Ⅱ和多目标粒子群优化(MOPSO)算法进行性能对比;最后,设计AGV不同充电策略并对设备数量配比进行实验研究。算法对比实验结果表明:相较于传统NSGA-Ⅱ算法,自适应NSGA-Ⅱ对双目标的优化分别提升了2.8%和2.63%。利用自适应NSGA-Ⅱ进行的充电策略和设备数量配比实验的结果表明:增加AGV充电次数能够减少AGV的充电时间,且调整设备数量配比至3∶3∶9和3∶7∶3时,场桥和AGV的时间利用率分别达到最高。可见,AGV充电策略及设备数量配比对码头多设备集成调度有一定影响。

    图表 | 参考文献 | 相关文章 | 多维度评价
    11. 概率故障条件下 k元( n-m)方体子网络的可靠性
    冯凯, 刘彤
    《计算机应用》唯一官方网站    2023, 43 (4): 1198-1205.   DOI: 10.11772/j.issn.1001-9081.2022030414
    摘要208)   HTML1)    PDF (894KB)(45)    收藏

    kn方体具有许多优良特性,已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时,系统子网络的保持能力对系统实际应用至关重要。为了精确度量kn方体中任意规模子网络的容错能力,研究了有故障发生时kn方体中k元(n-m)方体子网络的可靠性。当kk≥3)为奇整数时,在概率故障条件下得出了kn方体中存在无故障k元(n-m)方体子网络的概率的上界和下界,并给出了该可靠性的一种近似评估方法。实验结果表明,随着顶点可靠性的降低,k元(n-m)方体子网络可靠性的上下界趋于一致;当顶点可靠性较高时,利用近似评估方法得出的结果更为准确。

    图表 | 参考文献 | 相关文章 | 多维度评价
    12. 基于分解法与轨迹搜索的无人机群轨迹多目标优化模型
    柳隽琰, 江沸菠, 彭于波, 董莉
    《计算机应用》唯一官方网站    2023, 43 (12): 3806-3815.   DOI: 10.11772/j.issn.1001-9081.2022121882
    摘要142)   HTML3)    PDF (1873KB)(122)    收藏

    基于深度学习(DL)的传统多目标求解器存在模型利用率低以及容易陷入局部最优的问题。针对这些问题,提出了基于分解法与轨迹搜索的无人机群轨迹多目标优化模型(DTMO-UT)。所提模型包含编码与解码部分。首先,编码部分由设备编码器(Dencoder)和权重编码器(Wencoder)组成,用于提取物联网(IoT)设备的状态信息与权重向量的特征,其中权重向量代表分解多目标优化问题(MOP)的标量优化子问题,因此解决所有子问题即可解决该MOP。权重编码器可以实现对所有子问题的编码,从而提高了模型的利用率。然后,使用包含轨迹解码器(Tdecoder)的解码部分对编码特征进行解码,以生成帕累托最优解。最后,为了减少贪婪策略陷入局部最优的现象,为轨迹解码器设计轨迹搜索技术,即通过生成多个候选轨迹选标量值最优的轨迹作为帕累托最优解,从而增强了轨迹解码器在轨迹规划时的探索能力,并获得质量更好的帕累托集。仿真实验结果表明,所提模型相较于主流的基于DL的MOP求解器,在模型参数量降低98.93%的情况下,MOP解的分布性提高了0.076%,延展性提高了0.014%,平均综合性提高了1.23%,表现出较强的实用性路径规划能力。

    图表 | 参考文献 | 相关文章 | 多维度评价
    13. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题
    黄霖, 符强, 童楠
    《计算机应用》唯一官方网站    2023, 43 (12): 3840-3847.   DOI: 10.11772/j.issn.1001-9081.2022121847
    摘要203)   HTML6)    PDF (1437KB)(136)    收藏

    针对启发式算法在机器人路径规划过程中存在路径长度不稳定和易陷入局部极小点的问题,提出一种基于自适应调整哈里斯鹰优化(AAHHO)算法。首先,利用收敛因子调整策略,调节全局搜索阶段和局部搜索阶段的平衡,同时利用自然常数为底数,提高搜索效率和收敛精度;其次,在全局搜索阶段,采用精英合作引导搜索策略,通过3个精英哈里斯鹰合作引导其他个体更新位置以提高搜索性能,通过3个最优位置加强种群间的信息交流;最后,通过模拟种内竞争策略增强哈里斯鹰跳出局部最优的能力。函数测试和机器人路径规划对比实验结果表明,所提算法无论是函数测试还是机器人路径规划都优于IHHO(Improve Harris Hawk Optimization)和CHHO(Chaotic Harris Hawk Optimization)等对比算法,对于求解机器人的路径规划具有较好的有效性、可行性和稳定性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    14. 基于数据驱动的云边智能协同综述
    田鹏新, 司冠南, 安兆亮, 李建辛, 周风余
    《计算机应用》唯一官方网站    2023, 43 (10): 3162-3169.   DOI: 10.11772/j.issn.1001-9081.2022091418
    摘要540)   HTML29)    PDF (1772KB)(386)    收藏

    随着物联网(IoT)的快速发展,大量在传感器等边缘场景产生的数据需要传输至云节点处理,这带来了极大的传输成本和处理时延,而云边协同为这些问题提供了有效的解决方案。首先,在全面调查和分析云边协同发展过程的基础上,结合当前云边智能协同中的研究思路与进展,重点分析和讨论了云边架构中的数据采集与分析、计算迁移技术以及基于模型的智能优化技术;其次,分别从边缘端和云端深入分析了各种技术在云边智能协同中的作用及应用,并探讨了云边智能协同技术在现实中的应用场景;最后,指出了云边智能协同目前存在的挑战及未来的发展方向。

    图表 | 参考文献 | 相关文章 | 多维度评价
    15. 结合遗传算法和滚动调度的多机器人任务分配算法
    邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟
    《计算机应用》唯一官方网站    2023, 43 (12): 3833-3839.   DOI: 10.11772/j.issn.1001-9081.2022121916
    摘要361)   HTML6)    PDF (2617KB)(206)    收藏

    研究多机器人任务分配(MRTA)的目的是提高智能工厂中机器人完成任务的效率。针对现有算法在处理大规模、多约束的MRTA时存在不足的问题,提出一种结合遗传算法和滚动调度的MRTA算法(ACGARS)。首先,在遗传算法中采用基于有向无环图(DAG)的编码方式高效地处理任务之间的优先级约束;其次,在遗传算法的初始种群中加入先验知识以提高算法的搜索效率;最后,设计基于任务组的滚动调度策略用于减小求解问题的规模,从而实现对大规模问题的高效求解。在大规模问题实例上的实验结果表明,相较于构造性启发式算法(CHA)、最小化干扰算法(MIA)和基于惩罚策略的遗传算法(GAPS)生成的方案,当任务组数为20时,所提算法生成的方案的平均订单完成时间分别缩短了30.02%、16.86%和75.65%,验证了所提算法能有效地缩短订单的平均等待时间,提升多机器人任务分配效率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    16. 融合卷积与自注意力机制的基因型填补算法
    陈炯环, 鲍胜利, 王啸飞, 李若凡
    《计算机应用》唯一官方网站    2023, 43 (11): 3534-3539.   DOI: 10.11772/j.issn.1001-9081.2022111756
    摘要201)   HTML4)    PDF (1678KB)(69)    收藏

    基因型填补可以通过填补估算出在基因测序数据中未覆盖的样本区域弥补因技术限制导致的缺失,但现有的基于深度学习的填补方法不能有效捕捉到全序列位点间的连锁关系,造成整体填补准确率低、批量序列填补准确率分散等问题。针对这些问题提出一种融合卷积与自注意力机制的填补方法——FCSA,使用两种融合模块构成编解码器组建网络模型。编码器融合模块使用自注意力层得到全序列位点间的关联度,将该关联度融合到全局位点后再通过卷积层提取局部特征;解码器融合模块使用卷积对编码后的低维向量进行局部特征重建,应用自注意力层对全序列建模并融合。使用多物种的动物基因数据进行模型训练,并在Dog、Pig和Chicken数据集上进行比较验证,结果表明,与SCDA(Sparse Convolutional Denoising Autoencoders)、AGIC(Autoencoder Genome Imputation and Compression)和U-net相比,FCSA在10%、20%和30%缺失率下的平均填补准确率均取得了最高值,且批量序列填补准确率的分散程度较小;消融实验的结果也表明,这两种融合模块的设计能够有效提升基因型填补的准确率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    17. 面向DCU非一致控制流的编译优化
    杨小艺, 赵荣彩, 王洪生, 韩林, 徐坤坤
    《计算机应用》唯一官方网站    2023, 43 (10): 3170-3177.   DOI: 10.11772/j.issn.1001-9081.2022091338
    摘要160)   HTML10)    PDF (4315KB)(74)    收藏

    国产DCU采用单指令多线程(SIMT)的并行执行模型,在程序执行时核函数内会产生非一致控制流,导致线程束中的线程部分只能串行执行,即线程束分化。针对核函数的性能因线程束分化受到严重制约的问题,提出一种减少线程束分化时间的编译优化方法——部分控制流合并(PCFM)。首先,通过散度分析找到同构且含有大量相同指令和相似指令的可融合发散区域;其次,统计合并后节省的指令周期百分比,从而评估可融合发散区域的融合盈利;最后,查找对齐序列,并合并有收益的可融合发散区域。在DCU上使用PCFM测试从图形处理器(GPU)基准测试套件Rodinia和经典的排序算法中选择的测试用例,实验结果表明,PCFM对测试用例能够取得1.146的平均加速比,与分支融合+尾合并方法相比,使用PCFM的加速比平均提高了5.72%。可见,所提方法减少线程束分化的效果更好。

    图表 | 参考文献 | 相关文章 | 多维度评价
    18. 基于新评价指标自适应预测的动态多目标优化算法
    李二超, 张生辉
    《计算机应用》唯一官方网站    2023, 43 (10): 3178-3187.   DOI: 10.11772/j.issn.1001-9081.2022091453
    摘要224)   HTML8)    PDF (3391KB)(79)    收藏

    现实生活中的多目标优化问题(MOP)大多为动态多目标优化问题(DMOP),此类问题的目标函数、约束条件和决策变量都可能随时间的变化而发生改变,这需要算法在环境变化后快速适应新的环境,且在保证Pareto解集多样性的同时快速收敛到新的Pareto前沿。针对此问题,提出一种基于新评价指标自适应预测的动态多目标优化算法(NEI-APDMOA)。首先,在种群非支配排序过程中提出一种优于拥挤度的新评价指标,并分阶段平衡收敛快速性和种群多样性,使种群的收敛过程更加合理;其次,提出一种可判断环境变化强弱的因子,为预测阶段提供有价值信息,并引导种群更好地适应环境变化;最后,根据环境变化因子匹配3种更加合理的预测策略,使种群快速响应环境变化。将NEI-APDMOA与DNSGA-Ⅱ-A(Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A)、DNSGA-Ⅱ-B(Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B)和PPS(Population Prediction Strategy)算法在9个标准动态测试函数上进行对比。实验结果表明,NEI-APDMOA分别在9、4和8个测试函数上取得了最优的平均反世代距离(IGD)值、平均间距(SP)值和平均世代距离(GD)值,可以更快地响应环境变化。

    图表 | 参考文献 | 相关文章 | 多维度评价
    19. 混合自适应粒子群工作流调度优化算法
    马学森, 许雪梅, 蒋功辉, 乔焰, 周天保
    《计算机应用》唯一官方网站    2023, 43 (2): 474-483.   DOI: 10.11772/j.issn.1001-9081.2022010001
    摘要304)   HTML7)    PDF (2548KB)(101)    收藏

    针对具有截止期的云工作流完成时间与执行成本冲突的问题,提出一种混合自适应粒子群工作流调度优化算法(HAPSO)。首先,基于截止期建立有向无环图(DAG)云工作流调度模型;然后,通过范数理想点与自适应权重的结合,将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题;最后,在粒子群优化(PSO)算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法(FA)和粒子越界处理方法,从而平衡粒子群的全局搜索与局部搜索能力,进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法(WPSO)、蚁群算法(ACO)和HAPSO的优化结果。实验结果表明,HAPSO在权衡工作流(30~300任务数)完成时间与执行成本的多目标函数值上降低了40.9%~81.1%,HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外,HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果,验证了HAPSO的普适性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    20. 零点分布更均匀的广义极谐复指数变换
    曾泽芝, 杨建伟
    《计算机应用》唯一官方网站    2023, 43 (8): 2499-2504.   DOI: 10.11772/j.issn.1001-9081.2022071020
    摘要147)   HTML3)    PDF (5046KB)(55)    收藏

    针对极谐复指数变换(PCET)因自身径向函数实部和虚部的零点分布不均匀而存在的信息抑制问题,提出了一种零点分布更均匀的广义PCET。首先,改造了PCET,将PCET径向函数的指数推广为更一般的构造函数,而近来出现的指数傅里叶矩(EFM)、分数阶极谐变换、广义极谐变换、修正的广义极谐变换等都是所提广义PCET的特例;其次,选取了构造函数,使得所构造的广义PCET的径向函数实部和虚部的零点分布更均匀,并给出了这一特性的证明。在所取的汉字图像库、Coil-20库和COREL库上进行了图像重构实验,同时测试了广义PCET的旋转不变性及抗噪性能。当噪声强度为0时,PCET和广义PCET的识别率均为100%,这验证了PCET和广义PCET的旋转不变性。相较于PCET,所提广义PCET具有更低的重构误差及更高的识别率。理论分析和实验结果表明,零点分布比PCET更均匀的广义PCET同样具有旋转不变性和正交性,且其重构性能和抗噪性能均优于PCET,一定程度上解决了PCET的信息抑制问题,并在原点处数值稳定。

    图表 | 参考文献 | 相关文章 | 多维度评价
    21. 云平台下基于截止时间的自适应调度策略
    吴仁彪, 张振驰, 贾云飞, 乔晗
    《计算机应用》唯一官方网站    2023, 43 (1): 176-184.   DOI: 10.11772/j.issn.1001-9081.2021112018
    摘要205)   HTML8)    PDF (2505KB)(72)    收藏
    针对在共享集群中进行任务调度时,无法兼顾任务的响应速度与任务完成时间的问题,提出一种基于截止时间的自适应调度算法。该算法以用户提交的截止时间为依据,根据任务的执行进度自适应地分配适当的计算资源。不同于传统调度方式里由用户提交固定资源参数,该算法在资源约束的情况下会对优先级高的任务进行抢占式调度以保证服务质量(QoS),并在抢占过程结束后额外分配资源补偿被抢占的任务。在Spark平台进行的任务调度实验结果显示,与另一种资源协调者(YARN)框架下的调度算法相比,所提算法能严格地控制短任务的响应速度,并使长作业的任务完成时间缩短35%。
    参考文献 | 相关文章 | 多维度评价
    22. 基于可满足性模理论的多处理机通信延迟优化任务调度方法
    姜松岩, 廖晓鹃, 陈光柱
    《计算机应用》唯一官方网站    2023, 43 (1): 185-191.   DOI: 10.11772/j.issn.1001-9081.2021111862
    摘要192)   HTML6)    PDF (1508KB)(64)    收藏
    在一组相同处理器上调度带有通信延迟的任务图以实现其最短的执行时间,这在并行计算的调度理论和实践中具有重要的意义。针对具有通信延迟的任务图调度问题,提出一种基于可满足性模理论(SMT)的改进SMT方法。首先,将处理器映射约束和任务执行顺序等约束条件进行编码,将任务图调度问题转化为SMT问题;然后,调用SMT求解器对可行解空间进行搜索,以确定问题最优解。在约束编码阶段,使用整型变量表示任务和处理器的映射关系,从而降低处理器约束编码的复杂程度;在求解器调用阶段,通过添加独立任务的约束条件减小求解器的搜索空间,进一步提升最优解的查找效率。实验结果表明,与原始SMT方法相比,改进SMT方法在20 s和1 min超时实验中的平均求解时间分别减少了65.9%与53.8%,并且在处理器数量较多时取得了更大的效率优势。改进的SMT方法可以有效求解带通信延迟的任务图调度问题,尤其适用于处理器数量较多的调度场景。
    参考文献 | 相关文章 | 多维度评价
    23. 融合黄金正弦算法和纵横交叉策略的秃鹰搜索算法
    赵沛雯, 张达敏, 张琳娜, 邹诚诚
    《计算机应用》唯一官方网站    2023, 43 (1): 192-201.   DOI: 10.11772/j.issn.1001-9081.2021111868
    摘要271)   HTML9)    PDF (1555KB)(92)    收藏
    针对传统秃鹰搜索算法(BES)存在容易陷入局部最优、收敛速度慢等缺点,提出一种融合黄金正弦算法(Gold-SA)和纵横交叉策略的秃鹰搜索算法(GSCBES)。首先,在传统BES的搜索阶段设置基于惯性权重的位置更新公式;然后,在捕食猎物阶段引入Gold-SA;最后,引入纵横交叉策略对全局最优和种群进行修正。对11个Benchmark函数和CEC2014函数进行仿真实验并使用Wilcoxon秩和检验的方式评估所提算法的寻优能力,结果表明,所提算法收敛更快;同时,使用所提算法对反向传播(BP)神经网络模型的权值和阈值进行赋值,并将优化的BP神经网络模型用于空气质量的预测中,平均绝对误差(MAE)、均方根误差(RMSE)、均方误差(MSE)、平均绝对百分比误差(MAPE)值均小于BP神经网络模型以及基于粒子群优化(PSO)的BP神经网络模型,预测精确度有所提高。
    参考文献 | 相关文章 | 多维度评价
    24. 引入通信与探索的多智能体强化学习QMIX算法
    邓晖奕, 李勇振, 尹奇跃
    《计算机应用》唯一官方网站    2023, 43 (1): 202-208.   DOI: 10.11772/j.issn.1001-9081.2021111886
    摘要443)   HTML12)    PDF (1867KB)(194)    收藏
    非平稳性问题是多智能体环境中深度学习面临的主要挑战之一,它打破了大多数单智能体强化学习算法都遵循的马尔可夫假设,使每个智能体在学习过程中都有可能会陷入由其他智能体所创建的环境而导致无终止的循环。为解决上述问题,研究了中心式训练分布式执行(CTDE)架构在强化学习中的实现方法,并分别从智能体间通信和智能体探索这两个角度入手,采用通过方差控制的强化学习算法(VBC)并引入好奇心机制来改进QMIX算法。通过星际争霸Ⅱ学习环境(SC2LE)中的微操场景对所提算法加以验证。实验结果表明,与QMIX算法相比,所提算法的性能有所提升,并且能够得到收敛速度更快的训练模型。
    参考文献 | 相关文章 | 多维度评价
    25. 基于零模型的含时网络模体识别方法
    胡博仁, 裴忠民, 罗章凯, 丁杰
    《计算机应用》唯一官方网站    2023, 43 (8): 2505-2510.   DOI: 10.11772/j.issn.1001-9081.2022071033
    摘要168)   HTML7)    PDF (2277KB)(70)    收藏

    在带有时间属性的含时网络中,常规的基于频繁子图统计的网络模体识别方法容易受网络规模与结构差异的影响。而与实证网络具有相同规模和某些相同性质的零模型网络能为实证网络的特性挖掘提供了准确的基准,于是提出一种基于零模型的含时网络模体识别方法,用两种网络子图特征比较后的相对值来识别含时网络中的具有显著结构意义的子图。同时,为确定零模型网络何时达到稳定,采用成功置乱次数方法来改进基于时间置乱或时间随机化的含时网络零模型构造方法。在实验阶段,对包含卫星和地面站的46节点全球定位系统(GPS)星座进行仿真实验,确定了零模型网络子图特征稳定时的成功置乱次数;构造10个零模型网络与卫星网络比较,发现反映节点连接具有连续性特点的子图的出现次数仅为最高频子图的1/34,却是卫星网络中最重要的模体。实验结果表明,以零模型为参照的含时网络模体识别方法能更准确地识别出反映网络结构特性和动态变化过程的模体。

    图表 | 参考文献 | 相关文章 | 多维度评价
    26. 基于权重向量聚类的动态多目标进化算法
    李二超, 程艳丽
    《计算机应用》唯一官方网站    2023, 43 (7): 2226-2236.   DOI: 10.11772/j.issn.1001-9081.2022060843
    摘要177)   HTML4)    PDF (3030KB)(57)    收藏

    实际生活中存在许多的动态多目标优化问题(DMOP)。对于此类问题,当环境发生改变时,就要求动态多目标进化算法(DMOEA)能快速和准确地跟踪新环境下的帕累托前沿(PF)或帕累托最优解集(PS)。针对现有算法的种群预测性能差的问题,提出一种基于权重向量聚类预测的动态多目标进化算法(WVCP)。该算法首先在目标空间中生成均匀的权重向量,并对种群中的个体进行聚类,再根据聚类情况分析种群的分布性。其次,对聚类个体的中心点建立时间序列。对同一权重向量,针对不同的聚类情况采取相应的应对策略对个体进行补充,若相邻时刻均存在聚类中心,则采用差分模型预测新环境下的个体;若某一时刻不存在聚类中心,则用相邻权重向量聚类中心的质心作为该时刻的聚类中心,再运用差分模型预测个体。这样不仅可以有效地解决种群分布性差的问题,还可以提高预测的准确性。最后,引入个体补充策略,以充分地利用历史信息。为验证WVCP算法的性能,把它与四种代表性算法进行了仿真对比。实验结果表明,所提算法能够很好地解决DMOP。

    图表 | 参考文献 | 相关文章 | 多维度评价
    27. 信息迁移多任务优化共生生物搜索算法
    程美英, 钱乾, 熊伟清
    《计算机应用》唯一官方网站    2023, 43 (7): 2237-2247.   DOI: 10.11772/j.issn.1001-9081.2022060896
    摘要161)   HTML2)    PDF (3862KB)(58)    收藏

    针对现有共生生物搜索(SOS)算法只能求解单个任务,以及信息负迁移影响多任务优化(MTO)性能这两个难题,提出一个信息迁移多任务优化共生生物搜索(ITMTSOS)算法。首先基于多种群演化MTO框架,根据任务个数设置相应数量种群;然后各种群独立运行基本SOS算法,当某一种群连续若干代停滞进化时,引入个体自身最优经验和邻域最优个体以形成知识模块并将该模块迁移至该种群个体进化过程中;最后对ITMTSOS算法时间和空间复杂度进行分析。仿真实验结果表明,ITMTSOS算法同时求解多个不同形态高维函数时均能快速收敛至全局极值解0,与单任务SOS算法相比,平均运行时间最多缩短约25.25%;而在同时求解多维0/1背包问题和师生匹配问题时,所提算法在测试集weing1和weing7上的最优适应值与目前测试集公布的最优结果相比分别提高了22 767和22 602,师生最优匹配差和平均匹配差的绝对值分别下降了26和33,平均运行时间约缩短了7.69%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    28. 多策略融合的改进黏菌算法
    邱仲睿, 苗虹, 曾成碧
    《计算机应用》唯一官方网站    2023, 43 (3): 812-819.   DOI: 10.11772/j.issn.1001-9081.2022020243
    摘要381)   HTML7)    PDF (880KB)(188)    收藏

    针对标准黏菌算法(SMA)存在的容易陷入局部最优解、收敛速度慢以及求解精度低等问题,提出一种多策略融合的改进黏菌算法(MSISMA)。首先,引入布朗运动和莱维飞行机制以增强算法的搜索能力;其次,根据算法进行的不同阶段分别改进黏菌的位置更新公式,以提高算法的收敛速度和收敛精度;然后,应用区间自适应的反向学习(IAOBL)策略生成反向种群,以提升种群的多样性和质量,从而提高算法的收敛速度;最后,引入收敛停滞监测策略,当算法陷入局部最优时,通过对部分黏菌个体的位置重新初始化使算法跳出局部最优。选取23个测试函数,将MSISMA与平衡黏菌算法(ESMA)、黏菌-自适应引导差分进化混合算法(SMA-AGDE)、SMA、海洋捕食者算法(MPA)和平衡优化器(EO)进行测试和比较,并对算法运行结果进行Wilcoxon秩和检验。相较于对比算法,MSISMA在19个测试函数上获得最佳平均值,在12个测试函数上获得最佳标准差,优化精度平均提升23.39%~55.97%。实验结果表明,MSISMA的收敛速度、求解精度和鲁棒性明显较优。

    图表 | 参考文献 | 相关文章 | 多维度评价
    29. 无人机辅助移动边缘计算中的任务卸载算法
    李校林, 江雨桑
    《计算机应用》唯一官方网站    2023, 43 (6): 1893-1899.   DOI: 10.11772/j.issn.1001-9081.2022040548
    摘要431)   HTML6)    PDF (2229KB)(241)    收藏

    无人机(UAV)灵活机动、易于部署,可以辅助移动边缘计算(MEC)帮助无线系统提高覆盖范围和通信质量,但UAV辅助MEC系统研究中存在计算延迟需求和资源管理等挑战。针对UAV为地面多个终端设备提供辅助计算服务的时延问题,提出一种基于双延迟深度确定性策略梯度(TD3)的时延最小化任务卸载算法(TD3-TOADM)。首先,将优化问题建模为在能量约束下的最小化最大计算时延的问题;其次,通过TD3-TOADM联合优化终端设备调度、UAV轨迹和任务卸载比来最小化最大计算时延。仿真实验分析结果表明,与分别基于演员-评论家(AC)、深度Q网络(DQN)以及深度确定性策略梯度(DDPG)的任务卸载算法相比,TD3-TOADM得到的计算时延减小了8.2%以上。可见TD3-TOADM能获得低时延的最优卸载策略,具有较好的收敛性和鲁棒性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    30. 改进自组织映射的多无人机协同任务分配方法
    孙亚男, 吴杰宏, 石峻岭, 高利军
    《计算机应用》唯一官方网站    2023, 43 (5): 1551-1556.   DOI: 10.11772/j.issn.1001-9081.2022040592
    摘要268)   HTML4)    PDF (2598KB)(113)    收藏

    针对现有算法对多无人机(UAV)协同进行多任务分配时存在负载均衡和执行效率方面的不足,提出一种改进的自组织映射(ISOM)算法。该算法根据飞行时间和任务执行时间设计了UAV的负载均衡度,以提升任务完成的效率;还设计了新的非线性变化的学习率和邻域函数保证ISOM算法的稳定性和快速收敛。然后,在不同任务环境对ISOM算法进行了有效性验证。实验结果表明,与结合遗传算法的粒子群优化(GA-PSO)、Gurobi和ORTools算法相比,ISOM算法的任务完成时间可分别减少15.5%、12.7%和7.3%;在TSPLIB数据集的实例KroA100、KroA150、KroA200上进行航迹长度减小的有效性验证时,与杂草优化(IWO)算法、改进的单亲遗传算法(IPGA)和蚁群单亲遗传算法(AC-PGA)的对比结果表明,ISOM算法在无人机数量为2、3、4、5、8时,均获得了最小的航迹长度。由此可见,ISOM算法在解决多UAV协同多任务分配问题时效果显著。

    图表 | 参考文献 | 相关文章 | 多维度评价
2024年 44卷 3期
刊出日期: 2024-03-10
文章目录
过刊浏览
荣誉主编:张景中
主  编:徐宗本
副主编
:申恒涛 夏朝晖

国内邮发代号:62-110
国外发行代号:M4616
地址:四川成都双流区四川天府新区
   兴隆街道科智路1369号
   中科信息(科学城园区) B213
   (计算机应用编辑部)
电话:028-85224283-803
   028-85222239-803
网址:www.joca.cn
E-mail: bjb@joca.cn
期刊微信公众号
CCF扫码入会