【摘要】：MapReduce是一種流行的批處理框架,用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算,其主要作用是分布式集群節(jié)點(diǎn)分析、保持?jǐn)?shù)據(jù)局部原則、使數(shù)據(jù)更加真實(shí)有效.本文主要研究h臺(tái)同類機(jī),reduce任務(wù)可中斷和不可中斷的MapReduce在線排序模型,目標(biāo)函數(shù)是極小化工件的最大完工時(shí)間.本文結(jié)構(gòu)安排如下:第一章主要介紹排序問題的基本知識(shí)、MapReduce的基本概念.第二章主要研究h臺(tái)同類機(jī)reduce任務(wù)可中斷的在線MapReduce排序問題,工件以over list釋放.目標(biāo)函數(shù)是極小化工件的最大完工時(shí)間.在MapReduce排序模型中有兩個(gè)假設(shè):一是MapReduce排序的map任務(wù)可以并行加工,而reduce任務(wù)不可并行加工.二是必須得等一個(gè)工件中的map任務(wù)加工完成之后才可以加工reduce任務(wù).本章仍沿用這種假設(shè),即假設(shè)map任務(wù)可以無限分割,即可并行加工,而reduce任務(wù)不可并行加工,但在本章中,工件的reduce任務(wù)可以中斷,該模型假設(shè)為只有當(dāng)map任務(wù)完成之后才可以知道reduce任務(wù)的信息,所以在本章中設(shè)計(jì)的算法為工件到達(dá)之后先將所有map任務(wù)分到h臺(tái)機(jī)器上,使得加工完map任務(wù)的h臺(tái)機(jī)器的完工時(shí)間相等,對(duì)于reduce任務(wù)可中斷的情況,我們采用了文[26]提出的McNaughton’s around rule這一方法,該方法得到的機(jī)器的完工時(shí)間為Cmax=max(?),本章利用該方法設(shè)計(jì)了一個(gè)近似算法,給出了近似算法的競爭比的上界為2 (?),其中S1 ≥ S2 ≥...≥sh,其sj是機(jī)器j的加工速度,k0為使得Tk/Bk(1 ≤k≤h)達(dá)到最大值的機(jī)器的編號(hào),h是機(jī)器臺(tái)數(shù),其中Tk = |r1| + |r2| +...+ |rk|,Bk=s1 + s2+…+sk,|r1|≥|r2|≥ …≥ |rm|,|ri| 是第i長reduce任務(wù)的長度.第三章同樣研究了h臺(tái)同類機(jī)在線的MapReduce在線排序問題,與第二章不同的是:本章研究了 reduce任務(wù)不可中斷的情況,工件以over list釋放,目標(biāo)為極小化工件的最大完工時(shí)間,同樣假設(shè)一個(gè)工件的map任務(wù)完成之后才可以知道該工件reduce任務(wù)的信息,本章所采用的算法思想是:對(duì)于到達(dá)的工件將map任務(wù)放在h臺(tái)機(jī)器上加工,使得加工完map任務(wù)的機(jī)器完工時(shí)間均相等,然后將reduce任務(wù)以LPT規(guī)則排序,依據(jù)經(jīng)典排序的LPT規(guī)則,設(shè)計(jì)了近似算法,并得到了該近似算法的競爭比的上界.第四章是總結(jié)了全文主要內(nèi)容,并對(duì)接下來的努力方向提供了參考.
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O223

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 蔡圣義;;三臺(tái)同類機(jī)在線排序問題一種特殊情形的研究[J];系統(tǒng)工程理論與實(shí)踐;2006年07期

相關(guān)博士學(xué)位論文 前1條

1 蔣義偉;可中斷平行機(jī)排序問題研究[D];浙江大學(xué);2007年

本文編號(hào)：2764637