基于智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)研究

彭 慧

（湖南財(cái)政經(jīng)濟(jì)學(xué)院，湖南 長(zhǎng)沙 410205）

隨著信息技術(shù)的高速發(fā)展，計(jì)算機(jī)負(fù)荷并行處理技術(shù)得到了越來(lái)越多的人的關(guān)注，這是因?yàn)榇笠?guī)模的并行處理技術(shù)是一種主流技術(shù)，其技術(shù)當(dāng)中的關(guān)鍵在于高速的互聯(lián)網(wǎng)技術(shù)、網(wǎng)絡(luò)節(jié)點(diǎn)的結(jié)構(gòu)以及計(jì)算機(jī)程序?qū)崿F(xiàn)并行.在該項(xiàng)技術(shù)使用的過(guò)程中，同時(shí)也需要注意到計(jì)算機(jī)負(fù)荷的因素，如果計(jì)算機(jī)負(fù)荷無(wú)法達(dá)到要求，那么并行處理技術(shù)也無(wú)法起到應(yīng)有的效果，因此在使用計(jì)算機(jī)負(fù)荷并行處理技術(shù)的過(guò)程中，就需要著重注意到應(yīng)該使用智能化的分配算法.在這樣的情況下，就需要對(duì)基于智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)進(jìn)行研究.本文將從同構(gòu)星型的網(wǎng)絡(luò)為出發(fā)點(diǎn)，并且在網(wǎng)絡(luò)中是由N個(gè)鏈路以及N+1個(gè)處理器構(gòu)成的，包括了根處理器和前端處理器，所有處理器都必須通過(guò)聯(lián)路進(jìn)行連接，而通過(guò)智能化分配算法將系統(tǒng)中的總負(fù)荷科學(xué)地分配到各個(gè)合適的節(jié)點(diǎn)上.因此，系統(tǒng)通信的開(kāi)銷(xiāo)也就能夠變得最小，系統(tǒng)的等待時(shí)間也得到了縮短，效率提升，也因?yàn)檫@樣的原因，系統(tǒng)的整體性能也得到了提高，變?yōu)樽罴褷顟B(tài).

1 計(jì)算機(jī)并行處理技術(shù)的特點(diǎn)

計(jì)算機(jī)并行處理技術(shù)是一種全新的技術(shù)，目前在計(jì)算機(jī)各個(gè)領(lǐng)域使用的較為廣泛.其主要特點(diǎn)有如下幾點(diǎn)：

1.1 大規(guī)模并行處理

計(jì)算機(jī)的并行處理技術(shù)的一種大規(guī)模的并行處理技術(shù)，通常被我們稱(chēng)為MPP，該系統(tǒng)的種類(lèi)很多，其中MIMD型的存儲(chǔ)方式為松耦合分布，是這種并行處理方式中的主要技術(shù)，包括了高速互聯(lián)網(wǎng)絡(luò)、并行程序開(kāi)發(fā)以及節(jié)點(diǎn)結(jié)構(gòu)三個(gè)方面.

1.2 對(duì)稱(chēng)多處理技術(shù)

MPP系統(tǒng)中多是將多個(gè)計(jì)算機(jī)通過(guò)一條總線進(jìn)行連接，系統(tǒng)中所有的硬件和軟件都處于對(duì)稱(chēng)的位置上.其中硬件上的CPU擁有完全一致的計(jì)算能力，并且數(shù)據(jù)能夠?qū)崿F(xiàn)共享；而所有的軟件則擁有同樣的操作系統(tǒng)代碼.

1.3 工作站群機(jī)處理技術(shù)

在這一項(xiàng)技術(shù)當(dāng)中，將會(huì)通過(guò)互聯(lián)網(wǎng)將一組服務(wù)器和小型機(jī)包括工作站或是巨型機(jī)甚至大規(guī)模并行處理系統(tǒng)聯(lián)系在一起.而由于這些機(jī)器被連接在了一起，也就能夠進(jìn)行并行處理的工作.

1.4 并行數(shù)據(jù)庫(kù)處理技術(shù)

