摘要
针对在分布式系统下进行多序列比对等全比较计算的数据分发问题,提出了一种基于禁忌搜索优化的全比较数据分发策略用于提高计算效率.首先,以负载均衡、最小化存储为优化目标构建了全比较计算数据分发模型.其次,通过设计n进制编码方式、正向任务调度规则和异节点任务互换等优化算子对标准禁忌搜索算法进行改进,得到了基于禁忌搜索优化的负载均衡数据分发算法和最小化存储数据分发算法并在MATLAB上进行了实现.实验结果表明,本文提出的数据分发策略能让分布式系统达到负载均衡,节约40%-50%的存储空间,实现100%的数据本地化率,相比于主流的全比较数据分发算法具备最快的求解速度.
In order to solve the problem of data distribution for All-to-All comparison calculation such as multiple sequence alignment in distributed system,an All-to-All comparison data distribution strategy based on tabu search optimization is proposed to improve the compute efficiency.Firstly,we construct an all-to-all comparison data distribution model with load balancing and minimizing storage as the optimization goals.Secondly,we obtained load balancing and minimized storage data distribution algorithms based on tabu search that implemented on MATLAB by improving the standard tabu search algorithm′s optimization operators,which are as n-ary encoding,forward task scheduling rules,and different node task interchange.The experimental results show that the data distribution strategy proposed in this paper can enable distributed system to achieve load balancing,save 40%-50%of storage space,and achieve 100%data localization rate.Compared with popular all-to-all comparison data distribution algorithms,it has the fastest solution speed.
作者
邓丹
李雷孝
高静
杨艳艳
王永生
DENG Dan;LI Lei-xiao;GAO Jing;YANG Yan-yan;WANG Yong-sheng(College of Data Science and Application,Inner Mongolia University of Technology,Hohhot 010080,China;College of Computer and Information Engineering,Inner Mongolia Agricultural University,Hohhot 010011,China)
出处
《小型微型计算机系统》
CSCD
北大核心
2022年第11期2293-2301,共9页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61462070)资助
内蒙古自治区自然科学基金面上项目(2019MS06027)资助
内蒙古自治区科技重大专项项目(2019ZD015,2019ZD016)资助
内蒙古自治区关键技术攻关计划项目(2019GG273,2020GG0094)资助
内蒙古自治区科技成果转化专项资金项目(2020CG0073)资助。
关键词
全比较
数据分发策略
禁忌搜索
负载均衡
最小化存储
all-to-all comparison
data distribution strategy
tabu search
load balancing
minimizing storage
