【正文】 ? 有效地描述并實(shí)現(xiàn)多個(gè)問(wèn)題協(xié)同工作 START 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 典型的作業(yè)管理系統(tǒng)－ PBS系列 ?總體情況 ? 最初由 NASA在 20世紀(jì) 90年代早期開(kāi)發(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ò)研究所 附：主要的科研項(xiàng)目 ? 已結(jié)束的科研項(xiàng)目 ? 國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目《并行程序設(shè)計(jì)關(guān)鍵技術(shù)》（ 69933020，人民幣 90萬(wàn)元，國(guó)家撥款），北京大學(xué)子項(xiàng)目；－ （結(jié)題檢查“優(yōu)”）；協(xié)助導(dǎo)師具體負(fù)責(zé) ? IBM《共享大學(xué)研究（ SUR）》項(xiàng)目，北京大學(xué)課題“北京大學(xué)網(wǎng)格建設(shè)”； － ；協(xié)助導(dǎo)師具體負(fù)責(zé) ? Intel《 HPC 03》項(xiàng)目，北京大學(xué)課題 Task Scheduling Mechanism Program Supporting Environment for Intel Itanium 2 SMP Cluster System（ PO No. 4507076701）， 3萬(wàn)美元（來(lái)自 Intel公司）； － ；實(shí)際負(fù)責(zé)人 ? 正在進(jìn)行的科研項(xiàng)目 ? Intel《 Parallel Cache Simulator》項(xiàng)目（ PO No. 4507105230）， 2萬(wàn)美元（來(lái)自 Intel公司）； － ；實(shí)際負(fù)責(zé)人 ? 國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目《網(wǎng)絡(luò)計(jì)算環(huán)境綜合試驗(yàn)平臺(tái)》，北京大學(xué)子課題《網(wǎng)絡(luò)計(jì)算資源服務(wù)中間件》（ 90412023，人民幣 150萬(wàn)元，國(guó)家撥款）； － ；主要參加人 信息科學(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) ? 高效的，性能達(dá)到國(guó)際前列的實(shí)際管理系統(tǒng)，并在ChinaGrid北京大學(xué)主節(jié)點(diǎn)上提供穩(wěn)定的高質(zhì)量服務(wù) ? 最大效率地使用集群系統(tǒng)，達(dá)到最高的經(jīng)濟(jì)效益 ? 成為網(wǎng)格計(jì)算的基礎(chǔ) 第四部分：工作計(jì)劃 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 對(duì)潛在研究點(diǎn)的分析 ? 選取主要研究點(diǎn)的原則 ? 意義、難度、深度、可行性 ? 機(jī)器模型：計(jì)算資源、邏輯拓?fù)? ? 已經(jīng)有一些基本想法（層次化樹(shù)狀結(jié)構(gòu)） ? 能夠采取拿來(lái)主義；可以安排給碩士研究生進(jìn)行 ? 任務(wù)模型：任務(wù)描述、需求預(yù)知 ? 學(xué)界已經(jīng)開(kāi)始進(jìn)行較深入的研究 ? 容易借鑒別人的成果；同樣可以安排給碩士研究生進(jìn)行 ? 管理模型：邏輯模型、性能模型 ? 處于核心模型：此方面問(wèn)題的解決，意味著能夠?qū)Υ笠?guī)模集群系統(tǒng)計(jì)算資源的高效利用 ? 難度較大，需要深入細(xì)致的理論分析、猜想與試驗(yàn) ? 學(xué)界尚未有完全令人信服的，針對(duì)大規(guī)模集群系統(tǒng)的完善模型 ? 可行性：前面的思考、已有的基礎(chǔ)與自己的信心 第三部分：研究重點(diǎn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 已有的相關(guān)理論基礎(chǔ)與實(shí)際系統(tǒng) ?關(guān)于理論模型 ? LilyTask并行計(jì)算模型 ? 描述任務(wù)關(guān)系圖，實(shí)現(xiàn)任務(wù)關(guān)系驅(qū)動(dòng) ?關(guān)于計(jì)算資源與作業(yè)管理 ? 集群系統(tǒng)資源獲取 LilyCRM ? 集群系統(tǒng)信息查看 LilyView ? 集群作業(yè)管理系統(tǒng) LilyJM ?關(guān)于并行程序運(yùn)行環(huán)境 ? 任務(wù)并行語(yǔ)言與運(yùn)行時(shí)庫(kù)系統(tǒng) LilyTask ? 有關(guān)任務(wù)并行的認(rèn)識(shí)、實(shí)際系統(tǒng)實(shí)現(xiàn)的經(jīng)驗(yàn) ? 已有 6篇相關(guān)論文發(fā)表 /被接收，其中 1篇 SCI、 ISTP索引，1篇 EI索引， 1篇計(jì)算機(jī)學(xué)報(bào) 第三部分：研究重點(diǎn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 綜合考慮 ?理論研究 ? 機(jī)器模型、任務(wù)模型、管理模型 ?集中體現(xiàn)：猜想中的信息團(tuán)模型 ? 以信息團(tuán)為基礎(chǔ)，分層次連動(dòng)管理 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 子系統(tǒng)處理任務(wù)的最終結(jié)果 第二部分：若干思路 NX1 NX2 NY1 NY2 NZ1 NZ2 NUx | CX NUy | CY NUz | CZ CU TIM1 TIM2 T1 T2 現(xiàn)在， X和 Z都有任務(wù)在運(yùn)行 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 子系統(tǒng)處理任務(wù)過(guò)程 [1] 第二部分：若干思路 NX1 NX2 NY1 NY2 NZ1 NZ2 NUx | CX NUy | CY NUz | CZ CU TAll 子系統(tǒng) X首先把任務(wù) TAll在X內(nèi)部面向 NXi進(jìn)行處理 X 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 任務(wù)模型之動(dòng)態(tài)需求預(yù)知 ?感知任務(wù)運(yùn)行時(shí)對(duì)資源的需求 ? 利用系統(tǒng)調(diào)用，可以得知任務(wù)對(duì) CPU、內(nèi)存等計(jì)算資源的使用情況 ?使用資源預(yù)期函數(shù)來(lái)定量地預(yù)知資源需求 ? 系統(tǒng)定時(shí)或者不定時(shí)地得到任務(wù)的當(dāng)時(shí)針對(duì)某個(gè)資源的使用情況 ? 利用剛剛得到的當(dāng)前資源使用情況 UCUR和上次的資源使用情況 UOLD，計(jì)算預(yù)期的資源需求 UEXP ? 例如使用平滑函數(shù)進(jìn)行預(yù)期： UEXP=a?UCUR+(1a) ?UOLD ?待研究問(wèn)題 ? 監(jiān)控哪些資源；采用什么資源預(yù)期函數(shù) 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 對(duì)理論方面的分析二：任務(wù)模型 ?機(jī)器模型 ?任務(wù)模型 ?任務(wù)描述 ?需求預(yù)知 ?管理模型 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 關(guān)于系統(tǒng)層次劃分的思考 ? 需要一個(gè)指導(dǎo)方法，使系統(tǒng)可能達(dá)到最大服務(wù)能力 ? 適應(yīng)層次化管理思想 ? 參考實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)，在各種實(shí)際系統(tǒng)中指導(dǎo)如何劃分層次 ? 決定每一層次需要什么樣的計(jì)算資源信息（以及負(fù)載信息） ? 幾點(diǎn)在大規(guī)模集群系統(tǒng)中的具體目標(biāo) ? 避免單節(jié)點(diǎn)瓶頸 ? 產(chǎn)生較少的管理消息 ? 使管理盡量簡(jiǎn)單化，盡量不影響計(jì)算機(jī)本身計(jì)算 ? 避免信息滯后問(wèn)題 ? 實(shí)現(xiàn)跨網(wǎng)絡(luò)管理 ? 處理節(jié)點(diǎn)的動(dòng)態(tài)加入與退出 ? 兩點(diǎn)猜想 ? 各層所需信息不同 ：似乎是顯然的 ? 最底層應(yīng)小規(guī)模且對(duì)等 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 理論方面的三大問(wèn)題 ?大規(guī)模集群系統(tǒng)的機(jī)器模型是什么 ? 哪些計(jì)算資源是重要的；如何描述；性能參數(shù)是什么 ? 這些計(jì)算資源在大規(guī)模系統(tǒng)中的邏輯拓?fù)涫鞘裁? ?能有效利用這些計(jì)算資源的任務(wù)模型是什么 ? 如何描述任務(wù)的需求 ? 如何動(dòng)態(tài)預(yù)知任務(wù)對(duì)資源的需求情況 ?層次化管理的邏輯模型和性能模型是什么 ? 如何根據(jù)給定的機(jī)器描述與作業(yè) /任務(wù)描述，得到最適合的管理方式，并指導(dǎo)下一步的調(diào)度策略及算法 ? 如何根據(jù)邏輯模型得到的結(jié)論，給出性能參數(shù)以及對(duì)性能的預(yù)測(cè)與評(píng)價(jià) 只要解決了這三個(gè)問(wèn)題，就解決了理論方面的問(wèn)題 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 第二部分：解決問(wèn)題的若干思路 ?第一部分：面臨著的挑戰(zhàn) ?第二部分：解決問(wèn)題的若干思路 ? 直觀想法：分層次進(jìn)行資源管理 ? 理論方面的三大問(wèn)題 ? 綜合考慮：猜想中的信息團(tuán)模型 ?第三部分：研究重點(diǎn)的確立 ?第四部分：博士論文工作計(jì)劃 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 問(wèn)題著手前的一些零散思考 [1] ?集中式管理 ? 設(shè)立一個(gè)管理節(jié)點(diǎn)，對(duì)所有節(jié)點(diǎn)進(jìn)行集中式管理 ? 管理節(jié)點(diǎn)具有全部系統(tǒng)信息，易于進(jìn)行調(diào)度 ? 整個(gè)系統(tǒng)實(shí)現(xiàn)起來(lái)最簡(jiǎn)單 ? 可采用多管理節(jié)點(diǎn)相互備份功能，提高效率 ?問(wèn)題一：大規(guī)模系統(tǒng)中的單節(jié)點(diǎn)瓶頸 ? 所有資源管理工作由單一節(jié)點(diǎn)完成，這個(gè)節(jié)點(diǎn)負(fù)擔(dān)大，且其它節(jié)點(diǎn)需等待此節(jié)點(diǎn)的處理結(jié)果 ? 所有信息集中在單一節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)失效時(shí)，系統(tǒng)重新產(chǎn)生管理節(jié)點(diǎn)的代價(jià)大 ?問(wèn)題二：大規(guī)模系統(tǒng)中的信息滯后 ? 通過(guò)網(wǎng)絡(luò)通信，無(wú)法及時(shí)獲取所有節(jié)點(diǎn)的資源信息 ? 資源管理信息產(chǎn)生后，很難及時(shí)通知到所有相關(guān)節(jié)點(diǎn) 第一部分：面臨挑戰(zhàn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 提綱 ?第一部分：面臨著的挑戰(zhàn) ?第二部分：解決問(wèn)題的若干思路 ?第三部分：研究重點(diǎn)的確立 ?第四部分：博士論文工作計(jì)劃 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 并行與分布式計(jì)算組 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 本研究的對(duì)象：大規(guī)模集群 ?面向環(huán)境 ? 大規(guī)模集群系統(tǒng) ? 可能的擴(kuò)展：網(wǎng)格計(jì)算 ?面臨著的問(wèn)題 ? 大規(guī)模環(huán)境，節(jié)點(diǎn)數(shù)目眾多，連接復(fù)雜 ? 組成系統(tǒng)的各個(gè)節(jié)點(diǎn)計(jì)算能力可能不同 ? 可能有物理上的多層次拓?fù)? ? 系統(tǒng)需求：功能與性能 ? 最終要能夠充分地利用系統(tǒng)的計(jì)算能力 第一部分：面臨挑戰(zhàn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 問(wèn)題著手前的一些零散思考 [4] ?信息的獲取與處理 ? 系統(tǒng)需要什么樣的信息，才能夠有效地進(jìn)行下一步的資源與作業(yè)管理工作 ? 信息越豐富，越有助于資源管理的精確性 ? 信息越豐富，各節(jié)點(diǎn)負(fù)擔(dān)越大、通過(guò)網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量越大、資源管理的所需算法越復(fù)雜 ?各節(jié)點(diǎn)的存在信息與資源信息 ? 定時(shí)檢測(cè)：心跳 ? 處理器、內(nèi)存、網(wǎng)絡(luò) …… ? 物理資源信息和可用資源信息 ? 處理節(jié)點(diǎn)的動(dòng)態(tài)加入與退出 第一部分：面臨挑戰(zhàn) 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 層次化管理思想的兩個(gè)方面 ? 理論與實(shí)現(xiàn) ? 理論方面：這種分層次進(jìn)行資源管理相關(guān)的資源、作業(yè)模型是什么、如何交互（管理模型） ? 實(shí)現(xiàn)方面：如何在大規(guī)模的實(shí)際集群系統(tǒng)上高效實(shí)現(xiàn)分層次進(jìn)行資源管理 ? 實(shí)現(xiàn)方面需要理論方面進(jìn)行指導(dǎo) ? 理論方面需要實(shí)現(xiàn)方面作為表現(xiàn) ? 極大的挑戰(zhàn)性 ? 世界上尚未出現(xiàn)令人信服的模型 ? 世界上更未出現(xiàn)完全高效的系統(tǒng) ? 這正是我們的機(jī)遇，同時(shí)也是嚴(yán)峻的挑戰(zhàn) ? 本報(bào)告中主要討論理論方面 ? 最后部分將簡(jiǎn)單介紹實(shí)現(xiàn)方面的一些考慮 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 機(jī)器模型之邏輯拓?fù)? ? 層次化樹(shù)狀結(jié)構(gòu)－ 系統(tǒng)節(jié)點(diǎn)樹(shù) ? 樹(shù)中的每個(gè)節(jié)點(diǎn)，代表一個(gè)子系統(tǒng) ? 父節(jié)點(diǎn)代表其全部子節(jié)點(diǎn) ? 每個(gè)父節(jié)點(diǎn)只需對(duì)其子節(jié)點(diǎn)進(jìn)行資源管理 ? 全部葉子節(jié)點(diǎn)是系統(tǒng)的實(shí)際物理節(jié)點(diǎn) ? 引入概念： 信息點(diǎn)與信息負(fù)責(zé)點(diǎn) ? 信息點(diǎn)：在子系統(tǒng)內(nèi)，代表一個(gè)子節(jié)點(diǎn)的計(jì)算機(jī) ? 信息負(fù)責(zé)點(diǎn)：在子系統(tǒng)內(nèi)含有整個(gè)子系統(tǒng)信息的計(jì)算機(jī)、對(duì)外代表整個(gè)子系統(tǒng) ? 可以適應(yīng)大規(guī)模集群系統(tǒng) ? 子系統(tǒng)的構(gòu)造參考實(shí)際網(wǎng)絡(luò)結(jié)構(gòu) ? 對(duì)于 N個(gè)節(jié)點(diǎn)的系統(tǒng)，層數(shù)為 O(logN) ? 動(dòng)態(tài)可擴(kuò)展性 ? 可將不同網(wǎng)絡(luò)的系統(tǒng)組織成更大系統(tǒng)、甚至可擴(kuò)展到 Grid系統(tǒng) ? 需要考慮節(jié)點(diǎn)的動(dòng)態(tài)加入與退出機(jī)制 第二部分：若干思路 信息科學(xué)技術(shù)學(xué)院 網(wǎng)絡(luò)研究所 學(xué)界對(duì)機(jī)器模型的相關(guān)研究 ? 關(guān)于計(jì)算資源的表示 ? 從傳統(tǒng)的只考慮處理器信息，到考慮內(nèi)存、網(wǎng)絡(luò)、 IPC資源等信息 ? 越來(lái)越注重實(shí)際系統(tǒng)：開(kāi)始考慮多層次、異構(gòu)結(jié)構(gòu)等實(shí)際問(wèn)題 ? 一個(gè)面向?qū)哟位Y(jié)構(gòu)的研究 ? . Sacerdoti, …, . Culler, “ Wide Area Cluster Monitoring with Ganglia” , Proc IEEE Cluster 2023 Conference