全比较问题数据分发策略研究

作者简介

高静,内蒙古农业大学计算机与信息工程学院院长、博士生导师，致力于大数据和人工智能在农牧业等领域的应用研究。

内容简介

第3章基于启发式的基因组序列 比对大数据分发模型 为了解决大数据集的全比较问题,将大量的数据文件分 发到分布式计算 系统中会对整体计算性能产生很大的影响。本章提出 了一个启发式的数据 分配策略来处理同构分布计算系统中的全比较问题;从 构建原则出发,从不 同的角度讨论了为全比较问题分发数据文件所面临的 挑战;在分析数据分发 问题的基础上,提出一种基于贪婪思想的启发式数据分 发算法。该数据分发 策略不仅能够节省存储空间和数据分发时间,而且可以 实现全比较问题的所 有比较任务的负载均衡和良好的数据本地化。基于数 据分发的结果,我们还 提出了一种静态任务调度策略和数据分发策略,实现了 让系统以静态负载均 衡的方式分配比较任务。最后,不同的实验验证了该数 据分发策略在同构分 布计算系统中的有效性。 3.文件分发模型的构建 1 1.构建原则 3.1 在分布式系统中进行全比较计算的典型场景描述如图 3. 1所示。一般来 说,数据管理器应该首先管理所有数据并将其分发给计 算节点。然后,计算 任务由作业追踪器生成并分配给计算节点。最后,任务 执行者执行计算任务 来处理相关的数据集。 从图3.1的工作流程可以看出,要有效地解决全比较问 题,需要改进数据 分配和计算阶段。 ·63· 全比较问题数据分发策略研究 图3. 1 分布式环境下全比较计算工作流程 数据本地化和数据分发是分布式环境下大数据处理的 整体计算性能的 两个关键因素。 数据本地化是处理大数据问题的基本原则。这意味着 把计算操作分配 给拥有计算任务所需数据的计算节点通常可以获得更 高的计算效率。由于 繁重的网络通信和数据传输,需要访问远程数据集的计 算任务可能非常低效。 当所有计算节点都分配了与其处理能力相匹配的适当 本书在对全比较问题、全比较问题研究进展、大数据技术进行分析的基础上，对全比较问题进行了形式化描述，着重介绍了基于整数规划的基因组序列比对大数据分发模型、基于启发式的基因组序列比对大数据分发模型、基于粒子群优化的全比较计算数据分发策略等三种全比较问题数据分发策略，构建了面向全比较问题的文件切分评价模型并且实现了面向全比较问题的分布式文件分发框架构建。