并行計(jì)算中簡(jiǎn)易調(diào)度算法的探究

馮祥勝 張思聰 劉佐東 王凱 杜雨馨

摘要：近年來，并行計(jì)算越來越被人們所關(guān)注，而調(diào)度算法又是并行計(jì)算中的一大重點(diǎn)，所以與之相關(guān)的調(diào)度問題也成了現(xiàn)階段研究的焦點(diǎn)。通過相關(guān)實(shí)際問題闡述了調(diào)度算法的核心思想，并提出了一種簡(jiǎn)易的新型調(diào)度算法。旨在代碼復(fù)雜度和實(shí)用性方面滿足當(dāng)前計(jì)算機(jī)多核處理器與大規(guī)模平級(jí)任務(wù)之間的調(diào)度分配需求。并舉例分析了該種調(diào)度算法在On—line Judge系統(tǒng)中多平級(jí)任務(wù)的應(yīng)用。最后簡(jiǎn)要提出了未來計(jì)算機(jī)領(lǐng)域發(fā)展格局下，調(diào)度算法的發(fā)展前景以及調(diào)度算法在未來多領(lǐng)域的應(yīng)用。

關(guān)鍵詞：并行處理;調(diào)度算法;在線測(cè)評(píng);進(jìn)程隊(duì)列;UMA

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）01-0284-03

1概述

21世紀(jì)是計(jì)算機(jī)崛起的世紀(jì)，計(jì)算機(jī)的計(jì)算能力不斷提高，從而也帶動(dòng)了其他領(lǐng)域的進(jìn)一步發(fā)展，使得其他領(lǐng)域的計(jì)算更加趨向精細(xì)化，研究?jī)?nèi)容也變得定量化。諸如在制導(dǎo)系統(tǒng)、精密儀器學(xué)、遺傳學(xué)、有限元計(jì)算等學(xué)科中計(jì)算內(nèi)容變得更加精確，計(jì)算方面也變得更加細(xì)微，逐漸形成了一種計(jì)算性很強(qiáng)的獨(dú)立性學(xué)科。加之當(dāng)下科技呈指數(shù)式發(fā)展，各種多功能應(yīng)用軟件接踵而至以及當(dāng)下AI智能的興起，這對(duì)計(jì)算機(jī)的運(yùn)算速度以及處理大規(guī)模任務(wù)的能力提出了更高的要求，而并行計(jì)算可有效提高計(jì)算機(jī)運(yùn)算效率及大規(guī)模任務(wù)下的并發(fā)處理能力，目前并行處理技術(shù)普遍存在難以高效合理的分配任務(wù)給多核處理器的問題，而在處理器處理完畢一個(gè)任務(wù)之后與下一個(gè)新的未處理的任務(wù)之間的銜接問題是解決問題的關(guān)鍵所在。通過對(duì)調(diào)度算法的研究來實(shí)現(xiàn)任務(wù)與處理器之間的合理調(diào)度，可有效提高計(jì)算機(jī)的并行處理能力。

2目前并行處理領(lǐng)域的發(fā)展

2.1并行處理

計(jì)算機(jī)處理器在同一時(shí)刻處理多個(gè)進(jìn)程的過程稱為并行處理。并行處理對(duì)提高計(jì)算機(jī)內(nèi)存最大利用率及運(yùn)算速度具有重大意義，并行處理的實(shí)質(zhì)就是對(duì)時(shí)間的重復(fù)利用和對(duì)資源的合理分配，針對(duì)目前多核計(jì)算機(jī)的蓬勃發(fā)展，并行處理技術(shù)日趨成熟。

2.2國(guó)內(nèi)外并行研究現(xiàn)狀

