并行计算中简易调度算法的探究

冯祥胜 张思聪 刘佐东 王凯 杜雨馨

摘要：近年来，并行计算越来越被人们所关注，而调度算法又是并行计算中的一大重点，所以与之相关的调度问题也成了现阶段研究的焦点。通过相关实际问题阐述了调度算法的核心思想，并提出了一种简易的新型调度算法。旨在代码复杂度和实用性方面满足当前计算机多核处理器与大规模平级任务之间的调度分配需求。并举例分析了该种调度算法在On—line Judge系统中多平级任务的应用。最后简要提出了未来计算机领域发展格局下，调度算法的发展前景以及调度算法在未来多领域的应用。

关键词：并行处理;调度算法;在线测评;进程队列;UMA

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2020）01-0284-03

1概述

21世纪是计算机崛起的世纪，计算机的计算能力不断提高，从而也带动了其他领域的进一步发展，使得其他领域的计算更加趋向精细化，研究内容也变得定量化。诸如在制导系统、精密仪器学、遗传学、有限元计算等学科中计算内容变得更加精确，计算方面也变得更加细微，逐渐形成了一种计算性很强的独立性学科。加之当下科技呈指数式发展，各种多功能应用软件接踵而至以及当下AI智能的兴起，这对计算机的运算速度以及处理大规模任务的能力提出了更高的要求，而并行计算可有效提高计算机运算效率及大规模任务下的并发处理能力，目前并行处理技术普遍存在难以高效合理的分配任务给多核处理器的问题，而在处理器处理完毕一个任务之后与下一个新的未处理的任务之间的衔接问题是解决问题的关键所在。通过对调度算法的研究来实现任务与处理器之间的合理调度，可有效提高计算机的并行处理能力。

2目前并行处理领域的发展

2.1并行处理

计算机处理器在同一时刻处理多个进程的过程称为并行处理。并行处理对提高计算机内存最大利用率及运算速度具有重大意义，并行处理的实质就是对时间的重复利用和对资源的合理分配，针对目前多核计算机的蓬勃发展，并行处理技术日趋成熟。

2.2国内外并行研究现状

20世纪80年代出现了并行计算的第一个研究高潮，但是由于人们一贯的单一思维方式，往往会先遇到问题然后再去想办法解决问题，从而导致人们对并行算法的研究长期处于被动状态，以至于后来的10年间，在核心技术上没有太大的突破。现如今，人们的需求不断提高，各个领域的计算也越来越繁杂，逐渐开始意识到并行处理对于提高运算速度与性能的重要性，并行计算迎来了第二个黄金阶段。这期间，计算机体系结构经历了从并行向量处理机到大规模并行多处理机再到现在的SMP机群的发展历程，目前普遍存在的并行程序模型主要有消息传递并行模型、共享储存并行模型、锁无关的投机并行多线程模型、统一架构的并行多线程模型等。目前，如何提高支持并行计算的软件系统的抽象层次以及如何使软件系统适应多种并行体系结构是并行计算的两大困难所在。

3并行计算的高效性

3.1调度算法高效性的讨论

并行计算中调度算法的高效性体现在：合理分配进程队列中的作业，使得处理器在空闲状态下的总时间最短。例如：

当计算机存在p核处理器分别为P1P2P3……时，进程队列中存在n个作业分别为n1n2n3……且进程队列中的每一个作业都存在一定的计算量ti，开始执行时间和ri截止执行时间mi;每一作业可在不同处理器上处理，但一个作业仅能被单核处理机完全处理，且在处理过程中不能被打断。

如何将进程隊列中的所有作业在多核处理器内最短时间全部完成，就需要高效的调度算法进行进程调度。而高效的并行算法应在处理作业时，高效使用多核处理器，减少空闲处理器的存在。因为进程队列中作业总完成时间一定，而当多核处理器均保持计算状态下，就可保证总工作时间最短。从而在最短时间内最高效的完成进程队列中的所有任务。

3.2调度算法理论分析

设进程ni的实际完成时间为qi，则通过如下的分段函数来表示进程是否延期完成：

4简易调度算法的描述

针对上述问题，目前普遍存在的困难就在于：如何保证处理器在空闲状态下的总时间最短，使得计算机处理器在完成一个进程后的处于空闲状态下的时间最少。这就需要有一套合理的调度算法来进行合理调度，使处理器的空闲时间最少，该算法结合并行机的实际处理过程来完成调度。

4.1调度流程

调度方法为通过数组来存储计算机处理器的数据信息，再通过循环语句来循环往复的遍历计算机处理器，一旦发现闲置的处理器便通过数据传输至等待队列的任务，使处于等待队列最前端的任务与此闲置的处理器相匹配，如此往复，直至所有的任务完成为止。

4.2算法描述

此算法首先通过input语句输入将n个任务的相关信息储存到数组C[n]，将p个处理器的数据信息储存到P[n]中，其中n>>p，即任务数量远大于处理器数量。然后通过output输出语句将相关信息输入到任务分配处理器，通过UMA并行算法对C[n]和P[n]进行计算，接着执行do while语句进行循环，直至所有任务执行完毕，此算法结束。本文提出的调度算法仅仅是在同级别任务之间的调度，然而在实际问题中，尤其是大规模任务中，其每个子任务重要程度往往是不同的，此时应根据每个任务的重要程度来进行优先级排列，任务分配其将会根据任务的优先级，将优先级较高的任务优先分配先分配给闲置的处理器，这样才能更加合理地完成任务。其次，本文的算法未考虑大规模任务量下的聚类问题，若能根据每个子任务的执行单元数量与任务的重要程度得出一个合理的权重，选定聚类中心对子任务进行聚类，可进一步提高运算效率。

5在Online Judge系统中的实用价值

此调度算法的研究对目前各大高校的Online Judge系统具有重要意义，针对目前各大高校的Online Judge系统在大用户量下的并发处理能力弱，运行流畅度低等问题，并行处理技术可以有效解决上述问题，大大提高Online Judge系统的并发处理能力，提高用户满意度，让OJ系统更有力地为高校服务。并行处理是提高目前Online Judge系统性能的一大关键。其次，目前的Online Judge系统的评判方式均为同级任务之间调度评判而不存在优先级问题，而本文所研究的调度算法也不涉及优先级问题，这与Online Judge系统的性质相一致，故本算法对于Online Judge系统的题目评判调度问题非常适用。

6并行计算的未来展望

未来，随着Moore定律越来越不适用于当下的科技发展模式，计算机的发展也不仅仅由计算机原有的硬件性能决定，更多是由一套合理高效的算法来决定，而并行计算也将成为新世纪计算机领域的发展主流，并行算法的开发将会变得如火如荼，针对其调度问题的调度算法也将进入新的研究高潮。在信息高度交融的时代，并行调度算法可应用水资源的调度、居民用电分配、码头集装箱分拣等诸多领域，结合优先级调度，聚类算法，并行计算的调度算法将会日趋成熟与完善，将会得到更加充分的利用。