【作者】 熊科浪；

【导师】 孙济洲；

【作者基本信息】 天津大学 ， 计算机应用技术， 2008， 硕士

【摘要】 网格计算在动态多机构的虚拟组织中协调资源共享和协同求解问题。负载平衡均衡所有结点上的负载,提高系统的资源利用率,减少任务平均响应时间。可分负载理论是进行并行分布式任务调度实现负载平衡的一个模型,有易于处理、可操作性强、扩展性好、适用于多数网络拓扑结构、易于与实际结合等优点,因此在数据密集型网格计算中进行可分负载理论的研究和应用深受研究人员的青睐。本文应用并行传输,计算通信可重叠的可分负载理论求解天文图像合成网格服务的任务分配和再分配问题,取得了一些成果。本文首先设计了天文图像合成网格服务的系统结构,分析总结了该网格服务四个主要工作流程,设计了该网格服务的服务流程。然后讨论了天文图像合成网格服务的任务分配问题。通过对基于蚂蚁算法的网格任务调度方法进行分析和改造,提出了基于蚂蚁算法的性能预测方法以进行简单高效的性能预测,为负载平衡提供支持。针对该网格服务四个工作流程建立了根结点提交二次叠加、根结点提交一次叠加、根结点处理二次叠加和根结点处理一次叠加四个可分负载模型。为了更好的处理存储限制问题,提出了一种比增量平衡策略算法更快适用范围更广的快速存储限制分配算法。基于已有求取次优解的整数逼近算法,提出了增一堆排序整数逼近算法以求取可分粒度问题的最优解。基于以上的模型和算法,设计了该网格服务的任务分配总体流程。通过仿真实验分析选取了基于蚂蚁算法的性能预测方法的算法参数。最后讨论的是天文图像合成网格服务的任务再分配问题。选取CPU就绪队列长度、磁盘请求队列长度和任务进度三个负载参数衡量资源性能,提出了基于连通分图的负载聚类方法以决定是否需要任务迁移及迁移任务的发送者和接收者。通过分析任务迁移后总完成时间变化规律建立了该网格服务任务再分配的可分负载模型。提出了该网格服务的任务再分配算法。本文对天文图像合成网格服务的任务分配和再分配模型和算法进行了深入的研究和设计,给出了多项式时间求取该网格服务负载平衡最优解的完整方案,提高网格系统性能。更多还原

【Abstract】 Grid Computing implements resource sharing and coordinated problem solving in dynamic, multi-institutional virtual organizations. Load balance tries to balance the load of every computer node. Divisible load theory(DLT) is a methodology that implements load balance in data-intense parallel and distributed system scheduling. The paper uses the DLT to solve the task allocation and reallocation problem of astronomical image mosaicking grid service.Firstly, the system architecture of the grid service is designed. Four workflows are analysed and summarized. The service flow of the grid service is put forward.Secondly, the task allocation of the grid service is discussed. By making a deep research into the grid task scheduler based on the ant algorithm, the author brings forward a simple and effective performance prediction method based on the ant algorithm to support the load balance. Root submitting twice adding, root submitting once adding, root computing twice adding and root computing once adding divisible task models are proposed. To tackle the storage constraint and divisible granularity problems, a faster and wider used storage constraint allocation algorithm than IBS and increasing one heap sort optimum integer approximation algorithm based on a suboptimum integer approximation algorithm are designed. The task allocation flow based forenamed models and algorithms is found. A simulaton for choosing the parameters of the performance prediction method based on the ant algorithm is done.Finally, the task reallocation of the grid service is discussed. CPU queue length, disk request queue length and task progress rate are chosen to weigh the resource performance. A load cluster method based on connected subgraph is proposed to decide whether task migration is needed and the sender and receivers of it. By analysing the change of the complete time after the task migration, the author derives a task reallocation divisible task model. A task reallocation algorithm of the grid service is designed.The task allocation and reallocation models and algorithms of astronomical image mosaicking grid service are researched and designed. A integrated solution that can get the optimum allocation of the load balance of the grid service in polynomial time is presented to improve the grid system performance.更多还原