【正文】 當(dāng) X能力不足時(shí)，通過 CX將無法完成的部分任務(wù) TIM提交到 U U T1 T2 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 考察學(xué)界現(xiàn)有的任務(wù)模型 [1] ?最直觀的任務(wù)描述方法 ? 任務(wù)所需要的處理器個(gè)數(shù) ? 任務(wù)在某個(gè)處理器上的執(zhí)行時(shí)間 ? 任務(wù)之間的執(zhí)行序關(guān)系 ?目前任務(wù)描述方法的不足 ? 多數(shù)研究假定每個(gè)任務(wù)在每個(gè)處理器上的執(zhí)行時(shí)間已知、任務(wù)之間的通信時(shí)間也已知 ? 有些研究假定任務(wù)工作量相等，有些假定任務(wù)間無關(guān)系 ? 頂尖的期刊中也有很多這樣的情況（如 IEEE TPDS，., Scheduling Strategies for MasterSlave Tasking on Heterogeneous Processor Platforms） 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 對(duì)理論方面的分析一：機(jī)器模型 ?機(jī)器模型 ?計(jì)算資源 ?邏輯拓?fù)? ?任務(wù)模型 ?管理模型 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 問題著手前的一些零散思考 [2] ?完全分布式管理 ? 每個(gè)節(jié)點(diǎn)都含有其它節(jié)點(diǎn)的信息 ? 減輕了大規(guī)模系統(tǒng)中的單節(jié)點(diǎn)瓶頸問題 注意，在信息獲取后，每節(jié)點(diǎn)對(duì)所有節(jié)點(diǎn)信息的整合工作所需工作量與集中式相同，但每節(jié)點(diǎn)只需產(chǎn)生自己的調(diào)度信息，且不必將此信息傳遞給其它節(jié)點(diǎn) ?未解決大規(guī)模系統(tǒng)中的信息滯后問題 ?引發(fā)新的問題 ? 網(wǎng)絡(luò)中消息數(shù)目過多 獲取信息時(shí)，集中式算法中只需要 N1條（對(duì)）消息，而完全分布式算法需要 N*(N1)條消息，或者 N1條廣播 ? 當(dāng)系統(tǒng)規(guī)模變大時(shí)，由于所得其它節(jié)點(diǎn)的信息可能滯后，各節(jié)點(diǎn)進(jìn)行分布式資源管理所需協(xié)調(diào)工作更加復(fù)雜 第一部分：面臨挑戰(zhàn) 信息科學(xué)技術(shù)學(xué)院 博士研究生開題報(bào)告 大規(guī)模集群系統(tǒng)的 計(jì)算資源與作業(yè)管理 王韜 北京大學(xué)信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 問題著手前的一些零散思考 [3] ?跨網(wǎng)絡(luò)管理 ? 大規(guī)模集群系統(tǒng)中的一部分可能處于一個(gè)內(nèi)部子網(wǎng) ? 外界只能訪問子網(wǎng)內(nèi)連接到外部網(wǎng)絡(luò)的節(jié)點(diǎn) ?解決方法 ? 將子網(wǎng)內(nèi)連接到外部網(wǎng)絡(luò)的節(jié)點(diǎn)作為“代理”，系統(tǒng)管理“代理”，“代理”管理內(nèi)網(wǎng) ? 于是，如何有效地將這種“代理”納入到整體模型中就成為一個(gè)與性能相關(guān)的問題 第一部分：面臨挑戰(zhàn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 機(jī)器模型之計(jì)算資源 ?重要的計(jì)算資源 ? 處理器、內(nèi)存、網(wǎng)絡(luò)， …… ?重要的信息 ? 資源靜態(tài)信息：各計(jì)算機(jī)計(jì)算資源的固有性質(zhì) ? 資源動(dòng)態(tài)信息：各計(jì)算機(jī)的計(jì)算資源的當(dāng)前可用情況 ?信息表述 ? 多元組表示： C, M, N ? 統(tǒng)一數(shù)值表示 ?尚需更加深入的認(rèn)識(shí) ? 需要確定信息表述的方法 ? 需要給出性能參數(shù)與性能公式 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 考察學(xué)界現(xiàn)有的任務(wù)模型 [2] ? 近年來開始考慮切合實(shí)際的任務(wù)模型 ? 著眼點(diǎn)轉(zhuǎn)向任務(wù)對(duì)資源的需求 ? 最初只考慮對(duì)處理器時(shí)間的需求，后來開始考慮內(nèi)存、 I/O等需求 ? Globus Toolkit 3中使用 RSL2語言（ Resource Specification Language）來溝通任務(wù)對(duì)資源的需求：一種 XML ? 進(jìn)一步思考：要求任務(wù)提供對(duì)資源的需求是否合理？ ? 任務(wù)能否提供準(zhǔn)確的資源需求 ? 任務(wù)在運(yùn)行時(shí)的資源需求是否是不變量 ? 最近開始出現(xiàn)如何動(dòng)態(tài)對(duì)任務(wù)需求進(jìn)行預(yù)知的研究 ? 不要求任務(wù)在運(yùn)行前提供準(zhǔn)確的資源需求 ? 運(yùn)行時(shí)動(dòng)態(tài)處理 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 子系統(tǒng)處理任務(wù)過程 [3] 第二部分：若干思路 NX1 NX2 NY1 NY2 NZ1 NZ2 NUx | CX NUy | CY NUz | CZ CU U把 TIM面向 NUi進(jìn)行，選定一個(gè)（或多個(gè)）信息點(diǎn)，例如 NUz，即 CZ T1 T2 TIM U 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 對(duì)信息團(tuán)模型形式化的初步考慮 ? 傳統(tǒng)問題 ? 給定資源集 R、任務(wù)集 T ? 存在調(diào)度方法 D(R, T)，將 T分配到 R上執(zhí)行 ? 分配時(shí)間為 TS，完成時(shí)間為 TU ? 求 D(R, T)，使任一的 R、 T， TS+TU為最小值 ? 本身是一個(gè) NP難問題 ? 我們問題的特殊點(diǎn) ? 實(shí)際的大規(guī)模集群系統(tǒng) ? R規(guī)模大，且描述 R復(fù)雜 ? T中的任一任務(wù)，所需資源與所用時(shí)間可能事先未知 ? 對(duì)應(yīng)理論模型的三個(gè)部分 ? 機(jī)器模型－資源集 ? 任務(wù)模型－任務(wù)集 ? 管理模型－調(diào)度方法 ? 點(diǎn)擊此處進(jìn)入詳細(xì)討論 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 非主要研究點(diǎn)的工作安排 ?非主要研究點(diǎn) ? 機(jī)器模型：計(jì)算資源、邏輯拓?fù)? ? 任務(wù)模型：任務(wù)描述、需求預(yù)知 ?也需要進(jìn)行深入研究 ? 并非不重要，而是沒有被選擇作為博士論文中的具體研究點(diǎn) ? 已經(jīng)進(jìn)行了初步的思考，形成了研究基礎(chǔ) ? 安排碩士研究生進(jìn)行下一步的研究工作 ? 繼續(xù)負(fù)責(zé)總體構(gòu)思與指導(dǎo)工作 第三部分：研究重點(diǎn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 結(jié)束 謝謝大家 歡迎提問 王韜 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型中的基本概念（ 2） ?任務(wù)組，簡化任務(wù)間關(guān)系的描述形式 ?任務(wù)關(guān)系圖、任務(wù)關(guān)系驅(qū)動(dòng) START 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型的有效性 ?按照計(jì)算模型的算法設(shè)計(jì)過程 ? 定義任務(wù) ? 描述任務(wù)間的關(guān)系 ? 通知系統(tǒng)，開始按照任務(wù)關(guān)系運(yùn)行任務(wù)（關(guān)系驅(qū)動(dòng)） ?任務(wù)關(guān)系模型比照激活模型的優(yōu)勢 ? 實(shí)際上，將兩個(gè) DAG合并成一個(gè) DAG ? 簡單，無需每個(gè)任務(wù)都顯式激活 ? 自頂而下的設(shè)計(jì)模式，對(duì)應(yīng)思考問題的過程 ? 使高效的系統(tǒng)實(shí)現(xiàn)成為可能 ?有效性得證 ? 至此，命題“描述任務(wù)關(guān)系圖，實(shí)現(xiàn)任務(wù)關(guān)系驅(qū)動(dòng)的LilyTask計(jì)算模型能夠有效地描述并實(shí)現(xiàn)多個(gè)子問題協(xié)同工作”得證 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 引入概念：信息點(diǎn)與信息負(fù)責(zé)點(diǎn) ?引入概念目的 ? 子系統(tǒng)為邏輯概念，提供信息的工作必須由實(shí)際計(jì)算機(jī)完成 ? 信息點(diǎn)與信息負(fù)責(zé)點(diǎn)是實(shí)際的計(jì)算機(jī)，實(shí)現(xiàn)了邏輯與物理概念上的統(tǒng)一 ?信息點(diǎn)與信息負(fù)責(zé)點(diǎn) ? 在子系統(tǒng)內(nèi)，代表一個(gè)子節(jié)點(diǎn)的計(jì)算機(jī)稱為信息點(diǎn)，在子系統(tǒng)內(nèi)部提供本子節(jié)點(diǎn)的信息 ? 存在某計(jì)算機(jī)，它作為子系統(tǒng)內(nèi)的信息點(diǎn)的同時(shí)，也含有此子系統(tǒng)的整體信息；它可以代表整個(gè)子系統(tǒng)，被稱作這個(gè)子系統(tǒng)的信息負(fù)責(zé)點(diǎn) ? 信息負(fù)責(zé)點(diǎn)代表子系統(tǒng)時(shí)，在上層系統(tǒng)就是一個(gè)信息點(diǎn) 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 管理模型的形式化探索 [2] ? 信息負(fù)責(zé)點(diǎn)分層連動(dòng)制 ? 已知條件：各子系統(tǒng)的資源表示集 R={r(SX)}、各子系統(tǒng)的信息點(diǎn)集 I={{IXi}}、各子系統(tǒng)的信息負(fù)責(zé)點(diǎn)集 H={h(SX)}、各子系統(tǒng)內(nèi)的調(diào)度方法集 S={s(SX)}、任務(wù)需求表述集 T={t(JX)}、任務(wù)的資源預(yù)期函數(shù) g ? 求：如何根據(jù)資源集 R以及資源預(yù)期函數(shù) g，在信息負(fù)責(zé)點(diǎn)集 H間交互，并將任務(wù)表述集 T所代表的任務(wù)根據(jù)調(diào)度方法集 S調(diào)度到信息點(diǎn)集 I中，使系統(tǒng)的調(diào)度時(shí)間＋運(yùn)行時(shí)間盡可能少 ? 關(guān)鍵問題 ? 信息負(fù)責(zé)點(diǎn)產(chǎn)生方法集 ICS是什么 ? 信息負(fù)責(zé)點(diǎn)產(chǎn)生方法函數(shù) c(SX)是什么 ? 任務(wù)調(diào)度方法集 SCHEDS是什么 ? 調(diào)度方法函數(shù) s(SX)是什么 ? 如何在信息負(fù)責(zé)點(diǎn)集 H間交互 返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 一種可能的系統(tǒng)邏輯圖 全部系統(tǒng) 子系統(tǒng) C 子系統(tǒng) A 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 子系統(tǒng) B 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 子系統(tǒng) C1 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 子系統(tǒng) C3 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 子系統(tǒng) C2 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) 計(jì)算機(jī) C1 C3 C2 A B 返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 選擇主要研究點(diǎn)的原則 ?首要原則－研究要有意義 ? 機(jī)器模型、任務(wù)模型、管理模型 ? 所有的三大問題中的六小問題都有意義 ?深度、難度與可行性 ? 所研究問題要有深度和難度 ? 應(yīng)當(dāng)是別人沒有研究好的 ? 當(dāng)然要有可行性 ?最終要能夠成為一套完備的理論 ? 主要研究點(diǎn)應(yīng)該構(gòu)成理論中的亮點(diǎn) ? 其它部分要有研究安排 返回 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型中的任務(wù)樹 ? “葉子節(jié)點(diǎn)”對(duì)應(yīng)著任務(wù)關(guān)系圖中的節(jié)點(diǎn) ? 任務(wù)樹中的關(guān)系，是通過任務(wù)關(guān)系圖中的關(guān)系變化而來 ? 如果原有的所有任務(wù)都沒有子任務(wù)，這顆樹的第一層子任務(wù)就是任務(wù)關(guān)系圖 START 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 LilyTask計(jì)算模型的正確性（ 1） ? 引理 1：一個(gè)問題可以分解成一個(gè)或者多個(gè)子問題，每個(gè)子問題內(nèi)部串行工作 ? 證明：如果某個(gè)子問題內(nèi)部不是串行工作，那么必可被繼續(xù)分解成若干子問題，直到串行工作為止 ? 引理 2：任一內(nèi)部串行工作的問題，如果它與其它問題交換數(shù)據(jù)，那么它可以劃分成一個(gè)或者多個(gè)具有串行關(guān)系的子問題，每個(gè)子問題只在工作開始時(shí)接收其它問題傳遞過來的數(shù)據(jù)，工作結(jié)束時(shí)向其它問題傳遞數(shù)據(jù)，運(yùn)行過程中其數(shù)據(jù)不受其它問題影響 ? 證明： 1）任何交換數(shù)據(jù)，都可分為接受數(shù)據(jù)、發(fā)送數(shù)據(jù)兩種不同操作，這兩個(gè)操作是阻塞的；其它操作不會(huì)影響問題中的數(shù)據(jù) ? 2）問題內(nèi)部串行工作，所以”接受數(shù)據(jù)”、”發(fā)送數(shù)據(jù)”、”其它工作”必不在同一時(shí)刻，且互不影響； ? 3）我們可以用“其它工作 [work]”、“接受數(shù)據(jù) [recv]”、“發(fā)送數(shù)據(jù) [send]” 將此問題劃分為幾個(gè)工作塊，即 [work]、 [recv]、 [send]的一個(gè)排列 ? 4）我們?cè)谶@個(gè)排列中插入若干特殊的 [recv]和 [send]，這些特殊的 [recv]和 [send]都是空操作；使原有排列變?yōu)橐粋€(gè)規(guī)則排列 [recv][work][send]…… ? 5）把規(guī)則排列中的每個(gè) [recv][work][send]塊定義為一個(gè)子問題，這些子問題串行工作，完成原有問題 ? 6）由（ 1）（ 2）可知， [work]過程中數(shù)據(jù)不受其它問題影響 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 典型的作業(yè)管理系統(tǒng)－ PBS系列 ?總體情況 ? 最初由 NASA在 20世紀(jì) 90年代早期開發(fā) ? 目的是面向集群系統(tǒng)提供有效的作業(yè)管理服務(wù) ? 分化為免費(fèi)的 OpenPBS和商業(yè)化的 PBSPro ?免費(fèi)版本被廣為使用 ? 大多數(shù) HPC集成廠商為用戶提供 OpenPBS作為作業(yè)管理部件 ? 業(yè)界最著名的集群系統(tǒng)管理軟件 Scali集成了OpenPBS 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 預(yù)期成果表現(xiàn) ?直接表現(xiàn)：理論模型中的管理模型 ? 完善并證明管理邏輯模型 ? 形成精細(xì)的管理性能模型 ? 成為如何充分有效利用大規(guī)模集群系統(tǒng)的核心理論依據(jù) ?間接表現(xiàn)：理論中其它部分 ? 理論模型中機(jī)器模型的研究（沈堅(jiān)，碩士研究生） ? 理論模型中任務(wù)模型的研究（劉敏，碩士研究生） ?實(shí)際系統(tǒng) ? 高效的，性