計(jì)算機(jī)并行數(shù)據(jù)庫(kù)處理技術(shù)是計(jì)算機(jī)并行處理技術(shù)當(dāng)中重要的組成部分之一.通過(guò)并行數(shù)據(jù)庫(kù)處理技術(shù)，能夠有效提高計(jì)算機(jī)對(duì)數(shù)據(jù)查詢(xún)速度以及數(shù)據(jù)管理方面的能力.在這過(guò)程當(dāng)中，能夠?qū)崿F(xiàn)對(duì)計(jì)算機(jī)數(shù)據(jù)庫(kù)的并行查詢(xún)，并對(duì)數(shù)據(jù)庫(kù)進(jìn)行分區(qū)的管理，使數(shù)據(jù)庫(kù)的使用更加的便捷.就目前來(lái)看，并行數(shù)據(jù)庫(kù)處理技術(shù)在使用當(dāng)中最主要的是虛擬的服務(wù)技術(shù)和多線程技術(shù).

1.5 對(duì)稱(chēng)多處理技術(shù)

對(duì)稱(chēng)多處理技術(shù)的英文縮寫(xiě)為SMP，在這項(xiàng)技術(shù)當(dāng)中也是通過(guò)總線將多個(gè)處理器聯(lián)系而成，而且系統(tǒng)中的軟件和硬件是對(duì)稱(chēng)的，同時(shí)在硬件上的每個(gè)CPU計(jì)算能力相同，也是共享主存的.在軟件上，所有的軟件都是共享一份操作代碼的.

2 智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理的模型以及算法

2.1 智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)的模型描述

我們將以同構(gòu)星型的網(wǎng)絡(luò)為模型，在網(wǎng)絡(luò)中是由N個(gè)鏈路以及N+1個(gè)處理器構(gòu)成的，包括了根處理器和前端處理器，同時(shí)所有的處理器都和根處理器用過(guò)通信鏈路連接，并且與之相連的處理器和鏈路的線性成本系數(shù)為…以及…我們可以假設(shè)當(dāng)計(jì)算機(jī)達(dá)到一定的負(fù)荷時(shí)，總的負(fù)荷將通過(guò)根處理器被分成N+1份，并且根處理器將能夠保證自身的部分為a0，然后能夠?yàn)樽犹幚矸峙銹1、P2、P3、…、PN的部分也能夠保證其為 a1、a2、a3…、an.在負(fù)荷的分配完成之后，系統(tǒng)中包含的所有處理器會(huì)立即開(kāi)始計(jì)算，直到被分配的負(fù)荷被全部計(jì)算處理了為止.在計(jì)算的過(guò)程中，我們可以令Wi為第i個(gè)處理器的計(jì)算速度的倒數(shù)，ai為第i個(gè)鏈路上的處理器所分配到的負(fù)荷，Zi則是在第i個(gè)鏈路上的連接速度的倒數(shù)，計(jì)算強(qiáng)度的常數(shù)是Tcp，用來(lái)表示在WiTcp秒內(nèi)通過(guò)第i個(gè)鏈路時(shí)的總負(fù)荷.此外，Tf表示所有負(fù)荷被處理完成后的時(shí)間.

2.2 智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)的負(fù)荷分配算法

在對(duì)智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)的負(fù)荷分配模型進(jìn)行計(jì)算的過(guò)程中，首先需要明確服務(wù)器系統(tǒng)S是由n個(gè)可用的節(jié)點(diǎn)構(gòu)成的，并且系統(tǒng)中的數(shù)據(jù)可以劃分為p個(gè)數(shù)據(jù)分片，同時(shí)在整個(gè)系統(tǒng)中必須一共要有m個(gè)任務(wù).W用來(lái)表示整個(gè)系統(tǒng)中任務(wù)的等待處理的隊(duì)列，長(zhǎng)度用Q來(lái)表示，Wi對(duì)應(yīng)的應(yīng)該是第i個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上接收到的但是還沒(méi)有進(jìn)行處理的任務(wù)所形成的隊(duì)列，隊(duì)列的長(zhǎng)度為Qi.在計(jì)算機(jī)智能化分配算法實(shí)現(xiàn)的過(guò)程中，必須要包含以下幾個(gè)定義，才能使算法成立.

定義1 網(wǎng)絡(luò)節(jié)點(diǎn)類(lèi)型向量Tu，根據(jù)節(jié)點(diǎn)在工作中的荷載L來(lái)表示和記錄各個(gè)節(jié)點(diǎn)類(lèi)型中所包含的一維向量的取值.網(wǎng)絡(luò)中所有節(jié)點(diǎn)都要設(shè)置閾值f，這個(gè)值是根據(jù)系統(tǒng)運(yùn)行時(shí)的資源配置以及系統(tǒng)實(shí)際的處理能力來(lái)進(jìn)行設(shè)置的.與此同時(shí)，還要設(shè)定

