异构处理单元独立任务批模式任务调度算法研究

VIP免费

3.0 陈辉 2024-11-19 6 4 641.77KB 48 页 15积分

侵权投诉

摘要

随着互联网的迅速发展，需要计算机解决的和计算机可以解决的应用领域的

问题越来越复杂、规模也越来越大。在互联网上广泛分布着丰富的可共享的、异

构的、动态的资源，随之便产生了可以利用互联网实现高度共享这些地理上分散

的资源的互联网技术——网格技术。网格技术就是通过互联网或一些专用网络将

地理上广泛分散分布的、异构的、动态的各种资源组织互联或者重新整合，以实

现资源的全面共享和协同工作。

任务管理、任务调度和资源管理是网格系统必须具备的三个基本功能。任务

调度就是合理解决需要处理的任务在各种异构资源之间的动态最优匹配调度，任

务调度是网格技术研究的重点之一，是网格系统的一项核心技术。在网格系统中，

资源是动态的、异构的且自治的，不同的任务调度算法可能有不同的目标，有的

是为了使某些任务被优先处理，有的是为了使任务完成的时间最少，有的是为了

使任务以最低的经济成本来处理，由于网格资源的特点和任务的复杂性，所以网

格环境中的任务调度极其复杂，任务调度面临的是一个 NP 完全问题。在网格系统

中，任务调度也就成为了制约网格技术的一个瓶颈。

本文首先详细概述了网格计算的相关概念和发展现状，阐述了任务调度在网

格计算中的重要性，提出一种综合考虑计算能力、动态调度及负载平衡的任务调

度算法。

关键词：网格技术任务调度负载平衡动态最优匹配调度

ABSTRACT

With the fast development of the Internet, computer applications need to solve the

more complex problem, more and more large-scale. Shared, heterogeneous and dynamic

resources widely distributed on the Internet, with the attendant will have a new Internet

technology which utilizes the Internet to make geographically dispersed resources full

share—Grid Technology. Grid Technology will make geographically dispersed

resources, heterogeneous resources and dynamic resources interconnected or

re-integration by Internet or some private network, which aims at realizing resources

comprehensive sharing and collaboration.

Task management, task scheduling and resource management are three basic

functions in grid system. Task scheduling is a reasonable solution to find the optimal

and dynamic match between tasks and a variety of resources, which is one focus of

studying Grid and a core technology in Grid System. In the grid system, resources are

dynamic, heterogeneous and autonomous, different scheduling algorithms may have

different goals, some tasks are to make some priorities, some to make the task

completion time at least, some to make the task with minimal economic cost to deal

with, due to the characteristics of grid resources and the complexity of the task, so the

task scheduling in the grid environment is extremely complex. Task scheduling is facing

a NP-complete problem. In the grid system, task scheduling has become a bottleneck

restricting the grid.

In this paper, firstly introduce overview of the concepts of grid computing and the

development status, describes the importance of task scheduling. Finally, projects the

task scheduling algorithm which considers the computing power of an integrated,

dynamic scheduling and load balancing.

Key Words ：Grid Technology, Task Scheduling, Load Balance,

Dynamic Optimal Scheduling Match

摘要

ABSTRACT

第一章绪论 ........................................................ 1

§1.1 课题研究背景和意义 ......................................... 1

§1.2 课题研究内容 ............................................... 2

§1.3 本文组织结构 ............................................... 3

第二章相关技术 .................................................... 4

§2.1 网格计算综述 ............................................... 4

§2.2 网格计算 ................................................... 5

§2.2.1 网格计算的特点 ........................................ 5

§2.2.2 网格计算的应用 ........................................ 6

§2.3 网格计算的国内外发展现状 ................................... 7

§2.3.1 网格计算国外发展现状 .................................. 7

§2.3.2 网格计算国内发展现状 ................................. 10

§2.4 本章小结 .................................................. 11

第三章网格任务调度 ............................................... 12

§3.1 网格任务调度综述 .......................................... 12

§3.1.1 网格计算中任务调度的重要性 ........................... 12

§3.1.2 网格任务调度特点 ..................................... 13

§3.1.3 网格任务调度的性能指标 ............................... 15

§3.2 网格任务调度的分类 ........................................ 15

§3.3 经典批模式任务调度介绍与分析 .............................. 16