20世紀(jì)80年代出現(xiàn)了并行計(jì)算的第一個(gè)研究高潮，但是由于人們一貫的單一思維方式，往往會(huì)先遇到問題然后再去想辦法解決問題，從而導(dǎo)致人們對(duì)并行算法的研究長(zhǎng)期處于被動(dòng)狀態(tài)，以至于后來的10年間，在核心技術(shù)上沒有太大的突破。現(xiàn)如今，人們的需求不斷提高，各個(gè)領(lǐng)域的計(jì)算也越來越繁雜，逐漸開始意識(shí)到并行處理對(duì)于提高運(yùn)算速度與性能的重要性，并行計(jì)算迎來了第二個(gè)黃金階段。這期間，計(jì)算機(jī)體系結(jié)構(gòu)經(jīng)歷了從并行向量處理機(jī)到大規(guī)模并行多處理機(jī)再到現(xiàn)在的SMP機(jī)群的發(fā)展歷程，目前普遍存在的并行程序模型主要有消息傳遞并行模型、共享儲(chǔ)存并行模型、鎖無關(guān)的投機(jī)并行多線程模型、統(tǒng)一架構(gòu)的并行多線程模型等。目前，如何提高支持并行計(jì)算的軟件系統(tǒng)的抽象層次以及如何使軟件系統(tǒng)適應(yīng)多種并行體系結(jié)構(gòu)是并行計(jì)算的兩大困難所在。

3并行計(jì)算的高效性

3.1調(diào)度算法高效性的討論

并行計(jì)算中調(diào)度算法的高效性體現(xiàn)在：合理分配進(jìn)程隊(duì)列中的作業(yè)，使得處理器在空閑狀態(tài)下的總時(shí)間最短。例如：

當(dāng)計(jì)算機(jī)存在p核處理器分別為P1P2P3……時(shí)，進(jìn)程隊(duì)列中存在n個(gè)作業(yè)分別為n1n2n3……且進(jìn)程隊(duì)列中的每一個(gè)作業(yè)都存在一定的計(jì)算量ti，開始執(zhí)行時(shí)間和ri截止執(zhí)行時(shí)間mi;每一作業(yè)可在不同處理器上處理，但一個(gè)作業(yè)僅能被單核處理機(jī)完全處理，且在處理過程中不能被打斷。

如何將進(jìn)程隊(duì)列中的所有作業(yè)在多核處理器內(nèi)最短時(shí)間全部完成，就需要高效的調(diào)度算法進(jìn)行進(jìn)程調(diào)度。而高效的并行算法應(yīng)在處理作業(yè)時(shí)，高效使用多核處理器，減少空閑處理器的存在。因?yàn)檫M(jìn)程隊(duì)列中作業(yè)總完成時(shí)間一定，而當(dāng)多核處理器均保持計(jì)算狀態(tài)下，就可保證總工作時(shí)間最短。從而在最短時(shí)間內(nèi)最高效的完成進(jìn)程隊(duì)列中的所有任務(wù)。

3.2調(diào)度算法理論分析

設(shè)進(jìn)程ni的實(shí)際完成時(shí)間為qi，則通過如下的分段函數(shù)來表示進(jìn)程是否延期完成：

4簡(jiǎn)易調(diào)度算法的描述

針對(duì)上述問題，目前普遍存在的困難就在于：如何保證處理器在空閑狀態(tài)下的總時(shí)間最短，使得計(jì)算機(jī)處理器在完成一個(gè)進(jìn)程后的處于空閑狀態(tài)下的時(shí)間最少。這就需要有一套合理的調(diào)度算法來進(jìn)行合理調(diào)度，使處理器的空閑時(shí)間最少，該算法結(jié)合并行機(jī)的實(shí)際處理過程來完成調(diào)度。

4.1調(diào)度流程

調(diào)度方法為通過數(shù)組來存儲(chǔ)計(jì)算機(jī)處理器的數(shù)據(jù)信息，再通過循環(huán)語句來循環(huán)往復(fù)的遍歷計(jì)算機(jī)處理器，一旦發(fā)現(xiàn)閑置的處理器便通過數(shù)據(jù)傳輸至等待隊(duì)列的任務(wù)，使處于等待隊(duì)列最前端的任務(wù)與此閑置的處理器相匹配，如此往復(fù)，直至所有的任務(wù)完成為止。

