任务调度算法（共11篇）
任务调度算法 篇1
0 引 言
互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布式计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算技术[1]的发展则迎合了21世纪并行与分布式计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境。
网格资源包括计算资源、存储资源和通信资源。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。如何使这些资源高效地完成计算任务是网格系统的研究重点之一。
由于在网格环境下的任务调度主要考虑的是一组相互独立、任务之间没有通信和数据依赖的元任务(metatask)映射。现有的任务调度算法可以分为在线模式(on-line)和批模式(batch-mode)两种。在线模式是任务一到来就加以映射,而批模式则是把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言,批模式得到了大量的资源信息,从而可以做出更合理的任务映射策略。在这里讨论的是批处理模式的任务调度,即调度程序的执行周期到时再集中映射。
以时间跨度(makespan)为优化目标的任务—资源映射是一个NP完全问题,解决这类问题常用启发式算法。经典的批模式算法有Min-min、Max-min、Suffrage、遗传算法、蚁群算法等。T.Braun[3]等人通过对一些常用的算法进行了比较,在一定规模时遗传算法所求出的时间跨度要优于其他算法一些,但随着规模扩大,其收敛性降低[4],因此本文提出了将遗传算法和Min-min算法相结合的改进遗传算法的任务调度优化模型,该算法也适合大规模任务的调度,并进行了仿真实验。
1 问题描述
任务调度问题的实质[2]就是在一个有n个需要调度的任务、m个可用的资源(主机或集群) 的网格环境下,把n个子任务J={J1,J2,…,Jn}以合理的方式调度到m个资源R={R1,R2,…,Rm}上去,目的是得到尽可能小的总执行时间,提高系统吞吐量等。具体描述如下:
(1) J是n个需要调度的任务集合,Ji表示第i个任务。每个任务的任务量大小用百万指令(MI)表示,且每个任务只能一个资源上执行完成。
(2) R是m个可用的资源集合,Rj表示第j个资源。每个资源的计算能力用百万指令每秒(MIPS)表示。
(3) n个任务在m个不同资源上的预测执行时间ETC( Expected Time to Compute)是一个n×m的矩阵。矩阵中的每一行代表某一个任务在m台资源上的不同执行时间,每一列代表在同一台资源上n个任务的不同执行时间。ETC(i,j)表示第i个任务在第j个资源上的执行时间。
(4) 资源j的最早可用时间为STARTTIME(j)。
(5) 把任务i所需的数据从存储系统传输到资源j上的传输时间为TRANS(i,j)。
(6) 第i个任务在第j台资源上的预测最小完成时间为MCT(i,j),则MCT(i,j)=STARTTIME(j)+TRANS(i,j)+ETC(i,j)。
(7) 任务i的最小完成时间为Ci,当任务分配给第j个资源时,Ci=MCT(i,j)。
(8) 所有任务都执行完成的时间为时间跨度(makespan),即makespan=Max{Ci,i=1,2,…,n}。
2 设计与实现
遗传算法(GA)是Holland于1975 年受生物进化论的启发而提出的,并行性和全局解空间搜索是GA的两个最显著的特点。网格任务调度问题是一个NP问题,在一定规模时,用遗传算法进行网格任务调度能得到很好的性能。Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的时间跨度。遗传算法随着调度规模的扩大,在一定调度时间限制内,它的收敛性会逐渐降低。因此,本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法。
2.1 Min-min算法
Min-min算法的主要思想如下(仍然考虑n个任务,m个执行单元的情况):
(1) 对集合中每一个等待分配的任务T,分别计算出分配该任务到m台机器上的最小完成时间,这就得到了一个n×m的MCT矩阵。
当需要调度的任务集合非空时,反复执行以下操作直至集合为空:
(2) 利用MCT矩阵,对集合中每一个等待分配的任务分别找到能够最短时间完成该任务的执行单元及最短完成时间,在所有的最短完成时间中找出最小的最短完成时间对应的任务a,设其对应的主机为b,把任务a分配到机器b上。
(3) 从任务集合中把任务a删除,同时更新MCT矩阵。
2.2 染色体的编码与解码
染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码)或者间接编码。本文采用间接编码方式,对每个子任务占用资源编码。染色体的长度等于子任务的数量,染色体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号。假设有10个子任务,3个可用资源,则染色体串长为10,每个基因的值则为随机产生的3个资源的编号,则可以随机产生了下面的一个染色体编码:
{2,1,3,2,2,3,1,1,3,1}
这个染色体代表第一个任务由第二个资源上运行,第二个任务由第一个资源执行,以此类推,第十个任务由第一个资源执行。染色体以数组形式存放。
产生了一个染色体后,还必须对其进行解码,得到不同资源上任务的分布情况。将任务按照占用的资源分类,生成多组按照资源编号分类的任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的任务,这样我们就得到了所有任务在多个资源上运行的分布情况。以上面的染色体为例,解码后产生3个资源的任务序列:
R1:{2,7,8,10} R2:{1,4,5} R3:{3,6,9}
这样就可以计算出每个资源完成该资源上分配的所有任务花费的时间,最大花费时间即为时间跨度。
2.3 初始种群生成与适应度函数
在网格环境下,对任务调度的实时性有较高的要求,为提高算法收敛的速度以及改善算法的结果,要求初始种群既具有随机性的个体,又具有一些比较优秀的个体。本调度算法是在Min-min算法基础上,采用遗传算法对其性能进行提高,又可以避免单独采用遗传算法对大规模任务资源匹配的低收敛性。我们可以先将用Min-min算法产生的染色体作为初始种群的优秀个体,再随机产生其他个体。
遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。由于网格调度的目标是时间跨度尽可能小,因此适应度可定义为:
fitness(i)=1/makespan(i)
即染色体i的适应度值等于该染色体的时间跨度的倒数。若时间跨度越小,则适应度值越大,被选择的可能性越大。
2.4 个体选择
选择操作是决定父代种群中哪些个体,以及能以多大可能性被挑选来复制或遗传到下一代的进化操作。选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向:挑选最优秀个体,使算法避免无效搜索且能快速搜索到问题的最优解。
假设本算法的种群大小为popsize,为了保留优秀个体,先选择Min-min算法产生的个体和父代中的最优个体,其他的popsize-2个个体采用轮盘赌法[5]进行选择。个体的选择概率为:
Pi=fitness(i)/∑fitness(j)
需要进行popsize-2轮选择。每一轮产生一个[0,1]均匀随机数,若该数位于某个体累积概率下的那个区间,则选择该个体。
2.5 交叉与变异
交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。这里的交叉算子采用多点交叉,对于m个交叉点的多点交叉,随机选择m个交叉位置,在交叉点之间的变量间续地相互交换,产生两个新的后代,但在第一位变量与第一交叉点之间的一段不做交换,交叉点的个数根据染色体的长度进行选择。多点交叉具有很强破坏性,可以促进解空间的搜索。
变异本身是一种局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,是遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。
这里变异算子实质上就是将某个子任务迁移到另一个资源上执行,为了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行。
2.6 算法流程
(1) 随机产生n个任务,m个资源,根据任务的任务量大小和资源的计算能力生成一个n×m的初始MCT矩阵。
(2) 根据Min-min算法生成一条对应该调度的染色体。
(3) 随机产生大小为M的初始种群,根据每个资源上的子任务的执行序列,计算每条染色体的适应值。
(4) 选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群。
(5) 判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(4)。
3 仿真结果与分析
本文的实验是对gridsim、遗传算法、Min-min算法深入研究的基础上进行的,任务的长度范围、资源的执行能力范围、任务分配给某一资源的执行时间等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法用到的主要参数有:解的群体规模为20,交叉和变异概率分别为0.8和0.2,任务个数为表2中的几种,资源个数为10,算法终止条件设为到达一定的进化终止代数,最大进化代数设为100,如果算法连续20代没有找到更好的解我们则认为算法基本收敛。
图1描绘了三种算法时间跨度随任务数大小的变化曲线。从图中我们可以看出:改进GA相对于Min-min算法在性能上会普遍有所提高;对于GA,当任务数较少时(小于40个),性能对于Min-min算法也会提高,较小还高于IGA,随着任务数的增加,性能会逐渐下降,甚至还低于Min-min算法。所以GA不太适合用于大规模的网格任务调度,而本文提出的这种改进遗传算法对网格任务调度普遍适用。
4 结束语
用遗传算法和Min-min算法作为网格任务调度算法已经得到广泛的应用。当规模较小时,遗传算法被证明是一种最有效的启发式调度算法,但随着资源数和任务数的不断增加,遗传算法的性能逐渐降低,到达一定规模时甚至还低于Min-min算法,这样不仅性能得不到提高,而且还会增加调度时间。本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法,这种算法对于大规模任务调度性能也比较高。
由于本文在设计时没有将经济因素考虑在内,下一步的工作可以将开支预算与时间期限考虑在内,再结合本算法,可用于基于经济模型的网格任务调度。另外,模拟退火算法局部搜索能力比较强,遗传算法全局搜索能力较强,将两者结合搜索能力会尽一步提高,性能可能会有所提高。
参考文献
[1]Foster I,Kesselman C.The Grid-Blueprint for a New Computing Infra-structure.Morgan Kaufmann Publishers,1998.
[2]Abraham A,Buyya R,Nath B.Nature’s heuristics for scheduling jobs on computational grids.In The8th IEEE International Conference on Advanced Computing and Communications India,2000.
[3]Braun T,Siegel H,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810-837.
[4]Carretero J,Xhafa F.Using genetic algorithms for scheduling jobs in large scale grid applications.In Workshop of the European Chapter on Metaheuristics EUME2005,Metaheuristics and Large Scale Optimiza-tion.Vilnius,Lithuania,2005(5):19-21.
[5]王小平,曹立明.遗传算法[M].西安:西安交通大学出版社,2002.
任务调度算法 篇2
FCFS 算法是优先为最先到达的请求服务。例如，有如下请求磁盘服务队列，要访问的磁道数分别是：
98，183，37，122，14，124，65，67
排在前面的是先到达的请求，假设磁头目前停留在53磁道上，按照先来先服务的算法，接下来磁头的移动顺序依次是：
53—>98—>183—>37—>122—>14—>124—>65—>67
这个过程总共移动了(98-53)+(183-98)+(183-37)+(122-37)+(122-14)+(124-14)+(124-65)+(67-65)=640个磁道
这种调度法产生的磁头移动服务太大，磁头频繁的大幅度移动，容易产生机械振动和误差，对使用寿命有损害。所以，要设计好的算法来减少磁头移动幅度，减少服务时间，改善磁盘的吞吐量。
2、最短寻道时间优先法(SSTF)
??优先服务接近于磁头当前位置的请求。SSTF从本质上将是SJF(最短作业优先算法)调度的形式。使用SSTF调度算法，上面那个请求队列的执行顺序是：
??53—>65—>67—>37—>14—>98—>122—>124—>183
总共移动了236个磁道，比FCFS的三分之一多一点，明显改善了磁盘服务，
??但是这种算法并不是最优的。例如，若把磁头从53道移动到37道(尽管不是靠的最近的)，然后移动到14，接下去是65，67，98，122，124，183，总共移动了208个磁道<236。
??SSTF也可能导致某些请求长期得不到服务(即“饥饿”问题)。如果当前磁头附近总会不断的到来新的请求，那么距离磁头远的请求将会一直等待下去。
3、扫描法(SCAN)
由于请求服务的队列具有动态性质，总会有新的请求到达 ，因此可采用扫描算法。读/写磁头从磁盘的一端出发，向另一端移动，遇到所需的磁道时就进行服务，直至到达磁盘的另一端。在另一端上，磁头移动方向反过来，继续做下面的服务。这样磁头就连续从盘的一端扫到另一端。
根据前面的例子，但要知道磁头移动的方向和它最近的位置。如果磁头向0道方向移动，则先为37道和14道服务。到达0道，磁头移动方向反过来，并移向磁盘的另一端，接下来服务序列分别是65，67，98，122，124，183。
在具体实现算法时，没有必要让磁头总是从磁盘的一端移到另一端。更通常的做法是：磁头仅移到每个方向上最远的请求磁道上，一旦在当前方向上没有进一步的服务请求了，磁头的移动方向就会反过来，继续为下面的请求服务。这种算法也称为“电梯算法”。例如上面的例子，磁头服务了37，14后发现前面没有新的请求了，就不会向前继续移动到0道，立即掉头服务65道……
这种算法会产生的问题是：假定对磁道的请求是均匀分布的，当磁头到达一方最远端并反过方向时，立即落在磁盘后面的请求相对而言很少，因为这些磁道刚刚得到过服务，而在盘的另一端却有较多的请求，其等待的时间也最长。
4、巡回扫描法(C-SCAN)
Linux CFS调度算法分析 篇3
关键词：Linux调度O(1)CFS调度器红黑树
1 linux进程调度的概述
所谓进程调度就是指操作系统正确的匹配CPU时间之后来准确的执行等待中的进程。怎样从若干个可运行的进程里面找到其中最优先的进程执行的同时又能保证响应时间短、吞吐量高是进程调度的核心所在。进程调度有何时启动调度器和调度器执行什么调度算法两部分。
进程调度的要求就是吞吐量大、响应时间快、周转时间短以及效率高。由进程的响应时间Linux内核可以把进程分为三类：实时进程、批处理进程和交互进程。根据这三类进程内核又产生了三种不同的调度方法：先进先出策略（SCHED_FIFD）、轮转策略（SCHED_RR）和适合交互分时的程序（SCHED_OTHER）。
2 进程调度算法
①当CPU运行进程时，调度是被禁止的；只有当CPU处于无进程运行时，可以进入调度。
②当准备队列空闲时，执行缺省的idle-task、进程。
③当准备队列非空闲时，执行的进程需要调度器在准备队列中挑选出来。这时，goodness（）函数将会从调度器在准备队列中挑选出来的进程中计算其权值，只有权值最大才能有执行的优先级。
④如果经过goodness（）函数计算之后每个进程的权值均是0，则说明CPU所提供给实时进程的准备队列中进程的时间片全部用光了，需要进行重置之后返回步骤①，继续执行调度。
⑤当实时进程都执行完成之后，CPU将对普通进程开始支持。当每一个普通进程的权值均是0时，则说明CPU所提供给普通进程的准备队列中进程的时间片全部用光了，需要进行重置之后返回步骤①，继续执行调度。
3 linux从O(1)调度器到CFS调度器
3.1 O(1)调度器
在Linux新版本Linux2.6.22中，其内核采用的是O（1）调度器，其不仅仅能够支持SMP并且可以确保系统的负载和处理器的数目如何变化，其判断相对应的任务所匹配CPU所利用的时间是不变的。
有2种不同的任务是O（1）调度器的分内工作：
①计算动态任务优先级。利用公式dynamicpriority=max（100，min（staticpriority-bonus+5,139））进行计算。
②当拥有最高优先级的进程执行过程中，选择出下一个需要进行执行的进程。CPU利用调度器对所有进程进行了任务排队：expired数组与active数组。其数组中的某一元素寄存着该任务队列某一优先级的指针，如果需要判断下一个执行的进程时，并不需要将所有的队列进行遍历，只需要在active数组排列好的队列中直接选择优先级最高的进程进行执行。上述方法的复杂度是O（1）。
为了让交互式任务的响应速度变得更快，任何一次时钟中断里，处于执行的任务的时间片减一，如果时间片是O的时候，将对其类型进行判断，若是交互式任务，需要将时间片进行重置然后将active数组再次插入其中；若不是交互式任务，需要把active数组转到expired数组中，如此便可以让CPU优先被交互式任务所使用。当然，并不能够将进城长期的放在active数组里面，当CPU被交互式任务占用达到了一定的数值时，将会把任务转到expired数组中去。如果active数组处于空的状态时，则将两个数组进行互换，从而执行下一轮调度。
O（1）调度器的优点已经显而易见了，与此同时其算法也存在一些不可避免的缺陷，如执行导交互式任务的时候反应速度并不理想。多任务队列和动态优先级是O（1）调度器所应用的相对繁琐的方法，这样就迫使了调度器较为繁琐以及对代码维护的时候难度非常之大。此外，在实际使用的时候发现，相对于在类似于服务器等不存在较大的交互性应用需求的时候，在桌面应用这种对交互性要求很高的环境下，O（1）调度器的效果表现非常不理想。基于这种缺点，Ingo Molnar研发了新的完全公平调度器 (Completely Fair Scheduler，CFS)，此款调度器与O（1）调度器的框架完全不同，在Linux2.6.23版本中，就将CFS作为默认调度器进行使用。
3.2 CFS 调度器
3.2.1 算法的主要思想
CFS并没有采用以往的将进程进行排列分组以及进行动态的优先级分类，也没有采用睡眠时间的概念，同时也没有将任务分为交互任务和其他，CFS则是引入了一个新的概念——红黑树；所谓红黑树就利用时间来计算一个键值从而来选择下一个执行进程，进而利用全部进程所对CPU所利用的时间状态来调度任务。全部的准备状态中的进程被赋予的键值数值被放在红黑树的叶子节点上，按照键值从小到大一次排列在从左到右。在任何一个调度点上，调度器会从红黑树排列好的进程从左至右的对CPU进行进程的调度，这种执行的复杂度为O（log2N）。
在所有的时钟中断上面，其首要的任务是更新调度信息，其次是对红黑树上的排列好的进程进行进一步的调整。当检测到正在执行的进程并不是最左边的进程时，将对其进行need_resched标记，当执行中断返回的时候就要利用scheduler_tick（）来完成对进程的切换，如果没有这个过程，CPU将会被一直占用。
3.2.2 红黑树
CFS依靠进程的虚拟运行时间作为其变量，进而使用红黑树把每一个准备好执行的进程排列成“runqueue”。CFS将之前一直运用的FIFO以及Hash映射形式的线性“qunqueue”彻底移除，每一个runqueue都是利用红黑树来进行组成的。
红黑树的特点也是非常明显的：首先，红黑树上的每一个节点都能够保证一项规律，那就是该节点的左边节点永远小于该几点，相对的右边的节点就大于该节点，这就是之所以红黑树从左至右依次增大的效果；其次，红黑树上分布的所有节点都是均匀的，绝对不会出现不均匀的情况；最后，其操作代价非常低，插入、查找以及删除的代价都是0（logn）。在CFS实际的应用中，表现最为突出的还是第一条特点。
该算法中，每一个节点都作为virtual_runtime键值植入到红黑树里面，当有进程需要进行执行的时候，将键值进行更新之后植入到红黑树，之后从左至右的一次进行执行进程。
当CFS进行调度的过程中，其复杂度是O（logn），可是因为CFS具有实现代价低的特点，实际执行的过程中，反应速度反而快了很多。此外，Linux中的CFS还赋予了很多可操作性的功能，像可以进行灵活配置的调整选项等，这样可以让用户在任何情况之下都能够得到最好的性能体验。
3.2.3 源代码分析
我们参考内核2. 6. 24 源代码中的sched. c 和sched_fair. c来分析:
Scheduler_tick()函数是Sched.c中的一个函数，Scheduler_tick()函数改变当前的时间值与clock 值后CPU会刷新当前的负载情况，最后调用sched_class函数和task_tick( ) 函数。
static void task_tick_fair(struct rq* rq，struct task_struct * curr)
{
struct cfs_rq* cfs_rq;
struct sched_entity* se = ＆curr － > se;
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
entity_tick(cfs_rq，se);
}
}
task_tick_fair函数的目的是使待调度任务执行entity_tick()函数:
static void entity_tick( struct cfs_rq * cfs_rq，struct sched _entity *
curr)
用函数dequeue_entity( )与enqueue_entity( )的主要目的是在红黑树里把任务删除在插入到红黑树里用来调整任务在红黑树里的位置。_pick_next_entity()函数是返回到CFS中红黑树的最左边的叶子节点，如果发现这个节点它不是当前的任务，那么就调用_check_preempt_
curr_fair( ) 设置调度标志，当中断返回时就会调用schedule_tick() 进行调度，替换当前任务。
参考文献：
[1]杜慧江.Linux内核2.6.24的CFS调度器分析[J].计算机应用与软件，2010(2).
[2]冯宇.Linux进程调度算法分析[J].计算机与现代化，2009(6).
[3]张永选.Linux 2.6 内核调度机制剖析与改进[J].计算机系统应用，2009(11).
网格中任务调度算法研究 篇4
1 网格中任务调度算法概述
在异构的网格系统中,根据任务一机器的映射策略在任务执行前是否可以调整,可将这些启发式任务调度算法分为静态调度算法和动态调度算法两大类。
1.1 静态任务调度算法
静态调度算法[1,2]是指所有的机器一任务映射策略在执行任务调度前就已经全部确定。现在网格计算中,常用的静态调度算法有OLB(Opportunistic Load Balancing)、MET(Minimum Execution Time)、MCT(Minimum Completion Time)、Min-min、Max-min、Duplex(Min-min算法与Max-min算法的结合)、GA(Genetie Algorithms)、SA(Simulated Annealing)、GSA(Genetic Simulated Annealing)、Tabu(禁忌调度算法)、A*(基于u叉树算法)、蚁群优化等。
1.2 动态任务调度算法
动态调度算法[1]是指,部分机器一任务映射策略在执行任务调度期间根据实际情况进行确定。现有的动态调度算法可以分为两类:在线模式(on-Line mode)和批模式(Batch mode)[3]。在线模式是指,每当网格调度器收到一个用户提交的任务,立即为之选择适合的计算系统,并将任务发送到该计算系统。而在批模式下,每当网格调度器收到一个任务,不是立即映射到计算系统,而是检查是否凑够一批任务,当凑够一批任务时,才为这些任务确定各自适合的计算系统。
1.3 静态和动态任务调度算法比较
静态算法相对较为简单,调度算法运行开销低,对数据的依赖性小,因而静态调度算法是网格计算中最早被研究的算法。由于此类调度算法有充足的时间投入调度计算,因而在实时性要求不高的计算系统中,使用该类算法可能更好。动态调度算法能够有效的解决负载评估、作业选择和作业迁移等问题,因此,在异构平台中,动态调度带来的负载均衡优势更加明显。但是动态调度算法解决上述问题时需要付出较高的系统开销。本文研究的是静态算法中遗传算法在网格任务调度的应用。
2 遗传算法在任务调度中的应用
2.1 遗传算法概述
2.1.1 遗传算法基础术语
1)种群(Population)和个体(Individuals):遗传算法处理的是染色体,或者叫基因型个体,通常以一串结构信息来表现一定数量的个体组成了种群(Population)。
2)种群规模(Population Size):种群中个体的数目。
3)适应度函数(Fitness Function):各个个体对环境的适应度值叫适应度。对于优化问题,适应度函数即为目标函数。遗传算法要求适应度函数为可以加以比较的非负函数。
4)编码(Coding)、译码(Decoding)操作:遗传算法必须包含两个必须的资料转换操作,即把搜索空间中的参数或解转换成遗传空间中的染色体或个体,称为编码操作;反之,称为译码操作。
5)选择(Selection)、交叉(Crossover)、变异(Mutation)算子:这三个算子是遗传算法的三个主要操作算子,遗传算子(Genetic Operatoin)是遗传算法的特点。
2.1.2 遗传算法的基本过程
一般遗传算法主要步骤:
1)随机产生一个有确定长度的特征字符串组成的初始种群。
2)对该字符串种群迭代执行下面两步,直到满足停止准则为止。
(1)计算种群中每个个体字符串的适应值。
(2)应用复制、交叉和变异等遗传算子产生下一代种群。
把在后代中出现的最好的个体字符指定为遗传算法的执行结果,这个结果可以表示问题的一个解。
2.2 遗传算法的实现过程
以下从染色体的编码和解码、种群的产生、适应度函数、遗传操作对遗传算法的实现进行分析网:
2.2.1 编码和解码
二进制编码方法是遗传算法中常用的一种编码方法,它使用的编码符号集由二进制符号。和1组成的二值符号集{0,1},它所构成的个体基因是二进制符号串。
二进制编码符号串的长度与问题所要求的求解精度有关。
假设某一参数的取值范围是[A,B],等分成2l-1个子部分,记每个等分的长度为,则它能够产生2l种不同的编码,参数的对应关系如下[4]:
假设某一个的编码是:X:xlxl-1xl-2…x1x2
则上述二进制编码所对应的编码公式为:
二进制编码优点:编码、解码操作简单易行;交叉、变异等遗传操作便于实现;符合最小字符集编码原则。缺点是长度较大,对于一些多维、高精度要求的连续函数优化问题,使用二进制编码来表示个体时将会有一些不利之处。
2.2.2 产生种群
产生初始种群方法通常有两种。一种是完全随机方法产生,它适合于对问题解无任何先验知识的情况;另一种是由某些先验知识转变为必须满足的一组要求,然后在满足这些要求的解中再随机地选取样本。在网格任务调度问题中,产生初始种群的方法即属于后者。
2.2.3 适应度函数
为了体现染色体的适应能力,引入了对问题中的每个染色体都能进行度量的函数,叫做适应度函数(fitness function)。通过适应度函数来决定染色体的优劣程度,它体现了自然进化中的优胜劣汰原则。对于优化问题,适应度函数就是目标函数。例如Tsp(Travelling Salesman Problem)问题目标是路径总长度为最短,自然地,路径总长度就可作为Tsp问题的适应度函数:
其中wn+1=w1,d(wj,wj+1)表示两个城市间的距离(路径长度)。
适应函数要有效地反映每个染色体与问题的最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小,则对应的适应度函数值差就较小,否则就较大。适应度函数的取值大小与求解问题对象有很大关系。
2.2.4 遗传操作
简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。
选择操作也叫做复制(reproduction)操作,根据个体的适应度函数值所度量的优劣程度决定它在下一代是淘汰还是被遗传。一般地,选择将使适应度较大(优良)的个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小,例如通常采用的轮盘赌选择机制,∑fi表示群体的适应值之总和,fi表示群体中第i个染色体的适应度值,它产生后代的能力为其适应度值所占份额fi/∑fi。
交叉操作的简单方式是将被选择出的两个个体P1和P2(如图1所示)作为母体个体,将两者的部分码值进行交换。假设有如图1所示的8个位长的两个个体。
产生一个在1~7之间的随机整数c,假设现在产生的是3,将P1和P2的低三位交换:P1的高五位与P2的第三位组成10001001,这就是P1和P2的一个后代Q1个体;P2的高五位与P1的低三位组成数串1101110,这就是P1和P2的另一个后代Q2个体。其交换过程如图2所示。
变异操作的简单方式是改变数码串的某个位置的数码只有0和1这两种可能,有如下二进制编码表示:
其码长为8,随机产生一个1}8之间的数k,假如现在k=5,对从右往左的第五位进行变异操作,将原来的0变为1,得到如下数码串(第五位的数字1是经变异操作后出现的):
二进制编码表示的简单变异操作是将0与1互换,0变为1,1变为0。
现在对tsp的变异操作作简单介绍:随机产生一个l~n之间的数k,决定对回路中的第k个城市的代码w,做变异操作,又产生一个l~n之间的数w替代wk,并将wk加到尾部,得到:w1w2…wk-1wwk+1…wnwk
这个串有n+1个数码。注意,数w在此串中重复了,必须删除与数w重复的数以得到合法的染色体。
3 结束语
遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象,从而解决非常困难的问题。它不受搜索空间的限制性假设的约束,由于它固有的并行性,遗传算法非常适用于大规模并行计算,已在优化、机器学习和并行处理等领域得到了越来越广泛的应用。
摘要：该文首先分析比较了网格中任务调度的动态和静态算法,然后对遗传算法在任务调度中的应用进行了讨论,并给出了具体实现步骤,提供了一定的借鉴意义。
关键词：网格,任务调度,遗传算法
参考文献
[1]Braun T,Siegel H,Beck N,et al.A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C].8th IEEE Heterogeneous Computing Workshop(HCW'99),1999:1529.
[2]Singh H,Youssef A.Mapping and scheduling heterogeneous task graphs using genetic algorithms[C].5th IEEE Heterogeneous Computing Workshop(HCW'96),1996:8697.
[3]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002:9-11.
任务调度算法 篇5
关键词：μC/OS-II；多任务；任务调度
中图分类号：TP316文献标识码：A文章编号：1009-3044(2007)15-30794-02
The Task-scheduling Mechanism of μC/OS-II Operating Systems
WANG Yu-rong,ZHU Jian-bin
(Computer Science College Wuhan University of Science and Engineering,Wuhan 430073,China)
Abstract:As a multi-task embedded real time operation system, μC/OS-II Operating Systems has been widely used in more ten years.One of the reason is that the Operating Systems has many advantages.The hardest point is the schedul of tasks when we run multi-task Operating Systems.
Key words:μC/OS-II;Multi-task;task-scheduling
1 引言
嵌入式系统是一种应用范围非常广泛的系统。可以这样理解，除了桌面计算机和服务器外所有计算设备都属于嵌入式系统。在短短十多年的时间里，伴随着微电子技术、软件技术的发展，嵌入式系统被广泛的用于如生物医学仪器、智能汽车、通信设备、网络设备、仪器仪表、手持设备等诸多领域。[1] 它是以应用为中心的，而嵌入式操作系统则是嵌入式系统应用中的核心。
嵌入式系统是计算机硬件和软件的结合体，或许还加上机械等其他部分，被设计来完成专门的功能。在一些情况下，嵌入式系统是一个大的系统或产品的一部分，就象汽车上的防抱死装置，与通用计算机相对。最初的嵌入式系统是不带操作系统的，只是用来完成某一个特定的单一功能，随着软硬件技术的发展，完成单一功能的嵌入式系统已经不能适应市场的需要，因此出现了带操作系统的嵌入式系统。现在嵌入式系统的准确定义是：以嵌入式计算机为技术核心，面向用户、面向产品、面向应用，软硬件可剪裁的，适用于对功能、可靠性、成本、体积、功耗等综合性能有严格要求的专用计算机系统。[2]
μC/OS-II操作系统是一个完整的，可移植、固化、裁剪的占先式实时多任务操作系统。它之所以这么受欢迎，其中一个很重要的方面是因为它的实时性和多任务管理机制。由此可见它对任务的管理是成功的。在μC/OS-II操作系统中，一个任务，也称作一个线程，就是一个简单的程序，这个程序在执行时可以任务CPU完全属于该程序自己。而多任务的运行实际上并不是有多个CPU让多任务使用，而是靠CPU在多个任务间的转换和调度。
2 任务状态
μC/OS-II操作系统的任务状态有五种，分别是睡眠态、就绪态、运行态、等待状态和中断服务态。
睡眠态是指程序还在存储设备中，还没有被μC/OS-II操作系统管理，此时的任务只能通过任务创建函数才能脱离此状态，调用创建任务函数后，任务才能从睡眠态变成就绪态，在这个意义上来说，睡眠态就是μC/OS-II操作系统的入口，而任务创建函数就是入口的钥匙。[3]
任务被建立后，任务就进入到了就绪态，准备运行了。如果新建立任务的优先级高于就绪态中的其他任务的优先级，则新建立的任务就会立即得到CPU的使用权，会被优先执行，从而进入到运行态；而在就绪态的任务也可以通过调用任务删除函数回到睡眠态。
由于任何时刻只有一个任务处于运行态，所以一旦运行态中的任务被剥夺了CPU的使用权，它就从运行态回到等待状态。也可以通过人为的控制邮箱、信号量、延迟时间等使正在运行的任务从运行态转到等待状态。如果正在运行的任务是允许中断的，此时若中断服务程序正好到来，正在运行的任务也会进入中断服务状态，而进入中断服务状态的任务只有中断任务把CPU的控制权还给中断前的任务时，才能从中断服务状态退出来。运行态的任务也是可以被删除的，如果此时调用了任务删除函数，运行态的任务也会直接回到睡眠态。
一旦正在运行的任务通过将自己延迟一段时间或是由于要等待某一事件的发生而进入到了等待状态，如果延迟时间满，或是等待的某一事件发生了，任务就进入到了就绪态；或者等待状态的任务被删除了，那么它也会进入到睡眠态。由此看来，睡眠态又是μC/OS-II操作系统的出口，而出口的钥匙是任务删除函数，与任务建立函数相对。
3 任务调度
μC/OS-II操作系统总是运行进入就绪态任务中优先级最高的任务。它可以管理多达64个任务，但目前的版本里已经有两个任务被系统占用。一般来说用户可以使用从优先级4到优先级OS_LOWEST_PRIO-4一共56个优先级。对于多任务的管理，μC/OS-II操作系统是通过调度器完成了。其中任务级的调度是由函数OSSched()完成，而中断级的调度是通过函数OSIntExiT()完成。这两个函数是很相似的，所不同的其中一点就是OSSched()调用了任务切换函数OS_TASK_SW()，而退出中断服务子程序OSIntExiT()却调用的是OSIntCtxSw()函数。这是因为中断服务子程序已经将CPU寄存器存入到中断了的任务的堆栈中，所以只需要恢复堆栈中的内容即可。
μC/OS-II操作系统是一个商业用的实时操作系统。这是因为它是可剥夺型内核。可剥夺型内核是指当有高优先级任务到来时，不用等待低优先级的任务执行完毕，可以直接切换到高优先级的任务执行，即高优先级任务可以剥夺低优先级任务的CPU的使用权。μC/OS-II操作系统是一个多任务的实时操作系统。对于多任务的调度，它主要通过以下四类方法的使用来完成。
3.1优先级
对于μC/OS-II操作系统定义的每一个任务，在创建任务之初，一定会给这个任务分配一个合适的优先级。如果一个操作系统在调度算法选择上只是基于优先级调度，即支持静态优先级，那么这个操作系统只是一个准实时操作系统。而在μC/OS-II操作系统中，任务的优先级是可变的，即支持动态优先级。因此μC/OS-II操作系统是一个实时操作系统。改变任务优先级的函数是OSTaskChangePrio()。
3.2互斥信号量与信号量
在μC/OS-II操作系统中，互斥信号量被定义为一个二值信号，可以实现对共享资源的独占式占用。当这个资源被一个任务占用时，就被定义为1。其他的需要这个资源的任务如果检查到互斥型信号量是1，则进入等待状态，当占用此资源的任务释放这个资源时，互斥型信号量则被置为0，此时等待这个资源的任务队列中优先级最高的任务则可以获得这个资源而得以执行。
在μC/OS-II操作系统中，信号量有两种用法：一种是执行与互斥信号量相同的功能。二是如果一个资源允许多个任务调用，但现在要调用此资源的任务数目却多于允许使用此资源的数目，此时就需要用到信号量。这种情况下就会为资源设置一个计数器，如果被一个任务调用一次就自动减一，被一个任务释放一次就自动加一，只要这个计数器是大于零的，其他的任务就可以调用这个资源。
3.3消息邮箱和消息队列
用来传递消息缓冲区指针的数据结构叫做消息邮箱。消息邮箱所传递的是指向消息的指针，并非消息本身。如果一个任务获得了这个指针，即获得了该指针指向的一个特定数据结构。
消息邮箱不仅用来传递一个消息，而且也可定义一个指针数组，让数组的每个元素都存放一个消息缓冲区指针。那么任务就可通过这个指针数组指针的方法来传递多个消息。这种可以传递多个消息的数据结构叫做消息队列。
消息邮箱和消息队列在功能上的不同点是邮箱中只能存放一则消息指针，而队列可以存放多则消息指针。
3.4事件标志组
当某个任务需要与多个任务同步时，必须要使用事件标志组。事件标志组一旦建立之后，只有当某个任务需要事件标志组中的某些事件标志位（置位或者清0），这个任务才能继续运行。而且几个任务可以同时得到所需要的事件标志而进入就绪态。因此只要任务所需要的标志位满足要求，任务便可以进入就绪态。而使用信号量的任务是在等待该信号量的任务中优先级最高的任务才能得到信号量进入就绪态。
事件标志组可以使一个任务与多个任务同步，而信号量只能使一个任务与另一个任务同步。这是事件标志组与信号量的不同之处。
4 结论
本文在理论上对μC/OS-II操作系统的任务调度原理及方法进行了详细的研究，了解了μC/OS-II操作系统所定义的任务状态，找到了整个状态循环过程中的出口和入口，并分析了此操作系统是如何运用优先级、信号量等一些方法进行任务的调度。在研究的同时，也使得我们了解了μC/OS-II操作系统不同于其他一些操作系统的地方。正是由于这些不同点，使得μC/OS-II操作系统在短短十多年的时间里迅速发展起来并得到了广泛的应用。
参考文献：
[1]季志均,马文丽,陈虎,郑文岭.四种嵌入式实时操作系统关键技术分析[J].计算机应用研究,2005,(9):4-8.
[2]张文学.两种嵌入式实时操作系统的分析和比较[J].移动通信,2003.
[3]Jean J. Labrosse. 邵贝贝.等.μC/OS2Ⅱ源码公开的实时嵌入式操作系统(第2 版)[M].北京:北京航空航天大学出版社,2003.
[4]任哲.嵌入式实时操作系统μC/OS-II原理及应用[M].北京: 北京航空航天大学出版社，2005.
基于负载平衡的任务调度算法 篇6
关键词：任务调度,完成时间,负载平衡
当今计算机技术已进入以网络为中心的计算时代,大量的应用都围绕着网络进行,对服务器的性能和可靠性提出越来越高的要求。例如,随着Internet的飞速发展和用户的剧烈增长,比较热门的Web站点会因为被访问次数急剧增长而不能及时处理用户的请求,导致用户长时间地等待甚至遭到拒绝,大大降低了服务质量。对于CPU密集型的应用,比如说带有数据库操作的Web服务,服务器性能瓶颈问题则更加突出。为了解决服务器的性能问题,分布式计算的概念就应用而生。
分布式计算研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后再分配给许多计算机进行处理这些小的部分问题,最后把这些小部分问题所对对应的计算结果综合起来得到最终的结果。由此可见,分布式计算所需的资源不仅有计算资源、存储资源还要有通信资源。那么如何使用这些资源高效的完成计算任务是分布式系统的研究重点之一。这就涉及到了计算任务的调度的问题。对于普通用户而言,它仅向分布式系统提交任务,但如何快速的完成这些任务,这就是调度程序要做的事情了。因此,分布式调度程序就是按照某种调度策略把用户提交的任务分配给分布式系统中的可用资源的重要模块,也是分布式计算的核心。
从上述分析可以看出,任务调度应该包括任务映射和调度两个方面。任务映射是逻辑地为每个任务匹配一个最合适的机器,以便最小化应用程序的执行时间或完成时间。任务调度则将任务传输到其映射的机器上运行。但本文所讲的任务调度主要强调的是前者即任务到资源的映射。以最小完成时间为优化目标的任务调度问题一直以来都是NP完全问题[1],针对这类问题科学家做了大量努力,但至今未能见到一个有效的解决办法,然而随着计算机技术的发展并考虑到计算机计算能力的提高,所以在工程实践应用中解决这类问题时,常采用贪心法又叫静态启发式算法,这类算法基本思想就利用计算机的快速性来进行穷举,但随着问题规模的增加其效能会降低太快,所以在实际应用中常采用动态启发式算法,针对于异构计算环境中原子任务的调度,动态启发式算法又分为在线模式启发式算法和批模式启发式算法。但这二个算法优点和缺点都比较明显,前者会导致负载不平衡,而后者会导致分配时间增加。为此,本文提出了一种算法来结合二者的优点从而保证任务调度的快速性和负载平衡性。
1 调度模型的建立
为了较好的描述分布式计算中的任务调度问题,我们采用数学模型的方法进行形式化的描述。分布式环境中资源的范围很广泛,它指加入到分布式系统中、所有可被共享的资源。所到达的任务可能是计算型也可能是数据存储型。为了描述问题的简单,本文所指的任务包括两类子任务:计算子任务和数据传输子任务。计算子任务是该任务中需要消耗计算资源的部分;传输子任务代表获得计算所需输入的数据通信即该任务中需要消耗存储资源和通信资源的部分。不考虑任务之间的依赖性。有如下定义:
1)参与调度的任务集合为T={t1,t2…tn},其中ti代表的是任务i。
2)参与调度的异构机器集合为H={h1,h2…hm},其中hj代表的是机器j。
3)定义任务ti在机器hj上的期望执行时间eij为机器hj在不考虑其它负载情况下执行任务ti所需要的时间。
4)定义任务ti在机器hj上的期望完成时间cij为任务ti映射到机器hj上执行完的时间。
5)定义机器hj的期望就绪时间为rj,则向量r存储了所有机器的期望就绪时间。
6)据(3)(4)(5)的定义有cij=rj+eij。
7)定义系统中有f个文件服务器或者数据仓库,S={s1,s2……sf}。
8)定义矩阵data,dataij表示子任务vi向文件服务器或数据仓库sj存取数据所需要的数据传输时间。
2 算法描述
2.1 Min-min
Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的性能。该算法的目的是将大量的任务指派给不仅完成它最早,而且执行它最快的机器。算法的思想是首先映射小的任务,并且映射到执行快的机器上。执行过程为:计算要参与映射事件的任务集中每个任务在各个机器上的期望完成时间,找到每个任务的最早完成时间及其对应的机器;从中找出具有最小最早完成时间的任务,将该任务指派给获得它的机器;指派完成后,更新机器期望就绪时间并将已完成映射的任务从任务集合中删除。重复上面的过程,直到所有的任务都被映射完。该算法形式化描述如下:
假定T为所有未调度的任务的集合。
(1)判断任务集合T是否为空,不为空,执行(2);否则跳到步骤(7);
(2)对于任务集中的所有任务,求出它们映射到所有可用机器上的最早完成时间cij;
(3)根据(2)的结果,找出最早完成时间最小的那个任务ti和所对应的机器hj;
(4)将任务ti映射到机器hj上;并将该任务从任务集合中删除;
(5)更新机器hj的期望就绪时间rj;
(6)更新其他任务在机器hj上的最早完成时间;回到(1)。
(7)此次映射事件结束,退出程序。
Min-min算法完成一次映射事件的时间复杂度为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。
2.2 Max-min
Max-min启发算法非常类似于上面提到的Min-min启发算法。同样要计算每一任务在任意可用机器上的最早完成时间。不同的是Max-min算法首先调度大任务。任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上。时间复杂度同Min-min一样也为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。
在Min-min算法中,每次都是选择小任务映射到执行快的机器上,这种映射会使得更多的任务映射到某一台或几台机器上,从而使得整个分布式系统中可用机器的负载不平衡。而Max-min算法同Min-min相反,它首先调度大的任务,一定程度上平衡负载。因此综合这两种算法的思想提出一种新的算法,该算法在对任务集合执行一次映射事件的过程中,会根据当前系统的负载平衡情况,动态的选择Min-min算法和Max-min算法中的一种来进行任务资源的映射。在本文中,称这种改进的新算法为MM算法。
2.3 MM算法
MM算法的思想借鉴于SA(Switching Algorithm)算法,SA是异构计算环境下,用来对任务进行在线模式映射的一种启发式算法。
分布式计算环境中,任一资源mi的期望就绪时间为ri,设所有机器的最大期望就绪时间为rmax,最小的期望就绪时间为rmin;设变量μ表示系统中机器间的负载平衡指数,μ=rmin/rmax,显然μ∈[0,1]。rmin=rmax=0,表明当前系统中所有机器都处于空闲状态,等待着任务的映射;μ=0,表明当前系统中存在处于空闲状态的机器;μ=1,表明当前系统中任务的分配基本处于平均状态。在算法中,为了轮回的调用Min-min和Max-min算法,设定了两个边界值rlow和rhigh。映射事件开始时,初始化变量μ=1。首先使用Min-min算法,当变量μ的值下降到rlow时,改用Max-min算法;当变量μ的值上升到rhigh时,在改用Min-min算法。如此轮回调用这两个启发式算法,直到此次映射事件结束。
另外Min-min算法和Max-min算法所执行的均是原子任务到资源的映射。在分布式系统中,一个计算任务所需要的数据往往是存放在另一个地方的数据库或数据仓库中,也就是说将一个任务分为计算子任务和数据传输子任务更为合理。但此处我们不将任务划分为更多的子任务,不考虑更多任务之间的依赖关系。对于分布式环境中包含计算子任务和数据传输子任务这样的任务,在调用Min-min启发算法或Max-min启发算法的过程中,需要同时考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,所以需要修改这两个算法中求最短完成时间的部分。将传输和计算子任务看作一个整体,计算总的完成时间,并统一调度[7],即确定使之最快完成的一对(存储和计算)资源。
MM算法的执行过程如下:
(1)初始化变量μ=1;初始化机器的期望就绪时间向量r;给变量rlow和rhigh设定初值;
(2)定义变量μ1,该变量代表系统机器间负载平衡走向;初始化μ1<=0;
(3)任务调度集合T是否为空,T不为空,执行步骤(3);否则到步骤(7);
(4)若μ1<=0,μ>rlow,调用Min-min映射算法进行任务的映射;
若μ1<=0,μ=rlow,改用Max-min映射算法进行任务的映射;
若μ1>0,μ>rlow,调用Max-min映射算法进行任务的映射;
若μ1>0,μ=rhigh,改用Min-min映射算法进行任务的映射;
(5)更新向量r;
(6)更新变量μ和μ1,回到步骤(3);
(7)算法结束。
2.4 算法分析
MM算法是在不影响Min-min的最小完成时间的前提下,为了降低由该算法所引发的系统中机器间负载不平衡问题而提出的。在MM算法中,对于每一任务在映射前,都要首先判断系统的当前负载平衡指数,最坏的情况下需花费O(m)(m为系统中计算资源总数),在每次映射中,调用Min-min或Max-min的时间复杂度均为O(mfn2),其中m为系统中计算资源总数、f为系统中存储资源总数。
3 结束语
本文介绍了异构计算环境下适用于原子任务调度的经典的批模式的启发算法:Min-min和Max-min。针对Min-min算法可能引发的负载不平衡,采用轮回调度Min-min和Max-min的策略,生成了一种新的映射算法MM。在分布式计算环境下,资源更是处于一种异构的环境,并且计算资源和存储资源等往往处于一种分布的状态。更多的任务不在是原子任务,而是包含计算和数据传输两部分。考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,在MM算法中,修改了Min-min算法和Max-min算法中求最早完成时间的方法。对计算资源和存储资源进行统一调度,更好的适应于分布式计算系统。最后在Matlab 7的仿真平台下进行模拟实验,仿真结果表明该算法确实可行有效。当然对于任何启发式算法,其性能都受很多因素的影响。比如任务到达的速度,任务中长短任务的比例,任务中计算和数据传输比例等,所以值得改进的地方也还有不少,重点研究各个因素对MM算法性能的影响。
参考文献
[1]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报,2005,28(5):60-67.
[2]张德富,李新.求解作业车间调度问题的快速启发式算法[J].计算机集成制造系统-CIMS,2005(2):89-93.
[3]谢志强,刘胜辉,乔佩利.基于ACPM和BFSM的动态Job-Shop调度算法[J].计算机研究与发展,2003,40(7):79-85.
网格环境中任务调度算法的研究 篇7
随着网络在人们日常生活和工作中的日益普及,以及因特网的飞速发展,在网络中聚集了大量的可用资源,比如计算资源、存储资源、仪器设备等等。而这其中被闲置的、浪费的资源不计其数,因此,为了解决这一资源浪费问题,一种新的技术———网格技术出现了。它试图将这些资源进行整合,构成一个高性能的计算环境,实现计算资源共享和协同工作,使用户以最小的投入获得最大的计算效率和处理能力。但网格环境极奇复杂,不确定的因素太多,比如处理机之间通信的延迟、网格资源的动态性和异构性等等,故而拥有一个良好的任务调度算法才能保障网格中各类资源的协同工作,这样用户在调用算法时才能得到满意的结果,拥有好的体验。
1. 传统算法的分类
网格环境是一个异构系统,故而它的任务调度问题就显得非常关键,很明显它属于NP完全问题,因此,任务调度成为了网格计算中讨论的焦点,引起了很多学者的关注。传统的调度算法根据其思想的不同主要分为4类。
1.1 表调度算法
它的基本思想是首先确定各节点的优先级,并按照优先级将节点进行排序,之后用排序的结果来构造调度列表,最后按照以下两个步骤重复循环地操作,直到任务图中的节点全部被调用完[1]:1)按顺序从调度列表中取出一个节点;2)把此节点分配到处理机(此处理机具有使它的启动时间最早的能力)上。经典的算法主要有ETF(Earliest Task First)、MCP(modified Critica Path)、DLS(Dynamic Level Scheduling)等。
1.2 基于任务复制的调度算法
它的基本思想是将要执行的一些任务重复地分配到某些处理机上,想通过此方式来减少处理机之间的通信开销,换句话说,此算法的思想是想利用处理机的空闲时间来复制前驱任务,借此来减少需要传输的数据量,最终达到缩短处理器等待的时间[2]。经典算法主要有DSH(Duplication Scheduling Heuristic)、BTDH(Bottom-up Top-down Duplication Heuristic)、CPFD(Critical Path Fast Duplication)等。
1.3 基于任务聚类的调度算法
它的主要思想是把等待执行的所有任务分配到集群上,这些集群是没有数量限制的。假如在同一个聚类中有多个任务被分配到了,那就表示在同一个处理机上会对它们进行处理,在进行了聚类制作之外,最后还要在每个处理机上对聚类中的任务按时间的先后进行排序[3]。经典的算法主要有DSC(Dominant Sequence Clustering)、DCP(Dynamic Critical Path)等。
1.4 基于随机搜索的调度算法
它的基本思想不是简单的、纯粹的随机搜索,而是通过有指向性的随机选择来搜索问题的解。此类技术可以将前期搜索结果与特定的随机搜索特点进行整合,从而产生新的结果。经典的算法主要有遗传算法。遗传算法的调度结果一般情况下都是比较好的,但它的时间复杂度往往也比较高,并且在算法执行过程中需要确定相关的控制参数。另外在实际应用中不同的任务最优控制参数也是不同的,要找到能让大多数任务执行后有较好调度结果的控制参数很难。在当前的网格环境下,主要研究的是独立的任务调度,这与实际的网格环境(异构环境)特征不相符,此类的经典算法主要有Max-Min和Min-Min等。当然也有一些算法考虑到了异构环境下任务间的约束问题,如DLSLMT等。
2. 算法的对比与分析
2.1 ETF算法
ETF(Earliest Task First)是表调度的一个代表性算法。此算法首先计算出某个进入就绪状态的节点在每个处理机上的最早启动时间,通过将这些时间进行比较,选出那个最早启动时间的节点处理机,如果有多个时间是相同的、并且是最早的,那么选择静态b-level更大的。ETF算法要经历两个过程:一是确定任务图中各任务的优先级;二是要选择出适合的处理机来执行具有最高优先级的任务。ETF算法能够早早地计算出任务的最早启动时间,这是它最大优点;不足之处是它的每一次调度不能有效地减少任务图中当前的调度长度。另外,网格是分布式的异构环境,其中的资源是动态变化的,节点可能会随机地增多或剔除,通常情况下,处理机增多,理应会缩短任务的完成时间,但在调用ETF算法时,在处理机增多的情况下,任务的完成时间也不会减少。
2.2 DSH算法
DSH(Duplication Scheduling Heuristic)算法是基于任务复制调度的代表性算法[4]。此算法的思想是把每一个处理机上正在调度任务的启动时间与某个被调度任务的完成时间之间的间隔作为任务复制的间隔,算法尽最大可能地复制某个正在被调度任务的前驱任务到此间隔,直到间隔被填满或者被调度任务的启动时间不再被改善。此算法在同构环境中对于处理机间的通信延迟有所改善,它在执行任务的同时还要不断地复制其它任务,并且要对这些任务进行备份和存储,所以它的执行效率不是很高,在实际的网格环境中很难实现,因此,它只限于理论研究。
2.3 FCBSH算法
FCBSH算法是经过了改进的聚类算法。它的核心思想是最大限度地减少每个任务的完成时间[5]。但任务的完成时间由两个因素来决定,一是任务的起始时间,二是任务的执行时间。其中任务的起始时间由其前驱任务的执行情况和所在处理单元网络位置以当前任务的执行情况和所在处理单元网络位置决定。因此,将一个任务分配到目标系统中哪个处理单元来执行,对后续任务的执行情况影响很大。此算法有效地缩短了选择处理机的时间,而把大块的时间用于任务的处理,减少了一些时间开销。当然,此算法也有缺陷:它没有考虑网格环境(异构环境)下节点可以自由添加和退出,此外它还忽略了通信延迟及链接竞争等情况,因此它是一个理想状态下的算法。
2.4 遗传算法
遗传算法(Genetic Algorithm)是模拟生物进化而来的一种随机搜索算法。它通过模拟生物进化过程,根据遗传学机理和自然选择理论,挑选和生物遗传论中类似概念的变异因子和遗传因子,以父类杂交诞生子类,子类经过筛选变异再诞生子类的思想,进行算法模拟,从而能够动态地、先进地解决许多棘手算法问题,具有动态性和灵活性的特点。
遗传算法的求解过程,通过选择、交叉、进化流程迭代的动态的产生问题的近似解,与传统算法追求最优解不同,其所期望的结果是满意解。这就让遗传算法在工程使用中有了很强的实用性。而传统的遗传算法比较简单,只是对任务的粒度进行了理想化的划分,忽略了任务间的联系及通信开销,且为局部收敛[6]。近年来,国际学术界对其进行的一系列改进,可谓数目繁多,应用于网格的遗传算法也已经逐渐走入了人们视野,例如:J.Herrera(2005)等人提出的面向网格遗传算法、D.Lim(2006)等人提出的基于网格计算的多层并行遗传算法等。不难看出,遗传算法在网格上的发展和应用将会继续发展下去。
3. 算法存在的问题
经上文对几种经典算法的分析与对比,不管是国际的,还是国内的,都存在一些没有解决的问题,应用过程中将它们进行了理想化。而在现实的网格环境(异构环境)中,随时都有可能出现不可预料的问题,它们主要表现在以下几方面。
(1)现有算法都没有考虑网格环境中各节点执行任务的时间和处理机之间的通信延迟,认为它们是固定的、没有变化的,或是按线性关系进行变化。而现实的网格环境中,这些都可能随机地发生变化,并且变化是无规律的、复杂的,能够准确地描述这些变化的算法到目前为止还没有出现。
(2)现有算法的执行都是基于或多或少假设条件下进行的,例如任务之间的联系是确定的,处理机处在同构环境中并且连接完好,链路畅通无冲突,任务能够在任何处理机上执行等,而在实际的网格环境下,情况非常复杂,任务之间的联系是随机的、不确定的,处理机也处在异构环境中,传递信息或数据时链路冲突也是随时可能发生的,正因为有这诸多的因素存在,现有算法在实际应用时就会受到很多限制。
(3)众所周知,DAG图调度的本质就是一个Max———Min问题[7],也就是要均衡最大化任务的并行度和最小化任务间的通信时间,而对这个均衡点起关键性作用的因素就是DAG图的粒度选择,当前所有调度算法对各任务的粒度划分是相同的,完全没有考虑实际情况的多样性。
(4)目前也出现了很多基于某某算法的改进算法,但这些算法在改进的过程中,往往是以牺牲某一方面性能为代价的,改进能力有限,没能很好地均衡调度算法的核心参数。
(5)在异构的网格环境中,现有算法在某种程度上忽略了节点的动态性,节点是可以随机加入或退出的,这样就会存在这种情况:正在执行任务的节点突然退出了,但算法却没有给出一种对任务运行状态进行保存的容错机制,而是忽略不计或重新分配任务并执行。
4. 总结
经过对各类型经典算法的对比与存在问题的分析,现有网格环境中任务调度算法还没有达到预期效果,因此还有很多工作要做,结合分析情况,可以从两个方面来入手:一是全面、充分地了解实际的网格环境,分析它的特性,设计一个真实、可用的、非理想状态的通用算法,在算法中要充分地考虑网格环境的异构性、动态性、节点之间通信延迟的随机性,以及任务粒度划分的不可预料性等等;二是要均衡考虑任务执行时的核心参数,设计的算法要能使得任务调度的结果达到全局最优。
因此,在复杂多变的网格计算环境中建立一个并行的应用模型,并设计一个通用的任务调度算法是一个非常艰巨的任务。笔者后期将继续阅读国内外的相关文献,力求在这一方面有所突破。
摘要：本文通过对四种不同的任务调度形式及相应的经典算法进行分析对比,总结出了当前网格环境中任务调度存在的问题,指出了后期研究网格任务调度的方向。
关键词：任务调度,算法,网格
参考文献
[1]Lan Foster,Carl Kesselman,Sleven Trecke.The Analomy of the Grid Enabling Scalable Virtual Organizations|J|.|nl|J Supercomputer Applications,2001:1-25
[2]Annie s,Wu,Han Yu,Shiyuan Jin等.An incremental genetic algorithm approach to multiprocessor scheduling.IEEE Transactions on Parallel and Distributed Systems,2004,15(9):824-834
[3]段立荣,曹礼宇.网格中任务调度机制研究.山西科技,2006,5:58~61
[4]林剑柠,吴慧中。一种基于任务复制调度算法研究,小型微型计算机系统,Vo 1127 No.7 July 2006
[5]杜晓丽,蒋昌俊,徐国荣,丁志军。一种基于模糊聚类的网格DAG任务图调度算法,软件学报,Vol.17,No.11,November 2006
[6]李力,薛胜军,网格任务调度机制的研究,现代计算机(专业版),2008.4
任务调度算法 篇8
随着信息技术的高速发展,云计算[1]已经成为产业界、学术界、政府等各界关注的焦点。至今为止,云计算以其便利、高效、高扩展性等优势吸引了许多企业的目光,各大IT商业巨头,例如Google、IBM、亚马逊等,都提出了自己的云计算平台,并把云计算发展作为最主要战略之一。
云计算是分布式计算的一种,是并行计算、网格计算的发展与延伸,其最基本的思想还是利用网络将海量用户提交的作业分割成若干个较小的任务,再交给多个计算机组成的庞大系统,经过查询、计算、合并后将处理结果返回给用户,提供这些资源的网络被称为“云”。云计算所面向的用户群是庞大的,因此云环境中的任务量也是巨大的,所以任务调度就成为了云计算中的重点与难点。现有的常见任务调度算法有三种:FIFO调度算法、公平调度算法以及计算能力调度算法,但都存在的一些不足[2]。另外,还有一些借鉴遗传算法、免疫算法、蚁群算法等智能算法的云环境任务调度算法相继被提出,王永贵、韩瑞莲提出了一种基于改进的蚁群算法的云环境任务调度算法[3],在传统的蚁群优化算法的基础上引入逆转变异策略,避免蚁群优化算法陷入局部最优,缩短了任务平均运行时间,提高了资源自用效率。李建锋,彭舰针对云计算的编程模型框架,提出了一种具有双适应度的遗传算法的任务调度算法[4],不仅能够快速确定总任 务完成时间的较短的调度策略,而且还能保证该调度策略的任务平均完成时间也较短,增加了问题搜索空间,避免局部最优。
本文根据克隆选择机理,利用生物工程中的基因重组技术,提出一种基于基因重组的克隆选择算法(GRCSA),并应用于云环境的任务调度问题中。根据抗体与抗原之间亲和力的大小,获取优秀抗体的优秀基因片段,并对亲和力低的抗体进行基因的交换与重新组合,实现定向变异的目的,防止种群退化,提高变异效率。另外,根据不同抗体浓度进行不同规模的克隆增殖,保持抗体种群的多样性,扩大全局的搜索范围,防止陷入局部收敛。最后通过仿真实验,验证其算法的有效性,并能够快速确定任务调度最优策略,提高了系统的整体性能与资源利用效率。
1 云环境中任务调度的形式化描述
目前,云计算环境中大多采用Google提出的Map-Reduce编程模型[5],它是一种并行编程模式,非常适用于产生和处理大规模的数据集。在Map-Reduce计算框架模型中,主要的分为Map阶段和Reduce阶段:(1) Map阶段 将用户提交的较大的作业拆分成若干个较小的任务,然后分配给多个任务服务器(Task Tracker)并行执行,输出处理后的中间数据;(2) Reduce阶段将Map阶段处理后的中间数据进行汇总分析处理,输出最终结果。执行过程如图1所示。
在云计算环境中,作业调度就是将合适作业的合适任务分配到合适的任务服务器上。Map-Reduce框架是由一个单独运行在主节点的JobTracker和运行在每个集群从节点上的TaskTracker共同组成,其中作业服务器JobTracker主要负责作业任务的调度以及监控它们的执行情况,任务服务器TaskTracker负责任务的执行。当用户提交作业后,每一个作业被拆分成若干个任务,包含Map任务和Reduce任务等,任务是具体执行的基本单位,它们被分配到合适的任务服务器上去执行,并且随时报告各个任务的状态,帮助作业服务器了解作业执行的整体情况、分配新的任务等。根据上述过程,将云环境的作业调度作如下形式化描述:
定义1 将作业调度问题描述为一个四元组JS=<J,T,N,W>的形式,其中,J=<Job1,Job2,…,Jobp>代表用户提交的作业队列,由p个作业组成;T=<task1,task2,…,taskm>代表由p个作业拆分成的m个任务的集合;N=(node1,node2,…,noden)代表n个任务服务器TaskTracker(计算资源)的集合;W=<wi,j|wi,j是任务taski在任务服务器nodej上的执行时间,1≤i≤m,1≤j≤n> 。
定义2 假设X代表所有可能的调度方案集π中的一种调度策略,在该调度策略下,完成全部作业所需要的总时间由下式给定:
其中,xi,j为二进制变量:当且仅当任务taski被分配给任务服务器nodej(计算资源)时,xi,j=1;否则,xi,j=0。
定义3 对于云环境的作业调度问题,就是以下式作为目标函数的优化问题。
2基于GRCSA的云环境中任务调度算法设计
克隆选择算法(CSA)是Castro根据免疫克隆选择机理提出的,并行性和自主学习是CSA的两个最显著的特点[6]。针对云环境下的任务调度问题,用克隆选择算法进行任务调度可以得到较好的效果。参考Map-Reduce模型,为了能得到总任务执行时间和任务平均执行时间都较短的任务调度策略,本文在传统克隆选择算法的基础上,结合生物工程中的基因重组技术[7],提出一种基于基因重组的克隆选择算法。根据抗体亲和力大小对抗体进行选择,获取优秀抗体的优秀基因片段[8],对抗体进行不同程度的基因重组,实现高频变异过程中的定向控制,避免种群退化,加快收敛速度,提高全局搜索范围,防止局部收敛。
2.1 抗体基因序列的编码与解码
对抗体基因序列的编码有很多方法,既可以采用直接编码,也可以采用间接编码,本文采用一种任务-资源的间接编码方式。抗体基因序列由一维数组表示,长度等于全部任务的个数,每个基因位的编号代表任务的编号,而该基因位的基因值为该任务分配到的任务服务器(计算资源)的编号。
假设有p个作业(Job),n个任务服务器TaskTracker(计算资源),第t个作业被拆分为的任务(Task)的数量为:taskNum(t)。则任务的总数量为TaskNum:
例如有3个Job,3个任务服务器TaskTracker,每一个Job又拆分成若干个Task,如Job1被分为:Task1,1,Task1,2两个Task;Job2被分为:Task2,1,Task2,2,Task2,3;Job3被分为Task3,1,Task3,2,Task3,3,Task3,4,Task3,5,则一共有10个Task,然后再对这些任务进行编号,采用作业-任务顺序编号方法,即第i个Job中的第j个Task的序号为m:
抗体基因序列的长度为10,每个基因位的取值为1~3,随机产生下面一个抗体基因序列:{2,1,3,1,2,3,1,1,2,3},这个抗体基因序列代表第1个Task在第2个TaskTracker上执行,第2个Task在第1个TaskTracker上执行,……,第10个Task在第3个TaskTracker上执行。
然后要对抗体基因序列进行解码,完成从基因型到表现型的映射,得到TaskTracker上的Task的分布情况,生成以TaskTracker编号的Task序列。如上述抗体基因序列解码为:
TaskTracker1:{2,4,7,8}
TaskTracker2:{1,5,9}
TaskTracker3:{3,6,10}
因此得到了每个TaskTracker上执行的任务的序列,然后再根据矩阵W(W[i,j]表示第i个Task在第j个TaskTracker上执行所需要的时间),可以计算出每个TaskTracker执行的所有任务需要的总时间以及完成所有作业的平均时间。
2.2 初始抗体种群生成
若初始抗体种群规模为S,Job个数为J,Task个数为m,任务服务器TaskTracker(计算资源)的个数为n,则抗体的种群初始化描述如下:系统随机产生S个抗体,抗体基因序列的长度为m,每个基因位的取值在任务服务器个数的范围内随机选取,即在[1,n]中随机选择。
2.3 克隆选择
克隆选择是根据抗体与抗原之间的亲和力大小,从抗体种群中选取优秀抗体进行克隆,增加优秀抗体的浓度,并通过不断地变异进化,从而找到最优抗体(问题的最优解)。因此,对于亲和力的计算显得尤为重要,它关系到算法的收敛速度以及解的优劣性。
对于云环境的作业调度,一个最主要的性能指标就是全部作业的完成时间。另外还需考虑作业的平均完成时间。在保证所有作业完成的时间最短的基础上,还应该满足作业的平均完成时间也要最短,因此亲和力函数定义如下:
F1(X)为完成所有作业的总时间函数,其中,tasktracker(j,i)为在第j个TaskTracker执行该第i个任务所用的时间,T为分配到该TaskTracker上的任务的数量。X为一种任务调度策略(抗体基因序列)。
F2(X)为完成所有任务的平均所用时间的函数,其中:k为第i个任务在被分到的TaskTracker中的位置,w[j,i]为第j个TaskTracker执行第i任务所需要的时间,X为一种任务调度策略(抗体基因序列)。
所有任务的完成时间和任务平均所用时间越短的抗体,其亲和力值越大,越容易被克隆选择。
2.4 抗体基因序列重组
在传统克隆选择算法中,抗体种群通过高频变异抗体克隆种群的亲和力,从而实现抗体种群不断进化最终找到最优的抗体,但是高频变异的随机性和不确定性可能导致出现种群的部分退化现象,影响算法的收敛速度和全局搜索能力。因此,本文利用生物工程中的基因重组技术,根据抗体与抗原之间亲和力的大小,获取优秀抗体的优秀基因片段,并对亲和力低的抗体进行基因的交换与重新组合,实现定向变异的目的,防止种群退化,提高变异效率。抗体的基因重组包含两个过程:① 获取优秀抗体的优秀基因片段。假设抗体种群,其中每个抗体基因序列的长度为l,根据亲和力大小,选取η个优秀抗体,定义一个参照抗体,用来记录优秀基因片段;② 定向改造抗体基因组成。利用参照抗体Abs,对亲和力低的抗体的基因进行交换与重组,将获取的优秀基因片段注入其基因序列内,定向改造抗体的亲和力,从而达到定向变异的目的。
2.5 基于GRCSA任务调度算法的流程
云环境下,基于GRCSA的任务调度算法的流程如下:
Step1 初始化抗体种群:随机产生为S的初始抗体种群Ag={ag1,ag2,…,agS},对于任意抗体agi,其基因序列的长度均为m,每个基因位的取值为c,i∈[1,S],c∈[1,n]。其中。m表示总任务的个数,n表示任务服务器TaskTracker的个数,agi表示任意一种任务调度策略。
Step2 针对每一代种群循环执行算法:
Step2.1 在初始抗体种群中,对于每一个抗体agi(调度策略),i∈[1,S],根据亲和力函数式(5)和式(6),分别计算抗体的亲和力Aff(i),并根据亲和力对抗体进行由小到大排序。另外,计算克隆选择概率P={p1,p2,…,pS},计算公式如下:
其中,pi表示第i种调度策略对应的抗体的克隆选择的概率。根据抗体亲和力大小,从初始种群中选择出N个抗体生成临时种群Ag
Step2.2 对于选择出来的临时种群Ag
Nc(i)=Round(μ×rank(i)1-γ) (8)
其中,Nc(i)是第i个抗体的克隆数量,μ为一个控制参数,γ是抗体浓度,Round()为取整函数,rank(k)是对抗体k在抗体种群中根据亲和力大的大小进行排序(升序)后所得到序号,序号越大,抗体的亲和力越大,那么克隆增殖的数量也就越多。另外,对于相同亲和力的抗体,根据其不同浓度进行不同规模的克隆增殖,抗体浓度越小,增殖的规模越大,这样有利于丰富抗体种类,提高抗体多样性,避免陷入局部最优的情况。
Step2.3 对于增殖种群Agp中亲和力低的抗体,借助生物工程中基因重组技术,进行定向变异,具体过程分为两步:
① 提取基因优势片段。根据抗体亲和力大的大小,选取η个优秀抗体。定义一个参照抗体abs,用来记录基因优势点,从而提取优秀基因片段,获取方法如下:
abs=ab1⊙ab2⊙…⊙abη (9)
② 定向改造抗体的基因组成。利用参照抗体abs,对亲和力低的抗体进行基因的交换与重新组合,将获取的优秀基因片段注入其基因序列中,定向改造亲和力低的抗体,从而达到定向变异的目的。具体方法如下:
ab′m=remove(abm,ab
其中,abm表示亲和力较低的抗体,ab′m表示经过基因重组改造以后的抗体,k∈[1,η],remove()是根据参照抗体ags对抗体agm内部的基因片段交换运算与重新组合,达到定向改变抗体基因组成的目的。将改造以后的抗体与增殖种群中亲和力低的抗体进行交换,生成目标种群Ag′p。此时完成变异过程。
Step2.4 从目标种群Ag′p中选取亲和力最高的抗体进入记忆细胞种群,成为记忆细胞。
Step2.5 将原种群S中亲和力低的(l+r)个抗体用l个优秀抗体和r个随机生成抗体细胞进行代替进入下一代新的抗体种群;本文引入随机生成的抗体,避免陷入局部最优解。
Step3 直到满足算法结束条件。
Step4 从抗体种群中选择出亲和力最高的抗体(使目标函数式(5)、式(6)达到最小值的解),确定最佳的任务调度方案,使完成所有任务的总时间和平均任务完成任务的时间最小。
3 仿真试验及结果分析
由于云计算可以看作是一个特殊的网格环境,所以本文用Gridsim来模拟一个云计算的局部环境。在相同情况下,分别用传统克隆选择算法(CSA)与GRCSA对云环境中的任务进行调度,并对这两种算法得到的总任务完成时间以及任务平均完成时间进行比较。
初始条件: Job个数为10,Task个数为20,任务服务器TaskTracker(计算资源)的个数为5,初始抗体种群规模为50。
算法终止条件:① 到达最大进化代数(这里取最大进化代数为100);② 连续20代总任务完成时间和任务平均完成都没有变化时,认为算法基本收敛,算法结束。
从图2、图3中可以看出,在进化初期,GRCSA的收敛速度要明显快于CSA的,并且GRCSA得出的总任务的完成时间和任务平均完成时间均要小于CSA得出的。GRCSA是借助基因重组技术,在进化迭代过程中,每次变异都保留了前一代优秀抗体的优秀基因,并将优秀基因通过交换与重组作用到亲和力较低的抗体中,实现了高频变异中的定向变异,防止出现种群退化现象,提高了抗体变异效率和算法收敛速度。另外,GRCSA根据相同亲和力的不同的抗体浓度,对抗体进行不同规模的克隆增殖,增加了优秀抗体的种类及多样性,避免了算法在收敛速度加快的同时,陷入局部收敛,造成局部最优的情况。因此在进化后期,虽然两种算法都达到了一种基本收敛,但是通过GRCSA得出的收敛迭代次数以及总任务完成时间和任务平均完成时间均小于CSA得到的,证明了其算法的优良性与有效性。
4 结 语
本文提出了一种基于基因重组克隆选择算法的任务调度算法,该算法在传统克隆选择算法的基础上,借鉴了生物工程中的基因重组技术,记录了每一代优秀抗体的优秀基因,实现了变异过程中的定向变异,降低了传统高频变异过程中的随机性与不确定性,提高了变异效率和算法收敛速度。通过本算法可以解决云计算环境中的任务调度问题,能够确定较优的任务调度策略,提高了系统效率与资源利用率,是一种有效的作业调度算法。
摘要：在云计算中,系统要面对庞大的用户群,处理大量任务以及数据。如何对云环境中的大量任务进行高效的调度、满足用户需求成为了云计算中所要解决的重要问题。针对云计算的并行编程模型,借鉴生物免疫系统的克隆选择机制,利用生物工程中基因重组技术,提出一种基于基因重组的克隆选择算法,将此算法应用到云环境的任务调度问题中,可以确定最佳的任务调度方案。通过仿真实验将此算法与传统克隆选择算法进行比较,结果证明此算法的收敛速度与收敛精度均优于传统克隆选择算法,并且通过此算法可以确定较优的任务调度策略,是一种云计算环境中有效的任务调度算法。
关键词：云计算,克隆选择,基因重组,任务调度
参考文献
[1]Buyya R.Market-Oriented Cloud Computing:Vision,Hype,and Real-ity of Delivering Computing as the 5th Utility[C]//2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid.
[2]夏袆.Hadoop平台下的作业调度算法研究与改进[D].华南理工大学,2010.
[3]王永贵,韩瑞莲.基于改进蚁群算法的云环境任务调度研究[J].计算机测量与控制,2011,19(5):1203-1206.
[4]李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186.
[5]Dean J,Ghemawat S.MapReduce simplified data processing on largeclusters[C]//Proceedings of the 6th Symposium on Operating SystemDesign and Implementation New York ACM,2004:137-150.
[6]Leandro N de Castro,Fernando J Von Zuben.The clonal selection al-gorithm with engineering applications[C]//Workshop Proc of GEC-CO’00 workshop on Artificial Immune Systems and Their Applica-tions.LasVegas,2000:36-37.
[7]Deem A K,Li X,Tyler J K.Epigenetic regulation of genomic integrity[J].Chromosoma,2012,121(2):131-151.
浅析网格环境中的任务调度算法 篇9
网格是以资源共享为目的,利用互联网将分散与不同地域的计算机组织起来,成为一个虚拟的“超级计算机”。每台参与的计算机就是一个“节点”,成千上万的节点组合起来,成为一张“网格”。从而能够充分地利用网络中的空闲计算能力,实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源等全面的共享。
随着Internet的发展, 网格计算技术逐渐成为新的研究领域。网格系统由大量异构资源组成,具有复杂、动态和自治等特点。高效的调度算法可以充分利用网格系统和处理能力,从而提高应用程序的性能。为了实现网格资源的优化配置,并为网格用户提供较为满意的服务质量,任务调度技术一直以来成为人们研究的热点。
文献[1]对当前现有的网格任务调度算法进行了深入而详细的讨论。文献[2]提出了一种基于任务池模型的分级调度方法,保持了系统资源之间的共享关系和高度可控性。文献[3]提出基于Min一Min算法的最小完成时间偏差调度算法(Dev_Min一Min),解决了任务调度的负载均衡和吞吐率高的问题。文献[4]提出了MD一sufferage算法,缩短调度跨度的同时保证较小的任务等待时间。文献[5]提出了同时考虑任务带宽要求和负载均衡要求的改进算法,设计了一种有依赖关系的任务调度算法。本文提出Segment Qos Min-Min RR任务调度算法,平衡了负载,提高了任务的完成时间和平均等待时间,达到算法简单并且效率较高的要求。
2 RR 算法
RR算法是一种动态调度算法。首先将网格任务以任意的顺序被提交到可用的处理单元(PE)上,直到所有的网格任务都提交完。然后把未执行完的任务连接成一个环,一旦此时有执行完的任务,立即从环中把一个还没有执行完的网格任务调度在此可用的处理单元上,即此时有多个处理单元同时在运行同一个网格任务。只要其中一个处理单元上的网格任务执行完,立即杀死所有的任务。重复上述过程,直到所有的任务执行完。如果此时动态有新的任务加入,就立即开始执行。
设T是一个大小为L的n个任务的集合,m为一个计算网格上处理器的数目,定义T的调度如下:
T的一个在具有m个处理器的网格上的调度S是一个三元组 <v,p,t> 的集合, 它们满足R1和R2规则,v∈T,1≤p≤m,t是任务v的起始时间,<v,p,t>∈S,意味着处理器p在时间间隔t~t+d执行任务v,d是通过p的处理能力和v的L计算出来的, 所以称t+d为任务v的完成时间。
R1:对每一个v∈T,至少有一个 <v,p,t>∈S。
R2:不存在这样的两个三元组 <v,p,t>,<v',p',t'>∈S;t≤t'≤t+d,t+d为任务v的完成时间。上述功能可以描述如下:
R1保证每一个任务v至少执行一次 ,R2是说每一个处理器在任何一个时刻最多只能执行一个任务,<v,p,t>∈S称为一个任务实体。
用下列公式来计算处理器的代价:
RR算法确定可以提高资源的利用率 , 但同时也造成了资源的浪费,另外,同一时刻有多个处理单元在运行同一个任务也是一种浪费。
改进的RR算法:就是所有的任务对处理单元都是共享的,只要有到来的任务想让它立即执行就可以。根据任务分配的处理速度 (MIPS), 定义了最大处理速度(MaxM IPS)、最小处 理速度 (Min MIPS) 和最大任 务数(Maxcount),所有的任务可以同时执行 ,所以任务的状态只有停止和运行,没有等待状态。此改进和算法大大提高了任务的完成时间,提高了系统的性能。
3 Min-Min 算法
在Min-Min算法中,首先分别计算每个任务在所有机器上的最小执行时间,执行时间最短的那个任务被选出来并被分配到相应的机器上,然后把这个最近被映射的任务从集合中删除,重复执行这个过程直到所有的任务都被映射。文献[3]研究表明,在不同的ETC矩阵下,Min一Min比OLB、MET、MCT、Max一min等算法均有更好的调度性能。 但还存在局限性:(1)潜在的负载不均衡,使得资源利用率低;(2)没有考滤网格任务的服务要求。
对于一个由n个元任务构成的集合T,以及m个主机集合M,Min一Min算法的执行过程如下:
(l)对主机的就绪时间向量R进行初始化 ,使得对于任意Mj∈M有R(j)=0,然后根据预测执行时间矩阵ETC计算出每个任务Ti在每个主机Mj上的预测完成时间,根据预测完成时间定义,有CT(i,j)=ETC(i,j)+R(j);
(2)当任务集合T不为空时 ,反复执行以下操作直至任务集合为空:
a.对集合中的每个任务Ti(i=1,2,…,n),计算它在所有主机上的最小预测完成时间, 若它在主机Mj上的预测完成时间最小,记minC T(i)=CT(i,j),并记录min CT(i)所对应的主机编号host_min CT(i)=j;
b.找出min CT矩阵中的最小值 ,即找出具有最小的最小完成时间的任务, 并将它分配给对应的主机执行。例如,若任务Ta对应的min CT(a)最小,则将编号为host_min CT(a)的主机分配给任务Ta;
c. 从任务集合T中删除任务Ta, 更新主机Mk(k=host_minC T(a))的就绪时间R(k)=min CT(a),并更新预测完成时间矩阵CT。
4 Qo S Guided Min-Min 算法
这种算法是让高服务质量的任务先执行,低服务质量的后执行,并且不让高的服务质量的任务长期处于等待状态,从而减少了等待时间。
5 Segmented Min-Min 算法
每一个任 务在每一 台机器上 都有一个 期望时间ETC (Expected Time to Comput), 如果这里有t个任务和m台机器,就获得一个t X m的ETC矩阵,ETC(i,j)表示任务i在机器j上的执行时间。
Segmented Min-Min算法根据ETC来对这些任务进行排序。根据平均这些任务按序排成链表。然后这些链表中的每一个任务分成同样大小的片,并且大任务的所有片先调度。每一个任务中的片均采用Min-Min算法来调度。
6 Segment Qos Min-Min RR 算法
这种算法是在改进的RR算法的基础上,一是先加入Min-Min算法的思想, 让完成时间最短的任务先执行,让尽可能多的任务找到合适的机器来执行;二是加入Qos Guided Min-Min算法的思想,对任务和资源分别设定服务质量级别,有某个服务质量级别的任务只能在同等级别或高于此级别的任务和资源之间达到最合理的匹配;三是利用Segmented Min-Min算法的思想,让大的任务先执行并且考虑到任务的分解,这样不但平衡了负载,也同时在任务的完成时间和平均等待时间上得到了提高。
以上算法得到了几种实现。
(1)实现RR算法和改进和RR算法(RR1)。由于原始的任务提交是任意顺序的,因此在这里采用先来先服务的方式,即先到达的任务先被提交,后来的只能等待前面的都提交了才能被调度。
(2)实现Min-Min算法。由于要让最小完成时间的任务先提交,因此就要有一个衡量标准,即评价任务的完成时间。在这里只考虑任务的大小,而不考虑其他因素的影响,那任务越小,完成时间越短,也就意味着要先调度小的任务。
(3)实现Qos Min-Min算法。为了定义任务和资源的服务质量级别,这里增加了一个参数Qos。
(4)实现Segment Qos Min-Min RR算法。为了实现任务的分解,可以编写一个任务分解函数segmentgridlet(),把任务分成几个子任务片来调度。
7 实验仿真
常用的模 拟器有Bricks、MicroG rid、Sim Grid、GridS im、Chic Sim、EDGSim等 ,其中重点Sim Grid。表1中的数据就是用Sim Grid模拟器仿真的。表1中记录了在任务数分别取200、300、400、500时,不同算法的任务最终完成时间。
8 结束语
任务调度算法 篇10
关键词：车辆路径问题；不确定决策；禁忌搜索算法
中图分类号：F224文献标识码：A
文章编号：1002-3100(2007)12-0026-04
Abstract: A vehicle routing problem in war is discussed, in which some routes may be destroyed uncertainly by competitor. A two-stage integer program model is constructed. The value of a route in a uncertain situation is analyzed. In the method, only the maximum value and the minimum value are countered into the object value, simpling the computation of the object value of the model. A two-stage tabu search algorithm is designed. In the end, an example is given.
Key words: vehicle routing problem; uncertain decision; tabu search algorithm
0引言
战争环境下，交通线路中的一些关键性的桥梁、隧道和线路枢纽随时可能被敌方破坏。利用这些关键性的桥梁（隧道）运输时间将会缩短，但如果这些桥梁被毁坏，运输车可能要绕道运输甚至原路返回，反而延误了运输时间。这一类问题同样也存在于自然灾害的救援活动中。在人类的发展历史上，地震、洪水、台风和雪崩等自然灾害也是破坏交通线的重要因素。1995年日本的神户地震、美国近期的飓风“丽塔”、我国1998年的特大洪水等都破坏了许多交通设施，同时这些自然灾害还随时威胁物资救援的运输线路。由于这类运输直接关系到整个军事（救援）活动的成功与否和人员的生命安全，因此研究这一类不确定的运输决策问题无论对于战争还是人类战胜自然灾害都具有重要的意义。目前关于车辆线路优化的研究很多，但涉及战争环境下（或自然灾害环境）的研究很少，正式的研究文献几乎没有看到。本文探讨了一个个别关键路段（桥梁、隧道等）可能被毁坏情况下的多车辆路径决策问题，提出了相应的数学模型并给出了求解模型的禁忌启发式算法。
1问题描述及复杂性分析
1.1问题的提出
2数学模型
调整上述模型的一些参数，即可建立不协作的两阶段规划模型，这里不再详述。
3线路方案的评价值
4禁忌搜索算法
禁忌搜索算法主要内容如下：
（1）随机产生一个路径序列为初始解。为n个需求点编序列号，仓库为0。路径解的首尾各为0，中间是n个需求点加上M-1个0的随机排列。相邻两个0之间为一个车辆的服务路径。以6个需求点，两辆车为例，一个路径解为0-1-2-3-0-4-5-6-0。
（2）邻域的产生。分别采用任意两个需求点交换位置、任意一个需求点插入到线路任意位置的方法产生新的解。
（3）车辆容量限制的处理。当一个车辆线路中的需求点的总需求量超过车辆最大载货量时，该线路方案被淘汰。
（4）禁忌对象为两个相邻的需求点。禁忌表的长度随进化代数的增加而加长。当前值优于历史最优值时，禁忌解除。
（6）线路的方向。在乐观准则下，毁坏后线路的调整变化没有被计算到评价值中，为了弥补这一缺陷，可选出乐观准则下的最优方案和多个次优方案，并计算出最坏情况下的结果，以供决策参考。即使是最优化方案，相同的线路次序但不同的线路方向也被认为是不同的方案。如线路0-1-2-3-4-0和0-4-3-2-1-0是不同的方案。
5示例
表1是一个路网的距离数据。其中路段2-4经过一个难以修复的桥梁，被敌方破坏的可能性非常大。0表示仓库，其它10个序号表示需求点，每个需求点需求为5，每辆车的最大载货量为35，用两辆车送货，要求规划不同期望值准则下的里程最短的线路。
由于车辆载货量的限制，完成任务必须两辆车。采用文中的禁忌搜索算法得到不同准则下的最优方案。
6结束语
战时或各种抢险救灾时的物流运输保障具有重大意义。但这类运输线路优化问题至今研究很少。本文把不确定决策技术和车辆路径优化技术结合起来，建立了不确定环境下的运输线路优化模型，研究结果可以为不确定环境下的物流配送决策提供参考。
参考文献：
[1] 李军，郭耀煌. 车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001:7-10.
[2] 甘应爱，田丰,等. 运筹学[M]. 北京：清华大学出版社，1990.
[3] 柳春光，焦双健. 城市震后救灾系统救灾决策研究[J]. 自然灾害学报，2000,9(3):21-24.
[4] 吴育华，杜纲. 管理科学基础[M]. 天津：天津大学出版社，2001.
[5] 张凤林，武小悦，郭波,等. 物流网络可用性研究[J]. 系统工程理论方法应用，2002,12(1):16-19.
任务调度算法 篇11
为了实现一定的计算要求, 现代电子技术主要采用两种方法:第一种是通用微处理器方法;第二种是专用处理器方法 (Application Specific Integrated Circuits, ASIC) , 即专用集成电路方法。现代通用处理器的体系结构与传统的冯.诺伊曼结构相比虽然己经有了很大的变化, 但是其基本框架仍然是以冯·诺伊曼结构为基础, 它的特点是使用范围广, 但计算效率低。另一方面, ASIC方法以完全硬件的方式来实现计算任务, 它的主要特点是为特定计算任务专门设计, 可得到较高的运算速度及效率, 设计的约束基本上是在物理层次的实现上, 但这种方法的最大缺陷是它几乎没有任何“弹性”, 即为某种应用而设计的ASIC无法用于另一种应用, 稍有变化则必需修改原来的电路。综合比较微处理器方法和ASIC方法, 一种新的技术路线与方法应运而生, 即可重构计算。它既具有ASIC的高性能、高速度和高可靠性, 又具有微处理器的高度通用性和强大的可编程功能, 从而恰好弥补了两者各自的缺陷。可重构处理器可以在比微处理器具备更高效率的同时, 取得比ASIC 更高的灵活性。更进一步的, 当应用程序与可重构处理器的结构匹配得较好, 且拥有足够的处理并行度的时候, 它可以获得与微处理器相比更高的吞吐率和更低的功耗, 因此可重构系统是上述几种解决方案的折中方案, 其灵活性接近RISC处理器, 而工作效率接近ASIC处理器。
由于C/C++程序无法直接映射到可重构阵列上执行, 所以需要编译器对C/C++程序进行处理, 根据将要映射到可重构阵列上的代码部分生成配置信息, 输入数据等。编译器工作流程如图1所示。
采用可重构系统实现一个计算逻辑的整个运行时间开销包括:对可重构阵列进行配置时带来的延时和通用处理器向可重构阵列输入数据的时间;可重构阵列向通用处理器输出运算结果的时间;用于实际计算的时间。目前, 制约可重构计算广泛应用的一个重要因素就是通用处理器和可重构阵列之间的配置传输时间, 数据传输时间相对于计算时间仍然太长, 如何加速配置过程和数据传输过程已经成为可重构系统的重要研究课题。
快速有效的任务调度算法是可重构阵列系统中一个关键问题, 其算法的实质在于将任务映射至可重构阵列上进行加速, 并且根据任务之间存在的数据依赖关系, 重新排列任务之间映射到可重构阵列上的先后顺序, 得到符合满足任务之间数据相关性的任务执行顺序, 并且得到最小的任务调度长度。
1 相关研究
常见的可重构硬件模型包括Morphosys[8], PipeRench[9]和RCA[10][11]已经证明了粗颗粒度的可重构处理器能够有效提高多媒体应用的执行速度, 但是它们仍然存在缺点。Morphosys对并行任务的运算支持不足, PipeRench只能有效处理存在并行性的流水运算, RCA则在处理颗粒较小的运算时存在着硬件面积的浪费, 同时也对并行的任务支持不足, 并且存在配置信息和解码操作数对总线竞争严重的现象。
常见的可重构系统任务调度算法包括表调度算法, 聚簇调度算法, 遗传算法, 基于任务复制调度算法等等。但是有的算法针对的是拥有无限硬件资源的模型, 并不适合现实中硬件资源有限的系统, 例如MD[2], DCP[3] , DSC[4]和 CPFD[5], TCSD[6];有的算法没有考虑任务传输数据和配置信息的通信代价, 实际应用中传输数据和配置信息的通信代价会严重制约可重构系统的性能, 例如CP/MIF[1]和DF/HIS[1];有的算法复杂度过高, 代码运行效率不高, 例如Genetic Algorithm[7]。
本文将提出一种有限个数可重构处理器, 存在通信代价, 能够支持任务并行计算的可重构系统和一种基于这种可重构系统的动态表调度算法。
2 新的可重构阵列架构
本文采用的可重构阵列系统包括:精简指令集处理器 (Reduced Instruction Set Computer, RISC) , 直接存储器访问 (Direct Memory Access, DMA) , 总线 (BUS) , 可重构阵列 (Reconfigurable Cell Array, RCA) , 存储器 (Memory) 组成, 如图2所示。
可重构系统的工作流程是:DMA将RISC或者Memory中的输入数据和配置信息通过AHB写入RCA中, 待RCA运算结束后, RISC直接通过AHB从RCA读出计算结果。
针对上文所提到的相关研究中的缺点和不足, 本文采用一种新的可重构阵列架构, 它的特点是采用多个可以独立进行并行计算的子可重构阵列, 利用其中某一个子可重构阵列的运算时间覆盖另一个子可重构阵列的配置信息的传输时间, 运算数据的输入时间或者运算结果的输出时间。
新的可重构阵列是由四个子可重构阵列, 一个全局配置存储器, 一个全局控制单元, 一个全局状态寄存器, 一个输入数据多路选择器, 一个配置信息多路选择器, 一个输出数据多路选择器组成, 如图3所示。
其中全局配置寄存器中存储指示向子可重构阵列写入配置信息和输入数据, 或者从子可重构阵列读出运算结果的配置信息, 而全局控制单元可以根据全局配置存储器中的配置信息和四个子可重构阵列的状态寄存器的状态, 通过控制多路选择器, 使得某个子可重构阵列和总线进行数据或者配置信息的传输, 而其它的子可重构阵列可独立进行数据的运算。
子可重构阵列是由一个存储输入数据的FIFO, 一个存储配置信息的FIFO, 一个存储输出数据的FIFO, 一个控制单元, 一个状态寄存器, 一个输入寄存器堆, 一个输出寄存器堆, 一个4×4可重构运算阵列组成的, 如图4所示。
其中的可重构运算阵列由4个路由控制单元和16个可重构运算单元 (Reconfigurable Cell, RC) 组成, 如图5所示。
路由控制单元根据配置存储器中的配置信息从输入寄存器堆的相应寄存器或者上一层4个可重构运算单元的结果中选择下一层4个可重构运算单元的输入数据。
这种结构使得利用可重构阵列的运算时间覆盖可重构阵列的配置和数据传输时间成为可能, 可以在硬件开销增加不大的情况下, 显著提高可重构阵列的性能。
3 任务调度算法
在进行硬件任务向可重构阵列映射时, 经常会遇见两者颗粒度上失配:硬件任务所需逻辑资源与可重构阵列所能提供的逻辑资源不匹配。两者的差异要求硬件任务必须进行划分。划分得到的子任务所需要的逻辑资源必须不大于可重构阵列所能提供的逻辑资源, 并且必须能构成有向无环图, 如图6所示, 其中有向无环图的每个节点代表一个划分后得到的子任务Ti, 每个子任务节点的信息包括:任务配置时间 (CT) , 输入数据时间 (LT) , 任务计算时间 (ET) , 输出数据时间 (ST) ;有向线段Ei表示子任务之间的数据依赖关系。为了充分利用可重构阵列的硬件资源, 实现并行计算, 需要对子任务的执行顺序进行调度。任务调度问题的定义如下:
(1) 输入:给定任务图G={T, E}。
(2) 输出:子任务Ti的执行顺序。
(3) 约束条件:保持子任务之间的数据依赖关系。
(4) 目标:使得划分后的任务集合执行时间最短。
由于有向无环图的调度问题是NP-HARD问题, 所以本文提出一种动态表调度算法, 算法的核心是:尽可能让sub_rca处于运算状态, 提高并行运算的sub_rca的数量, 因此在总线和sub_rca均有空闲时, 优先进行任务的配置信息和操作数据传输, 这样就可以让更多的任务同时在sub_rca上运算, 只有在sub_rca全部被占据或者当前待调度任务的前驱任务在sub_rca上时, 才进行sub_rca上任务的计算结果输出。算法步骤如下。
Step1:遍历所有任务节点, 查找未调度任务节点, 将所有前驱任务已经调度的未调度节点放入待调度的任务节点表。
Step2:计算待调度的任务节点表中每个任务节点映射在sub_rca阵列上的最早可能开始运算时间。
Step3:遍历待调度的任务节点表中的节点, 选择最早可能开始运算时间最小的待调度节点, 将其映射到sub_rca上。
Step4:根据所选择的待调度节点的参数, 更新所有的任务节点状态, sub_rca阵列状态, AHB总线状态。
Step5:重复步骤Step1-> Step4直到所有任务节点均已调度为止。
Step6:遍历sub_rca阵列, 将仍在sub_rca阵列上的任务节点, 根据任务执行完成时间从早到晚的顺序依次将运算结果输出, 更新sub_rca阵列状态, AHB总线状态。
算法流程如图7所示。
其中, 待调度节点Ti的最早可能开始运算时间Tipe的计算步骤如下:
if (no pre_task is on sub_rca current moment) {
if (there is sub_rca in idle state) {
Tipe=Tbi+CTi+LTi;
}else{
find out the task on sub rca that will finish earliest;
set the number of this task to earliest;
if (Tearliestf>Tbi) {
Tipe=Tearliestf+STearliest+CTi+LTi;
}else{
Tipe=Tbi+STearliest+CTi+LTi;
}
}
}else{
find out the task on sub_rca that will finish earliest;
set the number of this task to earliest;
if (Tearliestf>Tbi) {
Tipe=Tearliestf+STearliest;
}else{
Tipe=Tbi+STearliest;
}
while (on sub_rca exists result of pre_task not sent to bus)
{
find out the task on sub_rca that will finish earliest;
set the number of this task to earliest;
if (Tearliestf>Tipe) {
Tipe=Tearliestf+STearliest;
}else{
Tipe=Tipe+STearliest;
}
}
Tipe=Tipe+CTi+LTi;
}
Tbi:the time that bus starts in idle state.
Tjf:the time that task No.j finishes.
CTj:the time that configures task No.j to sub_rca.
LTj:the time that transfers the data of task No.j to sub_rca.
SYj:the time that sends the result of task No.j to bus.
4 实验结果及分析
验证平台是在SOCDesigner上搭建的系统模型, RISC采用的是ARM926EJ-S, 总线采用的是AHB, RCA采用SystemC编写的行为级模型。
矩阵乘法常被应用于许多视频处理算法中, 整数余弦变换/反变换 (DCT/IDCT) 是H.264中的核心算法, 快速傅里叶变换 (FFT) 是傅里叶变换 (DFT) 的一种计算机快速算法, 是离散数字信号处理的基础, 在采用相同的软件代码和映射硬件任务的条件下, 表1是与RCA的对比。
由表1可以看出, MAT_MUL相比原有的性能上有10.8%的提高, IDCT相比原有的性能上有11.3%的提高, FFT相比原有的性能上有8.7%的提高, 但是8×8DCT由于任务划分使得子任务之间存在很多的数据传输, 导致可重构阵列的计算时间无法有效的弥补由于任务划分而产生的额外数据传输所造成的性能损失。
5 结束语
提出了一种新的可重构阵列模型和基于其特点的任务调度算法, 完成了其在SOCDesigner平台上的软硬件协同验证。但是仍有大量工作需要做, 包括任务调度算法的优化, 硬件模型RTL代码的编写, 综合和时序分析, 以及布局布线等。
但是根据实验结果, 可以看出:
(1) 配置信息和操作数据之间仍然存在着对总线的竞争。
(2) 缺少对硬件任务进行最优划分的算法, 使得划分后的任务之间独立性不高, 较多的数据传输限制了系统的性能。
(3) 目前的可重构系统和任务调度算法由于受到子可重构阵列粒度的限制, 处理数据依赖关系紧密的任务集合时, 性能仍然存在不足。
因此还需要许多工作以提高该可重构阵列的性能。
摘要：提出了一种可以利用计算时间覆盖配置时间和数据传输时间的可重构阵列结构, 并且针对该可重构阵列结构提出了一种表调度算法进行任务调度。在SOCDesigner平台上进行了软硬件协同仿真, 对于IDCT, FFT, 4×4矩阵乘法新可重构阵列相比原来的可重构阵列有平均约10%的速度提升。
关键词：可重构,覆盖,表调度,协同仿真
参考文献
[1]Kasahara H, Narita S.Practical Multiprocessor Scheduling Algo-rithms for Efficient Parallel Processing[Z].IEEE Transactions onComputers, 1984.
[2]Wu Min-You, Gajski D.Hypertool:A Programming Aid for Mes-sage-Passing Systems[Z].IEEE Transactions on Parallel and Dis-tributed Systems, 1990.
[3]Yu-Kwong Kwok, Ishfaq Ahmad.Dynamic Critic-al-Path Schedu-ling:An Effective Technique for Allo-cating Task Graphs to Multi-processors[Z].IEEE Transactions on Parallel and Distributed Sys-tems, 1996.
[4]Yang Tao.DSC:Scheduling Parrallel Tasks on an Unbounded Num-ber of Processers[Z].IEEE Transactio-ns on Parallel and Distribu-ted Systems, 1994.
[5]Ahmad I, Kwok Y.A New Approach to Sched-uling Parallel Pro-grams Using Task Duplication[C].Proc.Int'1 Conf.Parallel Pro-cessing, 1994.
[6]Li Guodong, Chen Daoxu, Wang Daming, et al.Task Clusteringand Scheduling to Multiproce-ssors with Duplication[C].Procee-dings of the Internat-ional Pa rallel and Di stributed ProcessingSymposi-um (IPDPS'03) :April 22-26, 2003.
[7]Singh H, Youssef A.Mapping and Scheduling Heterogeneous TaskGraphs Using Genetic Algorit-hms.Proc[Z].Heterogeneous Com-puting Workshop, 1996.
[8]Singh H, Lee Ming-Hau.MorphoSys:an integ rated reconfigurablesystem for data-parallel and computation-intensive applications[Z].IEEE Transactions on Volume, 2000.
[9]Goldstein S C, Schmit H.PipeRench:a reconfigurable architectureand compiler[Z].Computer, 2002.
[10]肖钰, 刘雷波.应用于视频处理的可重构流处理器的设计与实现[J].器件与应用, 2008.