在本式中，要注意Tv[i]表示-1，表示的具體意義為系統(tǒng)在Si狀態(tài)欠載，并且為接收節(jié)點(diǎn)，如果Tv[i]為0，那么表示系統(tǒng)在Si為平衡狀態(tài)，如果Tv[i]為1，那么表示系統(tǒng)在Si為超載狀態(tài)，并且在此時(shí)為發(fā)送結(jié)點(diǎn).

定義2 節(jié)點(diǎn)的負(fù)載是用L來(lái)表示，并且用所有節(jié)點(diǎn)的CPU隊(duì)列的長(zhǎng)度比來(lái)表示每個(gè)節(jié)點(diǎn)的CPU隊(duì)列長(zhǎng)度.也就是說(shuō)，如果假設(shè)Si的CPU隊(duì)列長(zhǎng)度為L(zhǎng)i，那么在Si處的負(fù)載就可以使用如下過(guò)程進(jìn)行計(jì)算.

定義3 在該系統(tǒng)當(dāng)中，數(shù)據(jù)分配矩陣將用Dm來(lái)表示，那么我們可以通過(guò)計(jì)算整個(gè)系統(tǒng)中數(shù)據(jù)分片的分布來(lái)將Dm的值進(jìn)行確定，同時(shí)也能夠?qū)?shù)據(jù)分布情況的矩陣進(jìn)行確定，具體大小為n×p.

定義4 系統(tǒng)中數(shù)據(jù)分布冗余等級(jí)的向量為Rv，我們將通過(guò)這個(gè)向量來(lái)記錄某一個(gè)數(shù)據(jù)分片冗余等級(jí)的一維向量，具體的大小用p來(lái)表示，計(jì)算過(guò)程為：

定義5 開(kāi)銷(xiāo)矩陣Am是用來(lái)表示系統(tǒng)中的某一個(gè)任務(wù)被分配到某一節(jié)點(diǎn)上后，在執(zhí)行時(shí)產(chǎn)生的開(kāi)銷(xiāo)矩陣，開(kāi)銷(xiāo)矩陣的大小為m×n，其計(jì)算過(guò)程為：

其中Am[g,i]為任務(wù)再借點(diǎn)Si商上執(zhí)行的開(kāi)銷(xiāo).

定義6 節(jié)點(diǎn)任務(wù)在執(zhí)行的計(jì)算開(kāi)銷(xiāo)數(shù)組AA為記錄每一個(gè)節(jié)點(diǎn)中的所有任務(wù)執(zhí)行開(kāi)銷(xiāo)之和的一維數(shù)組，具體的大小為n，計(jì)算過(guò)程為：

定義7 在系統(tǒng)中的各個(gè)任務(wù)在進(jìn)行通信開(kāi)銷(xiāo)時(shí)，開(kāi)銷(xiāo)矩陣是用TM來(lái)表示的，當(dāng)不同節(jié)點(diǎn)機(jī)在執(zhí)行任務(wù)時(shí)，會(huì)進(jìn)行信息的交換，這時(shí)就會(huì)產(chǎn)生通信開(kāi)銷(xiāo)矩陣，具體大小用m×m來(lái)表示.計(jì)算過(guò)程為：

定義8 節(jié)點(diǎn)機(jī)在進(jìn)行任務(wù)處理的過(guò)程中，會(huì)產(chǎn)生一個(gè)值為CA.我們將用CA來(lái)表示任務(wù)通信的開(kāi)銷(xiāo)數(shù)組，其作用就是記錄每一個(gè)節(jié)點(diǎn)執(zhí)行任務(wù)時(shí)和其他節(jié)點(diǎn)進(jìn)行信息交換所產(chǎn)生的通信開(kāi)銷(xiāo)總和的數(shù)組，具體大小為n，數(shù)組的計(jì)算過(guò)程為：

定義9 節(jié)點(diǎn)機(jī)任務(wù)開(kāi)銷(xiāo)數(shù)組用FA來(lái)表示，可以用于記錄在每一個(gè)節(jié)點(diǎn)中計(jì)算通信開(kāi)銷(xiāo)以及開(kāi)銷(xiāo)之和，數(shù)組的具體大小為n，可以使用以下過(guò)程來(lái)進(jìn)行計(jì)算

