亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        多區(qū)域大規(guī)模迭代計(jì)算框架應(yīng)用研究

        2018-11-16 06:34:34王曉斌盧福軍馬忠義
        信息通信技術(shù) 2018年5期
        關(guān)鍵詞:分片數(shù)據(jù)量集群

        王曉斌 盧福軍 殷 穎 閆 萌 馬忠義

        1 中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司山西省分公司 太原 030006

        2 山西建筑工程(集團(tuán))總公司 太原 030012

        3 東北大學(xué)軟件學(xué)院 沈陽(yáng) 110169

        前言

        在數(shù)學(xué)中,迭代函數(shù)是可重復(fù)與自身復(fù)合的函數(shù),反復(fù)地運(yùn)用同一函數(shù)計(jì)算,前一次計(jì)算得到的結(jié)果被用做下一次計(jì)算的輸入,這個(gè)過程叫做迭代。在計(jì)算機(jī)科學(xué)中,迭代是程序中對(duì)一組指令(或一定步驟)的重復(fù),它通常描述一種特定形式的具有可變狀態(tài)的重復(fù)。迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn),讓計(jì)算機(jī)對(duì)一組指令(或一定步驟)進(jìn)行重復(fù)執(zhí)行,在每次執(zhí)行這組指令(或這些步驟)時(shí),都從變量的原值推出它的一個(gè)新值。即使是看上去很簡(jiǎn)單的算法,在經(jīng)過迭代之后也可能產(chǎn)生復(fù)雜的行為,衍生出困難問題的求解方法[1]。

        隨著數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等相關(guān)領(lǐng)域的發(fā)展,越來越多的迭代計(jì)算應(yīng)用到諸如社會(huì)網(wǎng)絡(luò)分析、高性能計(jì)算、推薦系統(tǒng)、搜索引擎、模式識(shí)別等領(lǐng)域中[2]。例如:網(wǎng)頁(yè)排名算法PageRank算法根據(jù)網(wǎng)頁(yè)之間的鏈接關(guān)系進(jìn)行迭代并收斂至最終結(jié)果,其迭代本質(zhì)即從任意迭代初始點(diǎn)開始,根據(jù)迭代函數(shù)進(jìn)行反復(fù)迭代更新;K-means算法反復(fù)迭代更新數(shù)據(jù)聚類中心點(diǎn),根據(jù)最終收斂的不動(dòng)點(diǎn)結(jié)果來判定數(shù)據(jù)單元的聚類所屬關(guān)系;協(xié)同過濾(Collaborative Filtering)算法,通常作用在用戶與購(gòu)買商品關(guān)系的二維圖上,通過交叉運(yùn)行以用戶為核心的和以商品為核心的兩個(gè)迭代計(jì)算過程,最終收斂的兩個(gè)向量表示購(gòu)買習(xí)慣相似的用戶群和功能相似的商品群,利用相似用戶群中其他用戶的商品喜好信息來進(jìn)行個(gè)性化推薦。

        “海量”是大數(shù)據(jù)的一個(gè)主要特點(diǎn)。大數(shù)據(jù)是數(shù)據(jù)量龐大且分布廣泛的數(shù)據(jù),當(dāng)我們談及大數(shù)據(jù)時(shí),很難假設(shè)數(shù)據(jù)是集中存儲(chǔ)的,也很難認(rèn)為數(shù)據(jù)是靜態(tài)存儲(chǔ)的。眾所周知,大數(shù)據(jù)分析算法期望作用在全集數(shù)據(jù)而非局部數(shù)據(jù)之上,而“全集”又是相對(duì)的。因此迭代分析算法既會(huì)在各局部數(shù)據(jù)上執(zhí)行,得到相對(duì)局部的分析結(jié)果;又會(huì)在匯總的全集數(shù)據(jù)上運(yùn)行,產(chǎn)生相對(duì)整體的分析結(jié)果。我們對(duì)這種迭代稱為多區(qū)域大規(guī)模多級(jí)迭代計(jì)算,簡(jiǎn)稱多區(qū)域迭代。多區(qū)域迭代計(jì)算原理如圖1所示,這是本文的研究重點(diǎn)。我們從文獻(xiàn)[2]中得到了大量的啟發(fā),類似的工作包括Pramod等人提出了Incoop[3]框架,以及文獻(xiàn)[4]中,提出的針對(duì)PageRank算法的增量式迭代分析計(jì)算。

        1 系統(tǒng)架構(gòu)

        在大數(shù)據(jù)環(huán)境背景下,基于Hadoop MapReduce[5]的HaLoop框架[6]是現(xiàn)階段相對(duì)成熟的分布式迭代計(jì)算框架,它采用MapReduce的編程模型使得其可以充分利用廉價(jià)的分布式服務(wù)器集群得到強(qiáng)大的迭代分析能力,并對(duì)Hadoop框架進(jìn)行適應(yīng)迭代分析算法的改進(jìn),從而支持大數(shù)據(jù)下大部分迭代分析算法的運(yùn)行。近些年,由于計(jì)算機(jī)硬件的快速發(fā)展,UC Berkeley AMP Lab提出了Spark框架[7]。Spark框架與HaLoop框架不同,它完全作用于內(nèi)存計(jì)算,而無需從HDFS上讀寫迭代數(shù)據(jù),迭代的分析速度更快、更便捷,因此Spark框架能更好地適用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等計(jì)算機(jī)科學(xué)領(lǐng)域中的迭代分析算法。綜上所述,多區(qū)域大規(guī)模迭代計(jì)算將選擇Spark計(jì)算框架作為計(jì)算平臺(tái),通過對(duì)Spark框架的擴(kuò)展實(shí)現(xiàn)大數(shù)據(jù)環(huán)境下的多區(qū)域迭代計(jì)算。

        將迭代計(jì)算模型運(yùn)用于山西聯(lián)通大數(shù)據(jù)業(yè)務(wù)分析領(lǐng)域,其系統(tǒng)架構(gòu)如圖2所示。例如山西聯(lián)通組織機(jī)構(gòu)可以根據(jù)地理位置劃分為太原分公司、大同分公司、呂梁分公司、臨汾分公司等11個(gè)地市分公司,每個(gè)行政地市都有對(duì)應(yīng)的通信業(yè)務(wù)分析機(jī)構(gòu),對(duì)區(qū)內(nèi)自身的通信數(shù)據(jù)進(jìn)行分析操作,獲得區(qū)域內(nèi)可靠的通信結(jié)果;而對(duì)于山西聯(lián)通省公司而言,也對(duì)應(yīng)存在一個(gè)省級(jí)分析機(jī)構(gòu),用于全省數(shù)據(jù)的分析,即將各個(gè)地市的移動(dòng)通信進(jìn)行匯總,并在匯總后的全集數(shù)據(jù)上進(jìn)行數(shù)據(jù)分析得到某市整體的分析結(jié)果。

        在圖2中,藍(lán)色虛框標(biāo)記的是區(qū)域(地市)分析機(jī)構(gòu)的集群架構(gòu),包括各個(gè)地市自身的Spark&Yarn分析計(jì)算集群和存儲(chǔ)數(shù)據(jù)的分布式文件系統(tǒng),紅色虛框標(biāo)記的是省級(jí)分析機(jī)構(gòu)的集群架構(gòu),主要由計(jì)算集群Spark&Yarn框架組成。各個(gè)地市基于內(nèi)部的Spark&Yarn分析計(jì)算集群,在區(qū)內(nèi)自身的數(shù)據(jù)上進(jìn)行分析得到對(duì)應(yīng)的區(qū)內(nèi)分析結(jié)果,服務(wù)于區(qū)內(nèi)個(gè)性化的政策和未來科學(xué)合理地決策,而當(dāng)省級(jí)機(jī)構(gòu)需要對(duì)全市數(shù)據(jù)進(jìn)行分析時(shí),各個(gè)地市的機(jī)構(gòu)可以將自身區(qū)內(nèi)的數(shù)據(jù)以及區(qū)內(nèi)分析結(jié)果反饋給省級(jí)機(jī)構(gòu),省級(jí)機(jī)構(gòu)可以基于省級(jí)的Spark&Yarn分析計(jì)算集群,直接在區(qū)內(nèi)分析結(jié)果的基礎(chǔ)上進(jìn)行迭代計(jì)算,快速地得到全省的分析結(jié)果。其中,各個(gè)區(qū)內(nèi)(地市)的分析計(jì)算集群Spark&Yarn的架構(gòu)如圖3所示。

        圖1 多區(qū)域迭代計(jì)算原理

        圖2 多區(qū)域大規(guī)模迭代計(jì)算系統(tǒng)架構(gòu)圖

        多區(qū)域大規(guī)模迭代計(jì)算框架的運(yùn)行主要步驟為:Client提交迭代計(jì)算的應(yīng)用,主節(jié)點(diǎn)構(gòu)建迭代的運(yùn)行環(huán)境并啟動(dòng)Driver,Driver向主節(jié)點(diǎn)或者資源管理器申請(qǐng)迭代計(jì)算所需的資源,并通過SparkContext將迭代計(jì)算應(yīng)用轉(zhuǎn)化為RDD Graph,再通過DAGScheduler將RDD Graph分解為Stage的有向無環(huán)圖,將TaskSet發(fā)送給TaskScheduler,最終由TaskScheduler發(fā)送Task給對(duì)應(yīng)的Executor執(zhí)行迭代任務(wù)。在迭代計(jì)算任務(wù)執(zhí)行的過程中,Yarn中的Resource Manager負(fù)責(zé)迭代計(jì)算資源的分配和調(diào)度,其中Container是迭代計(jì)算資源分配和調(diào)度的基本單位,封裝了內(nèi)存、CPU、網(wǎng)絡(luò)、磁盤等計(jì)算節(jié)點(diǎn)中重要的機(jī)器資源。

        2 迭代算子

        基于上節(jié)對(duì)多區(qū)域大規(guī)模迭代計(jì)算系統(tǒng)架構(gòu)的介紹,我們可將框架主要分為以下幾個(gè)模塊:RDD(Resilient Distributed Datasets)算子模塊、迭代調(diào)度模塊、迭代計(jì)算模塊。其中最重要的為RDD算子模塊,是實(shí)現(xiàn)區(qū)域迭代的核心。

        圖3 多區(qū)域大規(guī)模迭代計(jì)算框架Yarn模式的架構(gòu)圖

        RDD彈性分布式數(shù)據(jù)集,是迭代計(jì)算系統(tǒng)中的數(shù)據(jù)抽象,提供了一種高度受限的共享內(nèi)存模型,即RDD是只讀的,分區(qū)記錄的集合。每個(gè)RDD數(shù)據(jù)集合都有以下屬性。①RDD之間的依賴關(guān)系:RDD在進(jìn)行變換過程中,會(huì)由一個(gè)舊RDD變換為一個(gè)新RDD,兩個(gè)新舊RDD數(shù)據(jù)集之間存在類似流水線一樣的前后依賴關(guān)系,通過RDD之間前后的依賴關(guān)系,我們可以在某些分區(qū)數(shù)據(jù)丟失時(shí)進(jìn)行恢復(fù)性計(jì)算,得到正確的迭代結(jié)果;②分片Partition:分片是RDD數(shù)據(jù)集的基本組成單元,針對(duì)每個(gè)RDD數(shù)據(jù)集而言,每個(gè)分片都會(huì)被指定一個(gè)迭代計(jì)算任務(wù)進(jìn)行處理,并決定了迭代計(jì)算的并行粒度。于此同時(shí),RDD還具有一個(gè)分片函數(shù),用于對(duì)RDD數(shù)據(jù)集進(jìn)行分片,包括基于哈希的分片函數(shù)HashPartitioner和基于范圍的分片函數(shù)RangePartitioner;③列表:用于存儲(chǔ)RDD數(shù)據(jù)集中每個(gè)分片的有限位置,在HDFS文件系統(tǒng)中,該列表存儲(chǔ)的是RDD數(shù)據(jù)集中每個(gè)分片所在塊的位置。通過該表對(duì)RDD數(shù)據(jù)集中各個(gè)分片位置的存儲(chǔ),我們可以實(shí)現(xiàn)“移動(dòng)數(shù)據(jù)不如移動(dòng)計(jì)算”的思想,在迭代計(jì)算任務(wù)調(diào)度過程中,盡可能地將計(jì)算任務(wù)分配給將進(jìn)行迭代計(jì)算所需資源所在的位置。

        同時(shí),RDD只能基于穩(wěn)定物理存儲(chǔ),并通過在其中的數(shù)據(jù)集合對(duì)其它已有的RDD執(zhí)行確定性變換操作來創(chuàng)建。當(dāng)RDD數(shù)據(jù)集創(chuàng)建完畢后,可以在RDD數(shù)據(jù)集上進(jìn)行兩種數(shù)據(jù)操作,分別是①轉(zhuǎn)換Transformation:在現(xiàn)有RDD數(shù)據(jù)集的基礎(chǔ)上創(chuàng)建一個(gè)新的RDD數(shù)據(jù)集;②動(dòng)作Action:在RDD數(shù)據(jù)集執(zhí)行完迭代計(jì)算后,將迭代結(jié)果返回給Driver組件。

        表1和表2分別列舉了迭代計(jì)算系統(tǒng)RDD算子模塊中重要的轉(zhuǎn)換操作和動(dòng)作操作,其中partition(Dataset)、merge(otherDataset)、loss(lossDataset)為多區(qū)域大規(guī)模迭代計(jì)算系統(tǒng)新增的3個(gè)RDD算子轉(zhuǎn)換操作,分別用于多區(qū)域迭代計(jì)算過程中的數(shù)據(jù)分區(qū)、合并區(qū)內(nèi)迭代計(jì)算結(jié)果、區(qū)內(nèi)迭代計(jì)算結(jié)果的誤差。其中,多區(qū)域迭代計(jì)算的編程模型如下所示。

        表1 RDD數(shù)據(jù)集的轉(zhuǎn)換操作表

        表2 RDD數(shù)據(jù)集的動(dòng)作操作表

        3 實(shí)驗(yàn)驗(yàn)證

        為了保證實(shí)驗(yàn)結(jié)果的正確性和真實(shí)性,我們使用真實(shí)的物理計(jì)算機(jī)作為分布式集群進(jìn)行實(shí)驗(yàn),其中包括1臺(tái)Master控制節(jié)點(diǎn)和12臺(tái)Slave計(jì)算節(jié)點(diǎn)。K-Means算法的測(cè)試數(shù)據(jù)集我們采用山西聯(lián)通真實(shí)的數(shù)據(jù)集。設(shè)多區(qū)域迭代計(jì)算模型中的迭代數(shù)據(jù)量為D,其中包含全集數(shù)據(jù)量以及區(qū)內(nèi)數(shù)據(jù)量,同時(shí)區(qū)內(nèi)數(shù)據(jù)量隨著全集數(shù)據(jù)量的增長(zhǎng)而增長(zhǎng);區(qū)內(nèi)迭代數(shù)據(jù)的分區(qū)記為P。K-means測(cè)試數(shù)據(jù)的相關(guān)信息如表3所示。

        表3 K-Means測(cè)試數(shù)據(jù)集

        全部實(shí)驗(yàn)結(jié)果如表4所示,其中分別測(cè)量了多區(qū)域迭代與Spark迭代的迭代時(shí)長(zhǎng),并通過計(jì)算優(yōu)化比例得出了多區(qū)域迭代的優(yōu)化效果,優(yōu)化比例的計(jì)算公式如下。

        表4 實(shí)驗(yàn)結(jié)果

        圖4分別從不同數(shù)據(jù)量和不同分區(qū)數(shù)的角度展示了部分實(shí)驗(yàn)結(jié)果。由于K-Means算法的迭代計(jì)算輪數(shù)對(duì)初始點(diǎn)的選擇非常敏感,為保證實(shí)驗(yàn)結(jié)果的正確性,我們對(duì)每一組測(cè)試用例都運(yùn)行了5次K-Means算法從而求取平均值進(jìn)行分析比較。由圖4可知以下結(jié)論:①在各種條件下,多區(qū)域迭代計(jì)算框架的性能較傳統(tǒng)的Spark都有明顯的優(yōu)化。優(yōu)化比例最低也在15%至20%之間。②對(duì)于多區(qū)域迭代框架和Spark,數(shù)據(jù)量對(duì)于性能的影響大于分區(qū)數(shù)目的影響,其中數(shù)據(jù)量越大,或者分區(qū)數(shù)目越多,迭代性能越差。③我們?cè)O(shè)計(jì)的多區(qū)域迭代計(jì)算框架在給定用例下較Spark有性能優(yōu)勢(shì)。

        圖4 多區(qū)域迭代計(jì)算框架與Spark的性能對(duì)比

        4 結(jié)論與展望

        多區(qū)域大規(guī)模多級(jí)迭代計(jì)算的研究來源于中國(guó)聯(lián)通山西省分公司的具體數(shù)據(jù)匯集方式和分析需求,該研究成功提高了多地市數(shù)據(jù)分析和省級(jí)數(shù)據(jù)分析的效率,減少了省級(jí)數(shù)據(jù)分析的時(shí)間,減少了數(shù)據(jù)傳輸時(shí)延,有著確切的實(shí)際應(yīng)用效果。然而,本研究仍處于初級(jí)階段,還有許多問題需要解決。首先,多區(qū)域迭代計(jì)算模型并非適用于所有的迭代算法,而且模型角度也不具有足夠的抽象性。其次,多區(qū)域迭代較全集迭代是有精度損失的,從實(shí)驗(yàn)和實(shí)際證明該損失對(duì)于部分適用的迭代算法可以忽略不計(jì),同時(shí)對(duì)損失的量化評(píng)估,還需要進(jìn)一步研究。

        猜你喜歡
        分片數(shù)據(jù)量集群
        上下分片與詞的時(shí)空佈局
        詞學(xué)(2022年1期)2022-10-27 08:06:12
        基于大數(shù)據(jù)量的初至層析成像算法優(yōu)化
        計(jì)算Lyapunov指數(shù)的模糊C均值聚類小數(shù)據(jù)量法
        分片光滑邊值問題的再生核方法
        CDN存量MP4視頻播放優(yōu)化方法
        高刷新率不容易顯示器需求與接口標(biāo)準(zhǔn)帶寬
        寬帶信號(hào)采集與大數(shù)據(jù)量傳輸系統(tǒng)設(shè)計(jì)與研究
        電子制作(2019年13期)2020-01-14 03:15:18
        海上小型無人機(jī)集群的反制裝備需求與應(yīng)對(duì)之策研究
        基于模糊二分查找的幀分片算法設(shè)計(jì)與實(shí)現(xiàn)
        一種無人機(jī)集群發(fā)射回收裝置的控制系統(tǒng)設(shè)計(jì)
        電子制作(2018年11期)2018-08-04 03:25:40
        又大又粗又爽18禁免费看| 精品人妻一区二区三区不卡毛片 | 香蕉色香蕉在线视频| 美女叉开双腿让男人插| 北条麻妃在线中文字幕| 日本啪啪一区二区三区| 国产91大片在线观看| 国产高清一区二区三区四区色 | 美女污污网站| 精精国产xxx在线视频app| 午夜不卡久久精品无码免费| 狠狠色噜噜狠狠狠8888米奇| 国产亚洲精品a片久久久| 无码午夜人妻一区二区三区不卡视频| 99re6久精品国产首页| 亚洲第一女优在线观看| 国产一精品一av一免费爽爽| 亚洲欧美日韩国产精品专区| av天堂线上| 夜夜高潮夜夜爽免费观看| 久久综合亚洲色hezyo国产 | 玖玖资源站无码专区| 久久狠狠爱亚洲综合影院| 中文字幕隔壁人妻欲求不满| 久久久精品人妻无码专区不卡 | 饥渴的熟妇张开腿呻吟视频| 亚洲国产精品中文字幕日韩| 一本色道加勒比精品一区二区 | 亚洲综合网在线观看首页| 最新亚洲av日韩av二区一区| 日本最新一区二区三区视频观看| 国产成人无码a区在线观看视频 | 精品日本韩国一区二区三区| 粉嫩av最新在线高清观看| 48沈阳熟女高潮嗷嗷叫| 国产成人免费一区二区三区| 国语对白自拍视频在线播放| 亚洲av首页在线| 亚洲精品成人专区在线观看| 亚洲中国美女精品久久久| 亚洲av高清一区二区三|