近年來,邊緣計(jì)算已經(jīng)成為了下一代網(wǎng)絡(luò)研究中最為矚目的技術(shù)亮點(diǎn),邊緣計(jì)算為許多諸如虛擬現(xiàn)實(shí),自動(dòng)駕駛,深度學(xué)習(xí)等新興的計(jì)算密集型應(yīng)用提供了強(qiáng)有力的計(jì)算力保證。這些新型的計(jì)算應(yīng)用的發(fā)展也對(duì)計(jì)算性能提出更高的要求。MapReduce是一種專門為大規(guī)模并行數(shù)據(jù)處理設(shè)計(jì)的分布式計(jì)算框架。在邊緣計(jì)算中通�？梢圆捎肕apReduce框架在多個(gè)邊緣服務(wù)器上分布式處理各種類型的計(jì)算任務(wù)。更進(jìn)一步,編碼MapReduce框架利用編碼技術(shù)與冗余計(jì)算資源通過調(diào)整計(jì)算負(fù)載可以對(duì)服務(wù)器之間的通信負(fù)載進(jìn)行優(yōu)化。隨著近些年計(jì)算應(yīng)用對(duì)于低時(shí)延的需求日益強(qiáng)烈。邊緣服務(wù)器之間的大量通信負(fù)載成為提高計(jì)算性能的瓶頸,并且邊緣計(jì)算資源具有時(shí)變特征。如何通過計(jì)算負(fù)載調(diào)度充分利用動(dòng)態(tài)變化的冗余計(jì)算資源來提高計(jì)算性能,如何對(duì)邊緣服務(wù)器之間通信負(fù)載進(jìn)行優(yōu)化。以此為動(dòng)機(jī),本文開展了對(duì)面向編碼MapReduce的通信有效計(jì)算負(fù)載調(diào)度的研究。首先,本文研究了單任務(wù)場景下通信有效計(jì)算負(fù)載調(diào)度算法。對(duì)于可以預(yù)先獲知整個(gè)時(shí)間范圍內(nèi)可用計(jì)算資源狀態(tài)的離線情況,將通信負(fù)載的調(diào)度算法轉(zhuǎn)化為優(yōu)化問題,利用最優(yōu)性條件對(duì)計(jì)算重復(fù)因子和計(jì)算任務(wù)量進(jìn)行解耦,將聯(lián)合... 

【文章來源】：浙江大學(xué)浙江省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：86 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１．１?ＭａｐＲｅｄｕｃｅ框架基本執(zhí)行流程［ｓ］??

?丨?＿ｉｉ?ｗｍ??圖１．１?ＭａｐＲｅｄｕｃｅ框架基本執(zhí)行流程［ｓ］??碼ＭａｐＲｅｄｕｃｅ框架中，將編碼技術(shù)的應(yīng)用擴(kuò)展到邊緣計(jì)算中來，通過編碼減少Ｓｈｕｆｆｌｅ階段??的通信負(fù)載，提高邊緣計(jì)算的整體性能。??編碼ＭａｐＲｅｄｕｃｅ通過建立計(jì)算負(fù)載與通信負(fù)載之間的關(guān)系，證明可以通過增加計(jì)算負(fù)??載以減少Ｓｈｕｆｆｌｅ階段的通信負(fù)載。編碼ＭａｐＲｅｄｕｃｅ利用不同計(jì)算節(jié)點(diǎn)上相同數(shù)據(jù)塊的重復(fù)??計(jì)算，以實(shí)現(xiàn)編碼。更具體地說，對(duì)于具有Ｋ個(gè)計(jì)算節(jié)點(diǎn)的服務(wù)器群集，通過多播ＬＡＮ網(wǎng)??絡(luò)互連，計(jì)算任務(wù)共有＜５個(gè)輸入文件，Ｂ個(gè)Ｒｅｄｕｃｅ函數(shù)。編碼ＭａｐＲｅｄｕｃｅ提出了一種特定??的策略來分配Ｍａｐ任務(wù)，可以對(duì)計(jì)算節(jié)點(diǎn)上每個(gè)數(shù)據(jù)塊進(jìn)行ｉ？次重復(fù)計(jì)算，并在Ｓｈｕｆｆｌｅ階??段進(jìn)行編碼可以大幅減少Ｓｈｕｆｆｌｅ階段的通信負(fù)載，具體實(shí)例可以參考如圖１．２所示。??在圖１．２中

□??引理２?（定理２注解）．我們發(fā)現(xiàn)在定理２中的計(jì)算負(fù)載調(diào)度算法與注水算法有異曲同工之??妙。如圖２Ｊ所示，Ａ是與＾相交的解平面，是它直接決定了調(diào)度方案，因?yàn)樗凶??入的水Ｓ⑷的總量滿足⑴Ｃ，＋?｝?＝?Ｍ，所以我們可以通過調(diào)整Ａ來??調(diào)整水平面以滿足最終水量的和為Ｍ達(dá)到最優(yōu)性。此時(shí)與最優(yōu)解平面Ａ＊與＾相交的結(jié)果??便是最優(yōu)調(diào)度算法。??２．４在線計(jì)算負(fù)載調(diào)度算法??在本節(jié)中，我們基于上一節(jié)的離線最優(yōu)計(jì)算負(fù)載調(diào)度算法希望可以可在在線場景中得??到相應(yīng)的解決方案。利用競爭分析方法，我們得到任意在線調(diào)度算法的競爭比下界，并且??１６??


本文編號(hào)：2906271