§3.4 本章小结 .................................................. 17

第四章异构处理单元独立任务批模式任务调度算法 ..................... 18

§4.1 任务模型 ................................................... 18

§4.2 算法模型 .................................................. 20

§4.3 算法思路 ................................................... 25

§4.4 算法推导过程 ............................................... 32

§4.5 算法实例 .................................................. 33

§4.6 实验结果分析 .............................................. 39

§4.7 本章小结 .................................................. 40

第五章总结与展望 ................................................. 41

§5.1 论文工作总结 .............................................. 41

§5.2 后续工作的展望 ............................................ 42

参考文献 ............................................................ 43

在读期间公开发表的论文和承担科研项目及取得成果 ...................... 45

致谢 ............................................................... 46

第一章绪论

§1.1 课题研究背景和意义

随着信息的全球化和科技的迅猛发展，对高性能计算的需求是越来越大，多

年以来高性能计算基本都是以研制更具高性能的并行计算机为目标，微处理器性

能的提升大都是在提高指令级的并行度或处理器的主频基础上进行的，但是现在

CPU 集成电路技术正逐渐走向技术的极限，因此不能再把通过提高指令并行度和

主频来提高计算机性能作为唯一的技术途径了，需寻求其它更有效的途径来提高

计算机的性能，网格计算[1]就是可选途径之一。使用网格计算进行分布并行处理，

使得以较低成本完成大型的科学计算成为了可能。网格是集成的计算与资源环境，

它可以充分汲取各类计算资源，并将它们转化成更经济的、随处可得的、标准的、

可靠的计算能力，以此来实现各种资源全面共享的目的。但是，网格计算同时也

面临着很多巨大的挑战，如算法的设计、资源的管理、通信的协调、任务的划分

和任务的调度[2]，诸如这些棘手问题若不解决，也就不能从网格分布并行处理中得

到任何好处。作为网格计算中的核心问题之一，网格任务调度是影响网格系统性

能的关键，当某个程序实现一组任务之后，就需要将这些任务合理地分配到网格

系统中的某些处理单元上，如果任务调度不当就很可能会抹煞网格计算的优点，

甚至比传统处理效果还要差。自网格计算被提出之日起，任务调度就是网格计算

系统中广大学者研究的重点。多任务调度本来就是调度理论中的经典问题，其计

算复杂性已经被确认是 NP 完全的，而且是强 NP 完全的，是最难的组合优化问题

之一。而在网格环境下的任务在不同处理单元上的执行处理具有不同的特性，更

是给任务调度提出了更大的挑战。任务调度问题的研究是跨学科研究领域的，既

属于计算机科学领域，也属于应用数学领域、统筹学领域和人工智能领域运，所

以研究求解网格中任务调度的高效算法具有非常重要的理论意义和应用意义。

任务调度目的是在满足一定的约束关系和一定的性能指标的前提下，将可执

行的任务按适当的分配调度策略确定一种执行顺序和指派，把指定的任务合理有

效地分配到各可用处理单元上让其有序地执行，以此来达到减少任务总执行时间

的目的。任务调度有很多种分类方法，按照任务调度的时机，可将调度类型分为

静态调度和动态调度两类，通常静态调度就是在编译时已确定了程序的特点和性

质，比如任务的通信和同步要求、处理时间和数据依赖等，在静态调度中最常用

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要随着互联网的迅速发展，需要计算机解决的和计算机可以解决的应用领域的问题越来越复杂、规模也越来越大。在互联网上广泛分布着丰富的可共享的、异构的、动态的资源，随之便产生了可以利用互联网实现高度共享这些地理上分散的资源的互联网技术——网格技术。网格技术就是通过互联网或一些专用网络将地理上广泛分散分布的、异构的、动态的各种资源组织互联或者重新整合，以实现资源的全面共享和协同工作。任务管理、任务调度和资源管理是网格系统必须具备的三个基本功能。任务调度就是合理解决需要处理的任务在各种异构资源之间的动态最优匹配调度，任务调度是网格技术研究的重点之一，是网格系统的一项核心技术。在网格系统中，资源是动态的、...

展开>> 收起<<

异构处理单元独立任务批模式任务调度算法研究.pdf

共48页,预览5页

还剩页未读，继续阅读

异构处理单元独立任务批模式任务调度算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: