徐志偉 王一帆 趙永威 李春典
(計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)(中國(guó)科學(xué)院大學(xué) 北京 100049)
本文是一篇觀點(diǎn)文章,指出計(jì)算系統(tǒng)研究需要學(xué)習(xí)算法領(lǐng)域的經(jīng)驗(yàn),探索能夠刻畫計(jì)算系統(tǒng)本質(zhì)特征的可分析抽象,并提出了一個(gè)初步概念,稱為算禮,旨在拋磚引玉,促進(jìn)計(jì)算系統(tǒng)抽象的研究.
長(zhǎng)期以來(lái),計(jì)算系統(tǒng)領(lǐng)域缺乏“算法”這樣簡(jiǎn)潔的學(xué)術(shù)概念來(lái)刻畫系統(tǒng)的本質(zhì)特征,使得系統(tǒng)研究往往依賴原型研制和基準(zhǔn)程序測(cè)試.這種“原型測(cè)試”的計(jì)算系統(tǒng)設(shè)計(jì)方法非常耗時(shí)耗資源,研究結(jié)果往往難以被他人重現(xiàn).另一方面,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究正在進(jìn)入多樣性時(shí)代,各種加速器帶來(lái)的異構(gòu)硬件、領(lǐng)域特定體系結(jié)構(gòu)(domain-specific architecture)、庫(kù)操作系統(tǒng)、眾多的應(yīng)用框架、物聯(lián)網(wǎng)系統(tǒng)的昆蟲綱悖論,都是多樣性趨勢(shì)的表現(xiàn).業(yè)界迫切需要超越“原型測(cè)試”的計(jì)算系統(tǒng)分析與設(shè)計(jì)方法,尤其需要能夠簡(jiǎn)潔地刻畫計(jì)算系統(tǒng)的可分析抽象,即在原型測(cè)試之前,就能分析出系統(tǒng)重要性質(zhì)的抽象描述.
計(jì)算系統(tǒng)出現(xiàn)多樣性趨勢(shì)主要可以歸納為3個(gè)原因:1)應(yīng)用需求的多樣性,尤其是高能效(性能功耗比)的要求,難以被一種通用計(jì)算系統(tǒng)滿足[1-2];2)計(jì)算系統(tǒng)的范圍早已從單機(jī)拓展到并行計(jì)算機(jī)、分布式計(jì)算系統(tǒng);3)計(jì)算系統(tǒng)的層次近年來(lái)已經(jīng)從系統(tǒng)硬件層、系統(tǒng)軟件層拓展到包括Spark和TensorFlow等系統(tǒng)的應(yīng)用框架層.
John Hennessy與David Patterson最近指出,計(jì)算系統(tǒng)的多樣性趨勢(shì)為計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究帶來(lái)了又一個(gè)黃金時(shí)代[2].系統(tǒng)抽象是計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究的一個(gè)重要方向.本文學(xué)習(xí)算法的經(jīng)驗(yàn),指出計(jì)算系統(tǒng)研究需要能夠刻畫系統(tǒng)本質(zhì)特征的可分析抽象,并提出了一個(gè)初步候選,稱為算禮(computation protocol),以拋磚引玉,促進(jìn)學(xué)術(shù)社區(qū)對(duì)計(jì)算系統(tǒng)可分析抽象的研究.我們討論了算禮的黑箱模型和白箱模型,并用初步的實(shí)例指出,算禮思想有助于在計(jì)算系統(tǒng)領(lǐng)域提出系統(tǒng)猜想、分析新的并行計(jì)算模型、拓展現(xiàn)有架構(gòu)、啟發(fā)新的系統(tǒng)評(píng)價(jià)方法.
計(jì)算機(jī)應(yīng)用研究離不開計(jì)算機(jī)科學(xué)的一個(gè)本質(zhì)抽象——算法.今天,算法已廣泛滲透到計(jì)算機(jī)科學(xué)技術(shù)整個(gè)領(lǐng)域,包括它的3個(gè)二級(jí)學(xué)科:計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、軟件與理論、計(jì)算機(jī)應(yīng)用.
算法的廣泛滲透性得益于它是一個(gè)可分析抽象.學(xué)習(xí)和研究一個(gè)算法,并不一定要將該算法實(shí)現(xiàn)成程序代碼在真實(shí)或原型計(jì)算機(jī)上運(yùn)行,就可以分析出它的重要性質(zhì).事實(shí)上,國(guó)內(nèi)外很多算法課程不涉及編程.但是,計(jì)算系統(tǒng)領(lǐng)域缺乏“算法”這樣的抽象來(lái)刻畫系統(tǒng)的本質(zhì)特征,研究計(jì)算系統(tǒng)往往需要原型系統(tǒng)構(gòu)建和基準(zhǔn)程序測(cè)試.
算法這個(gè)抽象具備哪些特點(diǎn)呢?算法不同于程序,它是程序的簡(jiǎn)潔描述,體現(xiàn)了程序的本質(zhì)特征.Donald Knuth給出了算法的一般定義[3].
定義1.五特征算法定義[3].算法是一組有窮的規(guī)則,給出求解特定類型問(wèn)題的運(yùn)算序列,并具備下列5個(gè)特征:
1) 有窮性.一個(gè)算法在有限步驟之后必然要終止.
2) 確定性.一個(gè)算法的每個(gè)步驟都必須精確地(嚴(yán)格地和無(wú)歧義地)定義.
3) 輸入.一個(gè)算法有零個(gè)或多個(gè)輸入.
4) 輸出.一個(gè)算法有一個(gè)或多個(gè)輸出.
5) 能行性.一個(gè)算法的所有運(yùn)算必須是充分基本的,原則上人們用筆和紙可以在有限時(shí)間內(nèi)精確地完成它們.
定義1使得任何算法實(shí)例具備7個(gè)優(yōu)點(diǎn),我們可從算法概念本身和快速排序算法實(shí)例角度進(jìn)一步說(shuō)明.
1) 通用性.任何算法實(shí)例,不論是快速排序(quicksort)、高斯消元解方程、求最短路徑的Dijkstra算法,還是任何串行算法、并行算法、分布式算法,都滿足Donald Knuth的五特征算法定義.
2) 易描述.算法比實(shí)現(xiàn)該算法的程序往往簡(jiǎn)潔得多,例如幾行偽代碼足以精確描述quicksort算法.
3) 易理解.簡(jiǎn)潔描述特性也使得理解算法更容易,例如quicksort算法的基本邏輯與特色訣竅很容易被理解.
4) 可分析.quicksort算法的時(shí)間復(fù)雜度、空間復(fù)雜度可被嚴(yán)格地分析出來(lái).
5) 可證明.可嚴(yán)格地證明quicksort算法的正確性、復(fù)雜度和適用范圍.
6) 抽象性.算法不依賴于具體實(shí)現(xiàn)技術(shù)(硬件及軟件),包括已有技術(shù)和未來(lái)的技術(shù),英文稱這個(gè)特性為technology-proof和future-proof.
7) 可重復(fù).有了上述6條優(yōu)點(diǎn),算法本身和算法的研究結(jié)果具備可重復(fù)性(reproducibility),即他人可復(fù)制、可復(fù)現(xiàn)和可重用,這是任何科學(xué)方法的本質(zhì)特征.
上述7條優(yōu)點(diǎn)中,最重要的是可分析抽象.計(jì)算系統(tǒng)研究需要能夠簡(jiǎn)潔刻畫計(jì)算系統(tǒng)本質(zhì)特征的可分析抽象,使其具備算法的上述7條優(yōu)點(diǎn),能夠超越原型系統(tǒng)構(gòu)建和基準(zhǔn)程序測(cè)試,提升系統(tǒng)研究的效率.
超越原型測(cè)試并不是不要原型測(cè)試.原型測(cè)試仍將是計(jì)算系統(tǒng)研究的重要方法.可分析抽象可用在多種系統(tǒng)設(shè)計(jì)選擇中、多次系統(tǒng)設(shè)計(jì)迭代中,在原型測(cè)試之前,篩掉不合適的候選系統(tǒng),優(yōu)選剩下的設(shè)計(jì),再采用原型測(cè)試驗(yàn)證優(yōu)化.
計(jì)算系統(tǒng)可分析抽象的相關(guān)研究已有數(shù)十年歷史,本節(jié)討論了6類研究工作并總結(jié)了歷史經(jīng)驗(yàn).
1) Jim Gray在1999年的圖靈獎(jiǎng)獲獎(jiǎng)演說(shuō)中提出了未來(lái)計(jì)算機(jī)科學(xué)技術(shù)的12個(gè)挑戰(zhàn)難題[4],其中最后一個(gè)稱為“自動(dòng)程序員”(automatic programmer)難題,即計(jì)算系統(tǒng)應(yīng)該提供高效編程接口,使得設(shè)計(jì)應(yīng)用程序容易1 000倍.如果系統(tǒng)缺乏可分析抽象,很難想象可以實(shí)現(xiàn)應(yīng)用設(shè)計(jì)容易1 000倍的目標(biāo).
2) Leslie Lamport指出:這樣的可分析抽象,即刻畫系統(tǒng)本質(zhì)特征的高級(jí)設(shè)計(jì),是存在的[5].他引用了Tony Hoare的觀點(diǎn):“Inside every large program, there is a small program trying to get out”,其中small program是刻畫該large program本質(zhì)特征的算法,也稱為specification或high level design.Lamport開發(fā)了TLA+工具,可用于描述串行和并發(fā)系統(tǒng),并對(duì)其性質(zhì)做自動(dòng)模型檢測(cè)[6].
3) John Hennessy與David Patterson因提出計(jì)算系統(tǒng)的量化設(shè)計(jì)方法獲圖靈獎(jiǎng).在回顧其量化設(shè)計(jì)方法時(shí),Hennessy指出,處理器系統(tǒng)的CPI公式是量化設(shè)計(jì)方法的重要?jiǎng)?chuàng)新點(diǎn)[7].
事實(shí)上,這個(gè)公式既簡(jiǎn)潔又實(shí)用.例如,僅用一個(gè)指標(biāo)CPI(clocks per instruction)就能區(qū)分出不同的指令集體系結(jié)構(gòu).CPI>1(即執(zhí)行一條指令需要多于一拍時(shí)鐘)對(duì)應(yīng)著CISC體系結(jié)構(gòu);CPI=1對(duì)應(yīng)著RISC體系結(jié)構(gòu);CPI<1對(duì)應(yīng)著超標(biāo)量(superscalar)體系結(jié)構(gòu).
4) 系統(tǒng)的性質(zhì)不都是定量的,也有重要的定性性質(zhì),例如分布式系統(tǒng)的CAP定理:一個(gè)分布式系統(tǒng)能夠且僅能夠滿足一致性(consistency)、可用性(availability)、分區(qū)容錯(cuò)性(partition tolerance)三條性質(zhì)中的2條[8].CAP定理揭示了分布式系統(tǒng)的一種本質(zhì)的不可能性.這個(gè)貌似負(fù)面的定性結(jié)果被廣泛應(yīng)用于今天的云計(jì)算系統(tǒng)、大數(shù)據(jù)系統(tǒng)、互聯(lián)網(wǎng)服務(wù)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)中.
5) 針對(duì)并行計(jì)算系統(tǒng),Leslie Valliant提出了Bulk-Synchronous Parellel(BSP)模型[9].借鑒串行計(jì)算機(jī)的馮·諾依曼模型經(jīng)驗(yàn),BSP提供了一個(gè)并行計(jì)算機(jī)的簡(jiǎn)潔抽象模型,應(yīng)用算法研究者不用關(guān)心多種多樣的真實(shí)并行計(jì)算系統(tǒng),而是針對(duì)簡(jiǎn)潔唯一的BSP抽象模型研究并行算法.Valliant證明,不少典型并行算法,當(dāng)從BSP過(guò)渡到真實(shí)并行計(jì)算機(jī)上時(shí),映射開銷為O(1).這種在應(yīng)用算法和真實(shí)計(jì)算系統(tǒng)之間提供一個(gè)簡(jiǎn)潔抽象模型的思路稱為橋接模型(bridging model).今天,BSP已經(jīng)成為很多真實(shí)的并行計(jì)算、云計(jì)算、大數(shù)據(jù)系統(tǒng)支持的典型計(jì)算系統(tǒng)模式.
6) 針對(duì)萬(wàn)維網(wǎng),Roy Fielding提出了表象狀態(tài)轉(zhuǎn)移(representational state transfer, REST)體系結(jié)構(gòu)風(fēng)格[10],支撐了近20年的PC互聯(lián)網(wǎng)與移動(dòng)互聯(lián)網(wǎng)應(yīng)用.REST給出了一類系統(tǒng)抽象,即“體系結(jié)構(gòu)風(fēng)格”(也稱為架構(gòu)風(fēng)格):architectural style—an abstraction across many specific application architectures[11].體系結(jié)構(gòu)風(fēng)格的核心是一組體系結(jié)構(gòu)設(shè)計(jì)原則,又稱為體系結(jié)構(gòu)約束(architectural constraints).例如REST提出了統(tǒng)一界面(uniform interface)、無(wú)狀態(tài)通信(stateless communication)等6條原則.不同的桌面瀏覽器系統(tǒng)、移動(dòng)瀏覽器系統(tǒng)、安卓APP系統(tǒng)、各種WWW服務(wù)器系統(tǒng)都遵循這6條REST體系結(jié)構(gòu)設(shè)計(jì)原則.
上述研究提供了計(jì)算系統(tǒng)抽象的6條成功經(jīng)驗(yàn).它們表明,未來(lái)計(jì)算系統(tǒng)抽象應(yīng)該考慮6個(gè)研究方向和目標(biāo):1)高效接口,使得應(yīng)用設(shè)計(jì)容易1 000倍;2)刻畫系統(tǒng)本質(zhì)特征的高級(jí)設(shè)計(jì),揭示出大而復(fù)雜的系統(tǒng)中的小而簡(jiǎn)潔的可分析抽象,即the small program trying to get out;3)刻畫系統(tǒng)本質(zhì)特征的定量公式;4)刻畫系統(tǒng)本質(zhì)特征的定性定理;5)真實(shí)應(yīng)用算法與真實(shí)計(jì)算系統(tǒng)之間的橋接抽象模型;6)覆蓋多種真實(shí)系統(tǒng)結(jié)構(gòu)的體系結(jié)構(gòu)風(fēng)格.
研究算禮的目的是提煉出能夠簡(jiǎn)潔刻畫計(jì)算系統(tǒng)本質(zhì)特征的可分析抽象,使得計(jì)算系統(tǒng)研究具備算法研究的7條優(yōu)點(diǎn).那么,從直覺上看,算禮應(yīng)該具備什么新性質(zhì),為什么不沿用“算法”或“計(jì)算模型”這些名稱,而是要使用一個(gè)新詞呢?
Fig. 1 Comparison among arithmetic, algorithm, and computation protocol圖1 算術(shù)、算法、算禮之比較
1) 算禮不是算法.圖1顯示了算禮與算術(shù)和算法的區(qū)別.算術(shù)關(guān)注特定數(shù)值的加減乘除四則運(yùn)算.算法關(guān)注給定輸入數(shù)據(jù),能夠求出期望的輸出數(shù)據(jù)的計(jì)算方法,尤其是時(shí)間復(fù)雜度/空間復(fù)雜度較低的有效方法.算禮關(guān)注計(jì)算系統(tǒng)的簡(jiǎn)潔刻畫.一個(gè)算禮上可運(yùn)行多個(gè)算法.例如圖1中的Spark機(jī)群可用一個(gè)算禮刻畫,它可以支持快速排序、k-means聚類等多種算法.給定一個(gè)算法,從給定輸入可求出期望的輸出結(jié)果.給定一個(gè)算禮,從給定算法和給定輸入,才可能求出期望的輸出結(jié)果.
2) 算禮不等于傳統(tǒng)的計(jì)算模型.在計(jì)算機(jī)科學(xué)界,計(jì)算模型(models of computation)已有特定的定義[12-13],主要關(guān)注各種圖靈機(jī)、PRAM、I/O自動(dòng)機(jī)等串行、并行和分布式計(jì)算模型,這些模型難以刻畫Spark機(jī)群等計(jì)算系統(tǒng)的本質(zhì)特征,也難以刻畫人機(jī)物三元計(jì)算系統(tǒng)的本質(zhì)特征.我們可以稍微修改下Tony Hoare的觀點(diǎn),得到:“Inside every large system, there is a small protocol trying to get out.”這個(gè)“small protocol”就是該“l(fā)arge system”的算禮.簡(jiǎn)言之,算禮概念與計(jì)算模型有交叉,但不完全等同.
4) 算禮(computation protocol)之禮不是comm-unication protocol之protocol(協(xié)議),而是更像自然科學(xué)期刊《Nature Protocols》之scientific protocol,強(qiáng)調(diào)他人可復(fù)制的構(gòu)造性科學(xué)方法、他人可復(fù)制可重現(xiàn)可重用的系統(tǒng)抽象.
我們學(xué)習(xí)Donald Knuth的五特征算法定義,給出算禮的一般表述(稱為PEN刻畫).
定義2.算禮.算禮是一組有窮的規(guī)則,給出求解特定類型問(wèn)題的計(jì)算系統(tǒng),并具備下列4個(gè)特征.
1) 負(fù)載(payload, P):算禮支持的應(yīng)用負(fù)載類型.
2) 執(zhí)行模型(execution model, E):連接資源的體系結(jié)構(gòu),說(shuō)明負(fù)載在資源上如何執(zhí)行.
3) 賦名資源(named abstractions of resources, N):對(duì)負(fù)載和執(zhí)行模型可消耗的資源的明確命名與抽象.
4) 可重復(fù)性(reproducibility):給定算禮的PEN刻畫,他人可重現(xiàn)系統(tǒng)與結(jié)果.
算禮有白箱表示和黑箱表示.黑箱表示主要涉及P,白箱表示涉及PEN三者,如圖2所示.Payload除了算法和數(shù)據(jù)這些workload之外,還包含5個(gè)具體的P,即problem,principle,properties,programming model,policies,他們與workload一起共同刻畫了payload需求.算禮的黑箱表示主要關(guān)注problem,principle,properties,隱藏了PEN的其他內(nèi)容.
Fig. 2 The black-box representation and white-box representation of computation protocol圖2 算禮的黑箱表示與白箱表示
任何系統(tǒng)都是被設(shè)計(jì)用來(lái)有效支持一類負(fù)載的.它的算禮針對(duì)該負(fù)載的特有問(wèn)題(problem),提出解決該問(wèn)題的特有的原理(principle),凸顯期望的計(jì)算性質(zhì)(properties).
隨著科學(xué)技術(shù)的快速發(fā)展,人們的生活方式、學(xué)習(xí)方式、娛樂(lè)方式等都發(fā)生了翻天覆地的變化,同時(shí)各國(guó)之間的利益關(guān)系也變得微妙起來(lái),尤其是發(fā)展中國(guó)家的快速發(fā)展更是對(duì)國(guó)際力量產(chǎn)生了重要影響。與此同時(shí),中國(guó)面臨的國(guó)際形勢(shì)越發(fā)嚴(yán)峻。另一方面,我國(guó)仍處于社會(huì)主義初級(jí)階段,這是我國(guó)最大的國(guó)情,距離實(shí)現(xiàn)中華民族偉大復(fù)興還有很長(zhǎng)的一段路要走。在這樣的環(huán)境下,中國(guó)共產(chǎn)黨保持黨的先進(jìn)性,領(lǐng)導(dǎo)中國(guó)人民走向共同富裕、民族復(fù)興成為重要內(nèi)容,所以,重視黨的建設(shè)成為新時(shí)期中國(guó)共產(chǎn)黨的關(guān)鍵任務(wù)。[2]
例如大數(shù)據(jù)應(yīng)用框架Spark的設(shè)計(jì)初衷是針對(duì)MapReduce等應(yīng)用框架不能有效“重用多級(jí)計(jì)算的中間結(jié)果”(reuse intermediate results across multiple computations)的問(wèn)題[14].MapReduce也可以重用多級(jí)計(jì)算間的中間結(jié)果,但比較低效,其原因有2個(gè):1)中間結(jié)果需要存盤;2)為了容錯(cuò),數(shù)據(jù)需要復(fù)制.Spark解決這個(gè)低效問(wèn)題的原理是“內(nèi)存計(jì)算”(in-memory computing).Spark將數(shù)據(jù)和中間結(jié)果放在一種創(chuàng)新的內(nèi)存數(shù)據(jù)抽象RDDs(resilient distributed datasets)中,并通過(guò)粗粒度的RDD transformation以及l(fā)ineage機(jī)制實(shí)現(xiàn)容錯(cuò)計(jì)算.
Spark算禮具備3個(gè)性質(zhì):1)大多數(shù)情況下,數(shù)據(jù)的存儲(chǔ)和計(jì)算發(fā)生在處理器和內(nèi)存中,不涉及硬盤;2)特別地,多個(gè)RDD transformations的中間結(jié)果存放在內(nèi)存中,不用存盤,從而通過(guò)內(nèi)存計(jì)算支持了多級(jí)計(jì)算;3)容錯(cuò)不是靠多副本,而采用lineage機(jī)制,出錯(cuò)時(shí)重算,消除了復(fù)制開銷.
算禮的白箱模型暴露的PEN的全部,也稱為算禮的PEN模型.
定義3.算禮的PEN模型.一個(gè)算禮是三元組(負(fù)載,執(zhí)行模型,賦名資源)=(P,E,N),說(shuō)明如何利用賦名資源執(zhí)行負(fù)載的系統(tǒng)組成和執(zhí)行規(guī)則.三元組的含義說(shuō)明為:
1) P是負(fù)載(payload),或者說(shuō)是workloads,說(shuō)明算禮適用的負(fù)載類型,包括支持的(和不支持的)負(fù)載.Payload還包括problem,principle,properties,programming model,policies五個(gè)更加具體的P.例如,MapReduce系統(tǒng)(MR算禮)主要支持批處理類負(fù)載,而不是交互式負(fù)載.MR算禮提供分布式系統(tǒng)的MapReduce函數(shù)式編程模型[15].
2) E是執(zhí)行模型(execution model),即連接并組合賦名資源去實(shí)現(xiàn)負(fù)載的體系結(jié)構(gòu)和任務(wù)執(zhí)行方式.例如,MR算禮在機(jī)群上提供job,tasks的master-slave architecture,以及map-shuffle-reduce三階段執(zhí)行方式.
3) N是賦名資源(named abstractions of resources),為算禮提供模塊化的賦名資源和抽象接口.例如,MR算禮提供了機(jī)群節(jié)點(diǎn)資源抽象和HDFS分布式文件系統(tǒng)資源抽象.
云計(jì)算系統(tǒng)中各類無(wú)序現(xiàn)象(稱為計(jì)算系統(tǒng)熵),使得用戶體驗(yàn)和系統(tǒng)效率2個(gè)目標(biāo)難以被同時(shí)滿足.我們提出下一代云計(jì)算系統(tǒng)的目標(biāo),稱為“低熵云計(jì)算系統(tǒng)”[16],要求多個(gè)應(yīng)用負(fù)載在數(shù)據(jù)中心計(jì)算機(jī)上執(zhí)行時(shí),既能保證用戶體驗(yàn),又能提高系統(tǒng)利用率.
能否抽象出低熵云計(jì)算系統(tǒng)的主要性質(zhì)?具備什么能力的系統(tǒng)才能同時(shí)滿足用戶體驗(yàn)和系統(tǒng)效率2個(gè)目標(biāo)?為此,我們定義了“實(shí)用可計(jì)算性”(pro-duction computability)來(lái)刻畫系統(tǒng)實(shí)現(xiàn)用戶體驗(yàn)和提高系統(tǒng)效率的能力,并提出了實(shí)現(xiàn)“實(shí)用可計(jì)算性”的充分必要條件的猜想,稱為DIP(distinguishing, isolation, prioritizing)猜想.從算禮的黑箱表示看,低熵云計(jì)算系統(tǒng)需要考慮3個(gè)難題.
1) Problem:低熵云計(jì)算系統(tǒng)應(yīng)該解決什么問(wèn)題?
對(duì)于傳統(tǒng)的資源獨(dú)占式分區(qū)云和共享式的虛擬化云,前者能很好實(shí)現(xiàn)負(fù)載的用戶體驗(yàn),但是系統(tǒng)效率較低;后者理論上支持更高的系統(tǒng)效率,但是卻影響了特定負(fù)載的用戶體驗(yàn)?zāi)繕?biāo).
我們認(rèn)為“難以同時(shí)滿足用戶體驗(yàn)和系統(tǒng)效率”難題的本質(zhì)是無(wú)序現(xiàn)象.特別地,針對(duì)負(fù)載干擾的無(wú)序現(xiàn)象,由于共享資源的競(jìng)爭(zhēng)導(dǎo)致了系統(tǒng)的內(nèi)耗,資源的共享呈現(xiàn)互相的抑制和搶占,既影響了負(fù)載的資源保證,也會(huì)降低系統(tǒng)的效率.
所以,低熵云計(jì)算的主要問(wèn)題是“在共享式的云計(jì)算系統(tǒng)中,如何實(shí)現(xiàn)應(yīng)用負(fù)載間的有序共享(減小干擾造成的無(wú)序影響),在保障特定負(fù)載的用戶體驗(yàn)的基礎(chǔ)上,提高系統(tǒng)效率”.
2) Principle:解決這些問(wèn)題主要原理是什么?
云計(jì)算系統(tǒng)需要克服無(wú)序性影響,保障負(fù)載的用戶體驗(yàn)的基礎(chǔ)上,提高系統(tǒng)效率.顯然,這不只是特定負(fù)載有關(guān)的性質(zhì),而是云計(jì)算系統(tǒng)本身的能力:使得負(fù)載之間有序共享資源的能力.
我們不妨將云計(jì)算系統(tǒng)中的共享資源(時(shí)間資源、計(jì)算資源、存儲(chǔ)資源和通信資源)組成一個(gè)四維空間,稱為計(jì)算時(shí)空(cyberspacetime).那么,降低計(jì)算系統(tǒng)熵,或者實(shí)現(xiàn)負(fù)載的實(shí)用可計(jì)算性的主要原理是時(shí)空共享,即多個(gè)負(fù)載在總線周期粒度有序地共享計(jì)算時(shí)空,有利于同時(shí)保障用戶體驗(yàn)和資源利用率.
3) Properties:低熵云計(jì)算系統(tǒng)具備什么新的性質(zhì)才能實(shí)現(xiàn)計(jì)算時(shí)空的有序共享?
我們提出了實(shí)現(xiàn)實(shí)用可計(jì)算性的充分必要條件的猜想,稱為DIP猜想:如果應(yīng)用負(fù)載A是實(shí)用可計(jì)算的,那么在給定用戶體驗(yàn)閾值的前提下,云計(jì)算系統(tǒng)S實(shí)現(xiàn)A的實(shí)用可計(jì)算性,當(dāng)且僅當(dāng)S具備DIP能力.
這3點(diǎn)能力是:區(qū)分(distinguishing, D)、隔離(isolation, I)、優(yōu)先化(prioritizing, P).也就是說(shuō),該云計(jì)算系統(tǒng)能夠在運(yùn)行時(shí)動(dòng)態(tài)地區(qū)分、隔離、優(yōu)先化負(fù)載A在系統(tǒng)S的計(jì)算時(shí)空中執(zhí)行的相空間.云計(jì)算系統(tǒng)具備的3點(diǎn)能力,亦可作為系統(tǒng)的3個(gè)性質(zhì),即可區(qū)分性、可隔離性、可優(yōu)先化性.
這3個(gè)性質(zhì)的本質(zhì)是限制云計(jì)算系統(tǒng)中的無(wú)序影響.無(wú)序行為會(huì)一直存在,無(wú)法徹底消除.但通過(guò)系統(tǒng)創(chuàng)新限制住無(wú)序的影響范圍,從而使計(jì)算任務(wù)的尾延遲滿足用戶體驗(yàn)閾值,還是有可能的.
我們提出了分形馮·諾依曼體系結(jié)構(gòu)[17],一種同構(gòu)、串行編程、層次化且層次同性的新體系結(jié)構(gòu).實(shí)驗(yàn)表明,具有分形馮·諾依曼體系結(jié)構(gòu)的計(jì)算機(jī)Cambricon-F在機(jī)器學(xué)習(xí)領(lǐng)域能夠解決編程難題,同時(shí)性能不弱于目前最先進(jìn)的GPU系統(tǒng).但是Cambricon-F僅針對(duì)特定領(lǐng)域應(yīng)用負(fù)載、采用了特定的體系結(jié)構(gòu).我們能否拓展分形馮·諾依曼體系結(jié)構(gòu)的原理,使它能夠解決通用領(lǐng)域、廣泛的現(xiàn)有體系結(jié)構(gòu)上的編程難題呢?我們通過(guò)提出一種新的并行計(jì)算模型“分形計(jì)算模型”來(lái)實(shí)現(xiàn)這一目標(biāo),而算禮思想要求我們首先回答黑箱表述的3個(gè)難題分別是什么.
1) Problem:需要解決的“編程難題”究竟是什么?
目前并行計(jì)算模型既有注重于算法分析的理論模型(例如BSP[9],Multi-BSP[18],LogP[19],PRAM[20]),又有注重于編程實(shí)現(xiàn)的實(shí)用模型(例如MPI[21],OpenMP[22]).然而,現(xiàn)有通用并行計(jì)算模型都是并行編程、并行執(zhí)行(parallel code, parallel execution, PCPE)的.通常我們認(rèn)為并行編程比串行編程更為困難,因?yàn)椴⑿芯幊绦枰~外考慮多條執(zhí)行流之間的同步、通信等問(wèn)題.
為了簡(jiǎn)化編程,我們需要實(shí)現(xiàn)串行編程、并行執(zhí)行(sequential code, parallel execution, SCPE)——使用者只編寫串行執(zhí)行的程序,卻可以并行、高效地執(zhí)行在并行計(jì)算系統(tǒng)上.如果在分形計(jì)算模型上,編程與系統(tǒng)的規(guī)模無(wú)關(guān),那么無(wú)論系統(tǒng)的規(guī)模如何,其編程都與在規(guī)模最小的系統(tǒng)(即僅具有單一計(jì)算節(jié)點(diǎn)的串行系統(tǒng))上同樣簡(jiǎn)單,即可實(shí)現(xiàn)SCPE.
并行編程的復(fù)雜性,本質(zhì)來(lái)源于并行計(jì)算模型具有的編程-規(guī)模相關(guān)性(programming-scale variance):當(dāng)系統(tǒng)規(guī)模發(fā)生變化時(shí),程序需要重新調(diào)整才可保持最優(yōu)地執(zhí)行.因此,難題是如何設(shè)計(jì)分形計(jì)算模型,使其具有編程-規(guī)模無(wú)關(guān)性(programming-scale invariance).
2) Principle:解決問(wèn)題的主要原理是什么?
分形計(jì)算模型解決問(wèn)題的主要原理與分形馮·諾依曼體系結(jié)構(gòu)相同,都是通過(guò)將系統(tǒng)刻畫為層次同性(isostratal)的層次結(jié)構(gòu),使系統(tǒng)在不同尺度上具有相同形式的硬件資源抽象、任務(wù)負(fù)載抽象和執(zhí)行行為抽象,因此可以做到根據(jù)單一層次結(jié)構(gòu)的刻畫對(duì)系統(tǒng)規(guī)模進(jìn)行任意的擴(kuò)展.
3) Properties:我們希望分形計(jì)算模型具備什么新的性質(zhì)?
通用性.我們希望分形計(jì)算模型是一種具有通用性的并行計(jì)算模型,即能夠廣泛、高效地支持各種可以并行計(jì)算的算法.
效率-規(guī)模無(wú)關(guān)性.我們希望分形計(jì)算模型的效率不會(huì)因系統(tǒng)規(guī)模擴(kuò)展而漸進(jìn)降低,只有如此,任意擴(kuò)展系統(tǒng)規(guī)模才具有實(shí)用意義.
編程-規(guī)模無(wú)關(guān)性.分形計(jì)算模型是一種串行編程、并行執(zhí)行的計(jì)算模型,用戶無(wú)需編寫并行程序,即可由分形計(jì)算模型自動(dòng)地展開至任意規(guī)模的系統(tǒng)上并行執(zhí)行.
REST體系結(jié)構(gòu)風(fēng)格支撐了PC互聯(lián)網(wǎng)與移動(dòng)互聯(lián)網(wǎng)應(yīng)用.能夠進(jìn)一步將REST拓展到智能萬(wàn)物互聯(lián)網(wǎng)嗎?我們的回答是肯定的,并將拓展后的體系結(jié)構(gòu)風(fēng)格稱為T-REST(representational state transfer for things)[23],如圖3所示.從算禮的黑箱表示看,T-REST需要考慮3個(gè)難題.
Fig. 3 Transition from PC Internet to mobile Internet only needs to inherit REST; Transition from mobile Internet to IoE needs to extend REST圖3 從PC互聯(lián)網(wǎng)過(guò)渡到移動(dòng)互聯(lián)網(wǎng)只需繼承REST;再過(guò)渡到智能萬(wàn)物互聯(lián)網(wǎng)需要拓展REST
1) Problem:T-REST架構(gòu)風(fēng)格應(yīng)該解決什么問(wèn)題?
我們的研究表明,主要問(wèn)題是:“物端設(shè)備應(yīng)該是WWW客戶端還是WWW服務(wù)器端”這個(gè)client vs. server問(wèn)題.當(dāng)PC互聯(lián)網(wǎng)過(guò)渡到移動(dòng)互聯(lián)網(wǎng)時(shí),智能手機(jī)繼承了REST Web,主要思路是將PC上的WWW瀏覽器適配到智能手機(jī)的WWW瀏覽器和APP.這是合理的選擇,因?yàn)镻C機(jī)和智能手機(jī)都是人端設(shè)備,主要與人交互.但是,在智能萬(wàn)物互聯(lián)網(wǎng)中,物端設(shè)備(不論是固定的還是移動(dòng)的)主要與物理世界交互,包括傳感(sensing)與致動(dòng)(actuating).物端設(shè)備是數(shù)據(jù)源和制動(dòng)器,這是服務(wù)端的特征.物端設(shè)備主要是server,而不是像PC機(jī)或智能手機(jī)那樣的Web client.因此,難題是如何將原本在云端的WWW服務(wù)能力有效遷移到物端設(shè)備.
2) Principle:解決這些問(wèn)題的主要原理是什么?
T-REST的核心原理是將超文本(hypertext)和超媒體(hypermedia)拓展為超任務(wù)(hypertask),提供服務(wù)端按需代碼(server-side code on demand)能力.
3) Properties:T-REST體系結(jié)構(gòu)風(fēng)格具備什么新的性質(zhì)?
T-REST主要有2個(gè)性質(zhì),即2種新的體系結(jié)構(gòu)原則,即計(jì)算超文本(computational HyperText, cHT)和可復(fù)用遠(yuǎn)端求值(reusable remote evalua-tion, RREV),它們合起來(lái)提供服務(wù)側(cè)按需代碼(server-side code on demand)能力[23].
計(jì)算超文本原則.我們提出一種具體的新概念,稱為計(jì)算超文本,去實(shí)現(xiàn)超任務(wù).超任務(wù)就像超文本(hypertext)和超媒體(hypermedia)一樣,也由URI超鏈接指向,通過(guò)傳統(tǒng)的REST協(xié)議調(diào)用.引入超任務(wù)不違反“hypermedia as the engine of application state”的REST基本原則,但將超媒體的內(nèi)涵從數(shù)據(jù)內(nèi)容拓展到了任務(wù)代碼.
可復(fù)用遠(yuǎn)端求值原則.一旦一個(gè)超任務(wù)被成功部署到某個(gè)云端或邊緣端設(shè)備上,它就自動(dòng)變成了一個(gè)Web資源和Web服務(wù).該服務(wù)不是一次性的,而是具有持續(xù)復(fù)用的特點(diǎn).例如執(zhí)行HTTP方法“PUT http://edge.things.ac.cn/recognition_result recognize.cht”將超任務(wù)recognize.cht部署到邊緣服務(wù)器edge上,并自動(dòng)生成一個(gè)全球可訪問(wèn)的RESTful資源與服務(wù),其URI為http://edge.things.ac.cn/recognition_result.
物端設(shè)備通常是資源受限的計(jì)算系統(tǒng),在評(píng)價(jià)物端計(jì)算系統(tǒng)性能時(shí),不能僅考慮基準(zhǔn)程序的執(zhí)行性能,還需要考慮每類負(fù)載對(duì)物端計(jì)算系統(tǒng)的資源利用效率.為此,我們提出了資源服務(wù)效率(resource serve efficiency, RSE)匹配模型和歸一化的匹配度量,用于評(píng)價(jià)物端計(jì)算系統(tǒng)性能.從算禮的黑箱表示看,RSE匹配模型需要考慮3個(gè)難題.
1) Problem:RSE匹配模型需要反映的性能指標(biāo)具體是什么?
傳統(tǒng)的計(jì)算系統(tǒng)性能評(píng)價(jià)方式是將每個(gè)基準(zhǔn)程序的測(cè)試結(jié)果進(jìn)行幾何平均得到系統(tǒng)性能的量化指標(biāo).而設(shè)計(jì)物端計(jì)算系統(tǒng)時(shí),在保證特定負(fù)載的執(zhí)行性能的同時(shí),還會(huì)考慮盡量減少負(fù)載對(duì)資源的占用,則物端計(jì)算系統(tǒng)的評(píng)價(jià)方法也應(yīng)該將資源利用效率考慮至性能評(píng)價(jià)模型中.因此,難題是如何使用一個(gè)量化指標(biāo)同時(shí)反映負(fù)載執(zhí)行性能和系統(tǒng)資源利用效率.
2) Principle:解決問(wèn)題的主要原理是什么?
RSE匹配模型解決問(wèn)題的主要原理是使用“木桶原理”對(duì)每個(gè)資源針對(duì)負(fù)載的服務(wù)效率進(jìn)行加權(quán)平均,從而獲得系統(tǒng)-負(fù)載的匹配度量化指標(biāo).資源服務(wù)效率即為單個(gè)資源在不同利用率下負(fù)載執(zhí)行性能曲線的積分;“木桶原理”的量化表達(dá)即為匹配度較低的資源代表系統(tǒng)的性能瓶頸,則其對(duì)系統(tǒng)-負(fù)載的匹配度應(yīng)占有更高的計(jì)算權(quán)重,反之亦然.
3) Propertie:RSE匹配模型具備什么性質(zhì)?
歸一化的性能度量.RES匹配模型提供的系統(tǒng)-負(fù)載的匹配度指標(biāo)以及每個(gè)系統(tǒng)資源分量的匹配度指標(biāo)均是歸一化的形式.歸一化的性能量化指標(biāo)為物端計(jì)算系統(tǒng)提供橫向比較的基準(zhǔn),同時(shí)也為系統(tǒng)和負(fù)載性能優(yōu)化給出了理論的性能優(yōu)化上界.
反映系統(tǒng)性能瓶頸.負(fù)載和系統(tǒng)的匹配度指標(biāo)可以對(duì)系統(tǒng)性能進(jìn)行整體量化,而每個(gè)系統(tǒng)資源分量的匹配度指標(biāo)則可以揭示出針對(duì)特定評(píng)測(cè)程序系統(tǒng)存在的性能瓶頸,為系統(tǒng)和負(fù)載性能優(yōu)化提供方向.
我們?cè)谥悄芫W(wǎng)聯(lián)車計(jì)算系統(tǒng)基準(zhǔn)測(cè)試程序集CAVBench[24]中提出了RSE匹配模型一種具體的量化計(jì)算公式,使用該計(jì)算公式本文給出一個(gè)具體的優(yōu)化實(shí)例:在物端計(jì)算系統(tǒng)Intel FRD[25]上使用深度學(xué)習(xí)框架TensorFlow1.12運(yùn)行目標(biāo)檢測(cè)算法SSD[26],得到系統(tǒng)的CPU利用率、內(nèi)存帶寬、內(nèi)存腳跡資源與負(fù)載的匹配度分別為0.08,0.14和0.23,計(jì)算可得該系統(tǒng)與SSD負(fù)載的匹配度為0.15,負(fù)載實(shí)際執(zhí)行性能為2.5 FPS;RSE模型指出了CPU資源為該系統(tǒng)在執(zhí)行SSD負(fù)載時(shí)的性能瓶頸,則使用TensorFlow的SIMD指令編譯優(yōu)化,優(yōu)化后CPU利用率、內(nèi)存帶寬、內(nèi)存腳跡資源匹配度分別為0.18,0.22和0.38,系統(tǒng)與SSD負(fù)載的匹配度則提高至0.25,SSD負(fù)載實(shí)際執(zhí)行性能提高至4 FPS.
針對(duì)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)領(lǐng)域的多樣性趨勢(shì)和挑戰(zhàn),本文指出需要研究計(jì)算系統(tǒng)的可分析抽象,即在原型測(cè)試前就能分析出計(jì)算系統(tǒng)本質(zhì)特征的學(xué)術(shù)抽象.針對(duì)計(jì)算系統(tǒng)可分析抽象,本文歸納3個(gè)初步結(jié)論.
1) 繼承算法的7條優(yōu)點(diǎn).本文回顧了Donald Knuth的五特征算法定義及其帶來(lái)的算法的7條優(yōu)點(diǎn),并倡導(dǎo)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)領(lǐng)域應(yīng)該學(xué)習(xí)算法領(lǐng)域的成功經(jīng)驗(yàn),研究計(jì)算機(jī)科學(xué)的一個(gè)新概念:算禮.算禮是簡(jiǎn)潔刻畫計(jì)算系統(tǒng)本質(zhì)特征的可分析抽象,其目標(biāo)是使得計(jì)算系統(tǒng)研究具備算法的7條優(yōu)點(diǎn),能夠超越原型系統(tǒng)構(gòu)建和基準(zhǔn)程序測(cè)試,提升計(jì)算系統(tǒng)研究的效率.
2) 學(xué)習(xí)系統(tǒng)研究的6條經(jīng)驗(yàn).本文總結(jié)了6條歷史經(jīng)驗(yàn),它們建議了計(jì)算系統(tǒng)抽象應(yīng)該考慮的研究方向和目標(biāo):①高效接口,使得應(yīng)用設(shè)計(jì)容易1 000倍;②刻畫系統(tǒng)本質(zhì)特征的高級(jí)設(shè)計(jì),尤其是對(duì)Tony Hoare觀點(diǎn)的修改:Inside every large com-puting system, there is a small computation protocol trying to get out;③刻畫系統(tǒng)本質(zhì)特征的定量公式;④刻畫系統(tǒng)本質(zhì)特征的定性定理;⑤真實(shí)應(yīng)用與真實(shí)系統(tǒng)之間的橋接抽象模型;⑥覆蓋多種真實(shí)系統(tǒng)結(jié)構(gòu)的體系結(jié)構(gòu)風(fēng)格.
3) 以PEN刻畫為特點(diǎn)的算禮思想有助于啟發(fā)計(jì)算系統(tǒng)研究.本文提出了算禮的一個(gè)初步定義,即(負(fù)載,執(zhí)行模型,賦名資源)刻畫,簡(jiǎn)稱為PEN模型.一個(gè)算禮可由它所支持的應(yīng)用負(fù)載(payload)、執(zhí)行模型(execution model)、賦名資源(named abstr-actions of resources)三元組刻畫,并有只考慮P的黑箱表示以及考慮PEN全體的白箱表示.我們討論了4個(gè)算禮研究實(shí)例,即低熵云計(jì)算系統(tǒng)的DIP猜想、分形并行計(jì)算模型、萬(wàn)物互聯(lián)系統(tǒng)的T-REST架構(gòu)風(fēng)格、智能物端系統(tǒng)的性能匹配度模型.
這些實(shí)例和歷史經(jīng)驗(yàn)表明:與算法抽象相比,計(jì)算系統(tǒng)的可分析抽象研究還處于起步階段,有不少研究問(wèn)題和機(jī)會(huì);算禮思想有助于在計(jì)算系統(tǒng)領(lǐng)域啟發(fā)新的猜想、新的計(jì)算模型、新的架構(gòu)風(fēng)格、新的系統(tǒng)評(píng)價(jià)度量.