數(shù)據(jù)并行系統(tǒng)中應(yīng)用程序的爆炸式增長,以及對(duì)任務(wù)處理和數(shù)據(jù)分析的日益增長的高效需求,使得數(shù)據(jù)并行系統(tǒng)在處理具有高實(shí)時(shí)性需求的I/O密集型數(shù)據(jù)集時(shí)承受著較大的內(nèi)存壓力。低效的緩存策略會(huì)嚴(yán)重降低資源的利用率影響系統(tǒng)性能。通常情況下,對(duì)于需要大量內(nèi)存計(jì)算的數(shù)據(jù)流任務(wù),如何實(shí)現(xiàn)高效的緩存管理是權(quán)衡性能和內(nèi)存開銷的主要措施。近些年,設(shè)計(jì)出恰當(dāng)?shù)木彺婀芾聿呗砸云胶夤ぷ髫?fù)載,緩解傳輸瓶頸,減少內(nèi)存資源消耗是內(nèi)存計(jì)算中的研究重點(diǎn)之一。在緩存的設(shè)計(jì)和選擇的問題上,研究證實(shí)當(dāng)前主流的基于內(nèi)存計(jì)算并行數(shù)據(jù)處理系統(tǒng)中包括LRU在內(nèi)的默認(rèn)的傳統(tǒng)緩存算法并不能有效滿足當(dāng)前環(huán)境下應(yīng)用特征和實(shí)時(shí)需求,且容易造成低命中率、不必要的I/O開銷和資源浪費(fèi),主要?dú)w因于這些緩存算法多未充分利用數(shù)據(jù)并行系統(tǒng)中的數(shù)據(jù)依賴語義信息,而是依賴傳統(tǒng)的基于數(shù)據(jù)項(xiàng)最近訪問信息和頻率信息等局部信息進(jìn)行緩存管理。本文旨在設(shè)計(jì)一種新的緩存算法以達(dá)到性能與開銷之間進(jìn)行折衷的目的,該算法稱為非關(guān)鍵路徑最小引用計(jì)數(shù)（Non-critical Path Least Reference Count,簡稱NLC）。其與現(xiàn)有算法的不同之處在于:其一,NLC充分利... 

【文章來源】：中國科學(xué)院大學(xué)(中國科學(xué)院深圳先進(jìn)技術(shù)研究院)廣東省

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

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

【部分圖文】：

內(nèi)存計(jì)算硬件架構(gòu)

第2章背景知識(shí)介紹11圖3：最小引用計(jì)數(shù)算法示例計(jì)算作業(yè)的數(shù)據(jù)依賴DAG的可用性不僅限于Spark當(dāng)中，常見的并行框架例如ApacheTez[7]也可以提供數(shù)據(jù)依賴語義信息，Tez的設(shè)計(jì)包括支持從Task收集相關(guān)信息的可插拔頂點(diǎn)管理模塊。其API允許程序員明確定義工作流程DAG應(yīng)用程序，事先可供Tez調(diào)度程序使用，同時(shí)在運(yùn)行時(shí)可以動(dòng)態(tài)調(diào)整數(shù)據(jù)流圖以達(dá)到優(yōu)化性能和提高資源利用率的目的。2.3最小引用計(jì)數(shù)算法上節(jié)中介紹了在計(jì)算機(jī)領(lǐng)域和數(shù)據(jù)并行系統(tǒng)中數(shù)據(jù)依賴語義的具體含義。盡管在數(shù)據(jù)并行系統(tǒng)中存在有別于傳統(tǒng)系統(tǒng)的數(shù)據(jù)依賴語義信息，然而現(xiàn)有常見的數(shù)據(jù)并行系統(tǒng)在默認(rèn)情況下的緩存算法中并未充分利用該信息，如在1.2提到最近最少使用策略(LeastRecentlyUsed,LRU)，它依然時(shí)是在Spark中，BlockManager在存在高內(nèi)存壓力的情況時(shí)默認(rèn)的緩存策略。然而僅僅依靠用于緩存管理的最新訪問和訪問頻率信息會(huì)浪費(fèi)大量內(nèi)存以保存也許永遠(yuǎn)不會(huì)在下游計(jì)算中使[27]用的數(shù)據(jù)塊，這將會(huì)無可避免地會(huì)導(dǎo)致低效的資源利用率。因此這一節(jié)將介紹一個(gè)最小引用計(jì)數(shù)算法以及Yu等人地相關(guān)工作，改算法在一定程度上利用了數(shù)據(jù)并行系統(tǒng)中的依賴語義信息。Figure3：AnexampleofLeastReferenceCount圖3最小引用計(jì)數(shù)示例

面向資源約束的數(shù)據(jù)流并行自適應(yīng)緩存管理研究12在該示例中，最小引用計(jì)數(shù)算法根據(jù)下游數(shù)據(jù)依賴信息制定緩存規(guī)則，如圖3的例子所示，在DAG提交時(shí)，塊A、B、C和D的引用計(jì)數(shù)分別為A=4>B=3>C=2>D=1最小引用計(jì)數(shù)(LRC)策略跟蹤每個(gè)數(shù)據(jù)塊的引用計(jì)數(shù)，在需要的時(shí)候，它會(huì)清除引用計(jì)數(shù)最小的數(shù)據(jù)塊。直觀地說，引用計(jì)數(shù)越高，那么在未來該數(shù)據(jù)塊被訪問地可能性就越大。為了驗(yàn)證引用計(jì)數(shù)(ReferenceCount)能否成為未來數(shù)據(jù)訪問的簡單可行指標(biāo)。Yu等人針對(duì)最近使用信息，最頻繁使用信息，引用計(jì)數(shù)三種不同指標(biāo)的代表算法進(jìn)行了一系列實(shí)驗(yàn)測量其優(yōu)先級(jí)。實(shí)驗(yàn)表明使用引用計(jì)數(shù)的始終能比其他兩種指標(biāo)效果要好。Figure4:Uncertaintyofdatadependence如圖4中的一個(gè)例子。在計(jì)算了數(shù)據(jù)塊塊C和D之后，假設(shè)集群調(diào)度器提交兩個(gè)任務(wù)集Task1和Task2分別計(jì)算數(shù)據(jù)塊M和N（假設(shè)E和F已經(jīng)在內(nèi)存中）。在這種情況下，首先計(jì)算哪個(gè)塊E或F取決于Task1和Task2的調(diào)度順序，而這又決定了塊E和F的訪問次序,局部數(shù)據(jù)依賴語義信息如下:((′)∩())≠Φ((′)∩())≠Φ((′)∩())≠Φ((′)∩())≠Φ圖4數(shù)據(jù)依賴的不確定性


本文編號(hào)：3345464