【正文】 ? 偶然發(fā)現(xiàn)此文章關(guān)于機(jī)器模型方面與我們的猜想很相象，除了“最底層小規(guī)模且對(duì)等”；間接堅(jiān)定了我們的信心 ? 沒(méi)有解決每個(gè)層次應(yīng)該提供什么樣的信息，只是同樣闡述“更高層提供更綜合的信息”的原則 ? 沒(méi)有提及每個(gè)層次的系統(tǒng)應(yīng)當(dāng)如何組織的問(wèn)題 ? 另一個(gè)相關(guān)研究：從網(wǎng)格信息提供的角度考慮問(wèn)題 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 任務(wù)模型之任務(wù)描述 ?對(duì)資源需求的描述 ? 對(duì)不同資源分別處理：將對(duì)各種資源的需求描述為一個(gè) N元組，按照順序進(jìn)行配對(duì)，如 處理器數(shù)目、處理器時(shí)間，內(nèi)存， I/O， IPC； N元組的順序也是一個(gè)考慮因素 ? 統(tǒng)一參數(shù)：將對(duì)不同資源的需求通過(guò)某些算法統(tǒng)一歸結(jié)為一個(gè)參數(shù)；如統(tǒng)一成處理器利用率等 ? 精確度與簡(jiǎn)單性的權(quán)衡 ?任務(wù)之間關(guān)系的描述 ? 已有經(jīng)驗(yàn)： LilyTask并行模型中的任務(wù)關(guān)系 ?待研究問(wèn)題 ? 提供什么樣的資源參數(shù)供任務(wù)進(jìn)行描述 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 對(duì)邏輯模型重要問(wèn)題的思考 ?子系統(tǒng)內(nèi)部的調(diào)度框架 ? 顯然，不同層次的各個(gè)子系統(tǒng)的調(diào)度策略應(yīng)當(dāng)不同 ? 可以提供若干有效的調(diào)度策略供子系統(tǒng)選擇 ? 對(duì)每個(gè)子系統(tǒng)，需要找到在它內(nèi)部最有效的調(diào)度策略 ? 可能最有效的調(diào)度策略與待處理的任務(wù)集相關(guān) ? 也許每個(gè)子系統(tǒng)中最有效的調(diào)度策略不止一個(gè) ? 需要進(jìn)一步的仔細(xì)研究 ?面向子系統(tǒng)的管理 ? 猜想：信息負(fù)責(zé)點(diǎn)分層連動(dòng)制 ? 在子系統(tǒng)內(nèi)部，信息點(diǎn)向信息負(fù)責(zé)點(diǎn)負(fù)責(zé) ? 信息負(fù)責(zé)點(diǎn)代表自己所在的子系統(tǒng)向上層系統(tǒng)負(fù)責(zé) ? 子系統(tǒng)首先在子系統(tǒng)內(nèi)部進(jìn)行任務(wù)處理，超出處理能力時(shí)通過(guò)信息負(fù)責(zé)點(diǎn)提交到上層系統(tǒng)處理 ? 有很多具體細(xì)節(jié)需要思考，如信息負(fù)責(zé)點(diǎn)如何形成等 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 子系統(tǒng)處理任務(wù)過(guò)程 [4] 第二部分：若干思路 NX1 NX2 NY1 NY2 NZ1 NZ2 NUx | CX NUy | CY NUz | CZ CU Z把通過(guò) CZ得到的 TIM在 Z內(nèi)部面向 NZi進(jìn)行處理 T1 T2 Z TIM 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 學(xué)界對(duì)管理模型的相關(guān)研究 ?還沒(méi)有一個(gè)針對(duì)大規(guī)模的，可能具有計(jì)算能力異構(gòu)性質(zhì)的、多層并行性的集群系統(tǒng)的完善的邏輯模型和性能模型 ? 考察 IEEE TPDS近 5年的文章 ? 所有的模型都缺少理論上的完善 ? 面向?qū)嶋H系統(tǒng)的資源管理和調(diào)度策略都是基于自提出的啟發(fā)式算法，只是用“實(shí)驗(yàn)數(shù)據(jù)”來(lái)說(shuō)明問(wèn)題 ? 基本沒(méi)有見(jiàn)到完善的、統(tǒng)一的多層次管理模型 ?可能的多層次管理：網(wǎng)格系統(tǒng) ? Globus Tookit 3 GRAM 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 第三部分：研究重點(diǎn)的確立 ?第一部分：面臨著的挑戰(zhàn) ?第二部分：解決問(wèn)題的若干思路 ?第三部分：研究重點(diǎn)的確立 ? 已有的理論基礎(chǔ)與實(shí)際系統(tǒng) ? 主要研究點(diǎn)的選擇 ?第四部分：博士論文工作計(jì)劃 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 集群作業(yè)管理 LilyJM ?在集群上的作業(yè)管理系統(tǒng) ? 集群上直接面向最終用戶的系統(tǒng) ? 用戶提交腳本，腳本中含有多個(gè)作業(yè) ? 以作業(yè)為單位，在集群系統(tǒng)中進(jìn)行調(diào)度 ?現(xiàn)有實(shí)現(xiàn) ? 提供對(duì)作業(yè)現(xiàn)有狀態(tài)、輸出結(jié)果的查詢 ? 系統(tǒng)可根據(jù)節(jié)點(diǎn)資源情況（ CPU負(fù)載）進(jìn)行作業(yè)調(diào)度 ? 支持集群中動(dòng)態(tài)加入的節(jié)點(diǎn) ? 可以實(shí)現(xiàn)作業(yè)級(jí)容錯(cuò) ? 已經(jīng)在并行組內(nèi)部和北京大學(xué)科學(xué)與工程計(jì)算中心試用 ? 由碩士研究生劉敏實(shí)際完成 第三部分：研究重點(diǎn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 第四部分：博士論文工作計(jì)劃 ?第一部分：面臨著的挑戰(zhàn) ?第二部分：解決問(wèn)題的若干思路 ?第三部分：研究重點(diǎn)的確立 ?第四部分：博士論文工作計(jì)劃 ?工作內(nèi)容 ?工作安排 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 進(jìn)度安排 ? 先期階段：一年時(shí)間，已完成初步探索、工作基礎(chǔ) ? 第一階段：進(jìn)一步探討 ? 2023年 3月－ 2023年 5月（ 3個(gè)月） ? 完成更加深入的調(diào)研，初步提出理論邏輯模型 ? 初步實(shí)現(xiàn)原型系統(tǒng)，并在 ChinaGrid北大主節(jié)點(diǎn)上調(diào)試通過(guò) ? 第二階段：深入研究 ? 2023年 6月－ 2023年 8月（ 3個(gè)月） ? 得到實(shí)驗(yàn)數(shù)據(jù)、進(jìn)一步細(xì)化理論邏輯模型 ? 得到基本性能模型 ? 優(yōu)化實(shí)用系統(tǒng)，在 ChinaGrid北大主節(jié)點(diǎn)上提供穩(wěn)定服務(wù) ? 撰寫一篇投稿論文 ? 第三階段：總結(jié)收獲 ? 2023年 9月 2023年 11月（ 3個(gè)月） ? 完成最終的邏輯模型、性能模型；完成模型證明 ? 完成博士論文 第四部分：工作計(jì)劃 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 附錄：作業(yè)管理系統(tǒng)示例 ?典型的作業(yè)管理系統(tǒng)－ PBS系列 ?商業(yè)版本 PBSPro的特性簡(jiǎn)介 ?免費(fèi)版本 OpenPBS的局限 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 免費(fèi)版本 OpenPBS的局限 ?使用性的局限 ? 只支持類 Unix系統(tǒng) ? 不支持 SMP集群系統(tǒng) ? 只支持較小規(guī)模的集群環(huán)境 ? 沒(méi)有完善的使用文檔 ?功能性的局限 ? 只有輪詢的負(fù)載平衡策略 ? 不支持搶先式作業(yè)調(diào)度 ? 不支持利用桌面計(jì)算機(jī)空閑時(shí)間 ? 不支持資源預(yù)留 ? 不支持容錯(cuò) ? 不支持網(wǎng)格計(jì)算 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型的命題 ?命題 ? 描述任務(wù)關(guān)系圖，實(shí)現(xiàn)任務(wù)關(guān)系驅(qū)動(dòng)的 LilyTask計(jì)算模型能夠有效地描述并實(shí)現(xiàn)多個(gè)子問(wèn)題協(xié)同工作 ?基礎(chǔ)認(rèn)定 ? 一個(gè)問(wèn)題可以分解為多個(gè)子問(wèn)題（也許遞歸繼續(xù)分解），這些子問(wèn)題協(xié)同工作，共同完成待解決問(wèn)題 ? 問(wèn)題之間可以進(jìn)行數(shù)據(jù)傳遞 ? 除了最初工作的問(wèn)題，一個(gè)問(wèn)題必須由另外一個(gè)問(wèn)題通知運(yùn)行，我們將這個(gè)過(guò)程稱作“激活”；我們假定最初工作的問(wèn)題也是由一個(gè)特殊問(wèn)題“系統(tǒng)”激活；因此全部問(wèn)題都需要被“激活” 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型的正確性（ 4） ? 定理 1：任何任務(wù)，都可以分解成若干子任務(wù) ,這些子任務(wù)內(nèi)部串行執(zhí)行，且只有在子任務(wù)開(kāi)始的時(shí)候接收數(shù)據(jù)、子任務(wù)結(jié)束的時(shí)候發(fā)送數(shù)據(jù)；如果把這些子任務(wù)的每次運(yùn)行作為頂點(diǎn)，把子任務(wù)之間的數(shù)據(jù)傳遞作為有向邊，就構(gòu)成了一個(gè)有向無(wú)環(huán)圖 DAG－任務(wù)數(shù)據(jù)傳遞圖 ? 證明： 1）由引理 4，且由于基礎(chǔ)的數(shù)據(jù)傳遞是單向的，因此任務(wù)的每次運(yùn)行與數(shù)據(jù)傳遞構(gòu)成了有向圖 ? 2）如果有向圖存在一個(gè)環(huán)，設(shè)這個(gè)環(huán)的頂點(diǎn)為 T1?T2?… ?Tp?T1，由引理 5可知， ?具有傳遞性，反對(duì)稱性，矛盾；因此有向圖無(wú)環(huán) ? 定理 2：任何任務(wù)，都可以分解成若干子任務(wù) ,這些子任務(wù)內(nèi)部串行執(zhí)行，且只有在子任務(wù)開(kāi)始的時(shí)候接收數(shù)據(jù)、子任務(wù)結(jié)束的時(shí)候發(fā)送數(shù)據(jù)，在子任務(wù)結(jié)束的時(shí)候可能激活其它任務(wù)；如果把這些子任務(wù)的每次運(yùn)行作為頂點(diǎn)，把子任務(wù)之間的數(shù)據(jù)傳遞作為有向邊，仍然構(gòu)成一個(gè) DAG－任務(wù)數(shù)據(jù)傳遞圖；如果把子任務(wù)之間的激活關(guān)系作為有向邊，就構(gòu)成了另一個(gè)有向無(wú)環(huán)圖 DAG－任務(wù)運(yùn)行激活圖 ? 證明： 1）按照引理 3，可以將定理 1得到的任何任務(wù)，串行劃分成若干子任務(wù)，只有在每個(gè)子任務(wù)結(jié)束的時(shí)候激活其它任務(wù) ? 2）對(duì)于（ 1）中劃分成的若干子任務(wù)，只有在每個(gè)子任務(wù)結(jié)束的時(shí)候才能激活其它任務(wù)；每一個(gè)任務(wù)的子任務(wù)之間都存在數(shù)據(jù)傳遞，且只在子任務(wù)運(yùn)行前從上一個(gè)子任務(wù)處接受數(shù)據(jù)、運(yùn)行后向下一個(gè)子任務(wù)發(fā)送數(shù)據(jù)；按照定理 1，所有的任務(wù)的子任務(wù)及其數(shù)據(jù)傳遞關(guān)系可以構(gòu)成一個(gè)任務(wù)數(shù)據(jù)傳遞圖 ? 3）按照引理 6，把子任務(wù)之間的激活關(guān)系作為有向邊，就構(gòu)成了另一個(gè)有向無(wú)環(huán)圖 DAG－任務(wù)運(yùn)行激活圖 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型中的層次性任務(wù) ? 為了對(duì)應(yīng)層次思考問(wèn)題的過(guò)程，定義 ? 一個(gè)任務(wù)內(nèi)部不必是嚴(yán)格串行執(zhí)行，它可以繼續(xù)分解成若干子任務(wù)，只要分解過(guò)程中滿足任務(wù)封閉性即可 ? 如果一個(gè)任務(wù)具有子任務(wù)，那么它完成，當(dāng)且僅當(dāng)它的所有子任務(wù)完成 ? 規(guī)定一個(gè)任務(wù)，它代表整個(gè)問(wèn)題，是所有其它任務(wù)的祖先 ? 規(guī)定只有具有同一個(gè)任務(wù)的子任務(wù)之間才能描述任務(wù)間關(guān)系 ? 如果不同任務(wù)的兩個(gè)子任務(wù)之間存在任務(wù)間關(guān)系，則對(duì)這兩個(gè)子任務(wù)分別向上追溯，找到某兩個(gè)具有相同父任務(wù)的祖先任務(wù)，在這兩個(gè)祖先任務(wù)之間描述任務(wù)間關(guān)系 ? 實(shí)際上，一個(gè)具有若干子任務(wù)的任務(wù)可以理解成原有任務(wù)關(guān)系圖中的若干任務(wù)“合并”而成的 ? 只有“最終”子任務(wù)才是實(shí)際工作任務(wù)，其所有父任務(wù)的意義在于“層次性包容”與關(guān)系描述 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 預(yù)留資源的分時(shí)共享方法 ?保證某個(gè)任務(wù)對(duì)某些資源的占用 ? 需要任務(wù)向系統(tǒng)請(qǐng)求預(yù)留資源 ? 涉及到改變資源對(duì)任務(wù)的分配情況 ? 不代表在任何時(shí)刻都分配給任務(wù)請(qǐng)求的預(yù)留資源：任務(wù)的資源預(yù)留信息不一定很合適 ?對(duì)作業(yè)資源的調(diào)整策略 ? 作業(yè)開(kāi)始時(shí)，系統(tǒng)根據(jù)預(yù)留資源信息 UREV分配資源 ? 定時(shí)或不定時(shí)地計(jì)算預(yù)期資源 UEXP ? 根據(jù) UREV與 UEXP的比較情況進(jìn)行調(diào)整，分配實(shí)際資源 A ? 例如，如果任務(wù)上次分配資源小于預(yù)留資源，而預(yù)期資源超過(guò)預(yù)留資源，那么實(shí)際分配資源 A=min{UREV, (1+e)* UCUR}， e是一個(gè)預(yù)定義的常量 返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 實(shí)際系統(tǒng)、系統(tǒng)節(jié)點(diǎn)樹(shù)與信息點(diǎn) U為較高層系統(tǒng)，X、 Y、 Z為較低的同層子系統(tǒng)，每層系統(tǒng)都有若干信息點(diǎn) NUi、NXi、 NYi、 NZi和一個(gè)信息負(fù)責(zé)點(diǎn) CU、 CX、 CY、CZ 第二部分：若干思路 X NX1 NUx|CX NX2 Y NY1 NUy|CY NY2 Z NZ1 NUz|CZ NZ2 CU U Y Y1 Y2 X X1 X2 Z Z1 Z2 NX1 NX2 NY1 NY2 NZ1 NZ2 NUx | CX NUy | CY NUz | CZ CU UiZiZUiYiYUiXiXZiZYiYXiUiU NNCNNCNN NCNCNCNCUZYX ?????? ??????? 、 、 X返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 任務(wù)模型的形式化探索 ?對(duì)任務(wù)需求的表述方法 ? 設(shè)對(duì)于一個(gè)任務(wù) JX，資源需求表示為 t(JX) ? t(JX)需要兼容于 ?r(SX) ? 如果任務(wù) JX為任務(wù) JY的先驅(qū)任務(wù)，用 JX?JY表示 ?動(dòng)態(tài)預(yù)知運(yùn)行時(shí)任務(wù)對(duì)資源的需求 ? 只在最底層完成；設(shè)此層為 SX ? 設(shè)得到的當(dāng)前資源需求 t(JX)，上一次的資源需求為 t0(JX)，設(shè)預(yù)期資源需求為 t‘ (JX) ? 設(shè)當(dāng)前的資源信息為 rt(SX) ? 資源預(yù)期函數(shù) g： t39。 網(wǎng)絡(luò)研究所 猜想：各層所需信息不同 ?在大規(guī)模集群系統(tǒng)中的重要信息 ? 資源信息：靜態(tài)信息、動(dòng)態(tài)信息 ? 負(fù)載信息：各計(jì)算機(jī)上面的負(fù)載信息 ?從空間粒度來(lái)講 ? 最底層直接面向計(jì)算機(jī)，因此應(yīng)當(dāng)掌握最精確的信息 ? 更高層面向子系統(tǒng)，掌握同層其它子系統(tǒng)處理后的匯總歸并信息就已經(jīng)足夠，以減少傳播信息量，提高效率 ?從時(shí)間粒度來(lái)講 ? 資源管理應(yīng)當(dāng)最先在最底層解決，因此獲取的信息應(yīng)當(dāng)是最即時(shí)的，所以要短周期獲取信息 ? 更高層間不需要頻率很快地進(jìn)行資源管理，為了減輕系統(tǒng)負(fù)擔(dān)，可以加大獲取信息的時(shí)間間隔 返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 演講完畢，謝謝觀看！