一种独立任务调度问题的相对量化模型  

A relative quantitive model for independent task scheduling problem

作　　者：白兴宇 赵春晖[1] 姜煜 

机构地区：[1]哈尔滨工程大学信息与通信工程学院,黑龙江哈尔滨150001

出　　处：《哈尔滨工程大学学报》2007年第5期571-576,共6页Journal of Harbin Engineering University

基　　金：水声技术国防科技重点实验室基金资助项目(OOJS23.8.1CB0104);高等学校优秀青年教师教学科研奖励计划基金资助项目(2001-226)

摘　　要：在分布式处理领域,独立任务调度问题是一个NP难题.现有各种调度模型普遍采用基于运行时间的任务量化方式,这使得异构系统调度问题较同构系统更为复杂,因为异构系统中同一任务在不同节点上的运行时间不等.该文提出了一种独立任务调度问题的相对量化模型,该模型采用一种相对量化方案来量化任务的载荷量和计算节点的负载能力及负载状况.基于该模型,可用LPT、AI之类的同构调度算法解决异构调度问题,从而使异构调度问题的复杂度降到与同构调度问题相当.理论分析与实验研究证明了新模型的有效性和良好的工程实用性.In the field of distributed processing, the independent task scheduling problem is known to be NP-complete. Its complexity increases when task scheduling is to be done in a heterogeneous computing system, where the processors in the network may not be identical and the processing time for the same task is varied. In this paper a relative quantitative model for the independent task scheduling problem is presented based on a new method to quantize the workload of tasks and the capacity of computational nodes. Its characteristics are analyzed by comparing them with existing scheduling models. Based on the new model, heterogeneous scheduling problems may be worked out with homogeneous scheduling algorithms, such as LPT, AI, etc. , reducing the complexity of the heterogeneous scheduling problem to be similar to that of homogeneous scheduling problems. Theoretical analysis and computer simulations indicate that the new relative quantitive model is effective and superior to existing models.

关 键 词：异构系统 独立任务 相对量化模型 任务调度 

分 类 号：TP338.8[自动化与计算机技术—计算机系统结构]