主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘振英,方滨兴,姜誉,张毅,赵宏.一个调度Fork-Join任务图的新算法.软件学报,2002,13(4):693-697
一个调度Fork-Join任务图的新算法
A New Algorithm for Scheduling Fork-Join Task Graph
投稿时间:2000-04-04  修订日期:2001-08-21
DOI:
中文关键词:  任务调度  关键路径  调度长度  DAG
英文关键词:task scheduling  critical path  scheduling length  DAG
基金项目:国家"九五"国防预研基金资助项目(16.6.2.5)
作者单位
刘振英 哈尔滨工业大学,计算机科学与工程系,黑龙江,哈尔滨,150001 
方滨兴 哈尔滨工业大学,计算机科学与工程系,黑龙江,哈尔滨,150001 
姜誉 哈尔滨工业大学,计算机科学与工程系,黑龙江,哈尔滨,150001 
张毅 哈尔滨工业大学,计算机科学与工程系,黑龙江,哈尔滨,150001 
赵宏 哈尔滨工业大学,计算机科学与工程系,黑龙江,哈尔滨,150001 
摘要点击次数: 2370
全文下载次数: 2747
中文摘要:
      任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,
英文摘要:
      Task scheduling is one of the crucial factors influencing the efficiency of a network of workstations. Fork-Join task graphs can represent many parallel structures. All of the existing algorithms which schedule Fork-Join task graphs have ignored the problem that communications cannot be executed in parallel in non-fully-connected NOW, and some of algorithms with high efficiency even did not take the problem of how to save the processors into account. In this paper, a new static task scheduling algorithm called TSA_FJ is proposed,which is based on task duplication and trying to synthetically take the problems of schedule length shortening,unparallel communications and processor saving into account.By randomly generating the task execution time and communication time,several fork-Join task graphs are got and the scheduling results of TSA_FJ are compared with that of other algorithms for the generated task graphs.It shows that TSA_FJ algorithm has the shortest scheduling length and uses much less processors.It is much suitable to non-fully-connected NOW.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利