定義10 當(dāng)一個(gè)任務(wù)在任意的兩點(diǎn)之間進(jìn)行轉(zhuǎn)移時(shí)，也會(huì)產(chǎn)生開(kāi)銷(xiāo)，這被我們成為轉(zhuǎn)移開(kāi)銷(xiāo).在具體的計(jì)算過(guò)程中，我們可以設(shè)Csize（Tg）為任務(wù)Tg在執(zhí)行時(shí)的代碼數(shù)據(jù)量，與此同時(shí)，設(shè)Rsize（Tg）為任務(wù)Tg在執(zhí)行后結(jié)果信息的數(shù)據(jù)量，那么當(dāng)Tg從節(jié)點(diǎn)Si轉(zhuǎn)移到節(jié)點(diǎn)Sj時(shí)，所產(chǎn)生的開(kāi)銷(xiāo)Pg為

在這個(gè)式子當(dāng)中包括了發(fā)送者和接受者啟動(dòng)的模塊，當(dāng)兩個(gè)模塊在工作時(shí)，會(huì)根據(jù)總的任務(wù)負(fù)載和在等待中的任務(wù)量來(lái)選擇應(yīng)該啟動(dòng)的子模塊，從而保證任務(wù)的圓滿完成.

2.3 智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)的負(fù)荷的主要遞推公式

在進(jìn)行負(fù)荷的分配時(shí)，分配過(guò)程可以用一種與根特圖相類(lèi)似的時(shí)間分配表格來(lái)進(jìn)行表示.如圖所示，時(shí)間軸的上方表示的是系統(tǒng)的通信時(shí)間，而時(shí)間軸的下方則表示計(jì)算時(shí)間.在該時(shí)間圖的基礎(chǔ)上，我們同時(shí)假設(shè)所有的處理器在同一時(shí)間節(jié)點(diǎn)上都能夠停止計(jì)算，從而得到遞推公式.

通過(guò)此時(shí)間圖我們可以計(jì)算出系統(tǒng)的遞推公式為

其中Cn為系統(tǒng)在處理第n個(gè)處理器時(shí)總的負(fù)荷成本，而總成本為每個(gè)鏈路上到處理器上所得到的單個(gè)處理成本的總和，計(jì)算方法為

3 結(jié)語(yǔ)

在進(jìn)行分布式并行數(shù)據(jù)處理的過(guò)程中，對(duì)計(jì)算機(jī)負(fù)荷的正確處理顯得十分重要，因此就需要使用任務(wù)分配算法來(lái)進(jìn)行計(jì)算，這種計(jì)算方式將有效提高計(jì)算機(jī)處理任務(wù)的效率以及系統(tǒng)的處理開(kāi)銷(xiāo).文章所提出的智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)能夠根據(jù)負(fù)荷的變化智能地選擇啟動(dòng)策略，并同時(shí)將任務(wù)執(zhí)行時(shí)可能出現(xiàn)的需求進(jìn)行綜合的考慮，值得在數(shù)據(jù)處理過(guò)程中使用.

〔1〕李杰.計(jì)算機(jī)負(fù)荷并行處理技術(shù)的智能化分配算法[J].電子制作,2013(8):98.

〔2〕崔夢(mèng)天,趙海軍,李明東,等.基于智能化分配算法的計(jì)算機(jī)負(fù)荷并行處理技術(shù)[J].系統(tǒng)工程與電子技術(shù),2008,30(11):2270-2273.

〔3〕王超,劉偉,袁培苑,等.基于細(xì)粒度任務(wù)分配的空時(shí)自適應(yīng)并行處理算法研究[J].電子與信息學(xué)報(bào),2012,34(6):1398-1403.

〔4〕易會(huì)戰(zhàn),劉永鵬.改善系統(tǒng)能量效率的體系結(jié)構(gòu)方法:并行處理 [J].計(jì)算機(jī)學(xué)報(bào),2009,32(12):2475-2481.

〔5〕鐘敏,陳朝根,葛宇飛,等.基于網(wǎng)格技術(shù)的地震資料并行處理平臺(tái)建設(shè)與應(yīng)用[J].中國(guó)石油大學(xué)學(xué)報(bào)（自然科學(xué)版）,2014,38(2):180-186.

〔6〕王茂芝,郭科,徐文皙,等.基于集群和 GPU 的高光譜遙感影像并行處理 [J].紅外與激光工程,2013,(11):3070-3075.

〔7〕李江昀,孫麗婷.基于并行處理的一種新型有效的網(wǎng)絡(luò)架構(gòu)BSN-MOT[J].通信學(xué)報(bào),2014,(4):182-190.

〔8〕楊典華,潘欣.一種面向大型地理柵格數(shù)據(jù)的并行處理框架[J].國(guó)防科技大學(xué)學(xué)報(bào),2013,(6):152-156.