4.2算法描述

此算法首先通過input語句輸入將n個(gè)任務(wù)的相關(guān)信息儲(chǔ)存到數(shù)組C[n]，將p個(gè)處理器的數(shù)據(jù)信息儲(chǔ)存到P[n]中，其中n>>p，即任務(wù)數(shù)量遠(yuǎn)大于處理器數(shù)量。然后通過output輸出語句將相關(guān)信息輸入到任務(wù)分配處理器，通過UMA并行算法對(duì)C[n]和P[n]進(jìn)行計(jì)算，接著執(zhí)行do while語句進(jìn)行循環(huán)，直至所有任務(wù)執(zhí)行完畢，此算法結(jié)束。本文提出的調(diào)度算法僅僅是在同級(jí)別任務(wù)之間的調(diào)度，然而在實(shí)際問題中，尤其是大規(guī)模任務(wù)中，其每個(gè)子任務(wù)重要程度往往是不同的，此時(shí)應(yīng)根據(jù)每個(gè)任務(wù)的重要程度來進(jìn)行優(yōu)先級(jí)排列，任務(wù)分配其將會(huì)根據(jù)任務(wù)的優(yōu)先級(jí)，將優(yōu)先級(jí)較高的任務(wù)優(yōu)先分配先分配給閑置的處理器，這樣才能更加合理地完成任務(wù)。其次，本文的算法未考慮大規(guī)模任務(wù)量下的聚類問題，若能根據(jù)每個(gè)子任務(wù)的執(zhí)行單元數(shù)量與任務(wù)的重要程度得出一個(gè)合理的權(quán)重，選定聚類中心對(duì)子任務(wù)進(jìn)行聚類，可進(jìn)一步提高運(yùn)算效率。

5在Online Judge系統(tǒng)中的實(shí)用價(jià)值

此調(diào)度算法的研究對(duì)目前各大高校的Online Judge系統(tǒng)具有重要意義，針對(duì)目前各大高校的Online Judge系統(tǒng)在大用戶量下的并發(fā)處理能力弱，運(yùn)行流暢度低等問題，并行處理技術(shù)可以有效解決上述問題，大大提高Online Judge系統(tǒng)的并發(fā)處理能力，提高用戶滿意度，讓OJ系統(tǒng)更有力地為高校服務(wù)。并行處理是提高目前Online Judge系統(tǒng)性能的一大關(guān)鍵。其次，目前的Online Judge系統(tǒng)的評(píng)判方式均為同級(jí)任務(wù)之間調(diào)度評(píng)判而不存在優(yōu)先級(jí)問題，而本文所研究的調(diào)度算法也不涉及優(yōu)先級(jí)問題，這與Online Judge系統(tǒng)的性質(zhì)相一致，故本算法對(duì)于Online Judge系統(tǒng)的題目評(píng)判調(diào)度問題非常適用。

6并行計(jì)算的未來展望

未來，隨著Moore定律越來越不適用于當(dāng)下的科技發(fā)展模式，計(jì)算機(jī)的發(fā)展也不僅僅由計(jì)算機(jī)原有的硬件性能決定，更多是由一套合理高效的算法來決定，而并行計(jì)算也將成為新世紀(jì)計(jì)算機(jī)領(lǐng)域的發(fā)展主流，并行算法的開發(fā)將會(huì)變得如火如荼，針對(duì)其調(diào)度問題的調(diào)度算法也將進(jìn)入新的研究高潮。在信息高度交融的時(shí)代，并行調(diào)度算法可應(yīng)用水資源的調(diào)度、居民用電分配、碼頭集裝箱分揀等諸多領(lǐng)域，結(jié)合優(yōu)先級(jí)調(diào)度，聚類算法，并行計(jì)算的調(diào)度算法將會(huì)日趨成熟與完善，將會(huì)得到更加充分的利用。